IIT M FOUNDATION DIPLOMA AN EXAM QDF4 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 essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Concepts

1. Clustering (K-Means)

• Key Idea: Partition data into k clusters by minimizing within-cluster sum of squares (WCSS).

• Perfect Negative Correlation (Q2):

  • If features have a correlation of -1, data lies on a straight line.
  • K-means cluster centers will also lie along the same line (minimizing WCSS).
• Equation:

where $\mu_i$ is the center of cluster $C_i$.

2. Bias-Variance Tradeoff (Q3)

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

  • High bias: Linear model (Model 1: $\hat{y} = w_0 + w_1 x$).

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

  • High variance: Polynomial model (Model 2: $\hat{y} = w_1 x^2 + w_2 x + w_3$).

• Tradeoff:

  • Model 1 has higher bias, lower variance (simpler).
  • Model 2 has lower bias, higher variance (complex).

3. Logistic Regression (Q4)

• Decision Boundary: For binary classification, the boundary is where $\sigma(\mathbf{w}^T \mathbf{x} + b) = 0.5$, i.e., $\mathbf{w}^T \mathbf{x} + b = 0$.

• Angle $\theta$ of Weight Vector:

  • The weight vector $\mathbf{w} = [w_1, w_2]^T$ defines the boundary’s orientation.

  • Range for Class-1 Predictions:

    • For points $\mathbf{x}_1 = [1, \sqrt{3}]^T$ and $\mathbf{x}_2 = [-1, \sqrt{3}]^T$ to both be classified as 1, the angle $\theta$ must satisfy:

• Derivation:

  • The decision boundary must lie between the two points.
  • The angle of $\mathbf{x}_1$ is $60^\circ$, and $\mathbf{x}_2$ is $120^\circ$.
  • The weight vector must be between these angles to classify both as 1.

4. Kernel Methods (Q5)

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

  • Kernel PCA: Can reconstruct linear PCA if the kernel is linear ($k(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^T \mathbf{x}_j$).

  • Dimensionality:

    • The transformed space can have higher (even infinite) dimensions than the original.
    • Example: RBF kernel $k(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)$ maps to an infinite-dimensional space.

• Key Statements (True):

  • (C) Dimensionality of $\phi(X)$ can exceed the original feature space.
  • (D) The dimension of $\phi(X)$ can be infinite.

5. Linear Regression (Q6)

• Normal Equation: Closed-form solution for weights:

• Zero Training Loss Conditions:

  • (A) If $\mathbf{y}$ lies in the row space of $X$ (i.e., $\mathbf{y}$ is a linear combination of rows of $X$).
  • (C) If $\mathbf{y} = 0$ and $\sum x_i = 0$ (trivial solution).

6. Support Vector Machines (SVM) (Q7, Q8, Q10, Q15)

Hard-Margin SVM

• Decision Boundary: $\mathbf{w}^T \mathbf{x} + b = 0$.
• Support Vectors: Points lying on the margin boundaries $\mathbf{w}^T \mathbf{x} + b = \pm 1$.

• Linearly Separable Data (Q8):

  • If data is separable, hard-margin SVM works (no slack variables $\xi_i$).
  • Perceptron vs. SVM: Both can separate data, but their decision boundaries may differ.

Soft-Margin SVM (Q7, Q10)

• Optimization Problem:

subject to:

• Key Properties:

  • (B) If a point lies on the correct margin, its slack $\xi_i = 0$ (no "bribe" paid).
  • (D) There are 2n constraints (one for each $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i$ and one for $\xi_i \geq 0$).
  • (E) As $C \to \infty$, soft-margin SVM approaches hard-margin SVM.

• Support Vectors (Q7):

  • Points A, N are support vectors (lie on the margin).
  • Points F, A, C, I, N influence the optimal $\mathbf{w}$.

Perceptron Mistake Bound (Q15)

• Novikoff’s Theorem: For linearly separable data with margin $\gamma$, the maximum number of mistakes is:

where $R = \max \|\mathbf{x}_i\|$.

• Given:

  • $\|\mathbf{w}\| = 1$, $y_i (\mathbf{w}^T \mathbf{x}_i) \geq 0.5$, $\|\mathbf{x}_i\| \leq 2$.
  • Margin $\gamma = 0.5$, $R = 2$.
  • Maximum mistakes: $\left( \frac{2}{0.5} \right)^2 = 16$.

7. Maximum Likelihood Estimation (MLE) (Q12)

• Bernoulli MLE: For binary data, the MLE for $p$ is the sample mean:

• Grouped Data:

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

8. Decision Trees (Q13)

• Probability Calculation:

  • The decision tree classifies a point as 1 if:

    1. $x_1 \geq 0.5$ (probability = 0.5), or
    2. $x_1 < 0.5$ and $x_2 \leq 0.5$ (probability = 0.5 * 0.5 = 0.25).
  • Total probability: $0.5 + 0.25 = 0.75$.

9. Naive Bayes (Q14)

• Conditional Independence:

• Given Data:

  • $p(y=1) = \frac{3}{6} = 0.5$, $p(y=0) = 0.5$.

  • For $\mathbf{x}_{test} = [0, 1, 0]^T$:

    • $p(y=0 | \mathbf{x}) \propto p(y=0) \cdot p(x_1=0 | y=0) \cdot p(x_2=1 | y=0) \cdot p(x_3=0 | y=0)$.

    • From the table:

      • $p(x_1=0 | y=0) = \frac{2}{3}$,
      • $p(x_2=1 | y=0) = \frac{2}{3}$,
      • $p(x_3=0 | y=0) = \frac{1}{3}$.
    • $p(y=0 | \mathbf{x}) \propto 0.5 \cdot \frac{2}{3} \cdot \frac{2}{3} \cdot \frac{1}{3} = \frac{2}{27}$.
    • Similarly, $p(y=1 | \mathbf{x}) \propto \frac{1}{9}$.
  • Final Probability: $p(y=0 | \mathbf{x}) = \frac{2/27}{2/27 + 1/9} = \frac{2}{5} = 0.4$.
  • (Note: The answer key says 0, but calculations suggest 0.4. Verify data.)

10. AdaBoost (Q9, Q16)

• Weight Update Rule:

  • For misclassified points, increase weights:

where $\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$.

• Equal Weights (Q9):

  • After the first iteration, misclassified points get higher weights.
  • For the second stump, points with equal weights are those that were correctly classified in the first iteration.
  • Example: Points $[1, 1]^T$ and $[1, 4]^T$ (both misclassified equally).

• Weight Calculation (Q16):

  • Initial weights: $D_1(i) = \frac{1}{3}$.

  • After first iteration:

    • $x_1$: Misclassified (weight increases to $\frac{1}{2}$).
    • $x_2$: Correctly classified (weight decreases to $\frac{1}{4}$).
    • $x_3$: Misclassified (weight increases to $\frac{1}{4}$).

11. Neural Networks (Q17)

• Forward Pass:

  • Hidden layer neuron output:

where $\sigma$ is the sigmoid function.

• For Neuron 1:

12. Eigenvalues & Covariance (Q11)

• Variance from Eigenvalues:

  • Total variance = sum of eigenvalues of the covariance matrix.
  • Solve the system:

• Solution: $\lambda_1 = 1$, $\lambda_2 = 2$, $\lambda_3 = 2$.
• Total Variance: $1 + 2 + 2 = 5$.

Graph 2: Clustering & Dimensionality Reduction

Graph 3: Bias-Variance Tradeoff

Graph 4: SVM Components

Graph 5: Probabilistic Models