Unit 3 Cheat Sheet: Classification & Instance-Based Learning

Course - Machine Learning Algorithms (21CSC555J)
Assessment - Continuous Test 2 (CT-2)
Scope - Naïve Bayes Spam Filtering, Classifier Selection (SVM vs KNN vs NB), and K-Nearest Neighbors
Primary Reference - Unit 3 Full Exam Solutions

---

1. Exam Overview & Fast Mapping (40 Marks)

Question	Algorithm & Topic	Core Numerical Shortcut	Essential Theory Keywords
Q1.a (15M)	Naïve Bayes: Spam Filtering	$P(\text{Win} \mid \text{NotSpam}) = 0.0 \implies \mathcal{L}(\text{NotSpam}) = 0.0 \implies \mathbf{100\% \text{ Spam}}$	Class-conditional independence: $P(X_1, X_2 \mid C) = \prod P(X_i \mid C)$
Q1.b (5M)	Classifier Trade-offs: Medical Data	Mnemonic S-K-N: SVM for Shapes, KNN Killed by noise, NB for Nulls	Infinite-dimensional Hilbert space, Curse of dimensionality, Marginalization
Q2 (20M)	KNN ($K=3$): Customer Spending	Distances to $(40, 15)$: C3 & C5 tie at $11.18$, C4 at $16.55 \implies \mathbf{2 \text{ High vs } 1 \text{ Low}}$	Scale dominance, Overfitting ($K=1$) vs Underfitting ($K \to N$), Recommenders

---

2. Question 1.a: Naïve Bayes Spam Filtering (15 Marks)

Step 1: Prior Probabilities (1 Mark)

• Total $N = 4 \implies N_{\text{Spam}} = 2, \; N_{\text{NotSpam}} = 2$
• $P(\text{Spam}) = \frac{2}{4} = \mathbf{0.5}, \qquad P(\text{NotSpam}) = \frac{2}{4} = \mathbf{0.5}$

Step 2: Conditional Probabilities Table (5 Marks)

$P(X_i = x \mid C = c) = \frac{\text{Count}(X_i = x \text{ and } C = c)}{\text{Count}(C = c)}$

Feature ($X_i$)	Value	$P(X_i \mid \text{Spam})$	$P(X_i \mid \text{NotSpam})$	Exam Memory Note
Contains 'Offer'	Yes	$\frac{1}{2} = \mathbf{0.5}$	$\frac{1}{2} = \mathbf{0.5}$	Balanced across both classes
Contains 'Win'	Yes	$\frac{2}{2} = \mathbf{1.0}$	$\frac{0}{2} = \mathbf{0.0}$	Zero likelihood for NotSpam!

Step 3: Joint Likelihoods for Query: Offer=Yes, Win=Yes (5 Marks)

• Class Spam: $\mathcal{L}(\text{Spam}) = P(\text{Offer} \mid \text{Spam}) \times P(\text{Win} \mid \text{Spam}) \times P(\text{Spam}) = 0.5 \times 1.0 \times 0.5 = \mathbf{0.25}$

• Class Not Spam: $\mathcal{L}(\text{NotSpam}) = P(\text{Offer} \mid \text{NotSpam}) \times P(\text{Win} \mid \text{NotSpam}) \times P(\text{NotSpam}) = 0.5 \times 0.0 \times 0.5 = \mathbf{0.0}$

• Evidence & Posterior Normalization: $P(\mathbf{X}) = 0.25 + 0.0 = 0.25$ $P(\text{Spam} \mid \mathbf{X}) = \frac{0.25}{0.25} = \mathbf{1.0 \quad (100\%)}, \qquad P(\text{NotSpam} \mid \mathbf{X}) = \frac{0.0}{0.25} = \mathbf{0.0 \quad (0\%)}$

Step 4: Prediction & Theory (5 Marks)

• Prediction: By MAP rule ($\arg\max$), since $1.0 > 0.0$, predicted class is Spam.
• Independence Assumption: Assumes features are mutually conditionally independent given the class label: $P(X_1, X_2 \mid C) = P(X_1 \mid C) \cdot P(X_2 \mid C)$
• Why "Naïve": Keywords correlate in real natural language (promotional words like "Offer" and "Win" co-occur).
• Why It Works: Accurate classification only requires correct ranking ($\arg\max$), not calibrated probabilities. It reduces parameter complexity from $O(2^d)$ to $O(d)$.

---

3. Question 1.b: Classifier Trade-offs (5 Marks)

Remember the "S - K - N" rule:

• (a) Non-Linear Boundaries (2M): SVM with RBF Kernel

  • Infinite-Dimensional Mapping: Projects inputs into infinite-dimensional Hilbert space via $K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma \|\mathbf{x} - \mathbf{x}'\|^2)$.
  • Smooth Decision Surfaces: A linear hyperplane in this space maps to smooth, continuous non-linear contours.

• (b) Most Sensitive to Irrelevant Features (1.5M): KNN ($k=5$)

  • Uniform Distance Metric: Calculates Euclidean distance equally across all $D$ features: $d = \sqrt{\sum_{j=1}^D (x_j - y_j)^2}$.
  • Curse of Dimensionality: Irrelevant dimensions inject random noise, collapsing distance contrast ($d_{\max} \approx d_{\min}$).

• (c) Best for Small Data + Missing Values (1.5M): Gaussian Naïve Bayes

  • Parameter Efficiency: Estimates only $2$ parameters per feature ($\mu, \sigma^2$), resisting overfitting on small samples.
  • Native Missing Value Handling: Computes likelihoods by simply omitting missing attributes from conditional product: $P = \prod_{j \in \text{obs}} P(x_j \mid C)$.

---

4. Question 2: KNN Customer Spending (20 Marks)

• Query Point: $\mathbf{X}_{\text{new}} = (\text{Income}=40, \, \text{Spending}=15)$
• Euclidean Distance Formula: $d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} = \sqrt{(40 - x_{i1})^2 + (15 - x_{i2})^2}$
• Manhattan Distance Formula: $d_M = \lvert x_2 - x_1 \rvert + \lvert y_2 - y_1 \rvert = \lvert 40 - x_{i1} \rvert + \lvert 15 - x_{i2} \rvert$

Arithmetic Accelerator Table (Distances to All Points)

Customer	Class	Income ($x_1$)	Spending ($x_2$)	Euclidean Distance ($d_E$)	Manhattan Distance ($d_M$)
C1	Low	20	5	$\sqrt{500} \approx \mathbf{22.36}$	$\mathbf{30}$
C2	Low	25	7	$\sqrt{289} = \mathbf{17.00}$ (Exact!)	$\mathbf{23}$
C3	High	50	20	$\sqrt{125} \approx \mathbf{11.18}$	$\mathbf{15}$
C4	High	55	22	$\sqrt{274} \approx \mathbf{16.55}$	$\mathbf{22}$
C5	Low	30	10	$\sqrt{125} \approx \mathbf{11.18}$	$\mathbf{15}$

note

Speed Memory Hooks

• $15^2 + 8^2 = 225 + 64 = 289 = 17^2 \implies$ C2 has exact integer distance 17.00.
• $10^2 + 5^2 = 125 \implies$ C3 and C5 have identical distance 11.18 (Tie for Rank 1 & 2).

Ranking & Majority Voting ($K=3$)

1. Top-3 Nearest Neighbors:
   • Rank 1 (Tie): C3 ($d_E \approx 11.18$) $\implies$ High
   • Rank 2 (Tie): C5 ($d_E \approx 11.18$) $\implies$ Low
   • Rank 3: C4 ($d_E \approx 16.55$) $\implies$ High
2. Majority Voting: $2 \text{ High}$ vs $1 \text{ Low} \implies$ Predicted class: High Spender ($P = 2/3 \approx 66.7\%$).
3. Manhattan Comparison: Sorted distances are C3 ($15$), C5 ($15$), C4 ($22$) $\implies$ Same top-3 set $\{C3, C5, C4\} \implies$ Prediction is topologically invariant.

Theory Scoring Points

• Feature Scaling (1.5 Marks): Features with larger numeric ranges dominate Euclidean distances, collapsing multidimensional space into a 1D space. Fix with Min-Max Normalization ($[0, 1]$) or Z-Score Standardization.
• Choice of $K$ (1.5 Marks):
  • $K = 1$: Low Bias, High Variance $\implies$ captures noise and outliers (Overfitting).
  • $K \to N$: High Bias, Low Variance $\implies$ overly smooth, predicts majority class (Underfitting).
  • Rule: Choose odd $K$ to prevent ties ($K \approx \sqrt{N}$).
• Real-World Application (2 Marks): Recommender Systems / Collaborative Filtering (e.g., Amazon, Spotify). Preferred because lazy learning requires zero offline training time (instant profile ingestion) and intuitive neighborhood matching.

---

5. Golden Numbers & Exam Traps

Quick Number Reference

• Q1.a: Likelihood Spam $= 0.25$, Likelihood NotSpam $= 0.0$, Posteriors $= 100\%$ Spam vs $0\%$ NotSpam.
• Q2: C3 & C5 $= 11.18$ (Manhattan $15$), C4 $= 16.55$ (Manhattan $22$), C2 $= 17.00$ (Manhattan $23$), C1 $= 22.36$ (Manhattan $30$).

danger

Avoid These Common Traps

1. Forgetting Prior $P(C)$ in Bayes: Don't just multiply feature likelihoods; always include $P(\text{Spam}) = 0.5$.
2. Missing Normalization: Always show $P(\text{Spam} \mid \mathbf{X}) = \frac{0.25}{0.25} = 1.0$ so the posterior sums to $1$.
3. Omitting the Square Root in KNN: $\Delta^2 = 125 \implies d = \sqrt{125} \approx 11.18$.
4. $K=1$ is NOT High Bias: Remember: $K=1$ is complex and sensitive to noise $\implies$ Low Bias, High Variance.