Crammer-Singer Multiclass Hinge Loss

Scores, Labels, and the Crammer-Singer Loss

In multiclass prediction, a model assigns a score to each possible label. A prediction is made by selecting a label with the largest score, but training often uses a loss that penalizes the whole score vector. The Crammer-Singer hinge loss is a particularly direct construction: for the observed label, it compares that label's score with the highest-scoring competing label. Its conditional minimizers reveal both what this surrogate encourages and what it does not determine.

Let the finite label set be \(\mathcal{Y}=\{1,\ldots,K\}\), where \(K\geq 2\), and let \(s=(s_1,\ldots,s_K)\in\mathbb{R}^K\) be a score vector. For a fixed feature value, write \(p_y=P(Y=y\mid X=x)\), so \(p_y\geq 0\) and \(\sum_{y=1}^K p_y=1\). The score-based decoder returns a label maximizing the scores. To make it single-valued when there is a tie, fix a deterministic tie-breaking rule; below, examples use the smallest label.

Definition: The Crammer-Singer multiclass hinge loss for score vector \(s\) and observed label \(y\) is \(\ell_{\mathrm{CS}}(s,y)=\max\{0,\ 1+\max_{j\neq y}s_j-s_y\}\). The conditional risk at probabilities \(p=(p_1,\ldots,p_K)\) is \(R_p(s)=\sum_{y=1}^K p_y\ell_{\mathrm{CS}}(s,y)\). A conditional minimizer is any score vector that minimizes \(R_p(s)\) over \(s\in\mathbb{R}^K\).

The unit margin appears inside the loss: the observed label has zero loss when its score is at least one larger than every competitor's score. Adding the same constant to all scores leaves every loss unchanged, because only score differences occur. The decoder is \(\hat y(s)\in\arg\max_j s_j\), with the specified tie rule used if necessary.

How the Conditional Risk Depends on the Highest Score

Choose a label \(k\) with maximal score and define the gap to its nearest competitor by \(\delta=s_k-\max_{j\neq k}s_j\). If \(\delta>0\), \(k\) is the unique highest-scoring label. Every other label \(y\neq k\) has loss \(1+s_k-s_y\), since \(s_k\) is its highest-scoring competitor. The loss for \(k\) is \(\max(0,1-\delta)\). These observations reduce a lower bound on the full risk to a one-dimensional comparison involving \(p_k\) and \(\delta\).

Worked Example: A Majority Class with Probability Above One-Half

Take three labels with probabilities \(p=(0.7,0.2,0.1)\) and scores \(s=(0,-1,-1)\). The decoder selects label 1. For label 1, the highest competing score is \(-1\), so its loss is \(\max(0,1-1)=0\). For label 2, the highest competing score is \(0\), giving loss \(1+0-(-1)=2\). Label 3 also has loss 2.

The conditional risk is therefore \(0.7(0)+0.2(2)+0.1(2)=0.6\). The largest probability is \(0.7\), and \(2(1-0.7)=0.6\). The example attains the minimum derived below: the most probable label is one full score unit above each other label.

Worked Example: No Class Has Probability Above One-Half

Let \(p=(0.4,0.35,0.25)\), and set all three scores to zero. For each observed label, at least one competing label has the same score, so its loss is \(\max(0,1)=1\). Thus \(R_p(s)=0.4+0.35+0.25=1\).

Here the largest probability is \(0.4\), so no class has probability above one-half. The minimum conditional risk is 1. All labels tie in score, and the decoder's selected label is determined by its tie rule rather than by a strict score advantage.

Worked Example: A Continuum of Minimizers at the Threshold

Let \(p=(0.5,0.3,0.2)\), and consider \(s=(0,-0.4,-0.4)\). Label 1 has loss \(\max(0,1-0.4)=0.6\); labels 2 and 3 each have loss \(1+0.4=1.4\). Hence \(R_p(s)=0.5(0.6)+0.3(1.4)+0.2(1.4)=0.3+0.42+0.28=1\).

More generally, scores \(s=(0,-d,-d)\) give risk \(0.5(1-d)+0.5(1+d)=1\) for every \(0\leq d\leq1\). At \(d=0\) the labels tie; for \(d>0\), label 1 is the unique highest-scoring label. Thus the threshold case has minimizers with different score-gap patterns, even though the minimum risk remains 1.

Exact Minimum Conditional Risk

Theorem: For any finite label distribution \(p\), let \(p_{\max}=\max_y p_y\). Then \(\inf_{s\in\mathbb{R}^K} R_p(s)=\min\{1,\ 2(1-p_{\max})\}\). The infimum is attained.

Proof. First suppose the maximal score is tied, so \(\delta=0\). Each label at the maximal score has loss at least 1: another label has the same score and is a competitor. Every label below the maximum has loss greater than 1. Consequently, \(R_p(s)\geq1\).

Now suppose there is a unique highest-scoring label \(k\), and write \(q=p_k\) and \(\delta>0\). For every \(y\neq k\), \(s_k-s_y\geq\delta\), and the loss for \(y\) is \(1+s_k-s_y\). The loss for \(k\) is \(\max(0,1-\delta)\). It follows that

R_p(s)\ \geq\ q\max(0,1-\delta)+(1-q)(1+\delta).

For \(0<\delta\leq1\), the right-hand side is \(1+(1-2q)\delta\). If \(q\leq1/2\), this is at least 1. If \(q>1/2\), it is decreasing in \(\delta\), so it is at least its value at \(\delta=1\), namely \(2(1-q)\). For \(\delta\geq1\), the bound is \((1-q)(1+\delta)\geq2(1-q)\). Since \(q\leq p_{\max}\), these cases show \(R_p(s)\geq\min\{1,2(1-p_{\max})\}\).

For the reverse inequality, equal scores give risk 1. Alternatively, choose a label \(k\) with \(p_k=p_{\max}\), set \(s_k=0\), and set \(s_y=-1\) for every \(y\neq k\). The loss for \(k\) is zero; every other label has loss 2. The risk is \(2(1-p_{\max})\). The better of these two constructions attains the stated value. \(\square\)

Which Scores Minimize the Risk?

The value of the minimum alone does not describe all the minimizing score vectors. The cases below show precisely when the risk favors a unique highest-scoring label and when tied scores are unavoidable or possible. Write \(S=\{y:p_y>0\}\) for the support of the label distribution.

Theorem: The conditional minimizers have the following characterization.

If \(p_{\max}>1/2\), there is a unique label \(k\) with \(p_k=p_{\max}\). A score vector minimizes the risk exactly when \(k\) is uniquely highest, \(s_k-s_y\geq1\) for every \(y\neq k\), and \(s_k-s_y=1\) for each \(y\in S\setminus\{k\}\).
If \(p_{\max}<1/2\), a score vector minimizes the risk exactly when every label in \(S\) has the same maximal score. Labels outside \(S\) may have any score no larger than that maximum.
If \(p_{\max}=1/2\), minimizers include the tied case in which every label in \(S\) has the same maximal score. They also include the following case: for a label \(k\) with \(p_k=1/2\), \(k\) is uniquely highest and there is a gap \(\delta\in(0,1]\) such that \(s_k-s_y=\delta\) for every \(y\in S\setminus\{k\}\), while \(s_k-s_y\geq\delta\) for labels outside \(S\).

Justification. When \(p_{\max}>1/2\), the minimum is strictly below 1, so a minimizing vector cannot have a tie at the maximum. For its unique top label \(k\), the lower bounds in the proof of the risk theorem must be equalities. The bound is at least \(2(1-q)\), which is at least \(2(1-p_{\max})\). Equality requires \(q=p_{\max}\), \(\delta\geq1\), and \(s_k-s_y=1\) for every other label with positive probability; a larger gap for such a label would strictly increase its weighted loss. These conditions are also sufficient, including when some labels have probability zero.

When \(p_{\max}<1/2\), the minimum is 1. A unique top label with gap \(\delta>0\) cannot attain 1: if its probability \(q<1/2\), the bound \(1+(1-2q)\delta\) is strictly larger than 1. Thus a minimizer has tied maximal scores. A supported label below that maximum would have loss greater than 1, making the total risk greater than 1. Therefore all supported labels must be at the maximum. Conversely, if they are all tied there, each supported label has loss exactly 1, giving risk 1.

At \(p_{\max}=1/2\), a tied maximum attains risk 1 exactly when all supported labels are tied at the maximum. With a unique top label \(k\), equality in the bound requires \(q=1/2\) and \(0<\delta\leq1\). Equality in the weighted-loss bound further requires every other supported label to have gap exactly \(\delta\); zero-probability labels may have larger gaps. These conditions give risk 1 and are sufficient. This establishes the stated cases. \(\square\)

Interpretation and a Common Pitfall

When one label has conditional probability greater than one-half, every minimizer gives that label the unique top score, with a margin of at least one over all alternatives. In contrast, when no label exceeds one-half, minimizers can tie all supported labels at the top. At exactly one-half, both tied scores and a range of positive gaps can minimize the risk.

Pitfall: assuming every surrogate minimizer must select the most probable label. If \(p=(0.4,0.35,0.25)\), equal scores minimize the risk. Under a smallest-label tie rule the decoder chooses label 1, but a different fixed tie rule could choose label 2, which is not the most probable label.
Correction: distinguish the conditional risk minimum from the prediction made by a particular decoder. The loss can have tied minimizers, and the decoder's tie rule affects their predictions. A lowest achievable surrogate risk does not, by itself, prove that every minimizing score vector decodes to a most probable label.
Pitfall: reading a unit margin as a requirement that every minimizer have exactly that gap. For a class with probability above one-half, labels of zero probability may be more than one score unit below the top. At probability one-half, the gap to supported alternatives may range from zero (in the tied case) up to one.

Key takeaway: The minimum conditional Crammer-Singer risk is \(\min\{1,2(1-p_{\max})\}\). A unique highest score is forced when \(p_{\max}>1/2\); below that threshold the supported labels must tie at the maximum, while the boundary case allows both ties and a range of score gaps.

Check Your Understanding

Use the definitions and results above to answer the following questions.

For \(p=(0.6,0.25,0.15)\), what is the minimum conditional risk, and what score-gap conditions must a minimizer satisfy?
Why does the score vector \((0,0,0)\) have conditional risk 1 for every distribution on three labels?
For \(p=(0.5,0.5,0)\), do the scores \((0,-0.7,-0.7)\) minimize the conditional risk? Explain using the threshold characterization.
If \(p_{\max}<1/2\), why can a decoder's tie-breaking rule change the prediction made from a minimizing score vector?
When \(p_k>1/2\), which score gaps are required to equal one, and which may be larger?