SVM, Naive Bayes & Probabilistic Models

Question 1

(a) (6 marks)

• The hyperplane is $\mathbf{w}^\top\mathbf{x}+b=0$; $\mathbf{w}$ is normal to it. For any point $\mathbf{x}_i$, decompose $\mathbf{x}_i = \mathbf{x}_p + r\frac{\mathbf{w}}{\|\mathbf{w}\|}$ where $\mathbf{x}_p$ lies on the hyperplane. (2)
• Substituting: $\mathbf{w}^\top\mathbf{x}_i + b = \mathbf{w}^\top\mathbf{x}_p + b + r\|\mathbf{w}\| = 0 + r\|\mathbf{w}\|$, so $r = \frac{\mathbf{w}^\top\mathbf{x}_i+b}{\|\mathbf{w}\|}$, distance $=\frac{|\mathbf{w}^\top\mathbf{x}_i+b|}{\|\mathbf{w}\|}$. (2)
• With canonical scaling so margin points satisfy $|\mathbf{w}^\top\mathbf{x}+b|=1$, margin half-width $=\frac{1}{\|\mathbf{w}\|}$; maximizing $\frac{2}{\|\mathbf{w}\|}$ $\equiv$ minimizing $\frac12\|\mathbf{w}\|^2$ s.t. $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge1$. (2)

(b) (8 marks) Primal: $\min_{\mathbf{w},b,\xi}\ \frac12\|\mathbf{w}\|^2 + C\sum_i\xi_i$ s.t. $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1-\xi_i,\ \xi_i\ge0$. (3) KKT interpretation (complementary slackness $\alpha_i[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1+\xi_i]=0$, and $(C-\alpha_i)\xi_i=0$): (5, ~1.6 each)

• (i) $\alpha_i = 0$: point beyond margin, $y_i f(\mathbf{x}_i) > 1$, $\xi_i=0$ — not a support vector.
• (ii) $0 < \alpha_i < C$: point exactly on the margin, $\xi_i=0$, $y_i f=1$ — free support vector.
• (iii) $\alpha_i = C$: point inside margin or misclassified, $\xi_i>0$ — bounded support vector.

(c) (6 marks)

• Nearest opposite points: positive $x=2$, negative $x=0$. Boundary midway at $x=1$. (2)
• With canonical constraints $w\cdot2 + b = +1$ and $w\cdot0 + b = -1$: subtract → $2w=2 \Rightarrow w=1$, $b=-1$. Boundary $x=1$. ✓ (2)
• Margin width $=\frac{2}{\|w\|}=2$ (half-width 1). Support vectors: $x=2$ (+) and $x=0$ (−); $x=3,-1$ are not. (2)

(d) (4 marks)

• The dual objective and decision function depend on data only through inner products $\mathbf{x}_i^\top\mathbf{x}_j$; replacing with $K=\phi(\mathbf{x}_i)^\top\phi(\mathbf{x}_j)$ gives the high-dim solution without materializing $\phi$ (Mercer kernel). (2)
• For $\mathbf{x}=(x_1,x_2)$: $(\mathbf{x}^\top\mathbf{z}+1)^2 = 1 + 2x_1z_1 + 2x_2z_2 + x_1^2z_1^2 + x_2^2z_2^2 + 2x_1x_2z_1z_2$, so $\phi(\mathbf{x}) = (1,\ \sqrt2 x_1,\ \sqrt2 x_2,\ x_1^2,\ x_2^2,\ \sqrt2 x_1x_2).$ (2)

Question 2

(a) (5 marks)

• Assumption: features conditionally independent given class: $P(x_1,\dots,x_n\mid c)=\prod_j P(x_j\mid c)$. (2)
• Bayes: $P(c\mid\mathbf{x}) = \frac{P(c)P(\mathbf{x}\mid c)}{P(\mathbf{x})}$; apply independence → $\propto P(c)\prod_j P(x_j\mid c)$. (2)
• $P(\mathbf{x})$ is constant across classes, so it doesn't affect the $\arg\max$. (1)

(b) (9 marks) Smoothed likelihood: $P(w\mid c) = \frac{\text{count}(w,c)+1}{\text{total}_c + V}$, denom $=6+3=9$. (2)

• Spam: $P(\text{free})=\frac{4}{9}$, $P(\text{money})=\frac{4}{9}$. (2)
• Ham: $P(\text{free})=\frac{2}{9}$, $P(\text{money})=\frac{2}{9}$. (2)
• Score spam $= 0.5\cdot\frac{4}{9}\cdot\frac{4}{9} = 0.5\cdot\frac{16}{81}=\frac{8}{81}\approx0.0988$.
• Score ham $= 0.5\cdot\frac{2}{9}\cdot\frac{2}{9} = 0.5\cdot\frac{4}{81}=\frac{2}{81}\approx0.0247$. (2)
• Spam score > ham score → classify as SPAM. (1)

(c) (4 marks)

• Without smoothing, "meeting" absent in spam would give $P(\text{meeting}\mid\text{spam})=0$, zeroing the entire product regardless of other evidence — a single unseen word vetoes the class. (2)
• Add-$\alpha$: $\frac{count+\alpha}{total+\alpha V}$; as $V\to\infty$ with fixed counts, each probability $\to$ uniform-ish/tiny, smoothing dominates and washes out evidence — must keep $\alpha$ small relative to counts. (2)

(d) (6 marks)

import numpy as np
def predict_log_proba(counts, priors, likelihoods):
    # counts: dict token->freq in doc
    # priors: {class: P(class)}, likelihoods: {class: {token: P(token|class)}}
    scores = {}
    for c in priors:
        s = np.log(priors[c])
        for tok, n in counts.items():
            s += n * np.log(likelihoods[c][tok])  # log of product = sum of logs
        scores[c] = s
    return max(scores, key=scores.get)

(5) for correct log-space summation and argmax. One sentence (1): multiplying many probabilities $<1$ underflows to 0 in floating point; summing logs stays representable.

Question 3

(a) (6 marks)

• $\log P(c\mid x) = \log P(c) - \frac12(x-\mu_c)^\top\Sigma^{-1}(x-\mu_c)+\text{const}$. (2)
• With shared $\Sigma$, the quadratic term $x^\top\Sigma^{-1}x$ cancels in the log-ratio between two classes, leaving a term linear in $x$ → linear boundary (this is LDA). (2)
• RBF-SVM maps to an infinite-dimensional feature space where linear separation corresponds to nonlinear boundaries in input space; $\gamma$ controls the locality of that mapping, allowing curved decision regions. (2)

(b) (6 marks)

• $C$: penalty on margin violations. Large $C$ → low bias, high variance (hard margin, overfits noise); small $C$ → high bias, wider soft margin. (2)
• $\gamma$ (RBF): inverse kernel width. Large $\gamma$ → very local, high variance/overfit; small $\gamma$ → smooth, high bias. (2)
• $\alpha$ (NB smoothing): large $\alpha$ → pulls estimates toward uniform, high bias, low variance; $\alpha\to0$ → trusts sparse counts, low bias, high variance (zero-probability instability). (2)

[
  {"claim":"1D SVM: w=1,b=-1 gives correct canonical constraints and margin width 2",
   "code":"w,b=1,-1; c1=(w*2+b==1); c2=(w*0+b==-1); margin=Rational(2,abs(w)); result=bool(c1 and c2 and margin==2)"},
  {"claim":"Multinomial NB spam score exceeds ham score for 'free money'",
   "code":"ps=Rational(1,2)*Rational(4,9)*Rational(4,9); ph=Rational(1,2)*Rational(2,9)*Rational(2,9); result=bool(ps>ph and ps==Rational(8,81) and ph==Rational(2,81))"},
  {"claim":"Laplace smoothed P(free|spam)=4/9 with add-1, V=3, total=6",
   "code":"p=Rational(3+1,6+3); result=bool(p==Rational(4,9))"},
  {"claim":"Poly kernel expansion (x.z+1)^2 has 6 monomial terms matching phi",
   "code":"x1,x2,z1,z2=symbols('x1 x2 z1 z2'); K=expand((x1*z1+x2*z2+1)**2); phi=[1,sqrt(2)*x1,sqrt(2)*x2,x1**2,x2**2,sqrt(2)*x1*x2]; psi=[1,sqrt(2)*z1,sqrt(2)*z2,z1**2,z2**2,sqrt(2)*z1*z2]; dot=expand(sum(a*b for a,b in zip(phi,psi))); result=bool(simplify(dot-K)==0)"}
]