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 & Key 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_{\text{proj}} = X U_k$.
• Variance along PC1: Largest eigenvalue of $\Sigma$.

• Reconstruction Error: Sum of variances of discarded components.

  • If top-$k$ PCs retain all variance, error = 0 (Q3).

• Key Equations:

  • Covariance matrix: $\Sigma = \frac{1}{n} \sum_{i=1}^n (x_i - \mu)(x_i - \mu)^T$.
  • Variance along PC1: $\lambda_1$ (largest eigenvalue).

2. Probability & Bayesian Estimation

• Maximum A Posteriori (MAP) Estimate:

  • $\hat{\theta}_{\text{MAP}} = \arg \max_\theta p(\theta | X) \propto p(X | \theta) p(\theta)$.
  • For Uniform prior $\theta \sim \text{Uniform}[0, 60]$ and likelihood $X \sim \text{Uniform}[0, \theta]$, MAP = max observed value (Q4: $\hat{\theta} = 52$).

3. Logistic Regression & Classification Metrics

• Threshold Adjustment:

  • Low threshold → High recall (fewer false negatives, e.g., spam detection; Q5: 1).
  • High threshold → High precision (fewer false positives).

• Naïve Bayes:

  • Assumes feature independence given class: $p(x|y) = \prod_i p(x_i|y)$.

  • Parameters $\hat{p}_i^y$: Empirical frequencies (Q10–Q12).

    • Example: $b = p(x_1=1|y=1) = \frac{\text{Count}(x_1=1, y=1)}{\text{Count}(y=1)}$.

4. Clustering (k-Means)

• Properties:

  • Sensitive to outliers (Q6: B).
  • Initialization affects convergence speed (Q6: D).
  • Not guaranteed to converge to global optimum.

• Algorithm:

  1. Initialize centroids.
  2. Assign points to nearest centroid.
  3. Recompute centroids.
  4. Repeat until convergence.

5. Model Training & Validation

• Training vs. Validation Loss:

  • Training loss (Curve A) decreases monotonically.
  • Validation loss (Curve D) may increase if overfitting (Q7: A, D).

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

  • Error: $\text{error}_L = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{f}^{-i}(x_i))^2$.
  • For $\hat{f} = \beta x$, solve $\beta$ using least squares on $n-1$ points (Q13).

6. Optimization & Gradient Descent

• Gradient Descent Update:

  • $w_{t+1} = w_t - \eta \nabla f(w_t)$.
  • For linear regression: $\nabla f(w) = 2 X^T (X w - y)$ (Q8).

• Lagrangian & Constrained Optimization:

  • $L(x, \lambda) = f(x) + \lambda g(x)$.
  • For $\min x_1^2 + 2x_2$ s.t. $x_1 - x_2 \leq 3$, evaluate $L(x', \lambda)$ at $x' = [1, 4]$ (Q14: A).

7. Support Vector Machines (SVM)

• Soft-Margin SVM:

  • Slack variables $\xi_i$: Measure violation of margin constraints.
  • $\xi_i = 0$ if point is on correct side of margin (Q19–Q22).
  • $\xi_i =$ distance to margin if misclassified or within margin.

• Support Vectors:

  • Points on margin boundaries ($w^T x = \pm 1$).
  • Removing non-support vectors does not change the model (Q16: B).

8. Ensemble Methods

• AdaBoost:

  • Weights of correctly classified points are decreased (Q17: B).
  • Weak learners: Slightly better than random (Q15: C).

• Bagging:

  • Estimators can be trained in parallel (Q15: D).

9. Bias-Variance Tradeoff

• Underfitting: High bias, low variance (Q15: A is incorrect).
• Overfitting: High variance, low bias (e.g., deep decision trees; Q15: B).

Graph 2: Classification & Probabilistic Models

Graph 3: Model Evaluation & Optimization

Graph 4: SVM & Ensemble Methods

Graph 5: Clustering & Probability