2023 Dec24: IIT M AN EXAM ADD4 - 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 & Key Concepts

1. Principal Component Analysis (PCA)

• Purpose: Dimensionality reduction while preserving variance.

• Steps:

  1. Center the data (subtract mean).
  2. Compute covariance matrix: $\Sigma = \frac{1}{n} X^T X$.
  3. Eigen-decomposition: $\Sigma = V \Lambda V^T$, where $V$ = eigenvectors (principal components), $\Lambda$ = eigenvalues.
  4. Project data onto top-$k$ eigenvectors.

• Key Equations:

  • Covariance matrix: $\Sigma = \frac{1}{n} \sum_{i=1}^n (x_i - \mu)(x_i - \mu)^T$.
  • Reconstruction error: Zero if $k = d$ (original dimensions).
  • First PC: Eigenvector corresponding to the largest eigenvalue.
• Example: For dataset $\mathcal{D} = \{(-1,1), (0,0), (1,1)\}$, the first PC is $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$.

2. Linear Regression

• Model: $y = w^T x + \epsilon$.
• Loss Function (Squared Error): $L(w) = \sum_{i=1}^n (w^T x_i - y_i)^2$.
• Optimal Weights (Closed-Form): $w^* = (X X^T)^{-1} X y$ (if $X$ is full-rank).

• Key Properties:

  • Minimum loss at $w^*$ is 0 if data is linearly separable.
  • For underdetermined systems, infinite solutions exist.

3. K-Means Clustering

• Algorithm: Lloyd’s algorithm (iterative assignment + centroid update).

• Properties:

  • Local minima: Depends on initialization (use K-means++ to mitigate).
  • Complexity: $O(n \cdot k \cdot d \cdot I)$, where $I$ = iterations.
  • Choosing $k$: Elbow method or silhouette score.

• Trade-offs:

  • K-means++ is slower but avoids poor initializations.
  • Larger $k$ increases computational cost.

4. Decision Trees

• Splitting Criteria:

  • Gini impurity or entropy for classification.
  • Variance reduction for regression.
• Pure Leaves: A leaf is pure if all samples belong to one class.
• Example: For binary classification with threshold $p$ in $x < p$, the number of possible integer $p$ values depends on the sorted unique values of $x$.

5. Naive Bayes Classifier

• Assumption: Features are conditionally independent given the class.

• Parameters to Learn:

  • Class priors: $P(y = c)$ for each class $c$.
  • Likelihoods: $P(f_j = v \mid y = c)$ for each feature $f_j$, value $v$, and class $c$.
• Example: For 4 classes and 3 binary features, total parameters = $3 \times 2 \times 4 + 3 = 27$ (but simplified to 15 if features are binary and symmetries are exploited).

6. Perceptron Algorithm

• Update Rule: $w \leftarrow w + \eta \cdot y_i x_i$ if $y_i (w^T x_i) \leq 0$.
• Convergence: Guaranteed if data is linearly separable and learning rate $\eta$ is small.
• Counterexample: Non-separable data (e.g., XOR) leads to no convergence.

7. Logistic Regression

• Model: $P(y=1 \mid x) = \sigma(w^T x)$, where $\sigma$ = sigmoid.
• Decision Rule: Predict $\hat{y} = 1$ if $P(y=1 \mid x) > 0.5$ (or another threshold).
• Example: For $w = \begin{bmatrix} 3/2 \\ 5/12 \end{bmatrix}$ and $x = \begin{bmatrix} 0 \\ 2 \end{bmatrix}$, compute $\sigma(w^T x)$. If $\sigma(w^T x) < 0.75$, predict $0$.

8. Support Vector Machines (SVM)

• Hard-Margin SVM:

  • Optimization: $\min \frac{1}{2} \|w\|^2$ s.t. $y_i (w^T x_i + b) \geq 1$.
  • Decision Boundary: $w^T x + b = 0$.
  • Supporting Hyperplanes: $w^T x + b = \pm 1$.
  • Margin Width: $\frac{2}{\|w\|}$.

• Soft-Margin SVM:

  • Allows misclassifications via slack variables $\xi_i$.
  • Optimization: $\min \frac{1}{2} \|w\|^2 + C \sum \xi_i$.

  • Effect of $C$:

    • Small $C$: Wider margin, more misclassifications.
    • Large $C$: Narrower margin, fewer misclassifications.
• Kernel Trick: For non-linear boundaries, use $\phi(x)$ (e.g., RBF kernel).

9. Model Evaluation & Bias-Variance Tradeoff

• Underfitting:

  • High bias, low variance.
  • Poor performance on training and test data.

• Overfitting:

  • Low bias, high variance.
  • Good training performance but poor generalization.

• Diagnostics:

  • Compare training vs. test error (e.g., Model 1 in Q18 overfits; Model 4 underfits).

10. Ensemble Methods (Bagging & Random Forest)

• Bagging:

  • Train multiple models on bootstrapped samples.
  • Average predictions (regression) or vote (classification).
  • Reduces variance.

• Random Forest:

  • Extension of bagging with feature randomness.
  • Parallelizable (trees are independent).
  • Weak learners (shallow trees) are preferred to avoid overfitting.

11. Neural Networks

• Architecture:

  • Input layer, hidden layers (with non-linear activations), output layer.

• Key Properties:

  • Universal approximator with sufficient hidden units.
  • Non-linear activations (e.g., ReLU, sigmoid) are essential for non-linear decision boundaries.
  • Bias terms are optional but typically included.

12. Regularization

• L1/L2 Regularization:

  • Add $\lambda \|w\|_1$ (Lasso) or $\lambda \|w\|_2^2$ (Ridge) to loss.

  • Effect of $\lambda$:

    • $\lambda \to 0$: Approaches unregularized solution.
    • $\lambda \to \infty$: Weights $w \to 0$.

Key Equations Summary

Graph 2: Classification Algorithms

Graph 3: Model Evaluation & Ensemble Methods

Graph 4: Optimization & Regularization

Exam Tips

1. PCA: Always center the data first. The first PC is the eigenvector with the largest eigenvalue.
2. SVM: The margin width is $\frac{2}{\|w\|}$. Supporting hyperplanes are $w^T x + b = \pm 1$.
3. Logistic Regression: Predict class based on $P(y=1 \mid x)$ vs. threshold (default 0.5).
4. Decision Trees: Count unique splits for pure leaves.
5. Naive Bayes: Parameters = (classes) × (features) × (feature values) + (class priors).
6. Perceptron: Only converges if data is linearly separable.
7. Regularization: $\lambda = 0$ removes regularization; $\lambda \to \infty$ forces weights to zero.