2
$\begingroup$

Consider the SVM dual, i.e., \begin{align} &\text{maximize} \sum_{i=1}^n \alpha_i-\frac{1}{2\lambda} \sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j K(x_i,x_j)\cr &\text{subject to, } 0\leq \alpha_i \leq 1 \end{align} where $K$ is the kernel matrix and $\lambda$ is the regularization parameter.

My questions are:

  • What is the meaning of $\sum_{i=1}^n \alpha_i$?
  • When this value is equal to $n$, Can we say that model is
    underfitted?
  • Is it meaningful to add this constraint $\sum_{i=1}^n \alpha_i<n-t$
    with $t$ a parameter, to the above problem?
  • If yes, what is this constraint in the primal?
$\endgroup$
1
$\begingroup$

From strong duality, it's easy to see that $$ \sum_{i=1}^n \alpha_i = \frac{\lambda^2 + 1}{2\lambda}||w||^2 + L(w) $$ where $L(w)$ in your formulation is $\sum_{i=1}^n \max\{0, 1- y_i w^T x_i\}$.

If this value is equal to $n$, then you are no better than the case where $w=0$. So this is basically the null-case where you haven't really learned anything (and underfitted would seem to be apt).

Adding such a constraint is odd - one already has $\lambda$ in place to handle the tradeoff between model complexity and error. This constraint may be effective in finding a sparser solution (i.e., fewer support vectors) - of course, there is also the problem that the problem may not be solvable (i.e., for $t$ which is too large you have no solution). But there exist a large body of work already on finding sparse solutions to SVM which are well motivated - this constraint is not. Also adding in this constraint may alter the expression for $w$ itself, so it's not entirely clear what the end result would be.

Adding an additional constraint in the dual will result in a new variable in the primal, and the primal objective will look different. It's largely a mechanical process to transform from dual -> primal, but someone else (or perhaps OP) can do that.

$\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.