IIT M DIPLOMA AN EXAM QDD4 13 Apr 2025 - 13 Apr 2025

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 for the Diploma-Level Machine Learning Techniques exam, followed by Mermaid knowledge graphs to visualize relationships.

1. Core Topics & Concepts

A. Supervised Learning

1. Linear Regression & Regularization

   • Ordinary Least Squares (OLS): Minimizes $\|Xw - y\|^2$.

   • Ridge Regression (L2):

     • Loss: $\|Xw - y\|^2 + \lambda \|w\|^2$.
     • Role of regularization: Penalizes large coefficients to reduce overfitting (Q2).
     • Weight vector: Coefficients are shrunk but rarely zero.

   • Lasso Regression (L1):

     • Loss: $\|Xw - y\|^2 + \lambda \|w\|_1$.
     • Feature selection: Forces some coefficients to zero (sparse solution) (Q4).
   • Key Equation:

1. Logistic Regression

   • Sigmoid function: $\sigma(z) = \frac{1}{1 + e^{-z}}$.
   • Decision boundary: Predict $\hat{y} = 1$ if $P(y=1|x) > \text{threshold}$ (e.g., 0.55 in Q15).
   • Key Equation:

1. Support Vector Machines (SVM)

   • Hard-Margin SVM: Maximizes margin $\frac{2}{\|w\|}$ with no misclassifications.

   • Soft-Margin SVM: Allows misclassifications (slack variables $\xi_i$) with penalty $C$.

     • Primal Problem:

• Dual Problem: Solve for $\alpha_i$ (Lagrange multipliers).

  • KKT Conditions (Q9):

    • If $\alpha_i^* = 0$: Correctly classified (outside margin).
    • If $0 < \alpha_i^* < C$: Lies on margin ($\xi_i = 0$).
    • If $\alpha_i^* = C$: Misclassified or margin violator ($\xi_i > 0$).

• Prediction: $f(x) = \text{sign}\left( \sum \alpha_i^* y_i K(x_i, x) + b \right)$.

  • Kernel Trick: Non-linear decision boundaries via $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$.

1. Decision Trees

   • Impurity Measures:

     • Entropy: $H(S) = -\sum p_i \log_2 p_i$.
     • Gini Index: $G(S) = 1 - \sum p_i^2$.

   • Splitting Criteria:

     • Information Gain: $\Delta H = H(S) - \sum \frac{|S_v|}{|S|} H(S_v)$.
   • Pure Node: All samples belong to the same class ($H(S) = 0$) (Q3).

1. Model Evaluation

   • Bias-Variance Tradeoff (Q8):

     • High Bias (Underfitting): Model 1 (linear) has higher bias than Model 2 (polynomial).
     • High Variance (Overfitting): Complex models (e.g., high-degree polynomials) fit noise.
   • Weak Learners (Q7): Slightly better than random guessing (used in boosting).

B. Unsupervised Learning

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

   • Steps:

     1. Initialize centroids.
     2. Assign points to nearest centroid.
     3. Recompute centroids as mean of assigned points.
   • Convergence: Centroids stabilize (Q5).
   • Distance Metric: Typically Euclidean distance.

1. Dimensionality Reduction

   • PCA: Linear projection to maximize variance.

   • Kernel PCA: Non-linear projection via kernel trick (Q6).

     • Polynomial Kernel: $K(x, x') = (x^T x' + c)^d$.
     • Example: For $x_4^2 = x_1 x_2 + x_1 x_2 x_3$, use degree-3 kernel.

C. Ensemble Methods

1. AdaBoost

   • Algorithm:

     1. Initialize weights $D_i = \frac{1}{N}$.
     2. Train weak learner $h_t$, compute error $\epsilon_t$.
     3. Update weights: $D_i \leftarrow D_i \beta_t^{1-y_i h_t(x_i)}$, where $\beta_t = \frac{\epsilon_t}{1-\epsilon_t}$.
     4. Combine classifiers: $H(x) = \text{sign}\left( \sum \alpha_t h_t(x) \right)$, where $\alpha_t = \log \frac{1-\epsilon_t}{\epsilon_t}$.

   • Error Calculation (Q17, Q18):

     • Lower error classifier gets higher weight (e.g., $h_1$ in Q18).
     • Final classifier: $h^*(x) = \text{sign}(\alpha h_1(x))$.

1. Bagging vs. Boosting:

   • Bagging (e.g., Random Forest): Reduces variance by averaging independent models.
   • Boosting (e.g., AdaBoost): Reduces bias by sequentially correcting errors.

D. Probabilistic Models

1. Naïve Bayes

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

• Example (Q14): Compute $P(\text{Play}=\text{Yes}|\text{Overcast, Cool, High, Weak})$.

1. Bayesian Inference

   • Beta-Binomial Model (Q12):

     • Prior: $\text{Beta}(\alpha, \beta)$.
     • Posterior: $\text{Beta}(\alpha + \text{heads}, \beta + \text{tails})$.
     • Posterior Mean: $\frac{\alpha + \text{heads}}{\alpha + \beta + n}$.
     • Example: For 150 heads in 1000 flips with $\text{Beta}(10, 40)$ prior:

E. Neural Networks

1. Single-Layer Perceptron

   • Activation: Step function (for classification) or ReLU (for regression).
   • Training: Update weights via perceptron rule $w \leftarrow w + \eta (y - \hat{y})x$.
   • Convergence: Guaranteed if data is linearly separable (Q10).

1. Multi-Layer Perceptron (MLP)

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

   • Forward Pass (Q13):

     • Hidden layer: $h_1 = \text{ReLU}(w_1^{(1)} x_1 + w_2^{(1)} x_2)$, $h_2 = \text{ReLU}(w_1^{(2)} x_1 + w_2^{(2)} x_2)$.
     • Output: $\hat{y} = u_{out}^T h$.

F. Kernel Methods

1. Kernel Regression

   • Dual Form: $w^* = \Phi(X) \alpha$, where $\Phi$ is the feature map.
   • Prediction (Q11):

• Polynomial Kernel Example:

1. SVM Kernels:

   • Linear, polynomial, RBF, etc.

2. Key Equations Summary

Graph 2: Unsupervised Learning Relationships

Graph 3: Ensemble Methods

Graph 4: Probabilistic Models

Graph 5: Neural Networks

Graph 6: Model Evaluation

4. Exam Tips

1. Regularization (Q2, Q4):

   • Ridge: Shrinks coefficients (never zero).
   • Lasso: Sparse coefficients (some zero).
   • Match weight vectors: Large values → Linear/Ridge; sparse → Lasso.

1. Decision Trees (Q3):

   • Pure node: All samples same class or entropy = 0.

1. Clustering (Q5):

   • Recompute centroids after assignment, then reassign points.

1. Kernel PCA (Q6):

   • Match kernel degree to data relationship (e.g., $x_4^2 = x_1 x_2 + x_1 x_2 x_3$ → degree 3).

1. Bias-Variance (Q8):

   • Simpler model (Model 1) → higher bias, underfits.
   • Complex model (Model 2) → higher variance, may overfit.

1. SVM (Q9, Q16):

   • $\alpha_i^* = 0$: Correctly classified.
   • $0 < \alpha_i^* < C$: On margin.
   • $\alpha_i^* = C$: Misclassified or margin violator.
   • Prediction: $\text{sign}(\sum \alpha_i^* y_i K(x_i, x_{\text{test}}) + b)$.

1. AdaBoost (Q17, Q18):

   • Choose classifier with lower error.
   • Update weights: Increase for misclassified samples.
   • Final model: Weighted sign of selected classifier.

1. Naïve Bayes (Q14):

   • Use Laplace smoothing if zero probabilities occur.
   • Multiply conditional probabilities for prediction.

1. Bayesian Inference (Q12):

   • Posterior mean = $\frac{\alpha + \text{successes}}{\alpha + \beta + n}$.

1. Neural Networks (Q13):

   • ReLU: $\text{max}(0, z)$.
   • Forward pass: Compute hidden layer, then output.

1. Kernel Regression (Q11):

   • Predict using $\alpha^T K(X, x')$.
   • Expand kernel explicitly for polynomial cases.

1. Perceptron (Q10):

   • Converges if data is linearly separable.
   • Update weights iteratively for misclassified points.