Level 1 — RecognitionSVM, Naive Bayes & Probabilistic Models

SVM, Naive Bayes & Probabilistic Models

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Level 1: Recognition (MCQ + Matching + True/False with Justification)

Time Limit: 20 minutes
Total Marks: 30

Section A — Multiple Choice Questions (1 mark each)

Choose the single best answer.

Q1. In a Support Vector Machine, the "margin" refers to:

(a) The number of misclassified points
(b) The distance between the two classes of the decision boundary (the separating hyperplane)
(c) The learning rate of the algorithm
(d) The regularization penalty term

Q2. A hard-margin SVM can only be used when the data is:

(a) Non-linearly separable
(b) Perfectly linearly separable
(c) High-dimensional only
(d) Noisy with many outliers

Q3. The purpose of the kernel trick is to:

(a) Reduce the number of support vectors to zero
(b) Compute dot products in a higher-dimensional space without explicitly transforming the data
(c) Remove the need for a bias term
(d) Guarantee zero training error

Q4. The RBF (Gaussian) kernel is defined as:

(a) $K(x,z) = x^\top z$
(b) $K(x,z) = (x^\top z + c)^d$
(c) $K(x,z) = \exp(-\gamma \lVert x - z \rVert^2)$
(d) $K(x,z) = \tanh(x^\top z)$

Q5. In a soft-margin SVM, increasing the hyperparameter C generally:

(a) Increases tolerance for misclassification (wider margin)
(b) Decreases the penalty for misclassification
(c) Increases the penalty for misclassification (narrower margin, less tolerance)
(d) Has no effect on the margin

Q6. The naive assumption in Naive Bayes is that:

(a) All features are equally important
(b) Features are conditionally independent given the class label
(c) The prior probabilities are always uniform
(d) The data is always Gaussian

Q7. Gaussian Naive Bayes is most appropriate for:

(a) Word count data
(b) Binary presence/absence features
(c) Continuous-valued features
(d) Categorical labels only

Q8. Laplace (add-one) smoothing is applied primarily to:

(a) Speed up training
(b) Avoid zero probabilities for unseen feature-class combinations
(c) Normalize continuous features
(d) Increase the margin

Q9. The support vectors of a trained SVM are:

(a) All the training points
(b) The points lying on or within the margin (closest to the boundary)
(c) The points farthest from the decision boundary
(d) The test set points

Q10. For text classification counting how many times words appear, the most suitable Naive Bayes variant is:

(a) Gaussian
(b) Multinomial
(c) Bernoulli only
(d) None of these

Section B — Matching (5 marks)

Q11. Match each kernel/parameter in Column X with its correct description in Column Y. (1 mark each)

Column X	Column Y
1. Linear kernel	A. Controls influence radius of a single training example; large value → tight, wiggly boundary
2. Polynomial kernel	B. $K(x,z) = x^\top z$
3. RBF kernel	C. Uses $\exp(-\gamma\lVert x-z\rVert^2)$ ; can model complex non-linear boundaries
4. $\gamma$ (gamma)	D. Trades off margin width against classification errors
5. $C$	E. $K(x,z) = (x^\top z + c)^d$

Section C — True/False with Justification (3 marks each)

State True or False (1 mark) and give a one-line justification (2 marks).

Q12. In Bernoulli Naive Bayes, the absence of a word in a document contributes to the probability calculation.

Q13. A larger value of $\gamma$ in an RBF-kernel SVM always improves generalization to unseen data.

Q14. Multinomial Naive Bayes and Bernoulli Naive Bayes treat repeated occurrences of the same word identically.

Q15. Removing a non-support-vector training point and retraining the SVM will change the decision boundary.

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 — (b). The margin is the perpendicular distance between the separating hyperplane and the nearest data points of each class; SVM maximizes it. (1)

Q2 — (b). Hard-margin SVM requires zero training violations, so classes must be perfectly linearly separable. (1)

Q3 — (b). The kernel computes $K(x,z)=\langle\phi(x),\phi(z)\rangle$ directly, avoiding explicit mapping $\phi$ into high dimensions. (1)

Q4 — (c). RBF kernel: $K(x,z)=\exp(-\gamma\lVert x-z\rVert^2)$ . (a) is linear, (b) polynomial, (d) sigmoid. (1)

Q5 — (c). Large $C$ heavily penalizes slack variables $\xi_i$ , forcing fewer misclassifications → narrower margin. (1)

Q6 — (b). Naive Bayes assumes features are conditionally independent given the class. (1)

Q7 — (c). Gaussian NB models each continuous feature per class with a normal distribution. (1)

Q8 — (b). Add-one smoothing prevents any conditional probability from being zero (which would nullify the whole product). (1)

Q9 — (b). Support vectors are the points on or inside the margin; they alone define the boundary. (1)

Q10 — (b). Multinomial NB models word-count/frequency data, ideal for term-frequency text features. (1)

Section B (5 marks)

Q11.

1 → B (Linear: $x^\top z$ )
2 → E (Polynomial: $(x^\top z + c)^d$ )
3 → C (RBF: exponential of squared distance)
4 → A (γ controls influence radius)
5 → D (C trades margin vs errors)

1 mark per correct pair, total 5.

Section C (3 marks each: 1 for T/F, 2 for justification)

Q12 — TRUE. (1) Bernoulli NB uses a binary presence/absence model over the whole vocabulary, so a word being absent explicitly contributes a factor $(1-p_{w|c})$ to the likelihood. (2)

Q13 — FALSE. (1) Very large $\gamma$ shrinks each point's influence radius, producing highly complex boundaries that overfit the training data and generalize worse. (2)

Q14 — FALSE. (1) Multinomial NB counts multiplicities (frequency matters), whereas Bernoulli NB only records presence/absence (repeats ignored) — so they do not treat repeats identically. (2)

Q15 — FALSE. (1) Non-support vectors lie outside the margin and have zero dual coefficient; removing them leaves the optimal hyperplane unchanged. (2)

[
  {"claim":"RBF kernel value K(x,z)=exp(-gamma*||x-z||^2) equals exp(-1) when gamma=1 and ||x-z||^2=1","code":"gamma=1; d2=1; K=exp(-gamma*d2); result = simplify(K - exp(-1))==0"},
  {"claim":"Larger C reduces summed slack: minimizing 0.5*w^2 + C*xi over xi>=0 with C larger pushes optimal xi toward 0","code":"C1,C2=2,10; xi=symbols('xi',nonnegative=True); result = (C2 > C1)"},
  {"claim":"Laplace smoothing keeps probability positive: (0+1)/(N+V) > 0 for N=5,V=3","code":"N,V=5,3; p=(0+1)/(N+V); result = p > 0"},
  {"claim":"Polynomial kernel (x.z + c)^d with x=z=1D value 1, c=1, d=2 gives 4","code":"x=1; z=1; c=1; d=2; val=(x*z+c)**d; result = val == 4"}
]