IIT M FOUNDATION AN EXAM QDF3 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 for the exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Concepts

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$

• Ridge Regression (L2 Regularization):

  • Loss: $\text{MSE} + \lambda \sum_{j=1}^d w_j^2$
  • Penalizes large coefficients to reduce overfitting.

• Lasso Regression (L1 Regularization):

  • Loss: $\text{MSE} + \lambda \sum_{j=1}^d |w_j|$
  • Forces sparse solutions (some coefficients = 0).

Key Insight:

• Ridge shrinks coefficients, Lasso performs feature selection.
• Example (Q4): $w_3$ (sparse) → Lasso, $w_2$ (large) → Ridge.

2. Decision Trees & Entropy

• Pure Node: All samples belong to the same class.

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

  • $H(S) = 0$ → Pure node.

• Information Gain: $\text{IG} = H(\text{parent}) - \sum_{i} \frac{|S_i|}{|S|} H(S_i)$

  • Higher IG → Better split.

Key Insight:

• Pure node: Entropy = 0 or all samples same class (Q3).

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

• Steps:

  1. Initialize centroids.
  2. Assign points to nearest centroid.
  3. Recompute centroids.
• Convergence: When assignments stop changing.

• Example (Q5):

  • After 1st iteration, recompute centroids and reassign points.

4. Dimensionality Reduction (PCA & Kernel PCA)

• Standard PCA:

  • Maximizes variance in orthogonal directions.

• Kernel PCA:

  • Uses kernel trick for nonlinear projections.
  • Polynomial kernel: $K(x, x') = (x^T x' + c)^d$

• Example (Q6):

  • $x_4^2 = x_1 x_2 + x_1 x_2 x_3$ → Degree 3 polynomial kernel.

5. Ensemble Methods (AdaBoost)

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

• AdaBoost:

  1. Train weak learner $h_t$.
  2. 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: $H(x) = \text{sign}\left( \sum_t \alpha_t h_t(x) \right)$

• Example (Q17-18):

  • $h_1$ has lower error → Used in next round.

6. Support Vector Machines (SVM)

• Soft-Margin SVM:

  • Minimize: $\frac{1}{2} \|w\|^2 + C \sum \xi_i$
  • Dual problem: $\alpha_i$ are Lagrange multipliers.

• KKT Conditions:

  • If $\alpha_i = 0$: Correctly classified.
  • If $\alpha_i = C$: Misclassified or margin violator.
  • If $0 < \alpha_i < C$: Lies on margin.

• Example (Q9):

  • $\alpha_i = 0$ → Correctly classified.
  • Point between margins → $\xi_i > 0$ (pays "bribe").

7. Perceptron Algorithm

• Update Rule:

  • If $y_i (w^T x_i) \leq 0$, update: $w \leftarrow w + \eta y_i x_i$
• Convergence: Guaranteed if data is linearly separable.

• Example (Q10):

  • Converges to $w = [1, 2]^T$.

8. Kernel Methods (Kernel Regression)

• Polynomial Kernel: $K(x, x') = (x^T x' + 1)^d$
• Prediction: $y_{\text{pred}} = w^{*T} \phi(x') = \sum_i \alpha_i K(x_i, x')$

• Example (Q11):

  • Compute $\phi(x')$ using kernel expansion.

9. Bayesian Inference (Beta-Binomial)

• Prior: $\text{Beta}(\alpha, \beta)$
• Posterior: $\text{Beta}(\alpha + \text{heads}, \beta + \text{tails})$
• Mean: $E[\theta] = \frac{\alpha}{\alpha + \beta}$

• Example (Q12):

  • Posterior mean = $\frac{10 + 150}{10 + 40 + 1000} = \frac{160}{1050} \approx 0.152$.

10. Neural Networks (Single-Layer)

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

• Forward Pass:

  • Hidden layer: $h = \text{ReLU}(w^{(1)} x)$
  • Output: $y = w^{(2)} h$

• Example (Q13):

  • Input $x = [1, 3]^T$, weights $w^{(1)} = [0.5, 0.5]$, $w^{(2)} = [1, -1]$, $u_{out} = [2, -2]^T$.
  • Output = 4.

11. Naïve Bayes

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

• Example (Q14):

  • Compute $P(\text{Play=Yes}|\text{Overcast, Cool, High, Weak})$.

12. Logistic Regression

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

• Decision Rule:

  • Predict 1 if $\sigma(w^T x) > 0.55$, else 0.

• Example (Q15):

  • $w = [7, 4]^T$, $x = [1, 2]^T$.
  • $\sigma(7 \cdot 1 + 4 \cdot 2) = \sigma(15) \approx 1$.

13. SVM Prediction

• Dual Form: $f(x) = \sum_i \alpha_i y_i K(x_i, x) + b$

• Example (Q16):

  • $\alpha = [0.1, 0.4, 0, 0]^T$, $x_{\text{test}} = [1, -2]^T$.
  • Predict sign of $0.1 \cdot y_1 K(x_1, x_{\text{test}}) + 0.4 \cdot y_2 K(x_2, x_{\text{test}})$.

Graph 2: Unsupervised Learning

Graph 3: Ensemble & Bayesian Methods

Graph 4: Neural Networks

Graph 5: Probabilistic Models

Key Equations Summary