Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 218 / 4

For $X_i^{\ast }=(1,X_i^T{)}^T$ and $\gamma =({\gamma }_0,{\beta }^T{)}^T$, a linear support vector machine predictsOne penalized formulation minimizes empirical hinge loss plus a squared Euclidean norm penalty:Conventions often leave the intercept unpenalized, replacing $\Vert \gamma {\Vert }_2^2$ by $\Vert \beta {\Vert }_2^2$; this does not change the role of the two terms.

A separating hyperplane for signed data satisfies $Y_i({\gamma }_0+X_i^T\beta )>0$ for every $i$; its geometric set is $\{x:{\gamma }_0+x^T\beta =0\}$. The plot marks three support vectors. At the shown fit they lie on the two support-vector-machine margin boundaries, so their signed functional margins satisfyThe solid line is the decision hyperplane $X^{\ast T}\hat{\gamma }=0$, while the dashed parallel lines are $X^{\ast T}\hat{\gamma }=1$ and $X^{\ast T}\hat{\gamma }=-1$.

If $\lambda =0$, every parameter vector with all margins at least one has zero hinge loss. Scaling or changing a separating vector can therefore give another minimizer, so the objective need not select the displayed maximum-margin direction or the same three lines. Positive quadratic regularization selects a finite, minimum-norm compromise.

This is a normalized perceptron algorithm. Because $\Vert Z_i{\Vert }_2=1$, an update on a misclassified point obeysHere the two inequalities use the update condition $Y_i{Z}_i^T{\gamma }^{(m)}\le 0$ and the assumed unit margin $Y_i{Z}_i^T\hat{\gamma }\ge 1$. A squared distance cannot become negative, so there can be at most $\Vert {\gamma }^{(0)}-\hat{\gamma }{\Vert }_2^2$ updates. The algorithm then returns a vector that correctly separates every training point. The estimate $\hat{\gamma }$ is the comparison vector for the proof; without an additional uniqueness condition the returned separator need not equal that particular vector.

A binary logistic regression setsand classifies by the sign of ${\gamma }_0+x^T\beta$. Its unpenalized maximum-likelihood estimator minimizes the empirical logistic lossThe plotted data are complete separation data: there is a vector $v$ with every signed margin $Y_i{X}_i^{\ast T}v>0$. For every finite $c>0$, increasing $c$ strictly decreases each term of $L(cv)$, and $L(cv)\to 0$ as $c\to \infty$. No finite parameter attains zero, so the unpenalized optimization has no solution.

Adding an $L^2$ penalty $\lambda \Vert \gamma {\Vert }_2^2$ with $\lambda >0$, constraining $\Vert \gamma {\Vert }_2$, or using a finite stopping rule makes the problem attain a finite approximate solution. The penalized option is preferable because cross-validation can select the strength of regularization.