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

In the terminology used for positive-definite kernels, positive definiteness means positive semidefiniteness of every finite kernel matrix: $k$ is symmetric and, for every $m$, points $x_1,\dots ,x_m$ and real $c_1,\dots ,c_m$,The linear kernel is symmetric, andThus it is a positive-semidefinite kernel, with the identity as its feature map. It need not be strictly positive definite: a zero vector or linearly dependent points can make this quadratic form zero for nonzero $c$. This distinction is essential when interpreting the terminology.

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.

Choose a candidate grid of $C>0$. For each candidate and each $i$, fit the soft-margin support vector machine to all observations except $i$, keeping exactly the same $C$ in the unnormalized sum objective. Let $f_{-i,C}$ be its fitted score. Use a fixed rule for assigning a label when the score is zero. The binary misclassification estimate from Leave-one-out cross-validation isChoose a minimizing candidate, break tuning ties by a predetermined rule, and refit on all $n$ observations. Any estimated preprocessing must also be fitted inside each training fold to avoid data leakage. If a normalized average-loss parameterization is used instead, translate its parameter so that the same $C$ is retained when the sample size decreases.

First use the dual convention for support vectors, and interpret the stipulated uniqueness as applying to each training fit. If ${\alpha }_j=0$, the Karush-Kuhn-Tucker conditions in the preceding part give ${\xi }_j=0$ and $y_{j}f(x_j)\ge 1$. Delete the $j$th primal variable and its zero dual coefficient. All remaining primal constraints, stationarity equations and complementary-slackness equations still hold with the same $w,b$. These conditions certify a global minimizer of the reduced convex optimization problem, since the objective is convex and the Slater condition holds by choosing positive large slacks. Uniqueness therefore gives exactly the same fitted score and support-vector-machine decision boundary. The omitted point is correctly classified.

For the geometric convention, a non-support point has strict margin $y_{j}f(x_j)>1$. One can obtain the same conclusion using just uniqueness of the full fit: if the reduced problem had another optimizer, the convex segment from the original optimizer toward it would also consist of reduced optimizers. A sufficiently short segment retains strict margin at $j$, hence has zero omitted hinge loss and would give another full optimizer, a contradiction.

Only a support vector can therefore cause a held-out error. Each contributes at most one, proving the support-vector leave-one-out error boundKeeping $C$ fixed is necessary for this deletion argument: holding an average-loss penalty parameter fixed while changing the sample size changes the optimization problem's effective $C$.