3
$\begingroup$

Here is the dual problem for L2 support vector machine: $$\max_{\alpha\in\mathbb{R}^{n}} 2\alpha^{T}y-\alpha^{T}\left(K+n\lambda Id_{\mathbb{R}^{n}}\right)\alpha$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\alpha_{i}y_{i} \geq0$$

However, using the Lagrangian formulation, I get the following. Is there an argument missing? $$\max_{\mu\in\mathbb{R}^{n},\nu\in\mathbb{R}^{n}} \sum_{i=1}^{n}\mu_{i}-\frac{1}{4\lambda}\sum_{i=1}^{n}\sum_{j=1}^{n}\mu_{i}y_{i}\mu_{j}y_{j}K\left(x_{i},x_{j}\right)-\frac{n}{4}\sum_{i=1}^{n}\left(\mu_{i}+\nu_{i}\right)^{2}$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\mu_i\geq0$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\nu_i\geq0$$

Edit:

We want the max, which explains $\nu=0$.

$\endgroup$
  • $\begingroup$ I have updated your question with your "answer"; was this really an answer or just a comment? $\endgroup$ – chl Mar 9 '11 at 10:11
  • $\begingroup$ @chl I asked the question, although I almost had the result: I was not aware at the time I asked, sorry. Having $\nu=0$ gives the result since there is a special link between $\alpha$ and $\mu$. There were more details in my first edit about this point (I edited as I did not want to give the whole solution away, with respect to the professor who gave the homework, due for today). $\endgroup$ – Wok Mar 9 '11 at 16:20
3
$\begingroup$

The initial problem is: $$\min_{f\in H}\frac{1}{n}\sum_{i=1}^{n}\phi\left(y_{i}f\left(x_{i}\right)\right)+\lambda\left\Vert f\right\Vert _{H}^{2}$$ $$\lambda\geq0$$ $$\phi\left(u\right)=\max\left(1-u,\,0\right)^{2}$$


Since, $f=\sum_{i=1}^{n}\alpha_i K_{x_i}$ and we are considering a RKHS, the primal problem is: $$\min_{\alpha\in\mathbb{R}^{n},\zeta\in\mathbb{R}^{n}}\frac{1}{n}\sum_{i=1}^{n}\zeta_{i}^{2}+\lambda\alpha^{T}K\alpha$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\zeta_{i}\geq0$$ $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\zeta_{i}-1+y_{i}\left(K\alpha\right)_{i}\geq0$$


Using Lagrangian multipliers, we get the result mentioned in the question. The computations are right: $\nu=0$ gives the result we want to achieve since there is a special link between $\alpha$ and $\mu$, thanks to the Lagrangian formulation: $$\forall i\in\left\{ 1,\ldots,n\right\} ,\,\alpha_{i}^{*}=\frac{\mu_{i}y_{i}}{2\lambda}$$ where: $$\forall i\in\left\{ 1,\ldots,n\right\} ,\, y_i\in\left\{ -1,1\right\}$$


Why is $\nu=0$? Of course, $\nu=0$ since:

  • there is only one term depending on $\nu$
  • we want the max
  • $\mu$ and $\nu$ are positive.
$\endgroup$

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.