# Where does the multi class hinge loss come from?

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: 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): • Why do you say that margin below 1 is bad?
– CKM
Nov 10 '18 at 13:35
• @chandresh being bellow the margin is bad. The margin is arbitrary but the point is to have some margin from the gutter. Nov 10 '18 at 15:08
• 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.
– CKM
Nov 10 '18 at 15:25
• @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. Nov 10 '18 at 15:28
• 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
– CKM
Nov 10 '18 at 15:33

Remember that $$\hat y = argmax(W^Tx_i)$$, so there's no need for $$W^Tx_i$$ to be equal exactly to some (e.g.) $$e_{y_i} = (0,...,1,...,0)$$, it just needs that the $$y_i$$ position score will be the greatest than all the rest. If we ignore the margin for a second, the loss becomes $$(w_j^Tx_i - w_{y_i}^Tx_i)_+$$ which I think is kind of intuitive.
(Note, regarding your comment in the binary case, I think the $$1$$ in $$(1-y_ix_i^Tw)_+$$ is arbitrary. It comes from the problem formulation (mainly I believe it comes from the labels you choose for y $$\in \{-1, 1\}$$), and it ends up defining the margins you require between the two classes. You could set up a hinge loss with larger margins, say 2, ($$y_i \in \{-2,2\}$$) but then it would have to be: $$(2 - sign(y_i)x_i^Tw)_+$$. Since the final margin is $$\frac{2\Delta}{||w||}$$ increasing the $$\Delta$$ will have the same effect like decreasing $$||w||$$, so you can simply stay with the regular formulation, and add a regularization term to the loss, i.e. $$\sum_i(1-x_i^Tw)_+ + \frac{\lambda}{2}||w||^2$$.)