1
$\begingroup$

I have a question regarding SVM. I understand the Lagrange equation,

$L(w,b,\alpha) = \frac{1}{2}w'w - \sum_i \alpha_i (y_i(w'x_i+b)-1)=$

$\frac{1}{2}w'w - \sum_i \alpha_i y_i(w'x_i+b)+ \sum_i \alpha_i$

and that taking the derivative to $b$ and $w$ gives

$\frac{\partial L}{\partial b} = \sum_i \alpha_i y_i=0$

$\frac{\partial L}{\partial w} = w - \sum_i \alpha_i y_i x_i=0 \rightarrow w =\sum_i \alpha_i y_i x_i$

Filling this in the Lagrange gives

$L(\alpha)=\frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i' x_j + \sum_i{\alpha_i} $

But this is not how SVM fills in the Lagrange and I like to understand why.

After some time I saw that

$L(w,b,\alpha) = \frac{1}{2}w'w - \sum_i ((w'\alpha_i y_i x_i+\alpha_i y_i b)-\alpha_i y_i)=$

$\frac{1}{2}w'w - \sum_i ((w'w+\alpha_i y_ib)-\alpha_i y_i)$,

which then can be rewritten as the familiar dual problem.

$L(\alpha)=-\frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i' x_j + \sum_i{\alpha_i} $

But what is wrong, or what is the disadvantage of, the first representation?

$\endgroup$
  • $\begingroup$ Has dontloo answered your question? $\endgroup$ – Franck Dernoncourt Jan 10 '17 at 2:37
1
$\begingroup$

It seems there's a minus sign missing in the "Filling this in the Lagrange" step .

I got something like $$L = \frac{1}{2}w'w - \sum_i \alpha_i (y_i(w'x_i+b)-1)$$ $$=\frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i' x_j-\sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i' x_j- b\sum_i \alpha_i y_i + \sum_i{\alpha_i} $$ $$=-\frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i' x_j+\sum_i{\alpha_i} $$ which is the same as the other representation.

$\endgroup$
  • $\begingroup$ In the first case I use the fact that $\alpha_i y_i=0$, which is a condition that is derived. Filling in this condition gives the first equation right? Edit never mind stupid me. I see the mistake $\endgroup$ – Immer May 31 '16 at 9:02
  • $\begingroup$ @Immer ok saw the edit, cheers $\endgroup$ – dontloo May 31 '16 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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