IIT M FOUNDATION DIPLOMA AN EXAM - 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)

• Key Idea: 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. Eigen-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_{\text{new}} = X U_k$.

• Variance along PC1: For a dataset $\{ \alpha_1 \mathbf{u}, \alpha_2 \mathbf{u}, \dots \}$, the variance along the first PC is the largest eigenvalue of $\Sigma$.

  • Equation: If all points lie on a line (e.g., $\mathbf{x}_i = a_i \mathbf{u}$), the variance is $\text{Var}(a_i) \cdot \|\mathbf{u}\|^2$.
  • Example (Q2): For $\{-2\mathbf{u}, -\mathbf{u}, \mathbf{u}, 2\mathbf{u}\}$, variance along PC1 is $2.5$.

• Reconstruction Error: If data lies in a $k$-dimensional subspace, retaining top $k$ PCs gives zero reconstruction error (Q3).

2. Maximum A Posteriori (MAP) Estimation

• Key Idea: Bayesian estimate of parameters by maximizing the posterior distribution.

  • Posterior: $f(\theta | \mathbf{X}) \propto P(\mathbf{X} | \theta) \cdot P(\theta)$.
  • MAP Estimate: $\hat{\theta}_{\text{MAP}} = \arg \max_\theta f(\theta | \mathbf{X})$.
• Uniform Prior: For $\theta \sim \text{Uniform}[0, 60]$ and $X_i \sim \text{Uniform}[0, \theta]$, the posterior is:

• MAP Solution: $\hat{\theta}_{\text{MAP}} = \max(X_i)$ (Q4: $\theta = 52$).

3. Logistic Regression & Class Imbalance

• Key Idea: Binary classification using sigmoid function $\sigma(\mathbf{w}^T \mathbf{x})$.

• Threshold Adjustment:

  • Low threshold: Prioritizes recall (reduces false negatives, e.g., spam detection in Q5).
  • High threshold: Prioritizes precision (reduces false positives).
• Trade-off: Acceptable to have false positives (regular emails marked as spam) to minimize false negatives (missed phishing emails).

4. k-Means Clustering

• Key Properties (Q6):

  • Sensitive to outliers: Outliers can distort centroids.
  • Initialization matters: Different initializations can lead to different results (local optima).
  • Convergence: Always converges (but may not find global optimum).
  • Iterations: Initialization affects the number of iterations.
• Correct Statements: B (sensitive to outliers), D (initialization affects iterations).

5. Training vs. Validation Loss Curves

• Key Idea: Monitor overfitting/underfitting via loss curves (Q7).

  • Training Loss (Curve A): Decreases monotonically.
  • Validation Loss (Curve B): May increase if overfitting.

• Interpretation:

  • If validation loss > training loss → overfitting.
  • If both losses plateau at high values → underfitting.

6. Gradient Descent for Linear Regression

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

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

• Example: For $X = \begin{bmatrix} 1 & -2 & 0 \\ 2 & 5 & 1 \end{bmatrix}$, $\mathbf{y} = \begin{bmatrix} 1 \\ 6 \\ 1 \end{bmatrix}$, and $\mathbf{w}_0 = \begin{bmatrix} 1 \\ 0.5 \end{bmatrix}$, the updated weights after one iteration are $\mathbf{w}_1 = \begin{bmatrix} 0.76 \\ -0.02 \end{bmatrix}$.

7. Perceptron Algorithm

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

• Example:

  • Given $\mathbf{w}^t = \begin{bmatrix} 0.5 \\ -1 \end{bmatrix}$, $(\mathbf{x}_1, y_1) = (\begin{bmatrix} 0 \\ -1 \end{bmatrix}, -1)$, and $(\mathbf{x}_2, y_2) = (\begin{bmatrix} -1 \\ 2 \end{bmatrix}, 1)$:

    • $\mathbf{w}^{t+1} = \begin{bmatrix} 0.5 \\ 0 \end{bmatrix}$.
    • $\mathbf{w}^{t+2} = \begin{bmatrix} 0.5 \\ 2 \end{bmatrix}$.

8. Naïve Bayes Classifier

• Key Idea: Assume features are conditionally independent given the class.

• Parameter Estimation (Q10–Q12):

  • For binary features $x_i \in \{0,1\}$, estimate $P(x_i = 1 | y)$.
  • No Smoothing: $\hat{p}_i^y = \frac{\text{Count}(x_i = 1, y)}{\text{Count}(y)}$.
• Prediction: Choose class with highest posterior $P(y | \mathbf{x}) \propto P(y) \prod_i P(x_i | y)$.

• Example:

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

    • $a + b = 1$ (Q10), $b + d + f = 2$ (Q11).
    • Predict $\begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}$ as class $1$ (Q12).

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

• Key Idea: Train on $n-1$ points, validate on the left-out point (Q13).
• Error Calculation:

• Example: For $D = \{(1,2), (2,3), (3,4)\}$ and model $\hat{f} = \beta x$, $\text{error}_L \approx 0.33$.

10. Lagrangian & Constrained Optimization

• Lagrangian (Q14): For problem $\min f(x)$ s.t. $g(x) \leq 0$:

• Dual Problem: $\max_{\lambda \geq 0} L(x', \lambda)$.

  • If $x'$ is feasible ($g(x') \leq 0$), the max is $f(x')$.
  • If infeasible, $\max L = +\infty$.
• Example: For $x' = \begin{bmatrix} 1 \\ 4 \end{bmatrix}$, $g(x') = -2 \leq 0$, so $\max L = x_1'^2 + 2x_2' = 1 + 8 = 9$.

11. Model Complexity & Bias-Variance Trade-off

• Key Concepts (Q15, Q18):

  • Underfitting: High bias, low variance (simplistic model).
  • Overfitting: Low bias, high variance (complex model).
  • Bagging (e.g., Random Forest): Train estimators in parallel on bootstrapped data.
  • Boosting (e.g., AdaBoost): Train sequentially, reweighting misclassified points.
• AdaBoost (Q17): Decrease weights for correctly classified observations in next round.

12. Support Vector Machines (SVM)

• Soft-Margin SVM: Allows misclassification via slack variables $\xi_i$.

  • Slack Variable $\xi_i$: Distance from correct margin boundary (Q19–Q22).

    • $\xi_i = 0$ if point is on correct side of margin.
    • $\xi_i > 0$ if point violates margin or is misclassified.
  • Support Vectors: Points with $\xi_i > 0$ or on the margin.

• Key Properties (Q16):

  • Removing non-support vectors does not change the model.
  • Kernel trick: Map data to higher dimensions for linear separation.

2. MAP Estimation & Bayesian Learning

3. Logistic Regression & Class Imbalance

4. k-Means Clustering

5. Gradient Descent & Linear Regression

6. SVM & Slack Variables

7. Bias-Variance Trade-off

8. Ensemble Methods