6
$\begingroup$

The Lagrangian of a hard-margin SVM is: $$ L(w, b, \alpha)=\frac{1}{2}||w||^2 - \sum_{i}\alpha_i[y_i(\langle w, x_i\rangle)+b)-1] $$

It can be shown that: $$ w=\sum_{i}\alpha_iy_ix_i $$ $$ \sum_i \alpha_iy_i=0 $$

We derive the dual by substituting the second group of equations into the first. Most textbooks (sensibly) skip to the final expression: $$ -\frac{1}{2}\sum_{i}\sum_j \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle + \sum_i \alpha_i $$

but I want to work this out in detail myself and am really struggling with the substitution of $w$. Could someone please post a detailed guide to computation?

$\endgroup$

1 Answer 1

11
$\begingroup$

First, let's calculate the norm $||w||^2$.

$$||w||^2 = \sum_i \alpha_iy_i\big(\sum_j\alpha_jy_j\langle x_i,x_j\rangle\big)$$

which evidently can be rearranged to $\sum_i\sum_j\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle$.

The $\langle x_i, x_j\rangle$ construct is present because it's assumed that the norm is defined in terms of the inner product - every inner product induces a norm by the formula $||z||^2 = \langle z,z \rangle$ - so when we calculate $||w||^2$ (making the desired substitution from above) we use $\langle x_i,x_j \rangle$. The reason we don't get something like:

$$\sum_i \sum_j \langle \alpha_i y_i x_i, \alpha_j y_j x_j \rangle$$

is because the inner product is defined on $x$, and everything else is just a scalar multiplier, so, by basic properties of inner products, can get moved outside of the $\langle \rangle$.

Now, substituting into $\sum_i\alpha_i[y_i(\langle w, x_i\rangle+b)-1]$ can be done in parts:

$$\sum_i\alpha_i[y_i(\langle w, x_i\rangle+b)-1] = \sum_i\alpha_iy_i\langle w, x_i\rangle + b\sum_i\alpha_iy_i - \sum_i\alpha_i$$

The last term on the r.h.s. evidently equals $-\sum_ia_i$, and the middle term equals $0$, as the second constraint is that $\sum_i\alpha_iy_i = 0$. Substituting in for the first term gives:

$$\sum_i\alpha_iy_i\langle w, x_i\rangle =\sum_i\alpha_iy_i\langle \sum_j\alpha_jy_jx_j, x_i\rangle = \sum_i\sum_j\alpha_iy_i\alpha_jy_j\langle x_i, x_j \rangle$$

where the step to the last term is by basic properties of inner products.

Having gotten this far, we need to (remember to) a) multiply $||w||^2$ by $1/2$, b) multiply the long second term by $-1$, and c) combine them:

$${1\over 2}\sum_i \sum_j \alpha_iy_i\alpha_jy_j\langle x_i,x_j\rangle - \sum_i \sum_j \alpha_iy_i\alpha_jy_j\langle x_i,x_j\rangle - 0 + \sum_i\alpha_i $$

which evidently reduces to the desired result

$$-{1\over 2}\sum_i \sum_j \alpha_iy_i\alpha_jy_j\langle x_i,x_j\rangle + \sum_i\alpha_i $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.