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?
Answer
(B), (C)
Explanation
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