Where does the multi class hinge loss come from?

Question

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):

Answer 1

The (multi-class) hinge loss can be understood as attempting to make sure that the score for the correct class is higher than the other classes by at least some margin Δ>0 , otherwise a loss is incurred.

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