2
$\begingroup$

Consider SVM classification: $y_i \in \{+1,-1\} $ are labels, $\mathbf{x}_i$ are covariates ($i=1\ldots N$).

Let $K(\cdot,\cdot)$ be the kernel function, whose corresponding feature mapping is $h(\mathbf{x})$ with dimension $p$.

SVM would provide solution as $\hat{f}(\mathbf{x})= \sum_{i=1}^N{\alpha_i K(\mathbf{x}_i,\mathbf{x})}+b $. With $\mathbf{\alpha} \ \mbox{and}\ b$, there are in total $N+1$ parameter to be optimized.

Now consider the case where $N$ is very big, but the kernel is simple (eg. low order polynomial) leading to comparatively small $p$. Would it be simpler if we just forget about the kernel and optimize:

$$ \min_{\beta,b} \sum_{i=1}^N{ \big( 1-y_i(h(\mathbf{x}_i)^T\beta+b) \big) _+ } +\lambda||\beta ||^2$$

$\endgroup$
1
  • $\begingroup$ Note that the constant $b$ can be computed when the $\alpha_i$ are known, so there are $N$ parameters. $\endgroup$
    – user83346
    Aug 19, 2015 at 14:26

1 Answer 1

4
$\begingroup$

It sounds like you're asking why we always solve the dual SVM problem instead of the primal. The answer is regularization. Without the regularization term, the primal QP would have $k + 1$ variables and $N$ inequality constraints, where as the dual QP would have $N$ variables, $N$ inequality constraints and $1$ equality constraint. So you're correct that it should be faster to solve the primal QP, assuming $k < N$.

However, once you add the regularization term, this is no longer true. With the regularization term, the primal QP has $N + k + 1$ variables and $2N$ inequality constraints but the dual QP has $N$ variables, 1 equality constraint and $2N$ inequality constraints. Moreover, those $2N$ inequality constraints are actually box constraints on the variables, so only half can ever be active at the solution.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! I wanted to up-vote, but I don't have enough reputation yet.... without regularization, how's the perceptron algorithm compared to QP? $\endgroup$
    – Lii
    Aug 19, 2015 at 21:44
  • 1
    $\begingroup$ Sorry I didn't answer you sooner - I'm kind of new to StackExchange. Anyway, the only way you can really consider a classification algorithm without regularization is if the data are separable. Because this is usually an unrealistic assumption, we almost always use regularization. But since you asked: The perceptron model is almost identical to the SVM model. They have the same number of variables and constraints regardless of whether or not you use regularization. The big difference is that the perceptron problem is a linear program whereas the SVM problem is a quadratic program. $\endgroup$ Aug 25, 2015 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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