Pairwise Margins for Multiclass Prediction

Why Compare Every Pair?

A multiclass score rule assigns one real-valued score to each possible label and predicts a label with the largest score. An all-pairs margin loss trains these scores by comparing the score of the observed label with the score of each alternative. The central quantity is not an absolute score but a difference: a large positive difference means the observed label scores above that competitor.

These comparisons connect a multiclass prediction to many binary-style contests, one for each competing label. They also impose structure: differences formed from a single score vector cannot cycle. This matters when interpreting pairwise comparisons, especially if they come from separately estimated classifiers rather than from one common score vector.

Definition: Let the label set be $\{1,\ldots,K\}$, where $K\geq 2$, and let $s=(s_1,\ldots,s_K)\in\mathbb{R}^K$ be a score vector. The margin of the true label $y$ against competitor $j\ne y$ is $s_y-s_j$. Given a nonnegative margin loss $\phi:\mathbb{R}\to[0,\infty)$, the unweighted all-pairs loss is $$ \ell(y,s)=\sum_{j\ne y}\phi(s_y-s_j). $$ A common choice is the hinge loss $\phi(u)=\max(0,1-u)$. A weighted version replaces each summand by $w_{yj}\phi(s_y-s_j)$, where the specified weights $w_{yj}$ are nonnegative.

The margin convention is important: the true label's score comes first. If $s_y-s_j\geq 1$, the hinge loss against $j$ is zero; if the competitor scores higher, the margin is negative and the penalty is larger than one. All-pairs loss sums these penalties, so a single prediction can incur loss from several poorly ranked competitors.

How Score Comparisons Determine a Label

The usual score decoder predicts a label with maximum score. Equivalently, it selects a label whose score is at least as large as every pairwise competitor's score. A fixed tie-breaking rule makes this a single-valued prediction when several labels share the maximum.

Result: A label $a$ is a maximum-score prediction if and only if $s_a-s_j\geq 0$ for every $j\ne a$. It is the unique prediction without ties if and only if $s_a-s_j>0$ for every $j\ne a$.

To verify both directions, if $a$ has maximum score, then $s_a\geq s_j$ for every $j$, so each difference is nonnegative. Conversely, if all those differences are nonnegative, then $s_a\geq s_j$ for every $j$, which is exactly the definition of a maximum. Replacing the weak inequalities by strict inequalities gives the unique-maximum statement.

Score differences also obey a consistency identity. For any three labels $a,b,c$,

$$ (s_a-s_b)+(s_b-s_c)=s_a-s_c. $$

Consequently, strict comparisons from one score vector cannot say $a$ beats $b$, $b$ beats $c$, and $c$ beats $a$: adding the first two strict inequalities gives $s_a>s_c$, contradicting the third. This transitivity is a property of shared scores, not a guarantee about comparisons estimated separately.

Worked Example: Margins Against Each Competitor

There are three labels, $A,B,C$. The observed label is $B$, and the score vector is $s_A=0.7$, $s_B=1.5$, and $s_C=-0.2$. Find the margins and the all-pairs hinge loss.

Against $A$, the margin is $s_B-s_A=1.5-0.7=0.8$. Its hinge loss is $\max(0,1-0.8)=0.2$.

Against $C$, the margin is $s_B-s_C=1.5-(-0.2)=1.7$. Its hinge loss is $\max(0,1-1.7)=0$.

Adding the two competitor terms gives $\ell(B,s)=0.2+0=0.2$. The decoder predicts $B$, since its score $1.5$ exceeds both other scores. A positive prediction margin alone does not imply zero hinge loss: the margin against $A$ is positive, but smaller than the hinge target of $1$.

Conditional Risk as a Sum of Pair Contributions

At a fixed covariate value $x$, write $p_k=P(Y=k\mid X=x)$ for the conditional probability of label $k$. For a fixed score vector $s$, the conditional risk is the expected loss over the possible labels:

R_p(s)=E[\ell(Y,s)\mid X=x] =\sum_{y=1}^{K}p_y\sum_{j\ne y}\phi(s_y-s_j).

Each unordered pair $\{a,b\}$ contributes twice in this expression: once when $a$ is the true label and $b$ is its competitor, and once in the reverse direction. Grouping those two terms makes the role of the competing class probabilities explicit.

Result: For the unweighted all-pairs loss, the conditional risk can be written as $$ R_p(s)=\sum_{1\leq a<b\leq K} \left[p_a\phi(s_a-s_b)+p_b\phi(s_b-s_a)\right]. $$

To prove the identity, expand the defining risk as a sum over ordered pairs $(y,j)$ with $y\ne j$. For each unordered pair $\{a,b\}$, its two ordered terms are $p_a\phi(s_a-s_b)$ and $p_b\phi(s_b-s_a)$. Every ordered pair belongs to exactly one such unordered pair, so regrouping the finite sum gives the displayed expression. No terms are added or omitted.

This decomposition also explains why a pairwise contribution cannot be assessed by looking at just one direction. If $s_a>s_b$, then the margin for true label $a$ against $b$ is positive, but the reverse margin is negative. The two terms are multiplied by different probabilities, so both must be calculated.

Worked Example: Three-Class Hinge Risk

Let $p_A=0.5$, $p_B=0.3$, $p_C=0.2$, and use scores $s_A=1$, $s_B=0$, $s_C=-1$. For the hinge loss, calculate the full conditional risk by unordered pairs.

For the pair $\{A,B\}$, $s_A-s_B=1$ and $s_B-s_A=-1$. Since $\phi(1)=0$ and $\phi(-1)=2$, the contribution is $0.5\phi(1)+0.3\phi(-1)=0+0.3(2)=0.6$.

For the pair $\{A,C\}$, $s_A-s_C=2$ and $s_C-s_A=-2$. Here $\phi(2)=0$ and $\phi(-2)=3$, so the contribution is $0.5\phi(2)+0.2\phi(-2)=0+0.2(3)=0.6$.

For the pair $\{B,C\}$, $s_B-s_C=1$ and $s_C-s_B=-1$. Its contribution is $0.3\phi(1)+0.2\phi(-1)=0+0.2(2)=0.4$.

Thus $R_p(s)=0.6+0.6+0.4=1.6$. The direction of each margin is determined by the order in the loss term: for example, the $A,C$ contribution uses $\phi(s_A-s_C)=\phi(2)$ with weight $p_A$, and $\phi(s_C-s_A)=\phi(-2)$ with weight $p_C$.

What a Pairwise Hinge Term Prefers

The pair decomposition lets us examine what one pair alone would prefer. For two labels $a,b$, set $d=s_a-s_b$. Their conditional hinge contribution is $p_a\phi(d)+p_b\phi(-d)$. When one class has greater conditional probability, minimizing this single contribution favors giving that class the higher score.

Result: Suppose $p_a>p_b\geq 0$ and use the hinge loss. The pair contribution $p_a\phi(d)+p_b\phi(-d)$ is minimized at $d=1$. If $p_b>p_a\geq 0$, it is minimized at $d=-1$. If $p_a=p_b>0$, every $d\in[-1,1]$ minimizes the pair contribution.

For the first case, split the real line into three intervals. If $d\geq 1$, the contribution is $p_b(1+d)$, which is increasing in $d$, so its minimum on that interval is at $d=1$, with value $2p_b$. If $d\leq -1$, the contribution is $p_a(1-d)$, which decreases as $d$ increases, so its minimum on that interval is at $d=-1$, with value $2p_a>2p_b$. For $-1\leq d\leq 1$, it is $$ p_a(1-d)+p_b(1+d)=p_a+p_b+(p_b-p_a)d. $$ Because $p_b-p_a<0$, this expression decreases over the interval and reaches its minimum at $d=1$. These interval calculations establish the first case. Exchanging $a$ and $b$ gives the second. When $p_a=p_b>0$, the middle expression is constant, and the outer expressions are no smaller; hence the full interval $[-1,1]$ consists of minimizers.

This is a statement about one pair's contribution. In a multiclass score vector, the same score $s_a$ participates in every pair involving $a$, so pairwise margin choices are coupled. The decomposition is useful for understanding the objective, but it does not permit optimizing each pair with unrelated score differences.

Worked Example: Conflicting Independent Pairwise Preferences

Suppose a separate comparison system reports pairwise probabilities $q_{AB}=0.8$, $q_{BC}=0.7$, and $q_{CA}=0.6$. For each pair, the reverse probability is the complement, so $q_{BA}=0.2$, $q_{CB}=0.3$, and $q_{AC}=0.4$. Each comparison favors the first label in its subscript, giving $A$ over $B$, $B$ over $C$, and $C$ over $A$.

These strict preferences cannot all be represented by one score vector: $s_A>s_B$ and $s_B>s_C$ imply $s_A>s_C$, whereas the reported $C$-over-$A$ preference calls for $s_C>s_A$. The contradiction arises because the pairwise probabilities were specified independently, not because score differences themselves can cycle.

One possible aggregation is to sum each label's signed pairwise advantages. For $A$, the total is $(q_{AB}-q_{BA})+(q_{AC}-q_{CA})=(0.8-0.2)+(0.4-0.6)=0.4$. For $B$, it is $(0.2-0.8)+(0.7-0.3)=-0.2$. For $C$, it is $(0.6-0.4)+(0.3-0.7)=-0.2$. This rule selects $A$, even though $A$ loses the direct comparison with $C$. It resolves this example by aggregation; it does not make all three pairwise preferences jointly consistent.

Common Pitfall and Practical Interpretation

A frequent error is to treat every pairwise comparison as if it were an independent score difference, then assume all preferred directions can be satisfied at once. For example, three separate classifiers may produce a cycle. The mistaken reasoning is: “Each classifier picks a winner, so there must be a score vector that ranks all those winners higher.” The correction is that a shared score vector must satisfy the additive identity for its differences. A cycle of strict preferences violates that identity, so a decoder or aggregation rule is needed if the comparisons do not come from common scores.

A second error is to reverse a margin in one term or to use the same margin for both directions of a pair. In the conditional-risk contribution, $p_a$ multiplies $\phi(s_a-s_b)$, while $p_b$ multiplies $\phi(s_b-s_a)$. These margins have opposite signs. As the three-class calculation showed, replacing one by the other can change a positive penalty into zero.

Finally, all-pairs margin loss is a surrogate objective, not itself a probability estimate. Its numerical value summarizes margin penalties across competitors; it should not be read as a class probability. The scores are useful for ranking and decoding, while the loss specifies how errors in the score comparisons are penalized. Understanding both the margin direction and the constraints imposed by a shared score vector is essential when choosing or interpreting an all-pairs construction.

Key takeaway: An all-pairs loss adds a margin penalty for every competitor to the observed label. A common score vector makes these comparisons transitive, and its maximum-score decoder selects a label that is at least as high-scoring as every other label.

Check Your Understanding

Work through these questions using the margin convention $s_y-s_j$.

For three labels with true label $C$ and scores $s_A=0$, $s_B=1.2$, $s_C=1.5$, calculate both hinge-loss terms and identify the decoded label.
Write the conditional-risk contribution for the unordered pair $\{a,b\}$ using $p_a,p_b$ and the two score differences.
Explain why a shared score vector cannot satisfy the strict comparisons $s_A>s_B$, $s_B>s_C$, and $s_C>s_A$.
For hinge loss, what values of $d=s_a-s_b$ minimize the pair contribution when $p_a=p_b>0$?
When a set of independently estimated pairwise preferences cycles, what distinction should be made between those preferences and comparisons derived from a single score vector?