IIT M DIPLOMA ET1 EXAM QPD1 S2 30 Apr 2023 - 30 Apr 2023

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. Kernel Methods & Feature Transformations

• Kernel Trick: Maps data to higher dimensions implicitly (e.g., polynomial kernels).
• Kernel Function: $k(\mathbf{x}, \mathbf{y}) = \phi(\mathbf{x})^T \phi(\mathbf{y})$ Example (Q2): $k([x_1, x_2], [y_1, y_2]) = 1 + x_1 y_1 + x_1^2 y_1^2 + x_2^2 y_2^2$ Corresponding Feature Map (Q2): $\phi([x_1, x_2]) = [1, x_1, x_1^2, x_2^2]$

2. Bayesian Estimation

• Prior/Posterior Distributions:

  • Prior: $p(\theta)$ (e.g., Beta distribution for Bernoulli data).
  • Posterior: $p(\theta | \text{data}) \propto p(\text{data} | \theta) \cdot p(\theta)$.
• Bernoulli Likelihood: $p(\text{data} | p) = p^{\text{\# successes}} (1-p)^{\text{\# failures}}$.
• Beta-Bernoulli Conjugacy: Posterior is Beta with updated parameters: $\alpha_{\text{post}} = \alpha_{\text{prior}} + \text{\# successes}$, $\beta_{\text{post}} = \beta_{\text{prior}} + \text{\# failures}$.
• Key Insight (Q3): If posterior mode > prior mode, likely more successes (e.g., 5 successes in 6 trials).

3. Regularization (LASSO, Ridge)

• LASSO (L1 Regularization): $\min_{\mathbf{w}} \|\mathbf{y} - X\mathbf{w}\|_2^2 + \lambda \|\mathbf{w}\|_1$.

  • Sparsity: Higher $\lambda$ → more weights set to 0 (Q4).

• Ridge (L2 Regularization): $\min_{\mathbf{w}} \|\mathbf{y} - X\mathbf{w}\|_2^2 + \lambda \|\mathbf{w}\|_2^2$.

  • Smooths weights but doesn’t enforce sparsity.

4. Decision Trees & Information Gain

• Information Gain (IG): $IG = H(\text{parent}) - \sum_{\text{children}} \frac{N_i}{N} H(\text{child}_i)$, where $H$ is entropy.
• Entropy: $H(S) = -\sum_{i} p_i \log_2 p_i$.
• Key Insight (Q5): If $IG = 0$, children’s entropy = parent’s entropy. If one child’s entropy = parent’s entropy, the other must also equal it (symmetry).

5. Perceptron & Linear Separability

• Perceptron Update Rule: $\mathbf{w}_{t+1} = \mathbf{w}_t + \eta \cdot y_i \mathbf{x}_i$ if misclassified.
• Convergence: Converges only if data is linearly separable (Q6). If not separable, weights oscillate indefinitely.
• Weight Update Analysis (Q11): Given $\mathbf{w}^t$ and $\mathbf{w}^{t+1}$, solve for $\mathbf{x}_i$ and $y_i$ such that: $\mathbf{w}^{t+1} = \mathbf{w}^t + y_i \mathbf{x}_i$.

6. Support Vector Machines (SVM)

Hard-Margin SVM

• Primal Problem: $\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$ s.t. $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1$.
• Dual Problem: $\max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j$ s.t. $\alpha_i \geq 0$, $\sum \alpha_i y_i = 0$.

• Key Insights:

  • Optimal $\mathbf{w}^* = \sum \alpha_i^* y_i \mathbf{x}_i$ (Q8).
  • Support vectors have $\alpha_i^* > 0$ (Q9).
  • If $\alpha_i^* = 0$, point is correctly classified with margin > 1 (Q14).

Soft-Margin SVM

• Primal with Slack: $\min_{\mathbf{w}, b, \xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum \xi_i$ s.t. $y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i$, $\xi_i \geq 0$.
• Dual: $\max_{\alpha} \sum \alpha_i - \frac{1}{2} \sum \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j$ s.t. $0 \leq \alpha_i \leq C$, $\sum \alpha_i y_i = 0$.

• KKT Conditions:

  • If $\alpha_i^* = 0$, point is correctly classified or $\xi_i^* = 0$ (Q14).

7. Linear Regression & Loss Functions

• Squared Loss: $L(\mathbf{w}) = \|\mathbf{y} - X\mathbf{w}\|_2^2$.

• Impact of Features/Regularization (Q10):

  • More features ($d$): Can reduce training loss (but risk overfitting).
  • More data ($n$): May not reduce training loss (focuses on generalization).
  • Regularization (L1/L2): Increases training loss (penalizes complexity).
  • Learning rate: Smaller rates may refine convergence but don’t directly reduce loss.

8. Loss Function Properties (Q12)

• Key Comparisons (Q12):

  • For $y \mathbf{w}^T \mathbf{x} = 1$: Logistic loss > Hinge loss (hinge = 0).
  • Squared loss grows quadratically for large $y \mathbf{w}^T \mathbf{x}$.

9. Training vs. Validation Curves (Q13)

• Training Loss: Decreases monotonically with training (optimization).
• Validation Loss: Decreases initially, then may increase (overfitting).

• Identification:

  • Curve 1 (lower, decreasing): Training.
  • Curve 2 (higher, U-shaped): Validation.

10. PCA (Principal Component Analysis)

• Steps:

  1. Center data: $\mathbf{x}_i \leftarrow \mathbf{x}_i - \bar{\mathbf{x}}$.
  2. Compute covariance matrix $\Sigma = \frac{1}{n} X^T X$.
  3. Eigenvalue decomposition: $\Sigma = V \Lambda V^T$.
  4. Project onto top-$k$ eigenvectors (principal components).
• Variance Explained (Q16): $\text{Total variance} = \sum \lambda_i$. $\text{Variance of first } k \text{ PCs} = \sum_{i=1}^k \lambda_i$. Given $\lambda^5, \lambda^4, \lambda^3, \lambda^2, \lambda, 1$ and top-3 variance = 88.88%: $\frac{\lambda^5 + \lambda^4 + \lambda^3}{\lambda^5 + \lambda^4 + \lambda^3 + \lambda^2 + \lambda + 1} = 0.8888$. Solve for $\lambda \approx 2$.

11. K-Means Clustering

• Algorithm:

  1. Initialize centroids $\mu_1, \mu_2, \dots, \mu_K$.
  2. Assign points to nearest centroid (Euclidean distance).
  3. Recompute centroids as mean of assigned points.
  4. Repeat until convergence.
• Key Insight (Q17): Final centroids may coincide with initial centroids if points are symmetrically distributed.

12. Logistic Regression

• Sigmoid Function: $\sigma(\mathbf{w}^T \mathbf{x}) = \frac{1}{1 + e^{-\mathbf{w}^T \mathbf{x}}}$.
• Prediction Error (Q18): $|\sigma_i - y_i|$: Absolute difference between predicted probability and true label.
• Geometric Interpretation: Points farther from the decision boundary have $\sigma$ closer to 0 or 1.

13. Neural Networks

• Weight Calculation (Q19): For a fully connected network with layers $L_1, L_2, \dots, L_n$, total weights: $\sum_{i=1}^{n-1} \text{dim}(L_i) \times \text{dim}(L_{i+1})$. Example: $5 \rightarrow 30 \rightarrow 10 \rightarrow 1$: $5 \times 30 + 30 \times 10 + 10 \times 1 = 460$.

14. Gaussian Naive Bayes

• Assumptions:

  • Features are conditionally independent given the class.
  • Likelihood is Gaussian: $p(\mathbf{x}|y) = \mathcal{N}(\mu_y, \Sigma_y)$.

• Parameters (Q20–Q22):

  • $p$: Prior probability of class 1.
  • $\mu_y$: Mean of features for class $y$.
  • $\hat{\mu}_1$: Sample mean of class 1 features.

15. AdaBoost

• Weighted Misclassification Error (Q23–Q25): $\epsilon_t = \sum_{i=1}^n D_t(i) \mathbb{1}[h_t(\mathbf{x}_i) \neq y_i]$.
• Weight Update: $D_{t+1}(i) = D_t(i) \cdot e^{\alpha_t \mathbb{1}[h_t(\mathbf{x}_i) \neq y_i]}$, where $\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$.
• Key Insight: Misclassified points get higher weights in next iteration.

16. Ensemble Methods (Bagging, Random Forest)

• Bagging (Q15):

  • Trains multiple models on bootstrapped samples.
  • Reduces variance (helps if base estimators are high-variance/low-bias).
  • If estimators are identical, bagging offers no benefit.

• Random Forest:

  • Extends bagging by random feature subsets.
  • Parallelizable (independent trees).

Graph 2: Bayesian vs. Frequentist Methods

Graph 3: Regularization & Loss Functions

Graph 4: Dimensionality Reduction

Graph 5: Ensemble Methods