IIT M FOUNDATION AN EXAM QDF4 31 Aug - 31 Aug 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, along with Mermaid knowledge graphs to visualize relationships.

Core Topics & Key Concepts

1. Perceptron Algorithm

• Concept: Linear classifier for binary classification. Updates weights iteratively if misclassification occurs.

• Key Equations:

  • Update rule: $w \leftarrow w + \eta \cdot y_i x_i$ (if $y_i(w^T x_i) \leq 0$)
  • Decision boundary: $w^T x = 0$
• Convergence: Guaranteed if data is linearly separable (Novikoff’s theorem).
• Mistake Bound: Depends on margin and radius of data.

2. Kernel Methods & Feature Transformations

• Concept: Non-linear mapping of input features to higher-dimensional space using kernel functions.

• Key Equations:

  • Kernel trick: $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$
  • Example (Q3): $k(x, y) = 1 + x_1 y_1 + x_2 y_2 + x_1^2 y_1^2 x_2 y_2 + x_1 y_1 x_2^2 y_2^2$
  • Transformation $\phi$: Must satisfy $k(x, y) = \phi(x)^T \phi(y)$.
• Common Kernels: Linear, polynomial, RBF.

3. Support Vector Machines (SVM)

• Hard-Margin SVM:

  • Objective: Maximize margin $\frac{2}{||w||}$.
  • Constraints: $y_i(w^T x_i + b) \geq 1$.
  • Support Vectors: Points lying on the margin.

• Soft-Margin SVM:

  • Objective: $\min \frac{1}{2} ||w||^2 + C \sum \epsilon_i$.
  • Constraints: $y_i(w^T x_i + b) \geq 1 - \epsilon_i$, $\epsilon_i \geq 0$.

  • Role of $C$:

    • $C \to 0$: Ignores misclassifications (no support vectors).
    • $C \to \infty$: Hard-margin behavior (all points are support vectors if separable).

4. K-Means Clustering

• Concept: Partitions data into $K$ clusters by minimizing within-cluster variance.
• Objective Function: $F = \sum_{i=1}^n ||x_i - \mu_{z_i}||^2$

• Initialization:

  • Random: Pick $K$ points randomly.
  • Greedy (K-Means++): First center random, next centers maximize distance.
• Convergence: Guaranteed to local optimum (not necessarily global).

5. Neural Networks

• Architecture:

  • Input layer → Hidden layers (ReLU, sigmoid, etc.) → Output layer.

• Forward Propagation:

  • Hidden layer: $h = \text{ReLU}(W^{(1)} x)$
  • Output: $\hat{y} = \sigma(W^{(out)} h)$ (sigmoid for binary classification).
• Prediction: Output is probability $P(y=1)$.

6. Decision Trees

• Concept: Recursive partitioning of feature space.

• Key Properties:

  • Overfitting: Mitigated by limiting depth, pruning, or ensemble methods.
  • Feature Importance: Sensitive to small data perturbations.
  • Handling Data: Works for numerical and categorical features.

7. Logistic Regression

• Model: $P(y=1) = \frac{1}{1 + e^{-(w^T x)}}$.
• Interpretation: Log-odds linear in features.
• Example (Q12): $\hat{p} = \frac{1}{1 + e^{-(0.4x_1 + 0.1x_2)}}$. Solve for $x_1$ given $\hat{p} = 0.7$.

8. Random Forest

• Concept: Ensemble of decision trees. Predicts by averaging probabilities.

• Example (Q13):

  • Tree 1: $P(+1) = 0.7$
  • Tree 2: $P(+1) = 0.4$
  • Tree 3: $P(+1) = 0.8$
  • Final $P(+1) = \frac{0.7 + 0.4 + 0.8}{3} = 0.633$.

9. Bayesian Methods

• MAP Estimation: $\hat{\lambda}_{\text{MAP}} = \arg \max_\lambda f(\lambda | X)$.

  • Prior: $\lambda \sim \text{Uniform}(0, 2)$.
  • Likelihood: $X \sim \text{Exponential}(\lambda)$.
  • Posterior: $f(\lambda | X) \propto f(X | \lambda) f(\lambda)$.

10. Linear Regression & Ridge Regression

• Ordinary Least Squares (OLS): $\hat{w}_{ML} = (X^T X)^{-1} X^T Y$.

• Ridge Regression: $\hat{w}_{\text{Ridge}} = (X^T X + \lambda I)^{-1} X^T Y$.

  • Effect of $\lambda$:

    • High $\lambda$: Shrinks coefficients toward zero.
    • Low $\lambda$: Coefficients approach OLS solution.

11. Naive Bayes

• Concept: Assumes feature independence given class.

• Parameters:

  • For binary features and classes: $P(f_i | y)$ for each feature-class pair.
  • Laplace Smoothing: Adds pseudo-counts to avoid zero probabilities.

• Example (Q17-18):

  • 3 binary features → 2 (class priors) + 3 × 2 (feature probabilities) = 8 parameters.
  • With smoothing: 7 parameters (since one probability is determined by others).

12. Covariance & PCA

• Covariance Matrix: $C = \frac{1}{n} \sum (x_i - \mu)(x_i - \mu)^T$.
• Eigenvalues: Represent variance along principal components.
• Total Variance: Sum of eigenvalues $= \text{tr}(C)$.

Graph 2: Unsupervised Learning Relationships

Graph 3: Probabilistic Models

Graph 4: Regularization & Optimization

Key Equations Summary

This summary covers all questions in the exam, emphasizing equations, concepts, and relationships. The Mermaid graphs provide a visual hierarchy of topics. Focus on derivations (e.g., SVM constraints, kernel transformations) and practical implications (e.g., effect of $C$ in SVM, $\lambda$ in Ridge).