Support Vector Machines

GATE DA previous year questions · 2 questions

GATE DA 2025 | Question 53

MSQ · 2 marks

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

\[ \text{Class-1: } \left\{ \begin{pmatrix} 2 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 2 \end{pmatrix}, \begin{pmatrix} 2 \\ 2 \end{pmatrix} \right\}, \ \text{Class-2: } \left\{ \begin{pmatrix} 0 \\ 0 \end{pmatrix} \right\} \]

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

Options for GATE DA 2025 | Question 53

Explanation

Answer: (B), (C)

The triangle formed by the Class-1 points comes closest to the origin at \((1, 1)\), the midpoint of its edge from \((2, 0)\) to \((0, 2)\). The maximum-margin boundary is the perpendicular bisector of the segment from \((0, 0)\) to \((1, 1)\), the line \(x_{1} + x_{2} = 1\). In canonical form (Class-1 as \(+1\)), \(w = (1, 1)^{\top}\) and \(b = -1\): \(w^{\top}x + b\) is 1 at \((2, 0)\) and \((0, 2)\), \(-1\) at \((0, 0)\) and 3 at \((2, 2)\).

  • A fails: \(w = (4, 4)^{\top}\), \(b = 1\) gives every point, \((0, 0)\) included, a positive score, so it does not separate the classes.
  • B holds: \((2, 0)\), \((0, 2)\) and \((0, 0)\) lie on the margin lines; \((2, 2)\) lies beyond them.
  • C holds: the margin lines \(x_{1} + x_{2} = 0\) and \(x_{1} + x_{2} = 2\) are \(\frac{2}{\|w\|} = \sqrt{2}\) apart.
  • D fails: the data are separable, so training accuracy is 100%.

Answer: B, C

GATE DA 2024 | Question 17

MCQ · 1 mark · −0.33

Consider the dataset with six datapoints: \(\{(\boldsymbol{x}_{1}, \boldsymbol{y}_{1}), (\boldsymbol{x}_{2}, \boldsymbol{y}_{2}), \ldots, (\boldsymbol{x}_{6}, \boldsymbol{y}_{6})\}\), where \(\boldsymbol{x}_{1} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\), \(\boldsymbol{x}_{2} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\), \(\boldsymbol{x}_{3} = \begin{bmatrix} 0 \\ -1 \end{bmatrix}\), \(\boldsymbol{x}_{4} = \begin{bmatrix} -1 \\ 0 \end{bmatrix}\), \(\boldsymbol{x}_{5} = \begin{bmatrix} 2 \\ 2 \end{bmatrix}\), \(\boldsymbol{x}_{6} = \begin{bmatrix} -2 \\ -2 \end{bmatrix}\) and the labels are given by \(\boldsymbol{y}_{1} = \boldsymbol{y}_{2} = \boldsymbol{y}_{5} = 1\), and \(\boldsymbol{y}_{3} = \boldsymbol{y}_{4} = \boldsymbol{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?

Options for GATE DA 2024 | Question 17

Explanation

Answer: (D)

Each negative point is the mirror image of a positive one through the origin. Write the separator as \(\boldsymbol{w}^{\top}\boldsymbol{x} + b\) with \(\boldsymbol{w} = (w_{1}, w_{2})\). The hard-margin constraints \(y_{i}(\boldsymbol{w}^{\top}\boldsymbol{x}_{i} + b) \geq 1\) for \(\boldsymbol{x}_{1}\) and \(\boldsymbol{x}_{4}\) read \(w_{1} + b \geq 1\) and \(w_{1} - b \geq 1\), so \(w_{1} \geq 1\); \(\boldsymbol{x}_{2}\) and \(\boldsymbol{x}_{3}\) give \(w_{2} \geq 1\) in the same way. So \(\lVert\boldsymbol{w}\rVert^{2} \geq 2\), and \(\boldsymbol{w} = (1, 1)\), \(b = 0\) reaches this while meeting every constraint, so it is the maximum-margin solution.

For this hyperplane, \(\boldsymbol{x}_{1}\) to \(\boldsymbol{x}_{4}\) give \(y_{i}(\boldsymbol{w}^{\top}\boldsymbol{x}_{i} + b) = 1\): they lie on the margin and are the support vectors. \(\boldsymbol{x}_{5}\) and \(\boldsymbol{x}_{6}\) give 4, well outside the margin, which rules out A, B and C (A even holds points of one class only).

Answer: D