IIT M DIPLOMA AN1 EXAM ETD1 11 Dec 2022 - 11 Dec 2022

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 the core topics, concepts, principles, and equations essential for the Diploma-Level Machine Learning Techniques exam, along with a Mermaid knowledge graph to visualize relationships.

Core Topics & Key Concepts

1. Activation Functions

• ReLU (Rectified Linear Unit):

  • Definition: $\text{ReLU}(x) = \max(0, x)$
  • Outputs: $0$ for $x < 0$, $x$ for $x \geq 0$.
  • Example: For inputs $[-2.7, 3.9, -1.0, 4.2, 6.4, -7.3]$, outputs are $[0, 3.9, 0, 4.2, 6.4, 0]$ (Q2).

2. Gradient Descent & Optimization

• Learning Rate ($\alpha$):

  • If loss increases, the learning rate is too high (divergence).
  • Fix: Reduce $\alpha$ (Q3).

• Stochastic vs. Batch Gradient Descent:

  • Batch: Uses entire dataset.
  • Stochastic: Uses one sample per iteration.

3. Support Vector Machines (SVM)

Hard-Margin SVM

• Objective: Maximize margin $\frac{2}{||w||}$ for linearly separable data.
• Constraints: $y_i (w^T x_i + b) \geq 1$.

• Kernel Trick:

  • Quadratic Kernel: $K(x_i, x_j) = (x_i^T x_j + c)^2$.

  • Valid Kernels: Must satisfy Mercer’s condition (Q5).

    • If $k(x_1, x_2)$ is a valid kernel, then $x_1^3 x_2^3 k(x_1, x_2)$ is also valid.

Soft-Margin SVM

• Slack Variables ($\xi_i$): Allow misclassification.

• Dual Problem:

  • $\alpha_i^*$ (Lagrange multipliers) are nonzero only for support vectors.
  • If $\beta_i^* = 0$, the point is misclassified or within margin (Q10).

4. Model Complexity & Bias-Variance Tradeoff

• Bias:

  • High Bias (Underfitting): Model is too simple (e.g., low-degree polynomial).
  • Low Bias (Overfitting): Model is too complex (e.g., high-degree polynomial).

• Example (Q6, Q15, Q16):

  • Model 1: $\hat{y} = a_0 + a_1 x + a_2 x^2$ (higher bias, lower variance).
  • Model 2: $\hat{y} = a_0 + a_1 x + \dots + a_{10} x^{10}$ (lower bias, higher variance).
  • Test Error: Depends on the true data distribution (Q16).

5. Perceptron Algorithm

• Update Rule:

  • $w \leftarrow w + \eta \cdot y_i x_i$ if misclassified.

• Mistake Bound:

  • For separable data with margin $\gamma$, max mistakes:

• Example (Q13, Q21, Q22):

  • Given $||w|| = 1$, $y_i (w^T x_i) \geq 0.25$, and $||x_i|| \leq 1$, max mistakes = 16.
  • For 4 points in $\mathbb{R}^2$, Perceptron makes 2 mistakes and converges to $w$ with squared length 4.

6. Decision Trees

• Splitting Criteria:

  • Gini impurity, entropy, or misclassification error.

• Example (Q23-Q26):

  • Tree structure:

          x2 < a
         /      \
     x1 < b      p
     /    \
    q     x1 < c
         /      \
        r        s

  • Decision Regions:

    • $a = 2$, $b = 2$, $c = 4$ (for given labels).

  • Leaf Values:

    • $p, q, r, s \in \{0, 1\}$.
    • Expression: $(1 + p + r)(q + s) = 2$.

7. k-Nearest Neighbors (k-NN)

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

  • Lower error for higher $k$ (smoother decision boundaries).
  • Example (Q8): 3-NN has lower LOOCV error than 1-NN.

8. Clustering (Lloyd’s Algorithm / k-Means)

• Steps:

  1. Initialize centroids.
  2. Assign points to nearest centroid.
  3. Recompute centroids.

• Example (Q9):

  • Initial clusters: $C_1 = \{5, 6, -2, -3\}$, $C_2 = \{1, 7, -4, -1\}$.
  • After 1 iteration: $C_1 = \{5, 6, 1\}$, $C_2 = \{-2, -3, 7, -4, -1\}$.

9. Principal Component Analysis (PCA)

• Covariance Matrix ($C$):

  • Diagonal entries = variances.
  • Off-diagonal entries = covariances.

• Principal Components:

  • Eigenvectors of $C$, ordered by eigenvalues.

• Example (Q17, Q18):

  • Given $C = \begin{bmatrix} 12 & a & b \\ a & 6 & c \\ b & c & 3 \end{bmatrix}$, first PC variance = 12.
  • If eigenvectors are standard basis, features are uncorrelated.

10. Naive Bayes

• Assumption: Features are conditionally independent given the class.
• Prediction:

• Example (Q19, Q20):

  • If a feature is always 0, $P(x_j = 1 | y) = 0$.
  • Prediction for $x = [1, 1, 1, 0]$ is indeterminate (zero probability).

11. AdaBoost

• Weight Update:

  • Increase weights for misclassified points.
  • $w_i \leftarrow w_i \cdot e^{\alpha_t \cdot \mathbb{I}(y_i \neq h_t(x_i))}$.

• Error Calculation:

  • Training error = sum of weights of misclassified points.

• Example (Q27-Q29):

  • Initial weights: $\frac{1}{3}$.

  • After 1 iteration:

    • $x_1$: weight = $\frac{1}{2}$, true label = -1.
    • $x_2$: weight ≈ 0.25 (correctly classified).
    • Training error ≈ 0.33.

12. Maximum Likelihood Estimation (MLE)

• Uniform Distribution:

  • $X \sim \text{Uniform}[0, a]$.
  • MLE for $a$: $\hat{a} = \max(x_i)$.

• Example (Q12):

  • Given samples $\{15, 21.3, 8.5, 2, 40, 33, 28.4\}$, $\hat{a} = 40$.

13. Ensemble Methods (Bagging)

• Preferred Estimators:

  • High variance, low bias models (e.g., deep decision trees, k-NN with small $k$).

• Example (Q11):

  • Decision stump with random features (reduces variance).
  • k-NN with small $k$ (high variance, good for bagging).

14. Neural Networks

• Parameter Count:

  • For a network with $L$ layers, parameters = sum of $(n_{l-1} + 1) \times n_l$ (including biases).

• Example (Q14):

  • Input: 8, Hidden: 4 layers × 4 neurons, Output: 2.
  • Total parameters = $(8+1) \times 4 + (4+1) \times 4 \times 3 + (4+1) \times 2 = 106$.

Key Equations

Exam Tips

1. SVM: Know the difference between hard-margin and soft-margin, and how kernels work.
2. Perceptron: Understand the mistake bound and update rule.
3. Decision Trees: Focus on splitting criteria and interpreting tree structures.
4. PCA: Remember that principal components are eigenvectors of the covariance matrix.
5. AdaBoost: Pay attention to weight updates and error calculations.
6. Neural Networks: Count parameters carefully (include biases!).
7. k-NN: Higher $k$ smooths decision boundaries (lower LOOCV error).