Dual problem
Topic of Support vector machines, part of Statistical learning · Also in Support vector machines
Dual problem
| Type | Topic |
| Taught in | Support vector machines · Support vector machines |
| Part | Statistical learning |
The optimisation over Lagrange multipliers obtained from a constrained primal problem. For the support vector machine the dual depends on the data only through inner products \mathbf{x}_i^\top\mathbf{x}_j, which is what lets a kernel replace them.
In Support vector machines
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}
In Support vector machines, continued
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 1 (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
See also
Kernel · Signed distance · Vapnik’s radius–margin bound · Hard-margin primal · Hard-margin dual · Soft-margin primal · Linear separators and the margin · Distance to a hyperplane