2
$\begingroup$

Consider the the optimization program of the kernelized SVM:

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^TQ\alpha$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

where for the matrix $Q$, we have: $Q_{ij}=y_iy_j\text{kernel}(x_i,x_j)$.

This optimization program is resulted by taking the dual of the hinge-loss-based SVM with $L_2$ regularization.

Now here is my question: Why no body regularizes $\alpha$ in this optimization program?

I understand that $\alpha$ is just the dual variables' vector, but I'm really curious to know why people have not tried regularizing $\alpha$.

For example, if for what ever reasons we want to force the algorithm to introduce less support vectors, then adding an $L_1$ regularization on $\alpha$ would be usefull right?

I.e.,

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^TQ\alpha-\|\alpha\|_1$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

Or maybe, a Tikhonov regularization:

$$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^T(Q+\gamma I)\alpha$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$

I appreciate it if you share any comments that you might have.

$\endgroup$
3
$\begingroup$

From a regularization point of view, SVM is a special case of Tikhonov regularization using hinge loss. We are already inducing sparsity in the $\alpha$ vector by using hinge loss, i.e. the sum of slack variables $\xi$ in the primal:

$$\begin{align} \min_{\alpha, b,\xi}\quad &\frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^N \xi_i, \\ s.t.\quad&y_i\big(\langle\mathbf{w},\varphi(\mathbf{x}_i\rangle +b\big) \geq 1- \xi_i,\quad \forall i. \end{align}$$

You can see this by working out the primal Langrangian (which is being minimized): $$ L_p = \frac{1}{2}||\mathbf{w}||^2+C\sum_{i=1}^n\xi_i -\sum_{i=1}^n\alpha_i\Big[y_i\big(\langle\mathbf{w},\varphi(\mathbf{x}_i)\rangle+b\big)-(1-\xi_i)\Big]-\sum_{i=1}^n\mu_i\xi_i. $$ Some of the optimality conditions are: $$\begin{align} \frac{\partial L_p}{\partial \xi_i}=0 \quad \rightarrow \quad &\alpha_i=C-\mu_i, \quad \forall i, \\ \frac{\partial L_p}{\partial \mathbf{w}}=0\quad \rightarrow \quad &\mathbf{w}=\sum_{i=1}^n \alpha_i y_i \varphi(\mathbf{x}_i),\quad \forall i, \end{align}$$ Which leads to $\xi_i = 0 \rightarrow \mu_i = C \rightarrow \alpha_i = 0$: instances $i$ that are correctly classified ($\xi_i=0$), already have a dual weight $\alpha_i=0$ and $\xi$ is essentially $L_1$-regularized.

Adding regularization in the dual would inevitably change the solution and will result in a classifier that is no longer maximum-margin, which is one of the key reasons SVM is so popular.

This is one of the key differences between SVM and LS-SVM (which uses the sum of squares of (regression) errors and therefore loses sparsity in $\alpha$).

$\endgroup$
  • 1
    $\begingroup$ Could you elaborate on this a little bit: "Adding regularization in the dual would inevitably change the solution and will result in a classifier that is no longer maximum-margin". Here is my concern: sure, we have $L_1$ regularization on $\xi_i$'s in the primal, but penalizing the primal by different regularization functions shouldn't hurt either? E.g. if you want to allow large margins, you could use other M-estimator penalties on $\xi$'s. What do you think? $\endgroup$ – Alt Feb 1 '15 at 19:22
  • 1
    $\begingroup$ @Alt that's an interesting idea for sure, though at a glance I fear that a lot of M-estimators would result in non-convex cost functions (not sure about that, though ... I should probably think it over more). $\endgroup$ – Marc Claesen Feb 1 '15 at 19:36
  • $\begingroup$ Convexity is a separate issue. Since $L_1$ works well, I guess Huber (among the convex ones) would also work well (if not better); although the optimization will be computationally less efficient for sure. $\endgroup$ – Alt Feb 2 '15 at 8:05

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.