IIT M FOUNDATION DIPLOMA AN EXAM QDF3 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 core topics, concepts, principles, and equations for the Diploma-Level Machine Learning Techniques exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Key Concepts

1. Clustering (K-Means)

• Goal: Partition data into k clusters by minimizing Within-Cluster Sum of Squares (WCSS).

• Key Idea:

  • For perfect negative correlation (r = -1), data lies on a straight line.
  • Optimal cluster centers for k=3 will also lie on the same line (minimizes WCSS).
• Equation:

where $\mu_i$ = centroid of cluster $C_i$.

2. Bias-Variance Tradeoff

• Bias: Error due to overly simplistic assumptions (underfitting).

  • High bias: Linear models (e.g., $\hat{y} = w_0 + w_1 x$).

• Variance: Error due to excessive complexity (overfitting).

  • High variance: Polynomial/nonlinear models (e.g., $\hat{y} = w_1 x^2 + w_2 x + w_3$).

• Tradeoff:

  • Model 1 (Linear) → Higher bias, lower variance.
  • Model 2 (Quadratic) → Lower bias, higher variance.

3. Logistic Regression & Decision Boundaries

• Sigmoid Function:

• Decision Boundary: Points where $\sigma(z) = 0.5$ (i.e., $\mathbf{w}^T \mathbf{x} + b = 0$).

• Angle $\theta$ of Weight Vector:

  • For points $\mathbf{x}_1, \mathbf{x}_2$ to be class-1, the weight vector $\mathbf{w}$ must satisfy:

• Range for $\theta$: $30^\circ < \theta < 150^\circ$ (derived from geometry of given points).

4. Kernel Methods & Kernel PCA

• Kernel Trick: Maps data to higher-dimensional space via $\phi(\mathbf{x})$.

  • Kernel Function: $k(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)$.

• Key Properties:

  • Dimensionality of $\phi(\mathbf{x})$ can be infinite (e.g., RBF kernel).
  • Kernel PCA can reconstruct linear PCA if $k(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^T \mathbf{x}_j$ (linear kernel).

• Common Kernels:

  • Linear: $k(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^T \mathbf{x}_j$
  • Polynomial: $k(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i^T \mathbf{x}_j + c)^d$
  • RBF: $k(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)$

5. Linear Regression & Normal Equation

• Model: $\hat{y} = \mathbf{w}^T \mathbf{x}$.
• Loss (Squared Error):

• Normal Equation (Closed-form solution):

• Zero Training Loss:

  • If $\mathbf{y}$ lies in the row space of $\mathbf{X}$ (i.e., $\mathbf{y} = \mathbf{X}^T \mathbf{w}$ for some $\mathbf{w}$).
  • If all $y_i = 0$ and $\sum x_i = 0$ (trivial solution).

6. Support Vector Machines (SVM)

Hard-Margin SVM

• Objective: Maximize margin $\frac{2}{\|\mathbf{w}\|}$.
• Constraints: $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1$.
• Decision Boundary: $\mathbf{w}^T \mathbf{x} + b = 0$.
• Support Vectors: Points where $y_i (\mathbf{w}^T \mathbf{x}_i + b) = 1$.

Soft-Margin SVM

• Objective:

• Constraints:

• Key Points:

  • $C$: Tradeoff between margin width and misclassification.
  • As $C \to \infty$, soft-margin SVM → hard-margin SVM.

  • Dual Problem: Introduces Lagrange multipliers $\alpha_i$.

    • If $\alpha_i^* > 0$, $\mathbf{x}_i$ is a support vector.
    • If $\xi_i^* > 0$, point is misclassified or inside margin.

7. Principal Component Analysis (PCA)

• Covariance Matrix: $\mathbf{C} = \frac{1}{n} \mathbf{X} \mathbf{X}^T$.
• Eigenvalues ($\lambda_i$): Represent variance along principal components.
• Total Variance:

• Example: For 3 eigenvalues satisfying:

Solve the system to find $\lambda_i$, then sum for total variance.

8. Maximum Likelihood Estimation (MLE)

• Bernoulli Distribution:

• Likelihood for Grouped Data:

• MLE Estimates:

• Example:

  • Group 1: $\{0, 1, 1, 0, 1\}$ → $\hat{p}_1 = 3/5 = 0.6$.
  • Group 2: $\{1, 0, 1, 0, 1\}$ → $\hat{p}_2 = 3/5 = 0.6$.

9. Decision Trees & Probability

• Probability Calculation:

  • For a uniform distribution over the unit square $[0,1]^2$, the probability of a region is its area.

  • Example Tree:

    if x1 < 0.5:
        if x2 > 0.5: class 0
        else: class 1
    else: class 1

  • Class-1 Regions:

    1. $x1 \geq 0.5$ (area = 0.5).
    2. $x1 < 0.5$ and $x2 \leq 0.5$ (area = 0.25).
  • Total Probability: $0.5 + 0.25 = 0.75$.

10. AdaBoost & Weak Learners

• Algorithm:

  1. Initialize weights $D_1(i) = 1/n$.

  2. For $t = 1$ to $T$:

     • Train weak learner $h_t$ to minimize weighted error:

• Compute $\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$.
• Update weights:

where $Z_t$ is a normalization factor.

• Key Points:

  • Misclassified points get higher weights in the next iteration.
  • Example: If $x_2$ is correctly classified, its weight decreases.

11. Neural Networks (Forward Pass)

• Sigmoid Activation:

• Hidden Layer Output:

• Example:

  • Neuron 1: $z_1 = 0.5 \cdot 0.6 + (-0.2) \cdot 0.3 + 0.8 \cdot 0.8 + 0.1 = 0.3 + (-0.06) + 0.64 + 0.1 = 1.04$
  • Output: $a_1 = \sigma(1.04) \approx 0.74$ (between 0.70 and 0.80).

Graph 2: Unsupervised Learning & Dimensionality Reduction

Graph 3: Probability & Estimation