3
$\begingroup$

$\newcommand{\loss}{\operatorname{loss}}$Recently I am surveying different SVM optimization algorithms. I came across a strange scenario:

When we formulate the SVM primal problem like the following, $$\min_w \frac{1}{2}w^Tw + C\sum_{i=1}^{m}\loss(w, x_i, y_i),$$ $$\text{such that }\quad y_i(w^Tx_i + b) \ge 1 - c_i,$$ because of the linear constraint, we will have the following constraint in the dual formulation: $$\alpha^Ty = 0,$$ and this means that we need to optimize at least two variables at a time.

But some papers will formulate the SVM problem in the unconstrained version, simply: $$\min_w \frac{1}{2}w^Tw + C\sum_{i=1}^{m}\loss(w, x_i, y_i).$$ Then because we no longer have the linear constraint, we can apply method such as coordinate descent, which updates only one variable at a time.

I am confused, what is the difference between these two formulations of SVM?

$\endgroup$
3
$\begingroup$

Note that generally, the loss$(w,x_i,y_i)$ term you have written would actually be the $c_i$ value from the constraint, in both versions.

The dual-formulation constraint $\alpha^T y = 0$ arises from the bias term $b$ which offsets the solution plane from the origin. The most common alternative to using the bias term is extending all the inputs $x_i$ by adding on a dimension with constant value $1$. A less commonly used approach is to use a slightly modified kernel function formulation to replicate $b$ (i.e., so that calculating $<w,x>_{k'}$ with the modified kernel $k'$ is similar to evalutating $<w,x>_k + b$ with the original kernel).

From a practical perspective, there is little difference in the classifier performance between biased and unbiased SVM. Specific algorithms differ of course, and the time it takes to learn a classifier can be different. From a theoretical perspective, it is often easier to determine bounds for the unbiased version.

$\endgroup$
  • $\begingroup$ What if I do not add one more dimension? Does that mean that my SVM will pass through the origin? Will the performance be a lot worse? $\endgroup$ – Louis Kuang Nov 17 '16 at 12:36
  • $\begingroup$ When you remove the bias term, the SVM hyperplane will always pass through the origin in kernel space. Adding an additional dimension gives another degree of freedom (roughly equivalent to the bias term, although note that in the biased SVM formulation the $b$ term is not included in the normalization, yet, for unbiased SVM, this additional degree of freedom may show up in the normalization - for example, with a linear kernel, $w$ grows by 1-dimension and the value for $w^Tw$ will increase as a result). $\endgroup$ – MotiN Nov 17 '16 at 12:42
  • $\begingroup$ So the bias b represents some sort of prior knowledge? But we will change it after we get the optimal w right? $\endgroup$ – Louis Kuang Nov 17 '16 at 12:44
  • $\begingroup$ See jmlr.org/papers/volume12/steinwart11a/steinwart11a.pdf for some early work. In terms of prediction accuracy, there isn't much difference between the two. In terms of learning speed, one can often learn without a bias faster. $\endgroup$ – MotiN Nov 17 '16 at 12:45
  • $\begingroup$ $b$ and $w$ are generally optimized together. In the dual formulation one solves for $\alpha$ and one can then calculate $b$ and $w$ from these values. $\endgroup$ – MotiN Nov 17 '16 at 12:45

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.