Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 218 / 2 / b

Fix $C>0$ and use the unnormalized sum convention for the penalty. The linear soft-margin support vector machine solvesEliminating the slack variables of a support vector machine gives $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i\max \{0,1-y_{i}f(x_i)\}$, where $f(x)=w^{T}x+b$ and the maximum is the hinge loss. The classifier uses the sign of $f$ and its support-vector-machine decision boundary is $f=0$.

For clarity about dual support vectors and margin degeneracy, let ${\alpha }_i$ be the multipliers of the margin constraints. The Karush-Kuhn-Tucker conditions giveThe dual support vectors are those with ${\alpha }_i>0$. A coefficient strictly between $0$ and $C$ puts a point exactly on its margin boundary; a point with positive slack has ${\alpha }_i=C$. A zero coefficient implies zero slack and signed margin at least one. Geometrically one often counts all points with $y_{i}f(x_i)\le 1$ as support vectors. At a degeneracy, equality can occur with ${\alpha }_i=0$, so the two descriptions need not coincide. Either convention supports the bound in the following part when stated consistently.