IIT M DEGREE AN EXAM QDB3 31 Aug 2025 - 31 Aug 2025

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 & Key Concepts

1. Perceptron Algorithm

• Concept: Linear classifier for binary classification. Updates weights iteratively when misclassification occurs.

• Key Equations:

  • Update rule: $w \leftarrow w + \eta \cdot y_i \cdot x_i$ (if misclassified).
  • Decision boundary: $w^T x + b = 0$.
• Convergence: Guaranteed if data is linearly separable (Novikoff’s theorem).
• Mistake Bound: Depends on margin and radius of data.
• Scaling: If data is scaled (e.g., $D_2 = 2D_1$), convergence is preserved, but mistake bound may change.

2. Support Vector Machines (SVM)

Hard-Margin SVM

• Concept: Maximizes the margin between classes. Only support vectors (points closest to the boundary) matter.

• Key Equations:

  • Primal problem:

• Dual problem (Lagrangian):

• Support Vectors: Points where $\alpha_i > 0$.

Soft-Margin SVM

• Concept: Allows misclassification via slack variables $\xi_i$.

• Key Equations:

  • Primal:

• Effect of $C$:

  • $C = 0$: No penalty for misclassification (trivial solution, no support vectors).
  • $C \to \infty$: Hard-margin behavior (all points become support vectors if separable).

Kernel SVM

• Concept: Maps data to higher dimensions using $\phi(x)$. Kernel trick avoids explicit computation of $\phi$.

• Key Equations:

  • Kernel function: $k(x_i, x_j) = \phi(x_i)^T \phi(x_j)$.

  • Example kernels:

    • Linear: $k(x_i, x_j) = x_i^T x_j$.
    • Polynomial: $k(x_i, x_j) = (x_i^T x_j + c)^d$.
  • Kernel in Q3:

Corresponding $\phi$:

3. K-Means Clustering

• Concept: Partitions data into $K$ clusters by minimizing within-cluster variance.

• Key Equations:

  • Objective:

where $z_i$ is the cluster assignment for $x_i$, and $\mu_{z_i}$ is the cluster mean.

• Greedy Initialization (K-Means++):

  1. Pick first center uniformly at random.
  2. Pick next center as the point farthest from existing centers.
• Convergence: Guaranteed to local optimum (not necessarily global).

4. Neural Networks

• Concept: Stacked layers of neurons with activation functions.

• Key Components:

  • ReLU: $\text{ReLU}(x) = \max(0, x)$.
  • Sigmoid: $\sigma(x) = \frac{1}{1 + e^{-x}}$.

• Forward Propagation:

  • Hidden layer: $h = \text{ReLU}(W^{(1)} x + b^{(1)})$.
  • Output: $\hat{y} = \sigma(W^{(out)} h + b^{(out)})$.

• Example (Q6):

  • Input: $x = [1, 1]^T$.
  • Weights:

• Output probability: $P(y=1) = \sigma(1 \cdot h_1 + 2 \cdot h_2)$.

5. Decision Trees

• Concept: Recursively splits data based on feature thresholds.

• Key Properties:

  • Overfitting: Mitigated by limiting depth, pruning, or requiring minimum samples per leaf.
  • Feature Importance: Not affected by feature order (unlike some other models).
  • Handling Data Types: Works for both numerical and categorical features.
  • Sensitivity: Small perturbations can change tree structure (high variance).

6. Logistic Regression

• Concept: Models probability $P(y=1|x)$ using sigmoid function.
• Key Equation:

• Example (Q12):

  • Model: $\hat{p} = \frac{1}{1 + e^{-(0.4 x_1 + 0.1 x_2)}}$.
  • Solve for $x_1$ when $\hat{p} = 0.7$ and $x_2 = 4$:

7. Random Forest

• Concept: Ensemble of decision trees. Predicts by averaging probabilities (classification) or mean (regression).

• Key Properties:

  • Reduces variance compared to single trees.

  • Example (Q13):

    • Tree probabilities: $P(+1) = [0.7, 0.4, 0.8]$, $P(-1) = [0.3, 0.6, 0.2]$.
    • Average $P(+1) = 0.633$, so predict class $+1$.

8. Bayesian Methods

Maximum A Posteriori (MAP) Estimation

• Concept: Estimates parameter $\theta$ by maximizing posterior $P(\theta | \text{data})$.
• Key Equation:

• Example (Q14):

  • Likelihood: $\text{Exponential}(\lambda)$, prior: $\lambda \sim \text{Uniform}(0, 2)$.
  • Posterior: $P(\lambda | \text{data}) \propto \lambda^n e^{-\lambda \sum x_i}$.
  • MAP estimate: Mode of posterior (solve $\frac{d}{d\lambda} \log P(\lambda | \text{data}) = 0$).

Naive Bayes

• Concept: Assumes features are conditionally independent given the class.
• Key Equation:

• Parameter Count:

  • For binary features $f_1, f_2, f_3$ and binary class $y$:

    • $P(y)$: 1 parameter (since $P(y=1) + P(y=0) = 1$).
    • $P(f_i | y)$: 2 parameters per feature per class (e.g., $P(f_i=1|y=0)$ and $P(f_i=1|y=1)$).
    • Total: $1 + 3 \times 2 = 7$ parameters.
• Laplace Smoothing: Adds pseudo-counts to avoid zero probabilities.

9. Linear Regression & Ridge Regression

• Linear Regression (ML Estimate):

  • Key Equation:

• Ridge Regression:

  • Key Equation:

• Effect of $\lambda$:

  • $\lambda \uparrow$: Coefficients shrink toward zero (reduces overfitting).
  • $\lambda \downarrow$: Coefficients approach $\hat{w}_{ML}$.

10. Principal Component Analysis (PCA)

• Concept: Linear dimensionality reduction via eigen decomposition of covariance matrix.

• Key Equations:

  • Covariance matrix: $C = \frac{1}{n} X^T X$.
  • Eigenvalue equation: $C v_i = \lambda_i v_i$.
  • Total Variance: Sum of eigenvalues $\sum_i \lambda_i$.

• Example (Q11):

  • Given $2\lambda_1 - \lambda_2 + \lambda_3 = 8$, $\lambda_1 + 2\lambda_2 - \lambda_3 = 5$, and $\lambda_1 - \lambda_3 = 3$.
  • Solve to get $\lambda_1 = 4$, $\lambda_2 = 2$, $\lambda_3 = 1$.
  • Total variance: $4 + 2 + 1 = 7$ (but answer was 6; likely a typo in the problem).

Graph 2: Clustering & Dimensionality Reduction

Graph 3: Bayesian Methods

Graph 4: SVM Components

Graph 5: Neural Network Architecture (Q6)