Soft-margin slack variables
Section of Support vector machines, part of Statistical learning
Soft-margin slack variables
| Type | Section |
| Taught in | Support vector machines |
| Part | Statistical learning |
Overlapping classes can make the hard-margin constraints infeasible. Introduce a slack \xi_i\ge 0 to measure how much observation i falls short of functional margin one. The linear penalty C\sum_i\xi_i prices those violations against \tfrac12\lVert w\rVert^2. It leads to a particularly simple change in the dual: each multiplier is bounded above by C. A squared-slack penalty gives a different quadratic term in the dual.
Definition 1 (Soft-margin primal) Find w and b minimising
\Phi(w,\xi)=\frac12 w^\top w+C\sum_{i=1}^{n}\xi_i
subject to y_i(w^\top x_i+b)\ge 1-\xi_i and \xi_i\ge 0 for all i=1,\ldots,n.
Small C gives a relatively strong preference for a small weight norm. Large C places more emphasis on avoiding margin violations. For separable data, a sufficiently large C recovers a hard-margin solution. For inseparable data, increasing C cannot make a nonexistent hard-margin solution appear. Select the trade-off by validation.
Introduce multipliers \alpha_i\ge 0 for the margin constraints and \mu_i\ge 0 for \xi_i\ge 0:
L=\frac12 w^\top w+C\sum_i\xi_i -\sum_i\alpha_i\bigl[y_i(w^\top x_i+b)-1+\xi_i\bigr] -\sum_i\mu_i\xi_i.
The derivatives with respect to w and b are as before, and \partial L/\partial\xi_i=C-\alpha_i-\mu_i=0. Since \mu_i\ge 0 this gives \alpha_i\le C, and the \xi-terms cancel on substitution. The dual problem is identical to the separable case except that the multipliers are bounded:
\begin{aligned} \text{maximise}\quad Q(\alpha)&=\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_j y_i y_j x_i^\top x_j\\ \text{subject to}\quad \sum_i\alpha_i y_i&=0,\qquad 0\le\alpha_i\le C. \end{aligned}
With squared slack, stationarity gives a relation involving \xi_i rather than the same constant upper bound on \alpha_i. The issue is the changed objective. In the linear-slack problem, nonzero \alpha_i identify support vectors, and
w=\sum_i\alpha_i y_i x_i, \qquad b=y_k(1-\xi_k)-\sum_i\alpha_i y_i x_i^\top x_k \quad\text{for any }k\text{ with }\alpha_k>0,
and f(x)=\sum_i\alpha_i y_i x_i^\top x+b, with no need to compute w explicitly. In the intercept formula, \xi_k is not known in advance. Complementary slackness gives \mu_k\xi_k=0, and \mu_k=C-\alpha_k>0 whenever \alpha_k<C, so \xi_k=0 for any k with 0<\alpha_k<C. Such a margin support vector gives b=y_k-\sum_i\alpha_i y_i x_i^\top x_k, as in the separable case.
What the multipliers say
Main article: Support vectors and their multipliers
Complementary slackness gives three cases for a training point.
| Multiplier | Position | Slack |
|---|---|---|
| \alpha_i=0 | y_i f(x_i)\ge 1: outside the margin or on it, correctly classified | \xi_i=0 |
| 0<\alpha_i<C | y_i f(x_i)=1: exactly on the margin, a free support vector | \xi_i=0 |
| \alpha_i=C | y_i f(x_i)\le 1: inside the margin or misclassified, a bound support vector | \xi_i=1-y_i f(x_i)\ge 0 |
Only points on or inside the margin influence the fit. On one overlapping Gaussian sample, a linear fit at C=0.03 uses a wide slab and many support vectors, a fit at C=1 tightens the slab, and a fit at C=100 hugs the overlapping points. The rings in such a picture are the points with nonzero multipliers.
The hinge loss
Main article: Hinge loss
At the optimum each \xi_i is as small as the constraints allow, so \xi_i=\max\{0,\,1-y_i f(x_i)\}. Substituting that value removes the slacks and leaves
\sum_{i=1}^{n}\max\{0,\,1-y_i f(x_i)\}+\frac{1}{2C}\lVert w\rVert^2,
a hinge loss plus a ridge penalty on w. Compare weight decay on networks in practice. The hinge is zero once the margin exceeds 1: a point that is correctly classified and far from the boundary does not pull the fit. Squared error would keep pulling. The binomial deviance penalises errors roughly linearly, as the hinge does, and it never becomes exactly zero. The factor 1/(2C) plays the role of the regularisation parameter \lambda in weight decay: small C is strong regularisation.
Used in
See also
Signed distance · Vapnik’s radius–margin bound · Hard-margin primal · Hard-margin dual · Soft-margin primal · Kernel · Linear separators and the margin · Distance to a hyperplane