The GATE Grind

GATE 2025 DA – Question 53

Machine Learning · Supervised learning: classification · 2 marks · Multiple select

Consider designing a linear binary classifier $f(x) = \text{sign}(w^\top x + b)$, $x \in \mathbb{R}^2$ on the following training data:

Class-1: $\begin{pmatrix} 2 \\ 0 \end{pmatrix}$, $\begin{pmatrix} 0 \\ 2 \end{pmatrix}$, $\begin{pmatrix} 2 \\ 2 \end{pmatrix}$, Class-2: $\begin{pmatrix} 0 \\ 0 \end{pmatrix}$

Hard-margin support vector machine (SVM) formulation is solved to obtain $w$ and $b$. Which of the following options is/are correct?

  1. $w = \begin{pmatrix} 4 \\ 4 \end{pmatrix}$ and $b = 1$
  2. The number of support vectors is 3
  3. The margin is $\sqrt{2}$
  4. Training accuracy is 98%

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) The number of support vectors is 3; (C) The margin is $\sqrt{2}$

Explanation

By symmetry take $w = (a, a)$. The class-2 point $(0, 0)$ needs $-b \ge 1$, so $b \le -1$. The class-1 points $(2, 0)$ and $(0, 2)$ need $2a + b \ge 1$, and the point $(2, 2)$ needs $4a + b \ge 1$. To minimise $\|w\|$ choose the smallest $a$, which is $a = 1$ with $b = -1$. So $w = (1, 1)$ and $b = -1$, and A is false. The points on the margin are $(0, 0)$, $(2, 0)$ and $(0, 2)$, which are 3 support vectors (B is true). The width of the margin is $\frac{2}{\|w\|} = \frac{2}{\sqrt{2}} = \sqrt{2}$ (C is true). All 4 training points are classified correctly, so the training accuracy is 100 %, not 98 % (D is false).