Level 2 — RecallSVM, Naive Bayes & Probabilistic Models

SVM, Naive Bayes & Probabilistic Models

⏱ 30 minutes40 marksprintable — key stays hidden on paper

Level 2 — Recall (Definitions, Standard Problems, Short Derivations)

Time Limit: 30 minutes Total Marks: 40

Q1. Define the maximum margin in the context of a Support Vector Machine. For a hyperplane $\mathbf{w}\cdot\mathbf{x} + b = 0$ , write the expression for the geometric margin between the two supporting hyperplanes. (3 marks)

Q2. State the difference between a hard margin and a soft margin SVM classifier. Give one situation where a soft margin is preferred. (4 marks)

Q3. Explain the kernel trick. Why does it allow a linear SVM algorithm to produce non-linear decision boundaries without explicitly computing the high-dimensional feature mapping? (4 marks)

Q4. Write the mathematical form of the following kernels: (a) linear, (b) polynomial of degree $d$ , (c) RBF (Gaussian). (3 marks)

Q5. Describe the effect of the hyperparameters $C$ and $\gamma$ (in an RBF-kernel SVM). State what happens to the model as each is increased. (4 marks)

Q6. What are support vectors? In a trained SVM, how do they relate to the decision boundary, and why does removing a non-support-vector point not change the model? (4 marks)

Q7. State the Naive Bayes assumption. Using Bayes' theorem, write the classification rule (posterior proportionality) for predicting class $c$ given features $x_1,\dots,x_n$ . (4 marks)

Q8. A Gaussian Naive Bayes model estimates $P(x\mid c)$ for a continuous feature using a Gaussian. For a class with mean $\mu = 6.0$ and variance $\sigma^2 = 4.0$ , compute the likelihood $P(x=8\mid c)$ . Give the formula and the numeric value. (5 marks)

Q9. Explain Laplace (add-one) smoothing in Multinomial Naive Bayes. A word appears 0 times in a class with total word count 40 and vocabulary size 10. Compute the smoothed probability of that word. (4 marks)

Q10. Briefly describe how Naive Bayes is applied to text classification. State one difference between Multinomial and Bernoulli Naive Bayes in this setting. (5 marks)

End of Paper

Answer keyMark scheme & solutions

Q1. (3 marks)

Maximum margin = the largest possible distance (gap) between the separating hyperplane and the nearest data points of either class. (1)
SVM chooses the hyperplane that maximizes this margin for best generalization. (1)
Geometric margin between the two supporting hyperplanes $\mathbf{w}\cdot\mathbf{x}+b=\pm1$ : $\text{margin} = \frac{2}{\lVert \mathbf{w}\rVert}$ (1)

Q2. (4 marks)

Hard margin: requires all points to be correctly classified with no violations; only works if data is linearly separable. (1.5)
Soft margin: introduces slack variables $\xi_i \ge 0$ allowing some misclassifications/margin violations; minimizes $\tfrac12\lVert w\rVert^2 + C\sum \xi_i$ . (1.5)
Soft margin preferred when data is noisy or not perfectly linearly separable (avoids overfitting to outliers). (1)

Q3. (4 marks)

The kernel trick replaces the inner product $\mathbf{x}_i\cdot\mathbf{x}_j$ in the SVM dual with a kernel function $K(\mathbf{x}_i,\mathbf{x}_j)=\phi(\mathbf{x}_i)\cdot\phi(\mathbf{x}_j)$ . (2)
Since the SVM only needs dot products, $K$ computes the similarity in the high-dimensional space without explicitly mapping to $\phi(\mathbf{x})$ . (1)
This makes non-linear boundaries feasible/efficient even when $\phi$ is very high (or infinite) dimensional. (1)

Q4. (3 marks) — 1 mark each

(a) Linear: $K(\mathbf{x},\mathbf{z}) = \mathbf{x}\cdot\mathbf{z}$
(b) Polynomial: $K(\mathbf{x},\mathbf{z}) = (\mathbf{x}\cdot\mathbf{z}+c)^d$
(c) RBF: $K(\mathbf{x},\mathbf{z}) = \exp\!\left(-\gamma\lVert\mathbf{x}-\mathbf{z}\rVert^2\right)$

Q5. (4 marks)

$C$ controls the trade-off between margin width and classification error. (1)
- Large $C$ → penalizes misclassification heavily → narrower margin, less regularization, risk of overfitting. (1)
$\gamma$ controls the reach/influence of a single training point in RBF. (1)
- Large $\gamma$ → each point has small radius of influence → complex, wiggly boundary → overfitting; small $\gamma$ → smoother boundary. (1)

Q6. (4 marks)

Support vectors are the training points lying on the margin boundaries (or, in soft-margin, violating them) — i.e., the points closest to / defining the decision boundary. (2)
The optimal $\mathbf{w}$ is a linear combination of only the support vectors ( $\alpha_i > 0$ ). (1)
Non-support vectors have $\alpha_i = 0$ , so removing them leaves $\mathbf{w}$ and $b$ unchanged. (1)

Q7. (4 marks)

Naive Bayes assumption: features are conditionally independent given the class. (2)
Bayes rule: $P(c\mid x_1..x_n)=\dfrac{P(c)\prod_i P(x_i\mid c)}{P(x_1..x_n)}$ . (1)
Classification rule: $\hat{c} = \arg\max_c\ P(c)\prod_{i=1}^{n} P(x_i\mid c)$ (denominator constant, dropped). (1)

Q8. (5 marks)

Formula: $P(x\mid c)=\dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\!\left(-\dfrac{(x-\mu)^2}{2\sigma^2}\right)$ (2)
Substitute $x=8,\ \mu=6,\ \sigma^2=4$ : exponent $=-\dfrac{(2)^2}{2\cdot4}=-\dfrac{4}{8}=-0.5$ . (1)
Prefactor $=\dfrac{1}{\sqrt{8\pi}}=\dfrac{1}{5.0133}=0.19947$ . (1)
$P = 0.19947 \times e^{-0.5}=0.19947\times0.60653 \approx 0.1210$ . (1)

Q9. (4 marks)

Laplace smoothing adds a count of 1 (α=1) to every word to avoid zero probabilities: $P(w\mid c)=\frac{\text{count}(w,c)+1}{N_c + |V|}$ (2)
Substitute: count=0, $N_c=40$ , $|V|=10$ : $P = \frac{0+1}{40+10} = \frac{1}{50}=0.02$ (2)

Q10. (5 marks)

Text is converted to features (bag-of-words / token counts / presence). (1)
Compute $P(c)\prod P(\text{word}\mid c)$ over document tokens; predict the class with highest posterior (log-space to avoid underflow). (2)
Difference: Multinomial uses word frequency counts (how many times a word occurs); Bernoulli uses binary presence/absence of words and explicitly models non-occurrence. (2)

[
  {"claim":"Q8: Gaussian likelihood at x=8, mu=6, var=4 ≈ 0.1210",
   "code":"mu=6; var=4; x=8; val=1/sqrt(2*pi*var)*exp(-(x-mu)**2/(2*var)); result = abs(float(val)-0.1210) < 0.001"},
  {"claim":"Q8: exponent term equals -0.5",
   "code":"mu=6; var=4; x=8; e=-(x-mu)**2/(2*var); result = e == Rational(-1,2)"},
  {"claim":"Q9: Laplace smoothed prob = 1/50 = 0.02",
   "code":"p=(0+1)/(40+10); result = p == Rational(1,50)"},
  {"claim":"Q1: margin between w.x+b=±1 is 2/||w||",
   "code":"w=symbols('wn', positive=True); margin=2/w; result = simplify(margin - 2/w)==0"}
]