Hard-margin support vector machine
Section of Support vector machines, part of Statistical learning
Hard-margin support vector machine
| Type | Section |
| Taught in | Support vector machines |
| Part | Statistical learning |
| Questions using it | 3 |
For linearly separable data there are no slack variables. The construction chooses the orientation of the hyperplane so that the gap is as large as possible, with the support vectors on the boundary of that gap. The algebra that turns the largest gap into the smallest \lVert w\rVert is the derivation below. A factor \tfrac12 in front of \lVert w\rVert^2 does not move the hard-margin minimiser. It makes the derivative of the objective equal to w, which is the form the Lagrange multiplier step wants.
Let the training set \{(x_i,y_i)\}_{i=1}^{n}, with x_i\in\mathbb{R}^p and y_i\in\{-1,1\}, be separated by a hyperplane with margin \rho. Take a linear classifier with \lVert w\rVert=1. Then for each training example,
\begin{aligned} w^\top x_i+b&\le -\rho/2 &&\text{if }y_i=-1,\\ w^\top x_i+b&\ge \rho/2 &&\text{if }y_i=1, \end{aligned}
which is the same statement as y_i(w^\top x_i+b)\ge\rho/2. The constraint is a Euclidean width only together with a convention for \lVert w\rVert. With \lVert w\rVert=1, \rho is the full distance between the parallel planes y(w^\top x+b)=\pm\rho/2. Without that normalisation the same algebra describes the width \rho/\lVert w\rVert.
For every support vector x_s the inequality is an equality. After rescaling, dividing w and b by \rho/2, which does not alter the decision boundary, the distance between each x_s and the hyperplane is
r=\frac{y_s(w^\top x_s+b)}{\lVert w\rVert}=\frac{1}{\lVert w\rVert},
and the new margin is \rho'=2r=2/\lVert w\rVert in terms of the rescaled w and b, with constraints y_i(w^\top x_i+b)\ge 1. Maximising 2/\lVert w\rVert is equivalent to minimising \lVert w\rVert^2.
Definition 1 (Hard-margin primal) Find w and b such that \Phi(w)=\tfrac12 w^\top w is minimised subject to
y_i(w^\top x_i+b)\ge 1,\qquad i=1,\ldots,n.
An equivalent convention writes the objective as w^\top w without the factor \tfrac12, and in the soft-margin case as w^\top w+C\sum_i\xi_i, while quoting the dual Q(\alpha)=\sum_i\alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j x_i^\top x_j and the solution w=\sum_i\alpha_i y_i x_i. Those correspond to the objective \tfrac12 w^\top w used here. In the separable case the factor does not change the minimiser, so the two forms are equivalent. In the soft-margin case it only rescales C: minimising w^\top w+C\sum_i\xi_i gives w=\tfrac12\sum_i\alpha_i y_i x_i with 0\le\alpha_i\le C, which equals the \tfrac12 w^\top w+C'\sum_i\xi_i problem with C'=C/2. The factor \tfrac12 is used so that the primal and the dual match.
The feasible set is convex and the objective is strictly convex in w. Thus the optimal weight vector is unique when the hard-margin problem is feasible, and every local optimum is global. Strict convexity in w does not establish uniqueness of all dual multipliers: several representations can give the same vector. The intercept is also unpenalised. These distinctions matter when comparing numerical output from different solvers.
The dual
Main article: Hard-margin dual
The primal minimises a quadratic in w subject to one linear inequality per training point. Associate a Lagrange multiplier \alpha_i\ge 0 with each inequality. The Lagrangian is
L(w,b,\alpha)=\frac12 w^\top w-\sum_{i=1}^{n}\alpha_i\bigl[y_i(w^\top x_i+b)-1\bigr].
Set the derivatives in the primal variables to zero:
\frac{\partial L}{\partial w}=w-\sum_{i=1}^{n}\alpha_i y_i x_i=0 \quad\Rightarrow\quad w=\sum_{i=1}^{n}\alpha_i y_i x_i,
\frac{\partial L}{\partial b}=-\sum_{i=1}^{n}\alpha_i y_i=0 \quad\Rightarrow\quad \sum_{i=1}^{n}\alpha_i y_i=0.
Substitute back. Then \tfrac12 w^\top w=\tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j x_i^\top x_j, the linear term \sum_i\alpha_i y_i w^\top x_i equals that same double sum, and b\sum_i\alpha_i y_i=0. What remains is a function of the multipliers alone.
Definition 2 (Hard-margin dual) \begin{aligned} \text{maximise}\quad Q(\alpha)&=\sum_{i=1}^{n}\alpha_i-\frac12\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j x_i^\top x_j\\ \text{subject to}\quad \sum_{i=1}^{n}\alpha_i y_i&=0,\qquad \alpha_i\ge 0. \end{aligned}
This is again a quadratic programme, now in \alpha. It is concave, since the matrix (y_i y_j x_i^\top x_j) is positive semi-definite.
The Karush–Kuhn–Tucker conditions include complementary slackness, \alpha_i\bigl[y_i(w^\top x_i+b)-1\bigr]=0 for every i. So either \alpha_i=0, or y_i(w^\top x_i+b)=1, that is, x_i lies exactly on the margin. Each nonzero \alpha_i therefore identifies a support vector, and
w=\sum_i\alpha_i y_i x_i, \qquad b=y_k-\sum_i\alpha_i y_i x_i^\top x_k \quad\text{for any }k\text{ with }\alpha_k>0.
For a support vector, y_k(w^\top x_k+b)=1, and since y_k^2=1, b=y_k-w^\top x_k. The classifying function is
f(x)=\operatorname{sign}\Biggl(\sum_i\alpha_i y_i x_i^\top x+b\Biggr),
and one does not need w explicitly. It relies on an inner product between the test point x and the support vectors x_i, and solving the optimisation problem involved the inner products x_i^\top x_j between all training points. Both facts are the key to nonlinear support vector machines.
Strong duality holds: at the optimum Q(\alpha)=\tfrac12\lVert w\rVert^2. Strong duality is the convexity of the programme together with the existence of a strictly feasible point when the classes are linearly separable with a positive margin. The dual maximum equals the primal minimum. Complementary slackness identifies the support vectors. A multiplier that is zero drops its training point out of w.
Example 1 (Three points) Question. Find the maximum-margin separator of x_1=(1,0) with y_1=-1 and x_2=(3,1), x_3=(3,-1) with y_2=y_3=+1.
Solution. By symmetry, guess that all three are support vectors, so each constraint is an equality:
-(w_1+b)=1,\qquad 3w_1+w_2+b=1,\qquad 3w_1-w_2+b=1.
The last two give w_2=0, and then 3w_1+b=1 with w_1+b=-1 gives w_1=1, b=-2. So w=(1,0)^\top, the boundary is x_1=2, and the margin is \rho=2/\lVert w\rVert=2.
To find \alpha use w=\sum_i\alpha_i y_i x_i:
-\alpha_1(1,0)+\alpha_2(3,1)+\alpha_3(3,-1)=(1,0)
gives \alpha_2=\alpha_3 and -\alpha_1+6\alpha_2=1. The constraint \sum_i\alpha_i y_i=0 gives -\alpha_1+2\alpha_2=0. Hence \alpha_1=2\alpha_2 and 4\alpha_2=1, so \alpha=\bigl(\tfrac12,\tfrac14,\tfrac14\bigr)>0. All three are support vectors. The dual objective is Q=1-\tfrac12\lVert w\rVert^2=\tfrac12, equal to the primal value \tfrac12\lVert w\rVert^2=\tfrac12. Checking the intercept formula, b=y_1-\sum_i\alpha_i y_i x_i^\top x_1=-1-(1,0)\cdot(1,0)=-2. Primal feasibility, dual feasibility, and equality of the two objectives certify the proposed optimum.
Used in
- Taught in Support vector machines
- Questions that use it (3) — A two-point machine · Read the geometry · A unit-norm constraint (answer)
- All 10 questions on Support vector machines
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