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?
Answer
(D)
Explanation
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