IIT M IMPROVEMENT AN EXAM QDD4 22 - 22 Dec 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)

• Goal: Dimensionality reduction by projecting data onto orthogonal axes (principal components) that maximize variance.

• Steps:

  1. Center the data (subtract mean).
  2. Compute covariance matrix: $\Sigma = \frac{1}{n} X^T X$.
  3. Eigenvalue decomposition: $\Sigma = U \Lambda U^T$.
  4. Sort eigenvalues $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_d$.
  5. Project data onto top $k$ eigenvectors (principal components).

• Variance along PC1: For a dataset $\{ \pm \mathbf{u}, \pm 2\mathbf{u} \}$, the variance along the first PC is the largest eigenvalue of the covariance matrix.

  • Equation:

• For Q2, the variance is 2.5 (scaled by the eigenvalues of the structured dataset).

• Reconstruction Error: If data lies in a subspace spanned by $k$ PCs, retaining $k$ components gives zero reconstruction error (Q3).

2. Maximum A Posteriori (MAP) Estimation

• Goal: Estimate parameter $\theta$ by maximizing the posterior distribution $P(\theta | \text{data})$.
• Prior: $\theta \sim \text{Uniform}[0, 60]$.
• Likelihood: For $X_i \sim \text{Uniform}[0, \theta]$, the likelihood is:

• Posterior: $P(\theta | \text{data}) \propto L(\theta) \cdot \text{Prior}(\theta)$.

• MAP Estimate: $\hat{\theta}_{MAP} = \max(X_i)$ (for uniform prior and likelihood).

  • For Q4, $\hat{\theta}_{MAP} = 52$.

3. Logistic Regression & Class Imbalance

• Threshold Adjustment:

  • Low threshold: Increases recall (catches more positives, e.g., phishing emails) but may increase false positives.
  • High threshold: Increases precision (fewer false positives) but may miss positives.

• Trade-off: For safety-critical applications (e.g., spam detection), prioritize recall (low threshold).

  • Q5 answer: 1 (low threshold).

4. k-Means Clustering

• Sensitivity to Initialization:

  • Different initializations can lead to different local optima.
  • Outliers can distort cluster centers.
• Convergence: Guaranteed to converge (but may not be globally optimal).

• Key Points:

  • B. k-means is sensitive to outliers.
  • D. Initialization affects convergence speed.
  • Q6 correct options: B, D.

5. Training vs. Validation Loss Curves

• Training Loss: Decreases monotonically as the model fits the training data.

• Validation Loss:

  • Decreases initially, then may increase if overfitting occurs.

• Identification:

  • Curve A (lower): Training loss.
  • Curve B (higher): Validation loss.
  • Q7 correct options: A, D.

6. Gradient Descent for Linear Regression

• Objective: Minimize $f(w) = ||X^T w - y||^2$.
• Update Rule:

where $\nabla f(w) = 2 X (X^T w - y)$.

• Q8 Calculation:

  • Given $X, y, w_0, \eta$, compute gradient and update $w$.
  • Correct answer: $w_1 = [0.76, -0.02]^T$.

7. Perceptron Algorithm

• Update Rule: For misclassified point $(\mathbf{x}_i, y_i)$:

(where $\eta$ is the learning rate, often set to 1).

• Q9 Steps:

  1. Check $y_i (\mathbf{w}^t \cdot \mathbf{x}_i)$. If $\leq 0$, update weights.
  2. For $(\mathbf{x}_1, y_1)$, $\mathbf{w}^{t+1} = [0, 2, 1]^T$.

  3. For $(\mathbf{x}_2, y_2)$, no update (already correctly classified).

     • Correct answer: A.

8. Naïve Bayes Classifier

• Assumption: Features are conditionally independent given the class.
• Parameters: $\hat{p}_i^y = P(x_i = 1 | y)$.

• Estimation:

  • For binary features, $\hat{p}_i^y = \frac{\text{Count}(x_i = 1, y)}{\text{Count}(y)}$.

• Q10-Q12:

  • $a + b = 1$ (complementary probabilities for feature 1).
  • $b + d + f = 2$ (sum of probabilities for $y = 1$).
  • Predicted label for $[1, 0, 1]^T$: 1 (higher posterior for $y = 1$).

9. Leave-One-Out Cross-Validation (LOOCV)

• Error Calculation:

• Q13:

  • Fit $\hat{f} = \beta x$ to $D = \{(1,2), (2,3), (3,4)\}$.
  • LOOCV errors: $(2-1.5)^2, (3-2.5)^2, (4-3)^2$.
  • Average error: 0.33 (rounded to 2 decimal places).

10. Lagrangian & Constrained Optimization

• Lagrangian: $L(x, \lambda) = f(x) + \lambda g(x)$.
• Dual Problem: $\max_{\lambda \geq 0} L(x', \lambda)$.

• Q14:

  • For $x' = [1, 4]^T$, constraint $1 - 4 \leq 3$ is satisfied ($\lambda = 0$).
  • $\max L = f(x') = 1^2 + 2 \cdot 4 = 9$.
  • Correct answer: A ($x_1^2 + 2x_2$).

11. Model Complexity & Bias-Variance Trade-off

• Underfitting: High bias, low variance.
• Overfitting: Low bias, high variance.

• Q15 Incorrect Statement:

  • A. Underfitted models have less bias (false; they have high bias).

12. Support Vector Machines (SVM)

• Support Vectors: Points lying on the margin boundaries ($\mathbf{w}^T \mathbf{x} = \pm 1$).

• Slack Variables ($\xi_i$): Measure violation of margin constraints.

  • $\xi_i = 0$ if point is correctly classified and outside the margin.
  • $\xi_i > 0$ if point violates the margin.
• Q16: Removing non-support vectors does not change the model.

• Q19-Q22:

  • $\xi_1 = 0$ (on the margin).
  • $\xi_4 = 1$ (violates margin by 1 unit).
  • $\xi_6 = 2$ (violates margin by 2 units).

13. AdaBoost

• Weight Update: Increase weights for misclassified points, decrease for correctly classified points.

• Q17 Correct Option:

  • B. Weight decreases if classified correctly.

14. Model Complexity & Test Error

• Not Always True: Increasing complexity does not always increase test error (may decrease if model was underfitting).
• Q18 Answer: False.

Graph 2: MAP Estimation & Bayesian Learning

Graph 3: Logistic Regression & Class Imbalance

Graph 4: k-Means & Clustering

Graph 5: SVM & Slack Variables

Graph 6: Model Evaluation & Bias-Variance