IIT M IMPROVEMENT AN EXAM QDD3 01 - 01 Sep 2024

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. Linear Regression & Gradient Descent

Key Concepts:

• Sum of Squared Errors (SSE): $\text{SSE} = \sum_{i=1}^n (y_i - \hat{y}_i)^2$, where $\hat{y}_i = w^T x_i$.
• Gradient of SSE (for a single data point): $\nabla_w \text{SSE} = -2 (y - w^T x) x$. (From Q2: Correct option was missing, but the gradient is derived from $\frac{\partial}{\partial w} (y - w^T x)^2$.)

• Ridge Regression (L2 Regularization): $\text{Loss} = \text{SSE} + \lambda \|w\|^2_2$.

  • Effect of $\lambda$:

    • Small $\lambda$ (e.g., $10^{-4}$): Overfitting (high variance).
    • Large $\lambda$ (e.g., $10^2$): Underfitting (high bias).

    (From Q4: Correct answer was A.)

Equations:

1. SSE Gradient (Vector Form): $\nabla_w \text{SSE} = -2 X^T (y - Xw)$.
2. Ridge Regression Update: $w = (X^T X + \lambda I)^{-1} X^T y$.

B. Principal Component Analysis (PCA)

Key Concepts:

• Covariance Matrix $C$: $C = \frac{1}{n} X^T X$ (for centered data).
• Principal Components: Eigenvectors of $C$, sorted by eigenvalues (variance).
• Variance along a Principal Component $w$: $\text{Var}(w) = w^T C w$. (From Q3: Given $w_1 = [-1/\sqrt{2}, 0, -1/\sqrt{2}]^T$, variance = 3.)

Equations:

1. Variance Calculation: $\text{Var}(w) = w^T C w$.
2. Projection onto PC: $z = Xw$.

C. Support Vector Machines (SVM)

Key Concepts:

• Hard-Margin SVM:

  • Decision boundary: $w^T x + b = 0$.
  • Supporting hyperplanes: $w^T x + b = \pm 1$.
  • Margin: $\frac{2}{\|w\|}$. (From Q12: Margin = 0.2 ⇒ $\|w\| = 10$.)

• Soft-Margin SVM:

  • Allows misclassification with slack variables $\xi_i$.
  • Objective: $\min \frac{1}{2} \|w\|^2 + C \sum \xi_i$.
• Kernel Trick: $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$. (From Q10: Valid kernels include polynomial and RBF.)
• Support Vectors: Points with $\alpha_i > 0$. (From Q16: If $\alpha_i^* > 0$, $x_i$ is a support vector.)

Equations:

1. Hard-Margin Constraint: $y_i (w^T x_i + b) \geq 1$.
2. Soft-Margin Constraint: $y_i (w^T x_i + b) \geq 1 - \xi_i$, $\xi_i \geq 0$.
3. Kernel SVM Dual Problem: $\max \sum \alpha_i - \frac{1}{2} \sum \alpha_i \alpha_j y_i y_j K(x_i, x_j)$.

D. Ensemble Methods

Key Concepts:

• Bagging (Bootstrap Aggregating):

  • Trains models in parallel on bootstrapped samples.
  • Uses deep trees (high variance, low bias).
  • Example: Random Forest.

• Boosting:

  • Trains models sequentially, correcting errors.
  • Uses weak learners (e.g., decision stumps).
  • Example: AdaBoost, Gradient Boosting.

  (From Q5: Bagging → (2, 3); Boosting → (1, 4).)

E. Naive Bayes

Key Concepts:

• Class Conditional Independence: $p(x_1, x_2, \dots, x_d | y) = \prod_{i=1}^d p(x_i | y)$. (From Q7: Correct answer was A.)

Equations:

1. Posterior Probability: $p(y | x) = \frac{p(x | y) p(y)}{p(x)}$.

F. Clustering (k-Means)

Key Concepts:

• Cluster Boundary: Perpendicular bisector between centroids. (From Q8: Boundary equation was $2x_1 - x_2 = 0$.)

Equations:

1. Centroid Update: $\mu_k = \frac{1}{|C_k|} \sum_{x \in C_k} x$.

G. Logistic Regression

Key Concepts:

• Sigmoid Function: $\sigma(z) = \frac{1}{1 + e^{-z}}$, where $z = w^T x$.
• Probability Symmetry: $p(y=1 | x) = \sigma(z)$, $p(y=0 | x) = 1 - \sigma(z)$. (From Q9: $p(y=0 | [-1, -3]) = 0.75$.)

Equations:

1. Logistic Loss: $L = -[y \log \sigma(z) + (1-y) \log (1 - \sigma(z))]$.

H. Decision Trees & Information Gain

Key Concepts:

• Entropy: $H(S) = -\sum p_i \log_2 p_i$.
• Information Gain: $\text{Gain} = H(S) - \sum \frac{|S_v|}{|S|} H(S_v)$. (From Q14: IG = 0.594 for the split $x < 0$.)

Equations:

1. Binary Entropy: $H = -p \log_2 p - (1-p) \log_2 (1-p)$.

I. Neural Networks

Key Concepts:

• Learnable Parameters: $\text{Params} = \sum_{l=1}^{L-1} (n_l \times n_{l+1})$, where $n_l$ = neurons in layer $l$. (From Q29: 4→10→15→1 ⇒ 205 params.)

• Activation Functions:

  • Output Layer (Binary Classification): Sigmoid (with cross-entropy loss). (From Q30: Correct answer was A.)
  • Hidden Layers: ReLU (from Q31, since activations include zeros).

Equations:

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

J. Loss Functions

Key Concepts:

• Convex Surrogates for 0-1 Loss:

  1. Logistic Loss: $\log(1 + e^{-z})$.
  2. Hinge Loss (SVM): $\max(0, 1 - z)$.
  3. Perceptron Loss: $\max(0, -z)$.
  4. Squared Loss: $(1 - z)^2$.

  (From Q24–Q27: Match colors to curves.)

• Intersection of Logistic & Hinge Loss: Occurs at $z = \ln(e - 1)$. (From Q28: Correct answer was A.)

Equations:

1. Hinge Loss: $L = \max(0, 1 - y (w^T x))$.
2. Logistic Loss: $L = \ln(1 + e^{-y (w^T x)})$.

K. Bayesian Learning

Key Concepts:

• Beta-Binomial Conjugacy:

  • Prior: $p \sim \text{Beta}(\alpha, \beta)$.
  • Posterior: $\text{Beta}(\alpha + \text{ones}, \beta + \text{zeros})$.

  (From Q13: Posterior = Beta(15, 5) ⇒ $\hat{p} = 0.75$.)

Equations:

1. Beta Expected Value: $E[p] = \frac{\alpha}{\alpha + \beta}$.

Graph 2: Ensemble Methods

Graph 3: Dimensionality Reduction & Clustering

Graph 4: Neural Networks

Graph 5: Loss Functions

3. Summary of Key Equations