IIT M FOUNDATION AN EXAM QDF4 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 Diploma-Level Machine Learning Techniques exam, along with Mermaid knowledge graphs to visualize relationships.

1. Core Topics & Key Concepts

A. Supervised Learning

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$
  • Closed-form solution (Normal Equation):

• Ridge Regression (L2 Regularization):

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

• Lasso Regression (L1 Regularization):

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

• Key Differences:

  • Ridge: Smooths coefficients.
  • Lasso: Sparsity (feature selection).
  • Elastic Net: Combines L1 + L2.

2. Logistic Regression

• Model: $P(y=1|x) = \sigma(w^T x)$, where $\sigma(z) = \frac{1}{1 + e^{-z}}$
• Loss: Cross-Entropy = $-\sum_{i=1}^n [y_i \log(\hat{y}_i) + (1-y_i) \log(1-\hat{y}_i)]$
• Decision Rule: Predict $\hat{y} = 1$ if $P(y=1|x) > \text{threshold}$ (e.g., 0.5).

3. Support Vector Machines (SVM)

• Hard-Margin SVM:

  • Maximizes margin: $\min_{w,b} \frac{1}{2} \|w\|^2$ s.t. $y_i(w^T x_i + b) \geq 1$.
  • Only support vectors matter.

• Soft-Margin SVM (with slack $\xi$):

  • Loss: $\frac{1}{2} \|w\|^2 + C \sum \xi_i$
  • Dual Problem:

s.t. $0 \leq \alpha_i \leq C$, $\sum \alpha_i y_i = 0$.

• KKT Conditions:

  • If $\alpha_i = 0$: Correctly classified (outside margin).
  • If $0 < \alpha_i < C$: On margin boundary.
  • If $\alpha_i = C$: Misclassified or inside margin.
• Kernel Trick: $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$ (e.g., polynomial, RBF).

4. Decision Trees

• Impurity Measures:

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

• Splitting Criteria:

  • Information Gain (IG) = $H(\text{parent}) - \sum_{\text{children}} \frac{N_j}{N} H(\text{child}_j)$
  • Pure Node: All samples belong to the same class ($H = 0$, $G = 0$).

5. Model Evaluation & Bias-Variance Tradeoff

• Bias: Error due to overly simplistic model (underfitting).
• Variance: Error due to overly complex model (overfitting).

• Tradeoff:

  • High bias (e.g., linear model) → Underfits.
  • High variance (e.g., high-degree polynomial) → Overfits.

• Model 1 (Linear) vs. Model 2 (High-Degree Polynomial):

  • Model 1: Higher bias, lower variance.
  • Model 2: Lower bias, higher variance.

B. Unsupervised Learning

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

• Objective: Minimize within-cluster sum of squares (WCSS).

• Steps:

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

• Example:

  • After 1st iteration: Clusters $C_1, C_2, C_3$.
  • After 2nd iteration: Reassign points based on new centroids.

2. Dimensionality Reduction

• PCA (Principal Component Analysis):

  • Projects data onto directions of maximum variance.
  • Standard PCA: Linear transformation.
  • Kernel PCA: Nonlinear using kernel trick (e.g., polynomial kernel).

• Example:

  • If $x_4^2 = x_1 x_2 + x_1 x_2 x_3$, use Kernel PCA with degree 3.

C. Ensemble Methods

1. AdaBoost

• Weak Learners: Slightly better than random guessing.

• Algorithm:

  1. Initialize weights uniformly.
  2. Train weak learner, compute error $\epsilon_t$.
  3. Update weights: $w_i \leftarrow w_i \exp(\alpha_t y_i h_t(x_i))$, where $\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$.
  4. Combine predictions: $H(x) = \text{sign}(\sum_t \alpha_t h_t(x))$.

• Error Calculation:

  • For classifiers $h_1, h_2$, compute weighted error and choose the better one.

2. Random Forest / Bagging

• Reduces variance by averaging multiple trees.

D. Probabilistic Models

1. Naïve Bayes

• Assumes features are conditionally independent given the class.
• Prediction:

• Example:

  • Given weather data, compute $P(\text{Play Tennis} = \text{Yes} | \text{Overcast, Cool, High, Weak})$.

2. Bayesian Inference

• Prior: $\text{Beta}(\alpha, \beta)$
• Likelihood: Binomial (e.g., coin flips).
• Posterior: $\text{Beta}(\alpha + \text{heads}, \beta + \text{tails})$
• Posterior Mean: $\frac{\alpha + \text{heads}}{\alpha + \beta + n}$

E. Neural Networks

1. Single-Layer Perceptron

• Update Rule: $w \leftarrow w + \eta (y - \hat{y}) x$
• Convergence: Guaranteed if data is linearly separable.

2. Multi-Layer Perceptron (MLP)

• Activation Functions:

  • ReLU: $\text{ReLU}(z) = \max(0, z)$
  • Sigmoid: $\sigma(z) = \frac{1}{1 + e^{-z}}$

• Forward Pass:

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

F. Probability & Statistics

1. Beta Distribution

• PDF: $f(\theta) = \frac{\theta^{\alpha-1} (1-\theta)^{\beta-1}}{B(\alpha, \beta)}$
• Mean: $\frac{\alpha}{\alpha + \beta}$

2. Gaussian Noise

• $\epsilon \sim \mathcal{N}(0, \sigma^2)$

2. Key Equations Summary

Graph 2: Unsupervised Learning

Graph 3: Ensemble Methods

Graph 4: Probabilistic Models

Graph 5: Neural Networks

4. Exam Tips

1. Regularization:

   • Ridge: Shrinks coefficients (no zeros).
   • Lasso: Sparsity (some zeros).

2. SVM:

   • $\alpha_i = 0$: Correctly classified.
   • $0 < \alpha_i < C$: On margin.
   • $\alpha_i = C$: Misclassified or inside margin.

3. Decision Trees:

   • Pure node: All samples same class ($H = 0$).

4. AdaBoost:

   • Weak learners must be better than random (>50% accuracy).

5. Kernel PCA:

   • If relationship is $x_4^2 = x_1 x_2 + x_1 x_2 x_3$, use degree 3.

6. Bayesian Posterior:

   • For Beta prior, posterior mean = $\frac{\alpha + \text{successes}}{\alpha + \beta + n}$.