IIT M FOUNDATION DIPLOMA FN 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 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.
  4. Sort eigenvalues in descending order and select top-$k$ eigenvectors.
  5. Project data: $X_{\text{new}} = X U_k$.

• Variance along PC1:

  • For a dataset $\{x_1, \dots, x_n\}$, variance along the first PC is the largest eigenvalue $\lambda_1$ of the covariance matrix.
  • Equation:

• Example (Q2): For dataset $\{-2u, -u, u, 2u\}$, variance along PC1 is $2.5$.

• Reconstruction Error:

  • If you retain only the top-$k$ PCs, the reconstruction error is the sum of the discarded eigenvalues.
  • Equation:

• Example (Q3): For a dataset lying in a 2D subspace of $\mathbb{R}^4$, retaining 2 PCs gives zero error.

2. Bayesian Statistics & MAP Estimation

• Prior and Posterior:

  • Prior: $p(\theta)$ (e.g., $\text{Uniform}[0, 60]$ for $\theta$).
  • Likelihood: $p(X|\theta)$.
  • Posterior: $p(\theta|X) \propto p(X|\theta) p(\theta)$.

• MAP Estimate:

  • Maximizes the posterior: $\hat{\theta}_{\text{MAP}} = \arg\max_\theta p(\theta|X)$.
  • For uniform prior, MAP = MLE.
  • Example (Q4): For $X \sim \text{Uniform}[0, \theta]$, MAP estimate is $\max(X_i)$. Given data $\{10, 55, \dots\}$, $\hat{\theta}_{\text{MAP}} = 55$.

3. Logistic Regression & Class Imbalance

• Decision Threshold:

  • Lower threshold $\rightarrow$ higher recall (fewer false negatives, more false positives).
  • Higher threshold $\rightarrow$ higher precision (fewer false positives, more false negatives).
• Example (Q5): For spam detection, prioritize recall (detect all phishing emails) by setting a low threshold (answer: 1).

4. Cross-Validation (LOOCV)

• Leave-One-Out Cross-Validation (LOOCV):

  • For each data point $(x_i, y_i)$, train on $n-1$ points and test on $(x_i, y_i)$.
  • Error: $\text{Error} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{f}^{-i}(x_i))^2$.

• Example (Q6):

  • Dataset: $D = \{(1,2), (2,2), (0,1)\}$.
  • Model: $\hat{f} = \beta x$.
  • LOOCV error: $2$.

5. K-Means Clustering

• Algorithm Steps:

  1. Specify $k$ (number of clusters).
  2. Initialize centroids randomly.
  3. Assign points to nearest centroid.
  4. Recompute centroids as mean of assigned points.
  5. Repeat until convergence.
• Correct Sequence (Q7): 3 (random init) → 1 (assign) → 4 (recompute) → 2 (reassign).

6. Optimization & Lagrangian

• Lagrangian for Constrained Optimization:

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

• Example (Q8):

  • $f(x) = x_1^2 + 2x_2$, constraint $x_1 - x_2 \geq 3$.
  • For $x' = [1, 4]$, $L(x', \lambda) = 1 + 8 - \lambda (1 - 4) = 9 + 3\lambda$.
  • $\max_{\lambda \geq 0} L(x', \lambda) = \infty$ (but answer is 89, likely a miscalculation in options).

7. Gradient Descent for Linear Regression

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

• Example (Q9):

  • $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)$.
  • Updated weights: $w_1 = \begin{bmatrix} -0.2 \\ 3.1 \end{bmatrix}$.

8. Perceptron Algorithm

• Update Rule:

  • If $y_i (w_t^T x_i) \leq 0$, update: $w_{t+1} = w_t + \eta y_i x_i$.

• Example (Q10):

  • $w^t = [0, 1, 2]$, $x_1 = [1, -1, 0]$, $y_1 = 1$.
  • $w^{t+1} = [0, 1, 2] + [1, -1, 0] = [1, 0, 2]$.
  • Next point $x_2 = [-1, 1, 1]$, $y_2 = -1$.
  • $w^{t+2} = [1, 0, 2] + [-1, 1, 1] = [0, 1, 3]$ (but answer is $[2, -1, 1]$, likely due to $\eta \neq 1$).

9. Support Vector Machines (SVM)

• Key Concepts:

  • Support Vectors: Points lying on the margin boundaries $w^T x = \pm 1$.
  • Slack Variables ($\xi_i$): Measure violation of margin constraints.
  • Soft-Margin SVM: Minimize $\|w\|^2 + C \sum \xi_i$.

• Examples (Q11, Q19-22):

  • Removing non-support vectors does not change the model (Q11: B).

  • $\xi_i$:

    • $\xi_i = 0$ if point is correctly classified and outside margin.
    • $\xi_i =$ distance to correct margin if misclassified or inside margin.

  • Answers:

    • $\xi_1 = 0$ (Q20), $\xi_2 = 0$ (Q21), $\xi_4 = 1$ (Q19), $\xi_6 = 2$ (Q22).

10. AdaBoost

• Weight Update:

  • Increase weights for misclassified points.
  • Decrease weights for correctly classified points.
• Example (Q12): Weights decrease if classified correctly (answer: B).

11. Bias-Variance Tradeoff & Model Complexity

• Underfitting: High bias, low variance.
• Overfitting: Low bias, high variance.
• Example (Q13): Increasing complexity does not always increase test error (answer: B).

• Example (Q15):

  • B: Long decision trees can overfit.
  • C: Weak learners are slightly better than random.
  • D: Bagging estimators can be trained in parallel.

12. Naive Bayes

• Assumption: Features are conditionally independent given the class.

• Parameters:

  • $P(x_i | y)$ for each feature $i$ and class $y$.
  • $P(y)$ (class prior).

• Example (Q16-18):

  • Dataset: 8 binary points, 4 in each class.
  • $P(x_1 = 1 | y = 1) = b = \frac{3}{4}$, $P(x_1 = 1 | y = 0) = a = \frac{1}{4}$.
  • $a + b = 1$ (Q16), $b + d + f = 2$ (Q17).
  • Predicted label for $[0, ?, ?]$: Likely $y = 1$ (Q18).

13. Learning Curves

• Training vs. Validation Loss:

  • Training loss decreases monotonically.
  • Validation loss may increase if overfitting.

• Example (Q14):

  • Curve A (steep): Training loss.
  • Curve B (gradual): Validation loss.

Graph 2: Unsupervised Learning & Optimization

Graph 3: Model Evaluation

Graph 4: Ensemble Methods