23
$\begingroup$

People says soft margin SVM use hinge loss function: $\max(0,1-y_i(w^\intercal x_i+b))$. However, the actual objective function that soft margin SVM tries to minimize is $$ \frac{1}{2}\|w\|^2+C\sum_i\max(0,1-y_i(w^\intercal x_i+b)) $$ Some authors call the $\|w\|^2$ term regularizer and the $\max(0,1-y_i(w^\intercal x_i+b))$ term loss function.

However, for hard margin SVM, the whole objective function is just $$ \frac{1}{2}\|w\|^2 $$ Does that mean hard margin SVM only minimize a regularizer without any loss function? That sounds very strange.

Well, if $\frac{1}{2}\|w\|^2$ is the loss function in this case, can we call it quadratic loss function? If so, why the loss function of hard margin SVM becomes regularizer in soft margin SVM and make a change from quadratic loss to hinge loss?

$\endgroup$
  • $\begingroup$ For what I understand, hard margin means you don't accept datas in your margin. As a consequence, max(0, calculation) will always return 0. $\endgroup$ – merours Feb 19 '14 at 15:07
26
+50
$\begingroup$

The hinge loss term $\sum_i\max(0,1-y_i(\mathbf{w}^\intercal \mathbf{x}_i+b))$ in soft margin SVM penalizes misclassifications. In hard margin SVM there are, by definition, no misclassifications.

This indeed means that hard margin SVM tries to minimize $\|\mathbf{w}\|^2$. Due to the formulation of the SVM problem, the margin is $2/\|\mathbf{w}\|$. As such, minimizing the norm of $\mathbf{w}$ is geometrically equivalent to maximizing the margin. Exactly what we want!

Regularization is a technique to avoid overfitting by penalizing large coefficients in the solution vector. In hard margin SVM $\|\mathbf{w}\|^2$ is both the loss function and an $L_2$ regularizer.

In soft-margin SVM, the hinge loss term also acts like a regularizer but on the slack variables instead of $\mathbf{w}$ and in $L_1$ rather than $L_2$. $L_1$ regularization induces sparsity, which is why standard SVM is sparse in terms of support vectors (in contrast to least-squares SVM).

$\endgroup$
  • $\begingroup$ Can you explain the last two paragraphs with some more details and maths? $\endgroup$ – enterML Aug 23 '18 at 19:33
0
$\begingroup$

Just to clarify, $$ \frac{1}{2}\|w\|^2 $$ is minimized subject to the constraint that the points are linearly separable (I.e. one can draw a hyperplane that perfectly separates the two). In other words, the only allowed values of w that we can consider as solutions are those that separate the two sets of points.

Now, it is thought that hard margin SVM "overfits" more readily than soft margin. This is easier to imagine with a RBF SVM with high enough of a $\gamma$, which can create (overly) complicated and (potentially) over-fit decision boundaries. The harder the margin (emulated imprecisely with a higher "C"), the harder the search will try to find decision boundaries that perfectly classify the two sets of points.

When we move to "soft margin", the constraints are relaxed and replaced with a restraint through the introduction of "slack". This slack variable is defined with a "hinge loss" term. After simplification, one arrives at the hinge + l2 like loss term everyone associates with SVMs. FWIW, I like to frame SVMs as more of an optimization problem instead of the omnipresent "follow the gradients" problem.

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