Level 4 — ApplicationSVM, Naive Bayes & Probabilistic Models

SVM, Naive Bayes & Probabilistic Models

⏱ 60 minutes50 marksprintable — key stays hidden on paper

Level: 4 (Application — novel problems, no hints) Time limit: 60 minutes Total marks: 50

Question 1 — SVM Maximum Margin from Data (12 marks)

You are given four linearly separable 2-D training points:

Positive class ( $y=+1$ ): $A=(3,3)$ , $B=(4,4)$
Negative class ( $y=-1$ ): $C=(1,1)$ , $D=(0,0)$

(a) By inspection/symmetry, argue which points are the support vectors, and find the maximum-margin separating hyperplane $\mathbf{w}\cdot\mathbf{x}+b=0$ using the constraint that support vectors satisfy $y_i(\mathbf{w}\cdot\mathbf{x}_i+b)=1$ . Assume $\mathbf{w}=(a,a)$ by symmetry. (6)

(b) Compute the geometric margin $\dfrac{2}{\lVert\mathbf{w}\rVert}$ . (3)

(c) Classify the new point $P=(2,3)$ and report the value of the decision function $f(P)=\mathbf{w}\cdot P+b$ . (3)

Question 2 — Soft Margin, C and Kernel Choice (10 marks)

A colleague trains an RBF-kernel SVM on a noisy dataset and reports 100% training accuracy but only 62% test accuracy.

(a) Explain in terms of $C$ and $\gamma$ what is most likely happening, and state precisely how you would change each hyperparameter to fix it. (5)

(b) For a soft-margin SVM, write the primal objective and explain the role of the slack variables $\xi_i$ and the penalty $C$ . What happens to the margin and number of support vectors as $C\to 0$ ? (5)

Question 3 — Gaussian Naive Bayes Prediction (12 marks)

A Gaussian NB classifier is trained to detect spam using one feature $x$ = "number of links in email". The fitted per-class statistics are:

Class	Prior	Mean $\mu$	Variance $\sigma^2$
Spam ( $S$ )	0.4	6	4
Ham ( $H$ )	0.6	2	1

A new email has $x = 4$ links.

(a) Compute the class-conditional likelihoods $p(x=4\mid S)$ and $p(x=4\mid H)$ using the Gaussian density. Leave answers to 4 significant figures. (6)

(b) Compute the posterior probability $P(S\mid x=4)$ and give the predicted class. (4)

(c) GNB assumes feature independence given the class. If you added a second highly-correlated feature "number of images", would this assumption be violated, and what practical effect does the violation typically have on the classifier decision vs the probability estimates? (2)

Question 4 — Multinomial NB Text Classification with Laplace Smoothing (12 marks)

Training corpus (vocabulary = {win, free, money, meeting, report}):

Spam documents (2 docs):

D1: "win free money"
D2: "free money money"

Ham documents (2 docs):

D3: "meeting report"
D4: "report meeting report"

(a) Using Multinomial NB with Laplace (add-1) smoothing, compute the smoothed probability $P(\text{money}\mid \text{Spam})$ and $P(\text{money}\mid \text{Ham})$ . Use vocabulary size $|V|=5$ . (6)

(b) A new message is "free money". Using equal class priors $P(\text{Spam})=P(\text{Ham})=0.5$ , determine the predicted class by comparing the (unnormalized) log-scores. Show the smoothed probabilities used. (6)

Question 5 — Kernel Trick & Bernoulli NB Concepts (4 marks)

(a) State why the kernel trick lets an SVM find nonlinear boundaries without explicitly computing high-dimensional feature vectors, using the RBF kernel $K(\mathbf{x},\mathbf{z})=\exp(-\gamma\lVert\mathbf{x}-\mathbf{z}\rVert^2)$ as your example. (2)

(b) How does Bernoulli NB differ from Multinomial NB in how it treats word occurrence in a document? (2)

Answer keyMark scheme & solutions

Question 1 (12 marks)

(a) By symmetry the closest opposing points are $B=(4,4)$ (positive) and $C=(1,1)$ (negative) — these are the support vectors (2). Let $\mathbf{w}=(a,a)$ .

Support vector constraints ( $y_i(\mathbf{w}\cdot\mathbf{x}_i+b)=1$ ):

For $C=(1,1)$ , $y=-1$ : $-(a\cdot1+a\cdot1+b)=1 \Rightarrow -(2a+b)=1$
For $B=(4,4)$ , $y=+1$ : $+(4a+4a+b)=1 \Rightarrow 8a+b=1$

Subtract: $(8a+b)-(-(2a+b))$ ... solve directly: From $2a+b=-1$ and $8a+b=1$ : subtract $\Rightarrow 6a=2 \Rightarrow a=\tfrac13$ (2). Then $b=-1-2a=-1-\tfrac23=-\tfrac53$ (1).

Hyperplane: $\tfrac13 x_1+\tfrac13 x_2-\tfrac53=0$ , i.e. $x_1+x_2=5$ (1).

(b) $\lVert\mathbf{w}\rVert=\sqrt{(1/3)^2+(1/3)^2}=\sqrt{2}/3$ (1). Margin $=\dfrac{2}{\lVert\mathbf{w}\rVert}=\dfrac{2}{\sqrt2/3}=\dfrac{6}{\sqrt2}=3\sqrt2\approx4.243$ (2).

(c) $f(P)=\tfrac13(2)+\tfrac13(3)-\tfrac53=\tfrac{2+3-5}{3}=0$ ... check: $=\tfrac{0}{3}=0$ . Actually $x_1+x_2=5$ so $P$ lies on the boundary; $f(P)=0$ (2). Point is on the decision surface — ambiguous / margin boundary (1).

Question 2 (10 marks)

(a) Symptom = overfitting (1). Likely $C$ too large (hard penalty, fits noise) and/or $\gamma$ too large (very peaked RBF, each point its own island) (2). Fix: decrease $C$ (allow more slack / wider margin) and decrease $\gamma$ (smoother, wider kernel influence) (2). Use cross-validation grid search.

(b) Primal: $\min_{\mathbf{w},b,\xi}\ \tfrac12\lVert\mathbf{w}\rVert^2 + C\sum_i\xi_i \quad\text{s.t. } y_i(\mathbf{w}\cdot\mathbf{x}_i+b)\ge 1-\xi_i,\ \xi_i\ge0$ (2). $\xi_i$ measures margin violation (how far point is inside margin / misclassified) (1). $C$ trades margin width against violations (1). As $C\to0$ penalty vanishes → margin becomes very wide, many points become SVs, model tolerates more misclassification (underfits) (1).

Question 3 (12 marks)

Gaussian density $p(x)=\dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\!\left(-\dfrac{(x-\mu)^2}{2\sigma^2}\right)$ .

(a) Spam: $\sigma^2=4$ , $(4-6)^2=4$ : $p(4|S)=\dfrac{1}{\sqrt{8\pi}}e^{-4/8}=\dfrac{1}{\sqrt{8\pi}}e^{-0.5}=0.1995\times0.6065=0.1210$ (3).

Ham: $\sigma^2=1$ , $(4-2)^2=4$ : $p(4|H)=\dfrac{1}{\sqrt{2\pi}}e^{-4/2}=0.3989\times e^{-2}=0.3989\times0.1353=0.05399$ (3).

(b) Joint scores:

$S: 0.4\times0.1210=0.04840$
$H: 0.6\times0.05399=0.03239$

Evidence $=0.08079$ . $P(S\mid4)=0.04840/0.08079=0.599\approx0.60$ (3). Predict Spam (marginally) (1).

(c) Yes — correlated features violate conditional independence (1). Effect: probability estimates become over-confident (poorly calibrated), but the classification decision (argmax) is often still accurate (1).

Question 4 (12 marks)

Spam word counts: win 1, free 2, money 3, meeting 0, report 0. Total Spam tokens $=6$ . Ham word counts: win 0, free 0, money 0, meeting 2, report 3. Total Ham tokens $=5$ . $|V|=5$ .

(a) Laplace: $P(w|c)=\dfrac{\text{count}(w,c)+1}{N_c+|V|}$ . $P(\text{money}|S)=\dfrac{3+1}{6+5}=\dfrac{4}{11}=0.3636$ (3). $P(\text{money}|H)=\dfrac{0+1}{5+5}=\dfrac{1}{10}=0.1$ (3).

(b) Needed smoothed probs:

$P(\text{free}|S)=\dfrac{2+1}{11}=\dfrac{3}{11}=0.2727$ ; $P(\text{money}|S)=\dfrac{4}{11}$
$P(\text{free}|H)=\dfrac{0+1}{10}=0.1$ ; $P(\text{money}|H)=0.1$

Score (with equal priors, drop the $0.5$ ):

Spam: $\tfrac{3}{11}\times\tfrac{4}{11}=\dfrac{12}{121}=0.09917$
Ham: $0.1\times0.1=0.01$

Log-scores: $\ln(0.09917)=-2.311$ vs $\ln(0.01)=-4.605$ (3). Spam score higher → predict Spam (3).

Question 5 (4 marks)

(a) The SVM dual depends only on inner products $\mathbf{x}_i\cdot\mathbf{x}_j$ . A kernel replaces these with $K(\mathbf{x}_i,\mathbf{x}_j)=\phi(\mathbf{x}_i)\cdot\phi(\mathbf{x}_j)$ , computing the dot product in the (possibly infinite-dimensional, for RBF) feature space directly — no explicit $\phi$ needed (2).

(b) Bernoulli NB uses binary presence/absence of each vocabulary word (and penalizes non-occurrence), while Multinomial NB uses word counts/frequencies (2).

[
  {"claim":"Q1 hyperplane a=1/3, b=-5/3","code":"a,b=symbols('a b'); sol=solve([2*a+b+1, 8*a+b-1],[a,b]); result=(sol[a]==Rational(1,3) and sol[b]==Rational(-5,3))"},
  {"claim":"Q1 margin = 3*sqrt(2)","code":"w=sqrt((Rational(1,3))**2+(Rational(1,3))**2); m=2/w; result=simplify(m-3*sqrt(2))==0"},
  {"claim":"Q3 posterior P(S|4) approx 0.599","code":"import math; pS=0.4*(1/math.sqrt(8*math.pi))*math.exp(-0.5); pH=0.6*(1/math.sqrt(2*math.pi))*math.exp(-2); post=pS/(pS+pH); result=abs(post-0.599)<0.01"},
  {"claim":"Q4 Spam score > Ham score for 'free money'","code":"spam=(Rational(3,11))*(Rational(4,11)); ham=Rational(1,10)*Rational(1,10); result=spam>ham"},
  {"claim":"Q4 P(money|S)=4/11","code":"result=Rational(3+1,6+5)==Rational(4,11)"}
]