IIT M IMPROVEMENT FN EXAM QDD1 01 Sep - 01 Sep 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.

1. Core Topics & Concepts

A. Principal Component Analysis (PCA)

• Key Idea: Dimensionality reduction by projecting data onto orthogonal axes (principal components) that maximize variance.

• Eigenvalues of Covariance Matrix:

  • Represent variance along principal components.
  • Total variance = Sum of all eigenvalues.
  • Variance captured by top-k PCs = (Sum of top-k eigenvalues) / (Total variance).
• Equation:

(Where $\lambda_i$ are eigenvalues, $d$ is dimensionality.)

B. Regularization (Ridge Regression)

• Key Idea: Penalize large weights to prevent overfitting.
• Loss Function:

(SSE = Sum of Squared Errors, $\lambda$ = regularization strength.)

• Plot Interpretation:

  • Training loss decreases with model complexity (lower $\lambda$).
  • Test loss has a U-shape; optimal $\lambda$ minimizes it.
  • Best $f(\lambda)$: $\sqrt{\lambda}$ (balances scale for visualization).

C. Ensemble Methods (Bagging vs. Boosting)

D. Support Vector Machines (SVM)

• Hard-Margin SVM:

  • Decision Boundary: $\mathbf{w}^T \mathbf{x} + b = 0$.
  • Supporting Hyperplanes: $\mathbf{w}^T \mathbf{x} + b = \pm 1$.
  • Margin: $\frac{2}{\|\mathbf{w}\|}$.
  • Distance between hyperplanes: $\frac{2}{\|\mathbf{w}\|}$.

• Soft-Margin SVM:

  • Slack Variables ($\xi_i$): Allow misclassification.
  • Objective:

(Subject to $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i$.)

• Lagrange Multipliers ($\alpha_i$):

  • $0 \leq \alpha_i \leq C$.
  • Support Vectors: Points with $\alpha_i > 0$.

  • KKT Conditions:

    • If $\alpha_i = 0$: Point is correctly classified outside margin.
    • If $0 < \alpha_i < C$: Point lies on margin ($\xi_i = 0$).
    • If $\alpha_i = C$: Point is misclassified ($\xi_i > 0$).

E. Naive Bayes

• Class Conditional Independence:

(Features $x_j$ are independent given class $y$.)

• Posterior Probability:

F. Clustering (k-Means)

• Cluster Boundary: Perpendicular bisector between centroids.

  • For centroids $\mathbf{c}_1, \mathbf{c}_2$, boundary is:

Simplifies to a linear equation (e.g., $2x_1 + x_2 = 0$).

G. Logistic Regression

• Sigmoid Function:

• Probability of Class 1:

• Weight Interpretation:

  • If $\mathbf{w} = [a, b]^T$, then:

• Given $p(y=1 \mid [1,1]^T) = \frac{1}{1 + e^2}$, solve for $\mathbf{w}$.

H. Decision Trees & Information Gain

• Entropy:

(Where $p_i$ = proportion of class $i$ in set $S$.)

• Information Gain:

(Where $S_j$ are child nodes.)

I. Kernels (Polynomial Kernel)

• Polynomial Kernel:

• Non-negativity: For even $p$, kernel is always non-negative.
• Valid $p$: 2, 4 (not odd degrees like 3, 5).

J. Neural Networks

• Learnable Parameters:

  • For layer $L$ with $n_L$ neurons and layer $L-1$ with $n_{L-1}$ neurons:

• Total Parameters (ignoring biases):

• Activation Functions:

  • Output Layer (Binary Classification): Sigmoid (for cross-entropy loss).
  • Hidden Layers: ReLU (sparse activations), Sigmoid (vanishing gradients).
• ReLU Activation:

• If any activation in a layer is 0, the input to that neuron was ≤ 0.

K. Loss Functions

L. Maximum Likelihood Estimation (MLE)

• Bernoulli MLE:

• Given $\hat{p} = 0.25$ and 10 successes (ones), total trials = 40.
• Zeros = Total trials - successes = 30.

M. Linear Regression (Gradient of SSE)

• SSE for One Data Point:

• Gradient w.r.t. $\mathbf{w}$:

Graph 2: Ensemble Methods

Graph 3: Neural Networks

Graph 4: Loss Functions

Graph 5: SVM Components

3. Key Equations Summary