The GATE Grind

GATE 2024 DA – Question 17

Machine Learning · Supervised learning: classification · 1 mark · Multiple choice

Consider the dataset with six datapoints: $\{(x_1, y_1), (x_2, y_2), \ldots, (x_6, y_6)\}$, where $x_1 = \begin{bmatrix}1\\0\end{bmatrix}$, $x_2 = \begin{bmatrix}0\\1\end{bmatrix}$, $x_3 = \begin{bmatrix}0\\-1\end{bmatrix}$, $x_4 = \begin{bmatrix}-1\\0\end{bmatrix}$, $x_5 = \begin{bmatrix}2\\2\end{bmatrix}$, $x_6 = \begin{bmatrix}-2\\-2\end{bmatrix}$ and the labels are given by $y_1 = y_2 = y_5 = 1$, and $y_3 = y_4 = y_6 = -1$. A hard margin linear support vector machine is trained on the above dataset.

Which ONE of the following sets is a possible set of support vectors?

  1. $\{x_1, x_2, x_5\}$
  2. $\{x_3, x_4, x_5\}$
  3. $\{x_4, x_5\}$
  4. $\{x_1, x_2, x_3, x_4\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\{x_1, x_2, x_3, x_4\}$

Explanation

The positive points are $(1, 0)$, $(0, 1)$ and $(2, 2)$ and the negative points are $(0, -1)$, $(-1, 0)$ and $(-2, -2)$. The hyperplane $x_1 + x_2 = 0$ separates them, and the four points $x_1, x_2, x_3, x_4$ are the closest to it, all at the distance $\frac{1}{\sqrt{2}}$, while $x_5$ and $x_6$ are farther away (at distance $2\sqrt{2}$). With $w = (1, 1)$ and $b = 0$ these four points have $y(w \cdot x + b) = 1$ exactly, so they are the support vectors.