2
$\begingroup$

I was trying to understand where the loss function:

$$ l (W,(x,y)) = \max_{j \in \{1 , ... , k \} } \{ \mathbb{1}\{ j \neq y \} + W^T_j x - W^T_y x \}$$

come from?

The reason that I ask is that its easy to see that the usual hinge loss for 2 classes is a convex surrogate function for the indicator function. For example just by drawing a picture:

enter image description here

it seems to hardly require justification (ok fine, perhaps the 1 the expression $max(0,1 - ys)$ where s is the score, is a bit random. Why not 10-ys? or any number above 1? obviously bellow 1 is bad).

However the multi class hinge loss that is suggested in this question, seems non-trivial. For example I am not sure how I would write expressions down until I realize oh yea, this is the same as the usual hinge loss AND its a convex surrogate of the 1-0 misclassification loss. Maybe its just me but I even needed help to figure that out even though I already knew it was true as evidence by this question: How does one show that the multi-class hinge loss upper bounds the 1-0 loss?

Thus, my question, why is this such a natural function to be the generalization of the binary hinge loss? Is it suppose to be obvious? Or perhaps I am missing some crucial understanding of the multi-class hinge loss and thus I am asking this question. Perhaps I don't understand the loss (conceptually) well enough to understand what its saying and why its suppose to be so natural.


Note that I am aware of its other upper bound which might be the more common hinge loss used in practice (though not sure why its more commonly used):

enter image description here

$\endgroup$
  • $\begingroup$ Why do you say that margin below 1 is bad? $\endgroup$ – chandresh Nov 10 '18 at 13:35
  • $\begingroup$ @chandresh being bellow the margin is bad. The margin is arbitrary but the point is to have some margin from the gutter. $\endgroup$ – Pinocchio Nov 10 '18 at 15:08
  • $\begingroup$ Thanks. To answer to your question: Choosing 1 in hinge loss is because of 0-1 loss. The line 1-ys has slope 45 when it cuts x-axis at 1. If 0-1 loss has cut on y-axis at some other point, say t, then hinge loss would be max(0, t-ys). This renders hinge loss the tightest upper bound for the 0-1 loss. $\endgroup$ – chandresh Nov 10 '18 at 15:25
  • $\begingroup$ @chandresh you’d need to define tightest. What matters is that its a convex relaxation of the real loss we want to optimize. Classification error is the loss we actually care about in this case so we choose a surrogate loss thats helps. Cross entropy is another common one. It was shown by pro Srebro they converge to the same in the linear low noise case. $\endgroup$ – Pinocchio Nov 10 '18 at 15:28
  • $\begingroup$ By tighest, I mean of all the upper bounds given by different loss functions such as hinge, squared hinge, huber, log etc. gap between hinge loss and 0-1 is minimum. See for example, link/ references therein $\endgroup$ – chandresh Nov 10 '18 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.