IIT M DIPLOMA AN EXAM QDD3 13 Apr 2025 - 13 Apr 2025

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here’s a structured summary of core topics, concepts, principles, and equations for the Diploma-Level Machine Learning Techniques exam, along with Mermaid knowledge graphs to visualize relationships.

1. Core Topics & Key Concepts

A. Supervised Learning

1. Linear & Regularized Regression

• Linear Regression:

  • Model: $y = w^T x + b$
  • Loss: Mean Squared Error (MSE) = $\frac{1}{N} \sum_{i=1}^N (y_i - \hat{y}_i)^2$
  • Closed-form solution: $w = (X^T X)^{-1} X^T y$

• Ridge Regression (L2 Regularization):

  • Loss: $\text{MSE} + \lambda \|\mathbf{w}\|_2^2$
  • Penalizes large coefficients to reduce overfitting.
  • Solution: $w = (X^T X + \lambda I)^{-1} X^T y$

• Lasso Regression (L1 Regularization):

  • Loss: $\text{MSE} + \lambda \|\mathbf{w}\|_1$
  • Sparsity: Forces some coefficients to exactly zero (feature selection).

• Key Observations from Q4:

  • $w_3$ (sparse) → Lasso
  • $w_2$ (large coefficients) → Linear Regression
  • $w_1$ (small coefficients) → Ridge Regression

2. Logistic Regression

• Model: $P(y=1) = \sigma(w^T x)$, where $\sigma(z) = \frac{1}{1 + e^{-z}}$
• Decision boundary: $w^T x > \theta$ (e.g., $\theta = 0.55$ in Q15).
• Loss: Cross-Entropy = $-\sum_{i=1}^N [y_i \log(\hat{y}_i) + (1-y_i) \log(1-\hat{y}_i)]$

3. Decision Trees

• Impurity Measures:

  • Entropy: $H(S) = -\sum_{i=1}^c p_i \log_2 p_i$
  • Gini Impurity: $G(S) = 1 - \sum_{i=1}^c p_i^2$

• Stopping Criteria:

  • Pure node: All samples belong to the same class (Entropy = 0).
  • Information Gain: $\Delta H = H(\text{parent}) - \sum \frac{|S_v|}{|S|} H(S_v)$
• Overfitting: Prune trees using pre-pruning (early stopping) or post-pruning.

4. Support Vector Machines (SVM)

• Hard-Margin SVM:

  • Maximize margin: $\min \frac{1}{2} \|w\|^2$ s.t. $y_i (w^T x_i + b) \geq 1$.
  • Dual Problem: $\max \sum \alpha_i - \frac{1}{2} \sum \alpha_i \alpha_j y_i y_j x_i^T x_j$ s.t. $\alpha_i \geq 0$.

• Soft-Margin SVM:

  • Allows misclassification with slack $\xi_i$.

  • KKT Conditions (Q9):

    • If $\alpha_i^* = 0$: Correctly classified (outside margin).
    • If $0 < \alpha_i^* < C$: On margin boundary.
    • If $\alpha_i^* = C$: Misclassified or inside margin.
  • Prediction: $\text{sign}(w^T x + b)$, where $w = \sum \alpha_i^* y_i x_i$.

5. Ensemble Methods

• AdaBoost:

  • Combines weak learners (slightly better than random guessing, Q7).
  • Weight Update: Increase weights for misclassified samples.
  • Final Classifier: $H(x) = \text{sign}(\sum \alpha_t h_t(x))$, where $\alpha_t = \frac{1}{2} \log \frac{1 - \epsilon_t}{\epsilon_t}$.

• Error Analysis (Q17-Q18):

  • Training Error: $\epsilon_t = \frac{\sum_{i=1}^N w_i \mathbb{I}(y_i \neq h_t(x_i))}{\sum_{i=1}^N w_i}$.
  • Classifier Selection: Choose the one with lower error for next iteration.

B. Unsupervised Learning

1. Clustering (Lloyd’s Algorithm / K-Means)

• Steps:

  1. Initialize centroids $\mu_1, \mu_2, \dots, \mu_K$.
  2. Assign points to nearest centroid.
  3. Recompute centroids as mean of assigned points.
• Convergence: When assignments stop changing.

• Q5 Example:

  • After 1st iteration, centroids are means of $C_1, C_2, C_3$.
  • Reassign $(3,3)$: Compute distances to new centroids → closest to $C_1$.

2. Dimensionality Reduction

• PCA (Principal Component Analysis):

  • Maximizes variance along orthogonal axes.

  • Kernel PCA: For non-linear relationships (Q6).

    • Polynomial Kernel: $K(x, x') = (x^T x' + c)^d$.
    • Degree Selection: Match kernel degree to data’s polynomial structure (e.g., $x_4^2 = x_1 x_2 + x_1 x_2 x_3$ → degree 3).

C. Probabilistic Models

1. Naïve Bayes

• Assumption: Features are conditionally independent given the class.
• Prediction: $P(y|X) \propto P(y) \prod P(x_i|y)$.

• Q14 Example:

  • Compute $P(\text{Play=Yes}|\text{Overcast, Cool, High, Weak})$.
  • Use laplace smoothing if any $P(x_i|y) = 0$.

2. Bayesian Inference

• Beta-Binomial Model (Q12):

  • Prior: $\text{Beta}(\alpha, \beta)$.
  • Likelihood: Binomial ($k$ heads in $n$ trials).
  • Posterior: $\text{Beta}(\alpha + k, \beta + n - k)$.
  • Posterior Mean: $\frac{\alpha + k}{\alpha + \beta + n}$.

D. Neural Networks

1. Single-Layer Perceptron

• Activation: ReLU $\phi(z) = \max(0, z)$.

• Forward Pass (Q13):

  • Hidden layer: $h_i = \text{ReLU}(w_i^{(1)} x_1 + w_i^{(2)} x_2)$.
  • Output: $y = u_{out}^T h$.

• Perceptron Learning (Q10):

  • Update weights when misclassified: $w \leftarrow w + \eta y_i x_i$.
  • Convergence: Guaranteed if data is linearly separable.

2. Key Equations

Graph 2: Unsupervised Learning Relationships

Graph 3: Probabilistic Models

Graph 4: Neural Networks

4. Exam Strategy

1. Regression:

   • Identify Lasso vs. Ridge by checking sparsity (zero coefficients) or penalty terms.
   • For kernel methods, match the kernel degree to the data’s polynomial structure.

1. Classification:

   • SVM: Focus on support vectors and KKT conditions.
   • Decision Trees: Compute entropy/Gini and information gain.
   • Naïve Bayes: Apply conditional probability with independence assumptions.

1. Clustering:

   • K-Means: Iteratively assign points to nearest centroids and recompute means.

1. Probability:

   • Beta-Binomial: Update posterior parameters with observed data.
   • Bayes’ Rule: Use for Naïve Bayes and Bayesian inference.

1. Ensemble Methods:

   • AdaBoost: Select weak learners with lowest error, update weights, and combine predictions.

1. Neural Networks:

   • ReLU: Zero out negative activations.
   • Perceptron: Update weights only on misclassification.