Exact-Match Loss and Joint MAP Decoding

Why the Whole Output Matters

A structured prediction may be judged as one complete object: a vector of labels, a multilabel assignment, or another output whose components jointly form the answer. Under exact-match loss, a prediction receives no penalty only when every component is correct. Getting all but one component right still counts as an error. The relevant probability is therefore the probability of the whole output, not just the separate probabilities of its coordinates.

This distinction determines the Bayes decoder. Given the input $X=x$, the optimal exact-match decision is a complete output with the greatest conditional probability. This is called joint maximum a posteriori (MAP) decoding. It can differ from choosing the most probable value of each coordinate separately, the rule associated with Hamming loss and marginal decoding.

Exact-Match Loss and Conditional Risk

Let $\mathcal{Y}$ be a finite set of valid structured outputs, and let $Y\in\mathcal{Y}$ be the random output paired with an input $X$. A decoder $\delta$ maps the observed input to a prediction $\delta(X)\in\mathcal{Y}$. Finiteness is a convenient standard setting here: it ensures that a maximum conditional probability is attained. Write $q_x(y)=P(Y=y\mid X=x)$ for a version of the conditional probability, defined for almost every $x$.

Definition: The exact-match loss is $\Delta(\hat y,y)=\mathbf{1}\{\hat y\ne y\}$, where the indicator is 1 if the complete predicted output differs from the true output and 0 otherwise. The conditional risk of predicting $\hat y$ at $x$ is $R(\hat y\mid x)=E[\Delta(\hat y,Y)\mid X=x]$.

The loss is zero precisely on the event $Y=\hat y$. Thus its conditional expectation depends on the probability of that single complete output. The following result identifies every conditional Bayes decision.

Theorem: For almost every $x$, the conditional risk is $R(\hat y\mid x)=1-q_x(\hat y)$. Consequently, its minimizers are exactly the joint MAP outputs: $$ \operatorname*{arg\,min}_{\hat y\in\mathcal{Y}}R(\hat y\mid x) = \operatorname*{arg\,max}_{\hat y\in\mathcal{Y}}P(Y=\hat y\mid X=x). $$ If $\delta$ is a measurable decoder, its population exact-match risk is $E[1-q_X(\delta(X))]$. A decoder selecting a maximizer at each $x$ minimizes this risk.

Proof. For a fixed candidate $\hat y$, $\Delta(\hat y,Y)=1-\mathbf{1}\{Y=\hat y\}$. Taking conditional expectations gives

R(\hat y\mid x) =E[1-\mathbf{1}\{Y=\hat y\}\mid X=x] =1-P(Y=\hat y\mid X=x) =1-q_x(\hat y).

Since subtracting a number from 1 reverses its ordering, minimizing $1-q_x(\hat y)$ is equivalent to maximizing $q_x(\hat y)$. For the population claim, the tower property gives $E[\Delta(\delta(X),Y)]=E[R(\delta(X)\mid X)]$. At almost every $x$, a maximizer of $q_x(y)$ has no greater conditional risk than any other output. Integrating that pointwise inequality proves the population optimality. Because $\mathcal{Y}$ is finite, fixing an ordering of its elements and choosing the first maximizer yields a measurable choice whenever the conditional probabilities $q_x(y)$ are measurable. $\square$

A tie is not an exception: every output attaining the maximum is conditionally Bayes-optimal. The theorem does not say that a particular tie-breaking rule is uniquely best. It says that none of the maximizers has higher conditional exact-match risk than another.

Worked Example: Comparing Complete-Output Probabilities

Suppose $Y=(Y_1,Y_2)$ takes values in $\{0,1\}^2$, and at a particular input $x$ its conditional distribution is $P(00\mid x)=0.35$, $P(11\mid x)=0.34$, $P(01\mid x)=0.20$, and $P(10\mid x)=0.11$. The probabilities are nonnegative and sum to $0.35+0.34+0.20+0.11=1$.

The joint MAP output is $00$, since $0.35$ is the largest of the four complete-output probabilities. Its exact-match risk is $1-0.35=0.65$. For comparison, predicting $11$, $01$, or $10$ has risk $0.66$, $0.80$, or $0.89$, respectively.

Now calculate the marginal probabilities. The first coordinate has $P(Y_1=1\mid x)=P(10\mid x)+P(11\mid x)=0.11+0.34=0.45$, so its marginal mode is 0. The second has $P(Y_2=1\mid x)=P(01\mid x)+P(11\mid x)=0.20+0.34=0.54$, so its marginal mode is 1. Coordinatewise marginal decoding therefore gives $01$, which has joint probability $0.20$ and exact-match risk $0.80$. It is worse than the joint MAP decision under exact-match loss.

Joint MAP Versus Coordinatewise Marginal Decoding

For a vector-valued output $Y=(Y_1,\ldots,Y_d)$, coordinatewise marginal decoding chooses each coordinate from its own conditional distribution. With finite coordinate label sets, one version of this rule is

\hat y_j^{\mathrm{marg}}(x)\in \operatorname*{arg\,max}_{a}P(Y_j=a\mid X=x), \qquad j=1,\ldots,d.

This rule optimizes a sum of coordinatewise errors, as in Hamming loss; it does not in general maximize $P(Y=y\mid X=x)$ over complete outputs. Joint MAP instead compares the probability of each valid complete output. Marginal probabilities alone generally do not determine which complete output is most probable.

There is also a structural issue. The valid output set $\mathcal{Y}$ may be a strict subset of the Cartesian product of coordinate label sets. The combination of marginal modes can then fall outside $\mathcal{Y}$. Even if it is valid, it need not be a joint MAP output.

Worked Example: Marginal Modes Can Be Invalid

Suppose the valid outputs are the three binary vectors with exactly one coordinate equal to 1: $\mathcal{Y}=\{100,010,001\}$. At input $x$, let each of these outputs have conditional probability $1/3$; the probabilities sum to 1.

For each coordinate $j$, $P(Y_j=1\mid x)=1/3$ and $P(Y_j=0\mid x)=2/3$. Thus the unique marginal mode for every coordinate is 0, and coordinatewise decoding returns $000$. But $000\notin\mathcal{Y}$, so it is not a permissible prediction. Each of the three valid outputs is a joint MAP output, with exact-match risk $1-1/3=2/3$.

This example separates two questions: the most probable value of each component, and the most probable valid complete object. The answers need not combine into the same decision.

Proposition: For a fixed input $x$, let $q_{\max}(x)=\max_{y\in\mathcal{Y}}q_x(y)$. The excess conditional risk of predicting any $\hat y\in\mathcal{Y}$, relative to Bayes risk, is $$ R(\hat y\mid x)-\min_{y\in\mathcal{Y}}R(y\mid x) =q_{\max}(x)-q_x(\hat y). $$

Proof. By the theorem, $R(\hat y\mid x)=1-q_x(\hat y)$. A maximizer of $q_x$ has risk $1-q_{\max}(x)$, which is the minimum risk. Subtracting gives

R(\hat y\mid x)-\min_yR(y\mid x) =[1-q_x(\hat y)]-[1-q_{\max}(x)] =q_{\max}(x)-q_x(\hat y).

The difference is nonnegative because $q_{\max}(x)$ is a maximum. It is zero exactly when $\hat y$ is a joint MAP output. $\square$

This identity gives a direct interpretation of the cost of a decoding choice: under exact-match loss, the conditional excess risk is the gap between the largest joint probability and the probability assigned to the chosen complete output. It is not a sum of coordinatewise probability gaps.

Worked Example: Independence Makes the Rules Agree

Suppose $Y=(Y_1,Y_2)$ has conditionally independent binary coordinates at $x$, with $P(Y_1=1\mid x)=0.8$ and $P(Y_2=1\mid x)=0.3$. Independence means the joint conditional probabilities are products of the corresponding marginal probabilities.

The four complete-output probabilities are $P(00\mid x)=0.2(0.7)=0.14$, $P(01\mid x)=0.2(0.3)=0.06$, $P(10\mid x)=0.8(0.7)=0.56$, and $P(11\mid x)=0.8(0.3)=0.24$. They sum to $0.14+0.06+0.56+0.24=1$. The joint MAP output is $10$, with exact-match risk $1-0.56=0.44$.

The marginal modes are also $Y_1=1$ and $Y_2=0$, giving $10$. More generally, if all coordinate combinations are valid and the coordinates are conditionally independent, then $P(Y=y\mid x)=\prod_{j=1}^dP(Y_j=y_j\mid x)$. Maximizing this product over the Cartesian product can be done by maximizing each factor separately, so marginal modes form a joint MAP output. Ties may produce multiple maximizing vectors.

When the Distinction Matters

Exact-match loss is appropriate when the task regards the entire output as correct only when every part is correct, such as evaluating an entire label configuration as one unit. In that setting, reporting marginal modes as the final answer can optimize the wrong objective. Marginals can still be useful summaries, but they do not by themselves certify exact-match optimality.

The central practical question is what constitutes a valid output and what the evaluation loss rewards. If the loss is exact match, compare joint probabilities among valid outputs. If the loss is additive across coordinates, marginal decisions may instead be appropriate. For structured spaces, imposing validity is essential: a coordinatewise rule should not be assumed to produce an admissible complete answer.

Common Mistake

A common but incorrect argument is: “Each coordinate's most probable value is the best choice for that coordinate, so putting those values together must give the most probable complete output.” This reasoning silently switches from a complete-output objective to separate coordinatewise objectives. In general, dependence changes joint probabilities, and constraints can rule out the vector of marginal modes entirely.

The correction is to derive the decision from the stated loss. Under exact-match loss, $R(\hat y\mid x)=1-P(Y=\hat y\mid X=x)$, so the decision maximizes the joint conditional probability over valid outputs. Use marginal modes only when the loss or additional distributional structure justifies them.

Key takeaway: Exact-match Bayes decoding is joint MAP decoding: choose a most probable valid complete output. Coordinatewise marginal decoding solves a different decision problem in general; it agrees with joint MAP under conditions such as conditional independence on a full Cartesian output space, but need not otherwise.

Check Your Understanding

For each question, distinguish probabilities of complete outputs from probabilities of individual coordinates.

Under exact-match loss, express the conditional risk of predicting $y$ at input $x$ in terms of $P(Y=y\mid X=x)$.
If two valid outputs have the same largest conditional probability, what can be said about their exact-match risks?
Give one reason coordinatewise marginal modes might not be an admissible structured output.
For the distribution in the first worked example, what is the exact-match excess risk of predicting $01$ rather than a joint MAP output?
State the independence and output-space conditions under which coordinatewise marginal modes yield a joint MAP output.