6
$\begingroup$

I'm reading a book named The Elements of Statistical Learning by Hastie et al. In $\S 12.3.2$ it introduced the SVM as a penalization method:

With $f(x)=h(x)^T \beta+\beta_0 $, the solution of the optimization problem $$\min_{\beta_0,\beta} \sum_{i=1}^N [1-y_i f(x_i)]_+ +\frac{\lambda}{2}\|\beta\|^2 $$ with $\lambda=\frac{1}{C}$, is the same as that for $$\min_{\beta_0,\beta} \frac{1}{2}\|\beta\|^2 +C \sum_{i=1}^N \xi_i$$ $$\text{subject to } \xi_i \geq 0,y_i f(x_i)\geq 1-\xi_i ~ \forall i, $$

Could anyone kindly give me some hint why they are equivalent, and what's the benefit of introducing the "hinge" loss?

Thanks a lot!

$\endgroup$

3 Answers 3

8
$\begingroup$

Here is an intuitive illustration of difference between hinge loss and 0-1 loss:

enter image description here

(The image is from Pattern recognition and Machine learning)

As you can see in this image, the black line is the 0-1 loss, blue line is the hinge loss and red line is the logistic loss. The hinge loss, compared with 0-1 loss, is more smooth. The 0-1 loss have two inflection point and it have infinite slope at 0, which is too strict and not a good mathematical property. Thus, we soft this constraint to allow certain degree misclassificiton and provide convenient calculation.

$\endgroup$
8
$\begingroup$

I know this question old as dirt but I was just reading Hastie and had to figure it out.

From the constrains of the soft margin SVM formulation (the one at the bottom):

$1-y_if\left(x_i\right) \geq 1-\varepsilon_i$ we get

$\varepsilon_i \geq 1-y_if\left(x_i\right)$, since $\varepsilon_i$ must be greater than zero anyways, the constraint tells us

$\varepsilon_i \geq \left[ 1-y_if\left(x_i\right) \right]_+$

Now since we are minimizing, $\varepsilon_i$ will reach the lower bound

$\varepsilon_i = \left[ 1-y_if\left(x_i\right) \right]_+$

Substitute in the original formulation, multiply by $\lambda = \frac{1}{C} $ and you are good to go.

$\endgroup$
0
$\begingroup$

I know this question is very old but there is a more rigid way to get it:

Lagrangian: $$L = \|\omega\|^2_{2} + c\sum_{i=1}^{n}\zeta_i + \sum_{i = 1}^{n}r_i(\max(0,1-y_if(x_i))-\zeta_i)$$ by KKT condition (with respect to $\zeta_i$): $$ \frac{\partial L}{\partial \zeta_i} = c - r_i = 0 \Rightarrow r_i = c\,, \forall i $$ so $$ L = \|\omega\|^2_{2} + c\sum_{i=1}^{n}\max(0,1-y_if(x_i)) $$ thus it is equivalent to optimizing the hinge loss form.

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