17.2 Linear Multiclass Predictors 233
loss functions (see Section 12.3). In particular, we generalize the hinge loss to
multiclass problems.
17.2.4 Generalized Hinge Loss
Recall that in binary classification, the hinge loss is defined to be max{ 0 , 1 −
y〈w,x〉}. We now generalize the hinge loss to multiclass predictors of the form
hw(x) = argmax
y′∈Y
〈w,Ψ(x,y′)〉.
Recall that a surrogate convex loss should upper bound the original nonconvex
loss, which in our case is ∆(hw(x),y). To derive an upper bound on ∆(hw(x),y)
we first note that the definition ofhw(x) implies that
〈w,Ψ(x,y)〉≤〈w,Ψ(x,hw(x))〉.
Therefore,
∆(hw(x),y) ≤∆(hw(x),y) +〈w,Ψ(x,hw(x))−Ψ(x,y)〉.
Sincehw(x)∈Ywe can upper bound the right-hand side of the preceding by
maxy′∈Y(∆(y′,y) +〈w,Ψ(x,y′)−Ψ(x,y)〉) def= `(w,(x,y)). (17.3)
We use the term “generalized hinge loss” to denote the preceding expression. As
we have shown,`(w,(x,y))≥∆(hw(x),y). Furthermore, equality holds when-
ever the score of the correct label is larger than the score of any other label,y′,
by at least ∆(y′,y), namely,
∀y′∈Y \{y}, 〈w,Ψ(x,y)〉≥〈w,Ψ(x,y′)〉+ ∆(y′,y).
It is also immediate to see that`(w,(x,y)) is a convex function with respect tow
since it is a maximum over linear functions ofw(see Claim 12.5 in Chapter 12),
and that`(w,(x,y)) isρ-Lipschitz withρ= maxy′∈Y‖Ψ(x,y′)−Ψ(x,y)‖.
Remark 17.2 We use the name “generalized hinge loss” since in the binary
case, whenY={± 1 }, if we set Ψ(x,y) =y 2 x, then the generalized hinge loss
becomes the vanilla hinge loss for binary classification,
`(w,(x,y)) = max{ 0 , 1 −y〈w,x〉}.
Geometric Intuition:
The feature function Ψ :X × Y →Rdmaps eachxinto|Y|vectors inRd.
The value of`(w,(x,y)) will be zero if there exists a directionwsuch that
when projecting the|Y|vectors onto this direction we obtain that each vector is
represented by the scalar〈w,Ψ(x,y)〉, and we can rank the different points on
the basis of these scalars so that
- The point corresponding to the correctyis top-ranked
