IIT M DIPLOMA FN1 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, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Concepts

1. Supervised Learning

• Linear Regression & Gradient Descent

  • Key Equations:

    • Hypothesis: $h_\theta(x) = \theta_0 + \theta_1 x_1 + \dots + \theta_n x_n$
    • Loss (MSE): $J(\theta) = \frac{1}{2m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2$
    • Gradient Descent Update: $\theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta_j}$

  • Concepts:

    • Learning rate ($\alpha$) tuning (too high → divergence; too low → slow convergence).
    • Feature scaling for faster convergence.

• Logistic Regression

  • Key Equations:

    • Sigmoid: $\sigma(z) = \frac{1}{1 + e^{-z}}$
    • Loss (Log Loss): $J(\theta) = -\frac{1}{m} \sum_{i=1}^m [y^{(i)} \log(h_\theta(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_\theta(x^{(i)}))]$

  • Concepts:

    • Decision boundary, probability interpretation.

• Support Vector Machines (SVM)

  • Key Equations:

    • Hard-margin primal: $\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$ s.t. $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1$.
    • Soft-margin primal: $\min_{\mathbf{w}, b, \xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum \xi_i$ s.t. $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i$.
    • Kernel trick: $K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)$ (e.g., quadratic kernel).

  • Concepts:

    • Support vectors, margin maximization, slack variables ($\xi$), kernel SVM for non-linear boundaries.
    • Complementary Slackness: $\alpha_i (y_i (\mathbf{w}^T \mathbf{x}_i + b) - 1 + \xi_i) = 0$.
    • KKT Conditions: Primal/dual optimality conditions.

• Decision Trees

  • Key Concepts:

    • Splitting criteria (Gini impurity, entropy).
    • Overfitting vs. pruning (pre/post-pruning).
    • Feature selection at nodes (e.g., $x_2 < a$).

  • Example:

    • For Q23–Q26, interpret decision regions from tree structure (e.g., $a = 3, b = 1, c = 4$).

• k-Nearest Neighbors (k-NN)

  • Key Concepts:

    • Lazy learning, distance metrics (Euclidean, Manhattan).
    • Bias-variance tradeoff: Small $k$ → low bias/high variance; large $k$ → high bias/low variance.
    • Bagging: Prefer models with high variance (e.g., fully grown decision trees, small $k$ in k-NN).

• Naive Bayes

  • Key Equations:

    • Posterior: $P(y|\mathbf{x}) = \frac{P(\mathbf{x}|y) P(y)}{P(\mathbf{x})}$.
    • Likelihood (Bernoulli): $P(x_j|y) = p_j^{x_j} (1 - p_j)^{1 - x_j}$.

  • Concepts:

    • Feature independence assumption.
    • Handling zero probabilities (smoothing).

• Perceptron Algorithm

  • Key Equations:

    • Update rule: $\mathbf{w} := \mathbf{w} + \eta \cdot y_i \mathbf{x}_i$ if misclassified.
    • Mistake bound: $\leq \left(\frac{R \|\mathbf{w}^*\|\ }{\gamma}\right)^2$ (where $\gamma$ is the margin).

  • Concepts:

    • Linearly separable data, convergence guarantees.
    • For Q20–Q21: Track weight updates and count mistakes.

• Model Selection & Bias-Variance Tradeoff

  • Key Concepts:

    • Bias: Error due to overly simple model (e.g., linear model for quadratic data).
    • Variance: Error due to sensitivity to training data (e.g., high-degree polynomial).
    • Overfitting/Underfitting: Q7, Q14–Q15 highlight tradeoffs (e.g., Model 2 overfits if true relationship is linear).

2. Unsupervised Learning

• Principal Component Analysis (PCA)

  • Key Equations:

    • Covariance matrix: $\mathbf{C} = \frac{1}{n} \mathbf{X}^T \mathbf{X}$.
    • Eigenvalue decomposition: $\mathbf{C} = \mathbf{W} \mathbf{\Lambda} \mathbf{W}^T$.
    • Variance along PC1: $\lambda_1$ (largest eigenvalue).

  • Concepts:

    • Dimensionality reduction, orthogonal projections.
    • For Q16–Q17: Diagonal covariance matrix implies uncorrelated features.

• Clustering (Lloyd’s Algorithm for k-Means)

  • Key Concepts:

    • Iterative assignment and centroid update.
    • Sensitivity to initialization (Q22).

3. Ensemble Methods

• Bagging (Bootstrap Aggregating)

  • Key Concepts:

    • Reduces variance by averaging multiple models (e.g., decision trees, k-NN with small $k$).
    • Q2: Prefer high-variance base estimators (e.g., fully grown trees, small $k$).

• Boosting (AdaBoost)

  • Key Equations:

    • Weight update: $w_i := w_i \cdot e^{-\alpha_t y_i h_t(\mathbf{x}_i)}$ (normalized).
    • Final predictor: $H(\mathbf{x}) = \text{sign}\left(\sum_t \alpha_t h_t(\mathbf{x})\right)$.

  • Concepts:

    • Focuses on misclassified points (Q27–Q29).
    • Training error: $\frac{\sum_{i=1}^m w_i \mathbb{I}(y_i \neq h_t(\mathbf{x}_i))}{\sum_{i=1}^m w_i}$.

4. Mathematical Foundations

• Activation Functions

  • ReLU: $\text{ReLU}(z) = \max(0, z)$ (Q3).

• Maximum Likelihood Estimation (MLE)

  • For uniform distribution $U[0, a]$: $\hat{a}_{\text{MLE}} = \max(x_i)$ (Q9).

• Linear Algebra

  • Eigenvalues/eigenvectors (PCA), matrix operations (e.g., $\mathbf{w}^T \mathbf{x}$).

• Optimization

  • Gradient descent (Q4), Lagrange multipliers (SVM dual).

5. Evaluation & Cross-Validation

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

  • Concepts:

    • Higher $k$ in k-NN → smoother decision boundaries → lower LOOCV error (Q12).

• Support Vectors in SVM

  • Concepts:

    • Points on the margin ($\alpha_i > 0$) or misclassified ($\xi_i > 0$) (Q13, Q30–Q31).

Key Equations Summary

2. Unsupervised Learning & Ensemble Methods

3. Bias-Variance Tradeoff

4. SVM Components

5. Optimization & Evaluation

Exam-Specific Tips

1. SVM (Q5, Q6, Q11, Q13, Q30–Q31):

   • Hard-margin SVM requires linearly separable data (Q5: Both datasets are separable with a quadratic kernel).
   • Kernel validity: $x_1 x_2 k(x_1, x_2)$ is valid if $k$ is a kernel (Q6: YES, because product of kernels is a kernel).
   • Support vectors: Points with $\alpha_i > 0$ or $\xi_i > 0$ (Q13: Options B, D).

1. Decision Trees (Q2, Q23–Q26):

   • Bagging prefers high-variance models (Q2: B, C).
   • Interpret tree splits to find $a, b, c$ (Q23: $a = 3$, Q24: $b = 1$, Q25: $c = 4$).

1. Neural Networks (Q3, Q8):

   • ReLU outputs $0$ for negative inputs (Q3: C).
   • Parameter count: $(10 \times 5) + (5 \times 5) \times 4 + (5 \times 2) = 187$ (Q8).

1. Perceptron (Q10, Q20–Q21):

   • Mistake bound depends on margin $\gamma$ (Q10: 25 mistakes).
   • Track weight updates in order $\{x_4, x_3, x_2, x_1\}$ (Q20: 2 mistakes; Q21: $\|\mathbf{w}\|^2 = 4$).

1. AdaBoost (Q27–Q29):

   • Weight updates: Misclassified points get higher weights (Q27: $w_1 \approx 0.25$).
   • True label for $x_2$: Must be $+1$ to explain weight increase (Q28: $+1$).
   • Training error: $\frac{1/2 + 1/4}{1/2 + 1/4 + 1/4} \approx 0.33$ (Q29).

1. PCA (Q16–Q17):

   • Variance along PC1 = first diagonal entry of $\mathbf{C}$ (Q16: 15).
   • Uncorrelated features → off-diagonal entries $a, b, c = 0$ (Q17: C).

1. Naive Bayes (Q18–Q19):

   • $P(x_1 = 0) = 0$ → $P(y|x) = 0$ (Q19: C).

1. Clustering (Q22):

   • Lloyd’s algorithm: Reassign points to nearest centroid (Q22: C).