IIT M IMPROVEMENT AN EXAM QIM4 13 Apr - 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 essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Key Concepts

1. Linear Regression & Regularization

• 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$

• Ridge Regression (L2 Regularization):

  • Loss: $\text{MSE} + \lambda \sum_{j=1}^d w_j^2$
  • Penalizes large coefficients (shrinks weights but never to zero).

• Lasso Regression (L1 Regularization):

  • Loss: $\text{MSE} + \lambda \sum_{j=1}^d |w_j|$
  • Can force coefficients to exactly zero (feature selection).

• Key Insight:

  • $w_3$ in Q4 has sparse weights (zeros) → Lasso.
  • $w_2$ has large weights → Likely unregularized linear regression.
  • $w_1$ has small weights → Ridge.

2. Decision Trees & Entropy

• Entropy (measure of impurity): $H(S) = -\sum_{i=1}^c p_i \log_2 p_i$

  • $H(S) = 0$ → Pure node (all samples same class).
  • $H(S)$ max → Uniform class distribution.

• Information Gain (IG): $IG = H(\text{parent}) - \sum_{i=1}^k \frac{N_i}{N} H(\text{child}_i)$

  • Higher IG → Better split.

• Stopping Criteria:

  • All samples same class (pure node).
  • Max depth reached.
  • Min samples per node.

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

• Algorithm Steps:

  1. Initialize centroids randomly.
  2. Assign points to nearest centroid (Euclidean distance).
  3. Recompute centroids as mean of assigned points.
  4. Repeat until convergence.

• Key Idea:

  • After 1st iteration in Q5, centroids are means of $C_1, C_2, C_3$.
  • In 2nd iteration, $(3,3)$ will move to the nearest updated centroid.

4. Dimensionality Reduction (PCA & Kernel PCA)

• Standard PCA:

  • Linear projection to maximize variance.
  • Eigenvalue decomposition of $X^T X$.

• Kernel PCA:

  • Non-linear projection using kernel trick.
  • Kernel: $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$.
  • Polynomial Kernel: $K(x_i, x_j) = (x_i^T x_j + c)^d$.
  • Q6 Insight: $x_4^2 = x_1x_2 + x_1x_2x_3$ → Degree 3 polynomial.

5. Ensemble Methods (AdaBoost, Weak Learners)

• Weak Learner: Slightly better than random guessing (Q7: TRUE).

• AdaBoost:

  1. Initialize weights uniformly.
  2. Train weak learner, compute error $\epsilon_t$.
  3. Update weights: $w_i \leftarrow w_i \cdot e^{\alpha_t \cdot \mathbb{I}(y_i \neq h_t(x_i))}$.
  4. Combine learners: $H(x) = \text{sign}(\sum_t \alpha_t h_t(x))$.

• Error Calculation (Q17-18):

  • $h_1$ error = 2/5 (misclassifies $x_1, x_2$).
  • $h_2$ error = 3/5 → $h_1$ is better.
  • Final classifier: $h^* = \text{sign}(\alpha h_1)$, where $\alpha = \frac{1}{2} \ln \frac{1 - \epsilon}{\epsilon}$.

6. Support Vector Machines (SVM)

• Soft-Margin SVM:

  • Primal: Minimize $\frac{1}{2} \|w\|^2 + C \sum \xi_i$.
  • Dual: Maximize $\sum \alpha_i - \frac{1}{2} \sum \alpha_i \alpha_j y_i y_j K(x_i, x_j)$.

• KKT Conditions (Q9):

  • If $\alpha_i^* = 0$: Correctly classified (outside margin).
  • If $0 < \alpha_i^* < C$: On margin ($\xi_i = 0$).
  • If $\alpha_i^* = C$: Misclassified or on margin ($\xi_i > 0$).
  • Bribe ($\xi_i$): Penalty for margin violation.

• Prediction (Q16):

  • $f(x) = \sum \alpha_i^* y_i K(x_i, x) + b$.
  • For linear kernel: $f(x) = w^T x + b$, where $w = \sum \alpha_i^* y_i x_i$.

7. Perceptron Algorithm

• Update Rule: $w_{t+1} = w_t + \eta \cdot y_i x_i$ if $y_i (w_t^T x_i) \leq 0$.

• Convergence (Q10):

  • Cycles through data until all points are correctly classified.
  • Final weight vector depends on order of updates.

8. Kernel Methods (Kernel Regression)

• Polynomial Kernel (Degree 2): $K(x, x') = (x^T x' + 1)^2$.

• Prediction (Q11): $y_{\text{pred}} = w^{*T} \phi(x') = \sum_i \alpha_i K(x_i, x')$.

  • Compute $K(X, x')$ and dot with $\alpha$.

9. Bayesian Inference (Beta-Binomial)

• Prior: $\text{Beta}(\alpha, \beta)$.
• Likelihood: Binomial ($k$ heads in $n$ trials).
• Posterior: $\text{Beta}(\alpha + k, \beta + n - k)$.
• Posterior Mean (Q12): $E[\theta | \text{data}] = \frac{\alpha + k}{\alpha + \beta + n} = \frac{10 + 150}{10 + 40 + 1000} \approx 0.152$.

10. Neural Networks (Single Layer)

• ReLU Activation: $\text{ReLU}(z) = \max(0, z)$.

• Forward Pass (Q13):

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

11. Naïve Bayes

• Assumption: Features are conditionally independent given class.

• Prediction (Q14): $P(y | x_1, \dots, x_d) \propto P(y) \prod_i P(x_i | y)$.

  • Compute likelihoods from training data.

12. Logistic Regression

• Sigmoid: $\sigma(z) = \frac{1}{1 + e^{-z}}$.

• Prediction (Q15):

  • $z = w^T x$.
  • If $\sigma(z) > 0.55$, predict 1; else 0.

Graph 2: Dimensionality Reduction

Graph 3: Bayesian vs. Frequentist

Graph 4: Regularization Effects

Key Equations Summary