IIT M FOUNDATION FN EXAM FDF1 24 Dec 2023 - 24 Dec 2023

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 Concepts:

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

• Steps:

  1. Center the data: Subtract the mean from each feature.
  2. Compute covariance matrix $\Sigma = \frac{1}{n} X^T X$.
  3. Eigen decomposition: Find eigenvalues $\lambda_i$ and eigenvectors $v_i$ of $\Sigma$.
  4. Sort eigenvalues: Select top-$k$ eigenvectors (principal components) corresponding to the largest eigenvalues.
  5. Project data: $X_{\text{new}} = X \cdot V_k$, where $V_k$ contains the top-$k$ eigenvectors.
• Reconstruction Error: Zero if $k = \text{rank}(X)$. For the given problem (Q3), $k = 3$ because the data lies in a 3D subspace (3 linearly independent points).
• Kernel PCA: Non-linear extension using kernel trick. Computes eigenvectors of the kernel matrix $K = \phi(X)^T \phi(X)$.

Equations:

1. Covariance Matrix:

1. Eigenvalue Problem:

1. Projection:

1. Kernel Matrix:

2. Clustering (Lloyd’s Algorithm / K-Means)

Key Concepts:

• Goal: Partition data into $k$ clusters by minimizing within-cluster variance.

• Steps:

  1. Initialize cluster centers $\mu_1, \mu_2, \dots, \mu_k$.
  2. Assign each point to the nearest center.
  3. Recompute centers as the mean of assigned points.
  4. Repeat until convergence.
• Convergence: Guaranteed (finite iterations) but may reach local optima.

Equations:

1. Assignment Step:

1. Update Step:

Example (Q5):

• Dataset: $\{2, 5, 8, 11, 15, 18, 22, 25\}$
• Initial Centers: $5, 15, 25$
• Final Centers: Converge to $\{5.5, 15, 22\}$ (sum = 42.5).

3. Gaussian Mixture Models (GMM) & EM Algorithm

Key Concepts:

• Goal: Probabilistic clustering assuming data is generated from a mixture of Gaussians.

• EM Algorithm:

  • E-Step: Compute responsibilities $\lambda_k^i$ (posterior probabilities):

• M-Step: Update parameters $\pi_k, \mu_k, \Sigma_k$ using responsibilities.

  • Convergence: Monotonic increase in log-likelihood.

Equations (Q6):

1. Responsibility:

For $i = 1, k = 2$:

4. Linear Regression & Ridge Regression

Key Concepts:

• Linear Regression:

  • Model: $h(w) = w^T X$
  • Loss: $L(w) = \|Xw - y\|^2$
  • Solution: $w^* = (X^T X)^{-1} X^T y$ (if $X$ is full-rank).
  • Zero Loss: $y$ is in the column space of $X$ (Q7).

• Ridge Regression:

  • Regularization: $L(w) = \|Xw - y\|^2 + \lambda \|w\|^2$
  • Solution: $w_\lambda = (X^T X + \lambda I)^{-1} X^T y$
  • Effect of $\lambda$: Higher $\lambda$ shrinks weights (Q8).

Equations:

1. Linear Regression Solution:

1. Ridge Regression Solution:

5. Decision Trees

Key Concepts:

• Splitting Criterion: Gini impurity or entropy.
• Pure Leaves: All points in a leaf belong to the same class.

• Possible Splits (Q9):

  • For binary classification, splits are of the form $x < p$.
  • Example: For the dataset in Q9, $p$ can be any integer between $-8$ and $20$ that separates classes. 12 possible values (e.g., $-7, 1, 2, \dots, 19$).

6. Naive Bayes

Key Concepts:

• Assumption: Features are conditionally independent given the class.
• Prediction: $\hat{y} = \arg\max_y P(y) \prod_i P(x_i | y)$.
• Insufficient Information (Q10): Need priors $P(y)$ to predict.

7. Perceptron Algorithm

Key Concepts:

• Model: $h(w) = \text{sign}(w^T x)$

• Convergence: Guaranteed if data is linearly separable (Q11).

  • Non-convergence: Data is not linearly separable (e.g., XOR-like patterns).

8. Logistic Regression

Key Concepts:

• Model: $P(y=1|x) = \sigma(w^T x)$, where $\sigma$ is the sigmoid.
• Decision Boundary: $w^T x = 0$ (for threshold = 0.5).

• Custom Threshold (Q12):

  • For threshold $t = 0.6$, solve $\sigma(w^T x) \geq 0.6$.
  • For $x = [1, 0]$, $w^T x = 0.5$, so $\sigma(0.5) \approx 0.62 > 0.6$. Predicted label = 1.

Equation:

9. Support Vector Machines (SVM)

Key Concepts:

• Hard-Margin SVM:

  • Objective: Maximize margin $\frac{2}{\|w\|}$.
  • Constraints: $y_i (w^T x_i + b) \geq 1$.
  • Decision Boundary: $w^T x + b = 0$.
  • Supporting Hyperplanes: $w^T x + b = \pm 1$.

• Soft-Margin SVM:

  • Slack Variables: $\xi_i$ allow misclassification.
  • Objective: $\min \frac{1}{2} \|w\|^2 + C \sum \xi_i$.
  • Constraints: $y_i (w^T x_i + b) \geq 1 - \xi_i$, $\xi_i \geq 0$.

Equations (Q13, Q14):

1. Decision Boundary:

1. Margin Width:

For Q14, if $w = [5, 6]$, then $\|w\| = \sqrt{61}$, so width $= \frac{2}{\sqrt{61}} \approx 0.26$. (Note: The answer in Q14 seems inconsistent; recheck the problem statement.)

1. Soft-Margin Constraints (Q15):

   • For $n$ points, there are $2n$ constraints (one for each $\xi_i \geq 0$ and one for the margin).

10. Model Evaluation & Ensemble Methods

Key Concepts:

• Bias-Variance Tradeoff:

  • Overfitting: High variance, low bias (e.g., Model 1 in Q17).
  • Underfitting: High bias, low variance (e.g., Model 4 in Q17).

• Bagging (Random Forest):

  • Parallel Training: Trees are independent (Q16).
  • Diversity: Reduces variance.
• Boosting: Sequentially corrects errors (not covered here).

Key Statements (Q16):

• Correct:

  • Weak learners in random forests can overfit (if deep trees are used).
  • Bagging helps only if models are diverse.
  • Random forests allow parallel training.

11. Loss Functions for Classification

Key Concepts (Q18):

• Suitable for Gradient Descent:

  • Square Loss: $L(w) = \sum (w^T x_i - y_i)^2$ (regression, but can be used for classification with care).
  • Hinge Loss: $L(w) = \sum \max(0, 1 - y_i w^T x_i)$ (SVM).
  • Logistic Loss: $L(w) = \sum \log(1 + e^{-y_i w^T x_i})$ (not listed but standard).

• Non-Differentiable:

  • $L(w) = \sum \text{sign}(w^T x_i) - y_i$ (not suitable for GD).

2. Clustering & GMM

3. Linear Models (Regression & Classification)

4. Model Evaluation & Ensemble Methods

5. Classification Algorithms