IIT M FOUNDATION DIPLOMA FN EXAM QDF1 28 Apr 2024 - 28 Apr 2024

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 Mermaid knowledge graphs to visualize relationships.

1. Core Topics & Key Concepts

A. Linear Algebra & Statistics

1. Covariance Matrix & Eigenvalues

   • Covariance matrix $C$ for a dataset $X \in \mathbb{R}^{n \times d}$:

• Eigenvalues ($\lambda_1, \lambda_2, \lambda_3$) represent variance along principal components.
• Total variance = Sum of eigenvalues:

• Solve linear systems for eigenvalues (e.g., Question 2).

1. Probability & Distributions

   • Bernoulli Distribution:

• Maximum Likelihood Estimation (MLE) for $p$:

• For two groups (e.g., Question 3), estimate $p_1$ and $p_2$ separately:

1. Bayesian Probability (Naive Bayes)

   • Conditional independence assumption:

• Posterior probability (e.g., Question 5):

• If $P(y=0|x_{\text{test}}) = 0$, no test samples match the training data for $y=0$.

B. Supervised Learning

1. Decision Trees

   • Splitting rules (e.g., Question 4):

     • Split on $x_1 < 0.5$, then $x_2 > 0.5$.
     • Probability of class 0 = Area of region where $x_1 < 0.5$ and $x_2 > 0.5$:

• Entropy/Information Gain (not directly tested here but related).

1. Perceptron Algorithm

   • Update rule (e.g., Questions 6, 10):

• Mistake bound for linearly separable data:

where $R = \max ||x_i||$, $\gamma = \min y_i (w^T x_i)$.

• For Question 6: $R = 1$, $\gamma = 0.2$, so max mistakes = $(1/0.2)^2 = 25$.

  • Convergence: Stops when all points are correctly classified (e.g., Question 10 converges in 1 update).

1. Support Vector Machines (SVM)

   • Hard-margin SVM (e.g., Question 14):

     • Linearly separable if a hyperplane exists with $y_i (w^T x_i + b) \geq 1$.
     • Margin width:

• Soft-margin SVM (e.g., Questions 16, 17):

  • Optimization problem:

• KKT conditions:

  • If $\xi_i > 0$, then $\alpha_i = C$ (point is a support vector).
  • If $y_i (w^T x_i + b) = 1$, then $\xi_i = 0$ (no bribe paid).

• Effect of $C$:

  • Small $C$: Larger margin, more misclassifications.
  • Large $C$: Hard-margin-like behavior.

1. Linear Regression

   • Normal equation (e.g., Question 13):

• Zero training loss if $y$ is in the column space of $X^T$ (i.e., $y = X^T w$ for some $w$).

C. Unsupervised Learning

1. K-Means Clustering

   • Objective: Minimize within-cluster sum of squares (WCSS).

   • Behavior with correlated features (e.g., Question 8):

     • If features are perfectly correlated ($\rho = 1$), clusters align along a straight line (not triangular).

1. Principal Component Analysis (PCA) & Kernel PCA

   • Standard PCA = Kernel PCA with linear kernel $k(x_i, x_j) = x_i^T x_j$ (e.g., Question 12).
   • Kernel trick: Can map data to infinite dimensions (e.g., polynomial kernel $k(x_i, x_j) = (x_i^T x_j + 1)^2$).

D. Neural Networks

1. Feedforward Neural Network (e.g., Question 7)

   • Hidden layer with sigmoid activation:

• Output layer with linear activation:

• Example calculation (Neuron 1 in hidden layer):

E. Ensemble Methods

1. AdaBoost

   • Weighted misclassification error (e.g., Question 15):

• Weight updates: Increase weights for misclassified points.
• Example: Points misclassified in the first stump get equal weights in the second stump (e.g., $[2,2]^T$ and $[1,4]^T$).

F. Optimization

1. Lagrangian & Duality (e.g., Question 11)

   • Lagrangian for constrained optimization:

• Dual problem: Maximize $L$ w.r.t. $\lambda \geq 0$.

2. Key Equations Summary

Graph 2: Unsupervised Learning & Dimensionality Reduction

Graph 3: Probability & Estimation

Graph 4: Optimization & Neural Networks

4. Exam Strategy

1. Focus Areas:

   • Eigenvalues/Covariance: Solve linear systems for eigenvalues (Question 2).
   • MLE for Bernoulli: Separate estimates for groups (Question 3).
   • Geometric Probability: Calculate areas for decision trees (Question 4).
   • Naive Bayes: Check for zero posterior (Question 5).
   • Perceptron: Mistake bound and convergence (Questions 6, 10).
   • SVM: Margin width, KKT conditions, and kernels (Questions 14, 16, 17).
   • K-Means: Cluster shapes with correlated data (Question 8).
   • Neural Networks: Forward pass calculations (Question 7).
   • AdaBoost: Weight updates (Question 15).

1. Common Pitfalls:

   • Misapplying conditional independence in Naive Bayes.
   • Confusing hard-margin vs. soft-margin SVM.
   • Incorrectly calculating areas for decision tree probabilities.
   • Forgetting to normalize or center data for PCA/SVM.

1. Time Management:

   • Spend ~1-2 minutes per question on average.
   • Prioritize calculations (e.g., eigenvalues, MLE) over theoretical questions.