SVM, Naive Bayes & Probabilistic Models

Q1 (12 marks)

(a) The signed distance from point $\mathbf{x}_i$ to hyperplane $\mathbf{w}^\top\mathbf{x}+b=0$ is $r = \frac{\mathbf{w}^\top\mathbf{x}_i + b}{\lVert\mathbf{w}\rVert}$. Multiplying by label $y_i\in\{-1,+1\}$ gives the (positive for correct) geometric margin $\gamma_i = \frac{y_i(\mathbf{w}^\top\mathbf{x}_i+b)}{\lVert\mathbf{w}\rVert}$. (1 for signed distance formula, 1 for projection reasoning, 1 for $y_i$ factor)

(b) With canonical scaling, closest points (support vectors) satisfy $y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1$. The distance of a support vector = $\frac{1}{\lVert\mathbf{w}\rVert}$. The margin is bounded by the two nearest classes, one on each side, so total width $=\frac{2}{\lVert\mathbf{w}\rVert}$. (1 canonical constraint, 1 single-side distance, 1 doubling)

(c) $\min_{\mathbf{w},b}\ \tfrac{1}{2}\lVert\mathbf{w}\rVert^2 \quad \text{s.t. } y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1\ \forall i.$ Maximising $\frac{2}{\lVert\mathbf{w}\rVert}$ is equivalent to minimising $\lVert\mathbf{w}\rVert$, which is equivalent to minimising $\frac{1}{2}\lVert\mathbf{w}\rVert^2$; the squared form is smooth, convex, differentiable (quadratic program), unlike the norm/reciprocal. (1 objective, 1 constraint, 1 convexity reasoning)

(d) $\min\ \tfrac{1}{2}\lVert\mathbf{w}\rVert^2 + C\sum_i \xi_i \quad \text{s.t. } y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1-\xi_i,\ \xi_i\ge0.$ $C$ trades off margin width vs training violations: large $C$ penalises misclassifications heavily → narrow margin, low bias/high variance; small $C$ allows more slack → wider margin, more regularisation. (2 formulation, 1 role of C)

Q2 (10 marks)

(a) The kernel trick lets us compute inner products $\phi(\mathbf{x})^\top\phi(\mathbf{z})$ in a high-dimensional feature space without ever computing $\phi$ explicitly. Valid kernel: $K$ must be symmetric and produce a positive semi-definite Gram matrix (Mercer's condition). (1 avoid explicit mapping, 1 symmetry, 1 PSD/Mercer)

(b) For $\mathbf{x}=(x_1,x_2)$, $\mathbf{z}=(z_1,z_2)$: $(\mathbf{x}^\top\mathbf{z})^2 = (x_1z_1+x_2z_2)^2 = x_1^2z_1^2 + 2x_1x_2z_1z_2 + x_2^2z_2^2$. This equals $\phi(\mathbf{x})^\top\phi(\mathbf{z})$ with $\phi(\mathbf{x}) = (x_1^2,\ \sqrt{2}\,x_1x_2,\ x_2^2)$. (2 expansion, 2 correct $\phi$ incl $\sqrt 2$)

(c) Large $\gamma$ → narrow Gaussians, each point influences only its neighbourhood → highly wiggly boundary → overfitting. Small $\gamma$ → wide Gaussians → smooth, nearly linear boundary → risk of underfitting. (1 large, 1 small, 1 overfit link)

Q3 (12 marks)

(a) Assumption: features are conditionally independent given the class. Rule: $\hat y = \arg\max_c P(c)\prod_j P(x_j\mid c)$. (1 + 1)

(b) Class A $\{2,4,6\}$: mean $=4$. MLE variance $=\frac{(2-4)^2+(0)+(6-4)^2}{3}=\frac{4+0+4}{3}=\frac{8}{3}\approx2.667$. Class B $\{6,8,10\}$: mean $=8$, variance $=\frac{8}{3}\approx2.667$ (by symmetry). (mean A 1, var A 1, mean B 1, var B 1)

(c) $x=5$. $\sigma^2=8/3$, $\sqrt{2\pi\sigma^2}$ same for both, so compare exponents. Class A: $(5-4)^2=1$, exponent $=-\frac{1}{2\cdot8/3}=-\frac{3}{16}=-0.1875$. Class B: $(5-8)^2=9$, exponent $=-\frac{9\cdot3}{16}=-\frac{27}{16}=-1.6875$. Ratio $\frac{P(x|A)}{P(x|B)}=\exp(-0.1875+1.6875)=\exp(1.5)\approx4.48$. Priors equal → predict Class A. (likelihood A 1, likelihood B 1, ratio 1, decision 1)

(d) Even with true Gaussian densities, NB uses estimated (MLE) parameters from finite data and, more fundamentally, points near the decision boundary (Bayes-error region) can fall on the wrong side; overlapping distributions always incur irreducible Bayes error. (2)

Q4 (14 marks)

(a) 2 spam, 2 ham → $P(\text{spam})=P(\text{ham})=\tfrac{2}{4}=0.5$. (2)

(b) Smoothed: $P(w\mid c)=\frac{\text{count}(w,c)+1}{N_c+|V|}$, $|V|=5$. Spam word tokens: free,free,money,free,win → $N_{spam}=5$; count(free,spam)=3. $P(\text{free}|\text{spam})=\frac{3+1}{5+5}=\frac{4}{10}=0.4$. Ham tokens: meeting,money,meeting,today → $N_{ham}=4$; count(free,ham)=0. $P(\text{free}|\text{ham})=\frac{0+1}{4+5}=\frac{1}{9}\approx0.1111$. (formula 1, spam 1.5, ham 1.5)

(c) Need $P(\text{money}|c)$ too. count(money,spam)=1 → $P(\text{money}|\text{spam})=\frac{1+1}{5+5}=\frac{2}{10}=0.2$. count(money,ham)=1 → $P(\text{money}|\text{ham})=\frac{1+1}{4+5}=\frac{2}{9}\approx0.2222$. Spam score $=0.5\times0.4\times0.2=0.04$. Ham score $=0.5\times\frac{1}{9}\times\frac{2}{9}=0.5\times\frac{2}{81}=\frac{1}{81}\approx0.012346$. $0.04 > 0.0123$ → predict SPAM. (each P 1, each score 1.5, decision 1)

(d) Without smoothing, $P(\text{free}|\text{ham})=0$ would zero out the entire ham posterior for any document containing "free," making unseen words catastrophic. Laplace smoothing removes zero probabilities. (2)

Q5 (8 marks)

(a) Multinomial: models word counts/frequencies; a document is a bag of tokens, feature = number of occurrences. Bernoulli: models binary presence/absence of each vocabulary word; explicitly accounts for words that are absent via $(1-P(w|c))$ terms. (2 + 2)

(b) Support vectors are training points with $\alpha_i > 0$; they lie on or inside the margin ($y_i(\mathbf{w}^\top\mathbf{x}_i+b)\le1$). Since $\mathbf{w}=\sum_i \alpha_i y_i \mathbf{x}_i$, points with $\alpha_i=0$ contribute nothing to $\mathbf{w}$, so removing them leaves the solution unchanged. (2 definition, 2 reasoning via w)

Q6 (4 marks)

Use grid/random search with cross-validation over a log-spaced grid of $(C,\gamma)$ (e.g. $C\in\{10^{-2}..10^{3}\}$, $\gamma\in\{10^{-4}..10^{1}\}$), pick the pair maximising CV accuracy/F1. (2) High $C$ + high $\gamma$ → very tight, overfit boundary. Low $C$ + low $\gamma$ → smooth, underfit boundary. Best models balance both. (2)

[
  {"claim":"GNB variance for class A {2,4,6} is 8/3","code":"import statistics as st; vals=[2,4,6]; m=sum(vals)/3; var=sum((v-m)**2 for v in vals)/3; result = sympy.simplify(var-Rational(8,3))==0"},
  {"claim":"GNB likelihood ratio at x=5 equals exp(1.5)","code":"expA=-Rational(1,2)*(5-4)**2/(Rational(8,3)); expB=-Rational(1,2)*(5-8)**2/(Rational(8,3)); result = sympy.simplify((expA-expB)-Rational(3,2))==0"},
  {"claim":"P(free|spam)=0.4 and P(free|ham)=1/9 with Laplace","code":"pfs=Rational(3+1,5+5); pfh=Rational(0+1,4+5); result = (pfs==Rational(2,5)) and (pfh==Rational(1,9))"},
  {"claim":"Spam score 0.04 > ham score 1/81 for 'free money'","code":"spam=Rational(1,2)*Rational(4,10)*Rational(2,10); ham=Rational(1,2)*Rational(1,9)*Rational(2,9); result = (spam==Rational(1,25)) and (spam>ham)"}
]