Worked Comparisons of Multiclass and Structured Decoders

One Probability Distribution, Several Decisions

A model can provide a conditional distribution for an outcome given the observed features, but that distribution does not by itself specify which prediction to report. The decision also depends on the loss assigned to each possible prediction and truth. A prediction that is most probable can be optimal under one loss and suboptimal under another.

This distinction is especially important for structured outputs. A sequence can be predicted by choosing its most probable complete value, or by choosing each coordinate to minimize its own error probability. Those procedures answer different questions. The same issue appears in multilabel prediction, where the costs of false positives and false negatives can vary by label.

Definition: Let $\mathcal{Y}$ be a finite set of possible truths and $\mathcal{A}$ a finite set of allowable predictions. Given features $X=x$, write $p(y\mid x)=P(Y=y\mid X=x)$. For a loss $L(a,y)$, the conditional risk of prediction $a$ is $$ R(a\mid x)=\sum_{y\in\mathcal{Y}} L(a,y)p(y\mid x). $$ A Bayes decoder for this loss chooses any $a\in\arg\min_{a'\in\mathcal{A}}R(a'\mid x)$. A tie may be resolved by any fixed rule.

The distribution $p(y\mid x)$ describes uncertainty; the loss translates that uncertainty into a decision. Under multiclass zero-one loss, a wrong class always costs one, so choosing the most probable class is optimal. Under an asymmetric cost matrix, different errors have different consequences, and the most probable class need not minimize risk.

Multiclass Argmax and Cost-Sensitive Decoding

For a single multiclass label, let $\mathcal{Y}=\mathcal{A}=\{A,B,C\}$. Under zero-one loss, $L(a,y)=\mathbf{1}\{a\ne y\}$, the risk of predicting $a$ is $1-p(a\mid x)$. Thus minimizing risk is equivalent to maximizing the class probability. With a general cost matrix, however, the risk is a probability-weighted sum of the costs in the prediction's column.

Worked Example: A Cost Matrix Changes the Multiclass Prediction

Suppose the conditional probabilities are $P(Y=A\mid x)=0.50$, $P(Y=B\mid x)=0.30$, and $P(Y=C\mid x)=0.20$. The rows below are the true class and the columns are the prediction.

True class	Predict A	Predict B	Predict C
A	0	1	4
B	4	0	2
C	1	3	0

Under zero-one loss, the argmax decoder predicts $A$, since $0.50$ is the largest probability. For the displayed task costs, calculate each prediction's conditional risk by weighting its column by the true-class probabilities:

\begin{aligned} R(A\mid x)&=0.50(0)+0.30(4)+0.20(1)=1.40,\\ R(B\mid x)&=0.50(1)+0.30(0)+0.20(3)=1.10,\\ R(C\mid x)&=0.50(4)+0.30(2)+0.20(0)=2.60. \end{aligned}

The cost-sensitive decoder therefore predicts $B$, whose risk $1.10$ is smaller than both alternatives. The most probable class is still $A$; the change is due to the loss, not to a different probability estimate.

Result: For any finite $\mathcal{A}$ and $\mathcal{Y}$, a prediction minimizing $R(a\mid x)$ minimizes conditional expected loss among all deterministic predictions in $\mathcal{A}$. Under zero-one loss with $\mathcal{A}=\mathcal{Y}$, the minimizers are exactly the modes of $p(y\mid x)$.

Proof. Conditional on $X=x$, predicting $a$ incurs loss $L(a,Y)$. Since $Y$ takes values in the finite set $\mathcal{Y}$, the conditional expectation is the finite sum $$ E[L(a,Y)\mid X=x]=\sum_{y\in\mathcal{Y}}L(a,y)P(Y=y\mid X=x)=R(a\mid x). $$ Therefore any action attaining the minimum of this risk has no greater conditional expected loss than any other allowable action. Under zero-one loss, $$ R(a\mid x)=\sum_{y\ne a}p(y\mid x)=1-p(a\mid x), $$ so minimizing the risk is equivalent to maximizing $p(a\mid x)$. $\square$

Sequence Outputs: Marginal Decisions Versus Joint MAP

For a sequence $Y=(Y_1,\ldots,Y_m)$, the joint distribution assigns probability to complete sequences. The joint MAP decoder chooses a sequence with maximum joint probability. The marginal decoder instead chooses each coordinate using its own conditional marginal distribution. The appropriate choice depends on whether the task penalizes any incorrect coordinate separately or treats any incorrect sequence as a complete failure.

Worked Example: Hamming Loss and Exact-Match Loss on a Sequence

Suppose the possible binary sequences have the following conditional probabilities. The probabilities sum to $0.30+0.25+0.20+0.15+0.10=1.00$.

Sequence $y$	$P(Y=y\mid x)$
000	0.30
111	0.25
100	0.20
010	0.15
001	0.10
All other sequences	0

The joint MAP decoder chooses $000$, the most probable complete sequence. The coordinate marginals are

P(Y_1=1\mid x)=0.25+0.20=0.45,\qquad P(Y_2=1\mid x)=0.25+0.15=0.40,\qquad P(Y_3=1\mid x)=0.25+0.10=0.35.

Each coordinate's most probable value is zero, so the marginal decoder also chooses $000$ in this table. But their risks differ by loss. Under exact-match loss $L_{\mathrm{exact}}(a,y)=\mathbf{1}\{a\ne y\}$, the risk of $000$ is $1-0.30=0.70$; the risk of $111$ is $1-0.25=0.75$. Under Hamming loss $L_{\mathrm{Ham}}(a,y)=\sum_{j=1}^3\mathbf{1}\{a_j\ne y_j\}$, the risk of $000$ is $0.45+0.40+0.35=1.20$.

Now compare prediction $100$. Its Hamming risk is $0.55+0.40+0.35=1.30$, which is larger than the risk of $000$; its exact-match risk is $1-0.20=0.80$. This particular table gives the same optimal output under both losses, but the criteria and their risk calculations are distinct. The next result explains why marginal probabilities, rather than joint sequence probabilities, determine Hamming-optimal decisions.

Result: For binary sequences and Hamming loss, any Bayes decoder may choose each coordinate $a_j$ independently to minimize the coordinate error probability. Thus $a_j=1$ is optimal when $P(Y_j=1\mid x)>1/2$, $a_j=0$ is optimal when $P(Y_j=1\mid x)<1/2$, and either value is optimal at equality. For exact-match loss, a Bayes decoder is a joint MAP sequence.

Proof. For any proposed sequence $a$, linearity of conditional expectation and the definition of Hamming loss give $$ R_{\mathrm{Ham}}(a\mid x) =E\left[\sum_{j=1}^m\mathbf{1}\{a_j\ne Y_j\}\mid X=x\right] =\sum_{j=1}^m P(a_j\ne Y_j\mid x). $$ The $j$-th summand depends only on $a_j$. If $a_j=1$, it equals $P(Y_j=0\mid x)$; if $a_j=0$, it equals $P(Y_j=1\mid x)$. Selecting the smaller of these two probabilities for every coordinate minimizes their sum, proving the marginal rule. This argument does not require the coordinates of $Y$ to be independent. For exact-match loss, the risk of $a$ is $$ R_{\mathrm{exact}}(a\mid x)=P(Y\ne a\mid x)=1-P(Y=a\mid x), $$ so minimizing risk is equivalent to maximizing the joint probability. $\square$

Although the example produced the same output for both criteria, the outputs can differ. For instance, on binary sequences of length three, assign probabilities $0.30$ to $000$, $0.25$ to $111$, $0.20$ to $100$, $0.15$ to $010$, and $0.10$ to $001$, as above: this does not separate them. A different valid table does: put probabilities $0.30,0.25,0.20,0.15,0.10$ on $000,111,100,010,001$ respectively, and shift $0.21$ from $000$ to $111$ would change the mode, so it is not a valid illustration of differing decoders. Rather than infer disagreement from different definitions alone, use the multilabel example below, where the objectives demonstrably select different outputs.

Multilabel Decisions With Unequal Error Costs

A multilabel outcome is a vector of binary labels. Under Hamming loss, labels are treated as separate coordinates and the marginal rule applies. Under a cost-sensitive loss, each label can have its own false-positive and false-negative costs. If the loss is additive over labels, marginal probabilities still suffice for optimizing the total risk, but the threshold for each label depends on its costs rather than being fixed at one half.

Worked Example: Asymmetric Costs Produce a Different Multilabel Output

Let $Y=(Y_1,Y_2)$, where $1$ means a label is present. Suppose $P(Y_1=1\mid x)=0.35$ and $P(Y_2=1\mid x)=0.65$. For label 1, a false positive costs 1 and a false negative costs 4. For label 2, a false positive costs 4 and a false negative costs 1. Correct decisions cost zero.

For label 1, predicting present incurs a false-positive cost only when $Y_1=0$, so its expected cost is $1(1-0.35)=0.65$. Predicting absent incurs a false-negative cost when $Y_1=1$, so its expected cost is $4(0.35)=1.40$. The cost-sensitive choice is therefore $Y_1=1$.

For label 2, predicting present has expected cost $4(1-0.65)=4(0.35)=1.40$. Predicting absent has expected cost $1(0.65)=0.65$. The cost-sensitive choice is $Y_2=0$. Thus the cost-sensitive output is $10$, with total risk $0.65+0.65=1.30$.

Under ordinary Hamming loss, the marginal threshold is one half: label 1 is predicted absent because $0.35<0.50$, while label 2 is predicted present because $0.65>0.50$. This gives output $01$. Evaluated under the stated asymmetric costs, its risk is $1.40+1.40=2.80$, larger than the risk $1.30$ of $10$. The comparison shows why an ordinary marginal decoder is not automatically suitable when error costs are unequal.

For completeness, one joint distribution consistent with these marginals is obtained by taking the labels to be conditionally independent. Its probabilities are $P(00\mid x)=0.65(0.35)=0.2275$, $P(01\mid x)=0.65(0.65)=0.4225$, $P(10\mid x)=0.35(0.35)=0.1225$, and $P(11\mid x)=0.35(0.65)=0.2275$. They sum to $1.0000$, and the joint MAP output is $01$, not the cost-sensitive output $10$.

Choosing and Checking a Decoder

A decoder is a decision rule tied to a loss, not a universal post-processing step. The comparisons above can be summarized as follows.

Decoder	Decision criterion	Probability information used
Multiclass argmax	Minimize zero-one classification risk	Class probabilities
Cost-sensitive	Minimize expected task cost	Class or label probabilities and the cost specification
Marginal	Minimize additive coordinate-wise loss such as Hamming loss	Coordinate-wise marginals
Joint MAP	Minimize exact-match loss	Joint probabilities of complete outputs

A common mistake is to call the largest-probability output “the optimal prediction” without naming a loss. That is correct for zero-one loss on a single class and for exact-match loss on a structured output, but not in general. Another mistake is to choose every coordinate by its marginal probability and then claim that the resulting sequence is the most probable complete sequence. Marginal decisions minimize additive coordinate loss; joint MAP maximizes complete-output probability. These are different calculations, and neither can be substituted for the other without checking the task loss.

In practice, write down the allowable predictions, the conditional probabilities, and the loss before decoding. For a cost matrix, check whether rows index truths and columns index predictions before multiplying. For multilabel costs, a false positive uses the probability the label is absent, while a false negative uses the probability it is present. This simple check prevents reversing the probabilities in the expected-cost calculation.

Check Your Understanding

For each question, identify the loss or calculation that determines the decoder.

Under multiclass zero-one loss, explain why maximizing the class probability minimizes conditional risk.
A sequence decoder is evaluated by Hamming loss. Which probabilities are sufficient for choosing each coordinate, and is coordinate independence required?
For exact-match loss, what quantity should be maximized over complete sequences?
A binary label has probability $0.30$ of being present, false-positive cost 2, and false-negative cost 3. Compute the expected cost of predicting present and of predicting absent, then state the lower-risk decision.
Give one reason a cost-sensitive multilabel output can differ from the ordinary marginal Hamming output.