1
$\begingroup$

I have this confusion related to L1 and L2 svm. It is given in this paper that

The dual problem is given by

$$ min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha $$ subject to

$$ 0 <= \alpha_i <= U $$

$$ \hat Q = Q+D $$ D is a diagonal matrix and $Q_{ij}=y_iy_jx_i^Tx_j$. For L1 SVM U=C and $D_{ii}=0$. For L2 SVM U=inf and $D_{ii}=1/2C$

I didn't get what this U term is and why is in the case of L2 SVM U=inf and $D_{ii}=1/2C$. How was it derived?

This is how I tried to derive it but I think I am making certain mistake

$L(w,b,\zeta,\alpha,\gamma) = \frac{1}{2}||w||^2 + C\sum_i\zeta^2 - \sum_{i}\alpha_i(y^{(i)}(w^Tx^{(i) } +b)-1+\zeta_i) - \sum_{i}\gamma_i\zeta_i $

Differentiating with respect to $w,\zeta$ and b

$w=\sum_i\alpha^{(i)}y^{(i)}x^{(i)}$

$\sum_i\alpha_iy^{(i)} = 0$

$2C\zeta_i = \alpha_i + \gamma_i$

Now when I substitute these values into the objective function I get

$-\frac{1}{2}||w||^2 + \sum_i\alpha_i-C\sum_i\zeta^2)$

I don't get the expression as given in the paper. I know I am pretty close but I think I am screwing up somewhere. Can anyone give some suggestion where I am wrong?

$\endgroup$
  • 1
    $\begingroup$ You should write out the dual mechanically by using the Lagrangian (Boyd's book on convex optimization explains this step by step process quite well). $\endgroup$ – Suresh Venkat Apr 20 '13 at 7:13
  • $\begingroup$ Is svm "singular value method"? $\:$ $\endgroup$ – user6973 Apr 21 '13 at 2:09
  • $\begingroup$ @SureshVenkat I tried to derive it myself. However, I think I am making certain mistake. I have edited the post showing what I have tried. Can you provide some suggestions where I am wrong? I know if I manipulate some of the terms I will get it. $\endgroup$ – user34790 Apr 23 '13 at 23:31
  • 1
    $\begingroup$ @RickyDemer in this context SVM = support vector machine $\endgroup$ – Austin Buchanan Apr 24 '13 at 4:55
  • $\begingroup$ You forgot to substitute for $\|w\|^2$. that will recover the quadratic term in $\alpha$ $\endgroup$ – Suresh Venkat Apr 24 '13 at 6:16