IIT M IMPROVEMENT FN EXAM QDD2 01 Sep - 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 essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Concepts

1. Principal Component Analysis (PCA)

• Key Idea: Dimensionality reduction by projecting data onto directions (principal components) of maximum variance.

• Eigenvalues of Covariance Matrix:

  • Total variance = sum of eigenvalues.
  • Variance captured by top k PCs = (sum of top k eigenvalues) / (total variance).
• Equation:

(For Q2: Eigenvalues = [15, 5, 5, 0, 0] → Top 2 PCs capture (15+5)/25 = 80%)

2. Regularization & Ridge Regression

• Key Idea: Penalize large weights to prevent overfitting.
• Loss Function:

where SSE = Sum of Squared Errors.

• Plot Interpretation (Q3):

  • x-axis: Typically log(λ) (to visualize a wide range of λ values).
  • y-axis: Training/test loss.

  • Behavior:

    • Training loss increases with λ (more regularization).
    • Test loss may decrease initially (reduced overfitting) then increase (underfitting).

3. Ensemble Methods (Bagging vs. Boosting)

(Q4: Bagging → (2, 3); Boosting → (1, 4))

4. Support Vector Machines (SVM)

Hard-Margin SVM

• Decision Boundary: $\mathbf{w}^T \mathbf{x} + b = 0$.
• Supporting Hyperplanes: $\mathbf{w}^T \mathbf{x} + b = \pm 1$.
• Margin Width: $\frac{2}{\|\mathbf{w}\|}$.
• Prediction: $\text{sign}(\mathbf{w}^T \mathbf{x} + b)$.

(Q5: $x_1$ is in class +1 (0 < $\mathbf{w}^T x_1 < 1$); $x_2$ is in class -1 (-1 < $\mathbf{w}^T x_2 < 0$).)

Soft-Margin SVM

• Loss Function:

subject to $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i$, $\xi_i \geq 0$.

• Slack Variables ($\xi_i$): Measure margin violations.

• Lagrange Multipliers ($\alpha_i$):

  • $\alpha_i > 0$: Support vector.
  • $\alpha_i = C$: Margin violator.

(Q8: Distance between hyperplanes = $\frac{2}{\|\mathbf{w}\|}$. For $\mathbf{w} = [3, 4]$, $\|\mathbf{w}\| = 5$, so distance = 0.4.)

5. Naive Bayes

• Class Conditional Independence:

(Q6: Correct option is $p(x_1, x_2, x_3 | y) = p(x_1 | y) p(x_2 | y) p(x_3 | y)$.)

6. k-Means Clustering

• Cluster Boundary: Perpendicular bisector of the line joining centroids.

• Equation of Boundary (Q7):

  • Centroids: $C_1 = (2, 2)$, $C_2 = (-4, 0)$.
  • Midpoint: $(-1, 1)$.
  • Slope of $C_1C_2$: $\frac{1}{3}$.
  • Perpendicular slope: $-3$.
  • Equation: $y - 1 = -3(x + 1)$ → $y = -3x - 2$.

  (But answer is $2x_1 + x_2 = 0$. This suggests the boundary is the perpendicular bisector in standard form.)

7. Maximum Likelihood Estimation (MLE)

• Bernoulli MLE:

(Q9: $\hat{p} = 0.25$, successes = 10 → Total trials = 40 → Zeros = 30.)

8. Decision Trees & Information Gain

• Entropy:

• Information Gain:

(Q10: Parent entropy = 0.811, children entropy = 0.5 → IG = 0.311.)

9. Kernel Methods

• Polynomial Kernel:

• Non-Negative Output: Only possible for even-degree polynomials (p = 2, 4, ...).

(Q11: Possible values for *p are 2 and 4.)*

10. Logistic Regression

• Probability:

• Log-Odds:

(Q13: For $p = \frac{1}{1 + e^2}$, $\mathbf{w}^T \mathbf{x} = -2$. Check which weight vector satisfies this for $\mathbf{x} = [1, 1]$.)

11. Neural Networks

• Parameters:

  • Input → Hidden Layer 1: $5 \times 10 = 50$.
  • Hidden Layer 1 → Hidden Layer 2: $10 \times 10 = 100$.
  • Hidden Layer 2 → Output: $10 \times 1 = 10$.
  • Total: 160 (ignoring biases).

(Q28: Answer is 160.)

• Activation Functions:

  • Output Layer (Binary Classification): Sigmoid (for probabilities).
  • Hidden Layers: ReLU (sparse activations in Q30 suggest ReLU).

12. Loss Functions

(Q23: Logistic loss = 3; Q24: Hinge loss = 2; Q25: Perceptron loss = 4; Q26: Squared loss = 1.)

Graph 2: Dimensionality Reduction & Clustering

Graph 3: Ensemble Methods

Graph 4: Neural Networks