IIT M IMPROVEMENT FN EXAM QDD1 22 Dec - 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$, where $U$ contains eigenvectors (principal components) and $\Lambda$ contains eigenvalues (variances).
  4. Project data onto top-$k$ eigenvectors: $X_{PCA} = X U_k$.
• Variance along PC1: For a dataset $\{x_1, ..., x_n\}$, the variance along the first PC is the largest eigenvalue $\lambda_1$.
• Reconstruction Error: If retaining top-$k$ PCs, error = sum of discarded eigenvalues $\sum_{i=k+1}^d \lambda_i$.

Key Equations:

• Covariance matrix: $\Sigma = \frac{1}{n} \sum_{i=1}^n (x_i - \mu)(x_i - \mu)^T$.
• Variance along PC1: $\lambda_1 = \max_{||u||=1} u^T \Sigma u$.
• Reconstruction error: $||X - X_{PCA}||_F^2 = \sum_{i=k+1}^d \lambda_i$.

2. Maximum A Posteriori (MAP) Estimation

• Goal: Estimate parameter $\theta$ by maximizing the posterior $P(\theta | X)$.
• Prior: $\theta \sim \text{Uniform}[0, 60]$.
• Likelihood: For $X \sim \text{Uniform}[0, \theta]$, $P(X|\theta) = \frac{1}{\theta^n}$ if $\max(X) \leq \theta$, else 0.
• Posterior: $P(\theta|X) \propto P(X|\theta) P(\theta)$.
• MAP Estimate: $\hat{\theta}_{MAP} = \arg\max_\theta P(\theta|X) = \max(X)$ (if prior is uniform).

Key Equation:

• $\hat{\theta}_{MAP} = \max(X_1, ..., X_n)$ (for uniform prior).

3. Logistic Regression & Class Imbalance

• Goal: Binary classification with $P(y=1|x) = \sigma(w^T x)$, where $\sigma$ is the sigmoid.
• Class Imbalance: Prioritize recall (true positive rate) for rare but critical class (e.g., spam/phishing).

• Threshold Adjustment:

  • Low threshold: Higher recall (more true positives), but more false positives.
  • High threshold: Higher precision (fewer false positives), but lower recall.

Key Concept:

• For phishing detection, low threshold (answer = 1) is preferred to minimize false negatives.

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

• Goal: Estimate model generalization error by leaving out one sample at a time.

• Error Calculation:

  • For each $i$, train on $D \setminus \{i\}$, predict $y_i$, compute squared error.
  • Average error: $\text{Error} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{f}^{-i}(x_i))^2$.

Key Equation:

• $\text{Error}_{LOOCV} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{f}^{-i}(x_i))^2$.

5. K-Means Clustering

• Algorithm:

  1. Initialize $k$ centroids randomly.
  2. Assign points to nearest centroid.
  3. Recompute centroids as mean of assigned points.
  4. Repeat until convergence.
• Correct Sequence: Initialize → Assign → Recompute → Reassign (Option D: 5→3→1→4→2 is incorrect; correct is 1→2→3→5→4).

6. Lagrangian & Constrained Optimization

• Problem: Minimize $f(x)$ subject to $g(x) \geq 0$.
• Lagrangian: $L(x, \lambda) = f(x) - \lambda g(x)$.
• Dual Problem: $\max_{\lambda \geq 0} \min_x L(x, \lambda)$.

• For $x' = [1, 4]$, $f(x) = x_1^2 + 2x_2$, $g(x) = x_1 - x_2 - 3 \geq 0$:

  • $L(x', \lambda) = 1 + 8 - \lambda (1 - 4 - 3) = 9 + 6\lambda$.
  • $\max_{\lambda \geq 0} L(x', \lambda) = \infty$ (unbounded if $\lambda \to \infty$), but given answer is 89 (likely a miscalculation; correct is $\infty$).

7. Gradient Descent for Linear Regression

• Objective: Minimize $||X^T w - y||^2$.
• Update Rule: $w_{t+1} = w_t - \eta \nabla f(w_t)$, where $\nabla f(w) = 2X(X^T w - y)$.

• Example:

  • $X = \begin{bmatrix} 1 & -2 & 0 \\ 2 & 5 & 1 \end{bmatrix}$, $y = \begin{bmatrix} 1 \\ 6 \\ 1 \end{bmatrix}$, $w_0 = \begin{bmatrix} 1 \\ 0.5 \end{bmatrix}$, $\eta = 0.05$.
  • Gradient: $\nabla f(w_0) = 2X(X^T w_0 - y) = \begin{bmatrix} -4 \\ -20 \end{bmatrix}$.
  • Update: $w_1 = \begin{bmatrix} 1 \\ 0.5 \end{bmatrix} - 0.05 \begin{bmatrix} -4 \\ -20 \end{bmatrix} = \begin{bmatrix} 1.2 \\ 1.5 \end{bmatrix}$.
  • Given answer: $w_1 = \begin{bmatrix} -0.2 \\ 3.1 \end{bmatrix}$ (likely a typo; correct is above).

8. Perceptron Algorithm

• Update Rule: If $y_i (w^T x_i) \leq 0$, update $w \leftarrow w + y_i x_i$.

• Example:

  • $w^t = \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}$, $x_1 = \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}$, $y_1 = 1$.

    • $w^T x_1 = -1 \leq 0$ → Update: $w^{t+1} = w^t + y_1 x_1 = \begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix}$.

  • $x_2 = \begin{bmatrix} -1 \\ 1 \\ 1 \end{bmatrix}$, $y_2 = -1$.

    • $w^{t+1^T} x_2 = 2 > 0$ → No update: $w^{t+2} = w^{t+1}$.
  • Given answer: $w^{t+2} = \begin{bmatrix} 2 \\ -1 \\ 1 \end{bmatrix}$ (incorrect; correct is $w^{t+1}$).

9. Support Vector Machines (SVM)

• Soft-Margin SVM: Allows misclassification with slack variables $\xi_i$.
• Slack Variable $\xi_i$: Distance from margin boundary to point (if on wrong side or inside margin).

• Key Equations:

  • Primal: $\min_{w,b} \frac{1}{2} ||w||^2 + C \sum \xi_i$ s.t. $y_i(w^T x_i + b) \geq 1 - \xi_i$.
  • $\xi_i = \max(0, 1 - y_i(w^T x_i + b))$.

• Example:

  • For a point on the correct side of the margin, $\xi_i = 0$.
  • For a point inside the margin, $\xi_i = 1 - y_i(w^T x_i + b)$.
  • For a misclassified point, $\xi_i = 1 + |w^T x_i + b|$.

10. Naive Bayes Classifier

• Assumption: Features are conditionally independent given the class.
• Parameters: $P(x_i | y)$ for each feature $i$ and class $y$.
• Estimation: $\hat{P}(x_i = 1 | y) = \frac{\text{Count}(x_i = 1, y)}{\text{Count}(y)}$.

• Example:

  • For $X = \begin{bmatrix} 1 & 0 & \dots \\ 0 & 1 & \dots \\ \vdots \end{bmatrix}$, $y = \begin{bmatrix} 1 & 1 & 0 & \dots \end{bmatrix}$:

    • $P(x_1 = 1 | y = 1) = \frac{\text{Count}(x_1 = 1, y = 1)}{\text{Count}(y = 1)}$.

    • Given answers:

      • $a + b = 1$ (sum of $P(x_1 | y=0) + P(x_1 | y=1)$).
      • $b + d + f = 2$ (sum of probabilities for $y=1$).

11. AdaBoost

• Weight Update: Increase weights for misclassified points, decrease for correctly classified.
• Key Concept: Focuses on "hard" examples in subsequent rounds.

12. Model Complexity & Bias-Variance Tradeoff

• Underfitting: High bias, low variance (model too simple).
• Overfitting: Low bias, high variance (model too complex).
• Bagging (e.g., Random Forest): Train estimators in parallel on bootstrapped data to reduce variance.

13. Loss Curves (Training vs. Validation)

• Training Loss: Decreases monotonically.
• Validation Loss: May increase if overfitting.
• Early Stopping: Stop training when validation loss starts rising.

Graph 2: Classification Algorithms

Graph 3: Model Evaluation

Graph 4: Optimization & Gradient Descent

Graph 5: Ensemble Methods