Hamming Loss and Marginal Decoding

Why Hamming Loss Leads to Marginal Decisions

A structured prediction may be a sequence of labels, a collection of binary tags, or another vector of coordinated outputs. Under Hamming loss, each incorrect coordinate contributes separately to the total penalty. This additivity has an important consequence: when every combination of coordinate labels is an allowed prediction, minimizing conditional risk requires only the marginal distribution of each coordinate. The coordinates of the true output need not be independent.

The qualification about allowed predictions matters. A sequence may be required to obey a parity rule, grammar, or other structural constraint. In that case, the best decision at each coordinate considered separately may form an invalid output. The correct constrained decision still uses coordinate marginals, but must minimize their combined costs over the valid outputs.

Definition: Let $Y=(Y_1,\ldots,Y_m)$ be a structured response with coordinate alphabets $\mathcal{Y}_1,\ldots,\mathcal{Y}_m$, and let $a=(a_1,\ldots,a_m)$ be a prediction. The unnormalized Hamming loss is $$ L_H(a,Y)=\sum_{j=1}^{m}\mathbf{1}\{a_j\ne Y_j\}. $$ The normalized Hamming loss is $L_H(a,Y)/m$. For a predictor based on features $X$, its conditional Hamming risk is $E[L_H(a,Y)\mid X]$, evaluated at a fixed feature value or, equivalently, as a conditional expectation given $X$.

A coordinate marginal is the conditional probability of a particular label at one position: $P(Y_j=c\mid X)$, for $c\in\mathcal{Y}_j$. The full joint conditional distribution records probabilities of complete vectors; marginal decoding does not need that distribution in full. For a finite label set, all coordinatewise maxima exist.

The Coordinatewise Bayes Rule

For a fixed prediction $a$, the indicator of an error at coordinate $j$ has conditional expectation $1-P(Y_j=a_j\mid X)$. Linearity of conditional expectation therefore gives the risk as a sum of coordinate risks. No independence assumption appears in this calculation.

Theorem: Suppose each coordinate alphabet is finite and every vector in the product $\mathcal{Y}_1\times\cdots\times\mathcal{Y}_m$ is an allowed prediction. A conditional Bayes decision under Hamming loss satisfies, for every coordinate $j$, $$ a_j^*\in\operatorname*{arg\,max}_{c\in\mathcal{Y}_j}P(Y_j=c\mid X). $$ The same set of minimizers applies to normalized Hamming loss. In the binary case, with $\mathcal{Y}_j=\{0,1\}$, one predicts $1$ when $P(Y_j=1\mid X)>1/2$, predicts $0$ when that probability is less than $1/2$, and either label is optimal at a tie.

Proof. For any fixed vector $a$, finite additivity of conditional expectation yields $$ E[L_H(a,Y)\mid X] =\sum_{j=1}^{m}E[\mathbf{1}\{a_j\ne Y_j\}\mid X] =\sum_{j=1}^{m}\bigl(1-P(Y_j=a_j\mid X)\bigr). $$ For each term, minimizing over $a_j\in\mathcal{Y}_j$ is equivalent to maximizing $P(Y_j=a_j\mid X)$. Since every coordinate combination is allowed, choices that minimize each term can be combined into an allowed vector. Thus their combined vector minimizes the sum. Dividing the loss and risk by the positive constant $m$ does not change the minimizers. For binary labels, comparing the two probabilities $P(Y_j=1\mid X)$ and $P(Y_j=0\mid X)=1-P(Y_j=1\mid X)$ gives the stated threshold rule, including the tie case. $\square$

The theorem also gives the minimum conditional risk directly. With unrestricted predictions, it is the sum over coordinates of one minus the largest marginal label probability; normalized risk is that sum divided by $m$. This is a coordinatewise calculation even when the coordinates of $Y$ are strongly dependent.

Worked Example: Marginal Decoding for a Binary Sequence

At a fixed feature value, suppose the conditional distribution of a four-position binary sequence is a product distribution: the coordinates are independent Bernoulli variables with $P(Y_j=1\mid X)=0.82, 0.47, 0.50,$ and $0.15$, respectively. Every binary sequence is allowed. Find a Bayes prediction and its conditional Hamming risk.

At position 1, $0.82>1/2$, so predict 1; the error probability is $1-0.82=0.18$. At position 2, $0.47<1/2$, so predict 0; its error probability is $0.47$. At position 3, the marginal is exactly $1/2$, so either label has error probability $0.50$; choose 0 to specify one minimizer. At position 4, predict 0, with error probability $0.15$. The resulting prediction is $(1,0,0,0)$.

Its unnormalized conditional risk is $$ 0.18+0.47+0.50+0.15=1.30, $$ so its normalized conditional risk is $1.30/4=0.325$. Choosing 1 instead at the third position leaves the risk unchanged. Independence made the stated product distribution explicit, but the theorem shows that the same answer follows from these marginals under any joint distribution with these coordinate probabilities.

When Predictions Must Be Structurally Valid

Some tasks allow only a subset $\mathcal{C}$ of the full product space as predictions. The separate coordinatewise choices may then fail to form a member of $\mathcal{C}$. For a finite nonempty allowed set, the constrained conditional risk still has an exact marginal expression:

Theorem: If the allowed predictions are $\mathcal{C}\subseteq\mathcal{Y}_1\times\cdots\times\mathcal{Y}_m$, then a conditional Hamming Bayes decision is any $$ a^*\in\operatorname*{arg\,min}_{a\in\mathcal{C}}\sum_{j=1}^{m}\bigl(1-P(Y_j=a_j\mid X)\bigr). $$ Equivalently, it maximizes $\sum_{j=1}^{m}P(Y_j=a_j\mid X)$ over $a\in\mathcal{C}$.

Proof. The conditional-risk identity proved above holds for every vector in the product space, so it holds in particular for each $a\in\mathcal{C}$. Minimizing that identity over the allowed set gives the first expression. The sum contains the constant $m$, independent of $a$, minus $\sum_jP(Y_j=a_j\mid X)$. Minimizing the former is therefore equivalent to maximizing the latter. Finiteness and nonemptiness of $\mathcal{C}$ ensure that a minimizer exists. $\square$

Worked Example: A Parity-Constrained Sequence

Suppose the true three-bit sequence has the conditional distribution

True sequence $Y$	Conditional probability
011	0.36
101	0.34
110	0.30

All three possible true sequences have even parity. Predictions, however, are required to have even parity, so all four even-parity vectors $000,011,101,110$ are allowed. First calculate the coordinate marginals: $$ P(Y_1=1\mid X)=0.34+0.30=0.64,\qquad P(Y_2=1\mid X)=0.36+0.30=0.66,\qquad P(Y_3=1\mid X)=0.36+0.34=0.70. $$

Unconstrained coordinatewise decoding would predict $111$, because all three marginals exceed $1/2$. But $111$ has odd parity and is not allowed. To find the constrained minimizer, compare the expected unnormalized mismatch count for every allowed prediction. Distinct even-parity vectors in this example differ in exactly two positions. Thus predicting one of the three supported vectors incurs loss zero when it is the true vector and loss two for either of the other possible true vectors:

For prediction $011$, the risk is $2(0.34)+2(0.30)=1.28$. For prediction $101$, it is $2(0.36)+2(0.30)=1.32$. For prediction $110$, it is $2(0.36)+2(0.34)=1.40$. For the remaining valid prediction $000$, all three possible truths differ in exactly two positions, so its risk is $2(0.36)+2(0.34)+2(0.30)=2.00$.

The minimum is $1.28$, attained at $011$; its normalized risk is $1.28/3$. The comparison includes $000$, so it establishes that $011$ minimizes risk over the entire allowed set, not merely over the three sequences with positive probability.

Worked Example: Multilabel Prediction

For three labels $A,B,C$, suppose their presence indicators are conditionally independent Bernoulli variables with probabilities $0.70, 0.55,$ and $0.20$, respectively. Any subset of labels is allowed. Under Hamming loss, a predicted subset corresponds to a binary vector, and each label is decided from its own marginal.

The marginal probabilities for presence all exceed $1/2$ for $A$ and $B$, while the probability for $C$ is below $1/2$. The marginal prediction is therefore $\{A,B\}$. Its expected number of label errors is $$ (1-0.70)+(1-0.55)+0.20=0.30+0.45+0.20=0.95. $$ The expected number of correct coordinates does not enter the loss; the risk counts only false absences for included labels and false inclusions for excluded labels. Normalized by three, the conditional risk is $0.95/3$. Again, independence specifies a concrete joint distribution for this example, but only the three marginals are needed for this Hamming-risk calculation.

Common Mistake: Treating Marginal Decisions as Automatically Valid

A frequent error is to conclude that coordinatewise thresholding always solves structured prediction under Hamming loss. The theorem requires that the coordinatewise choices can be combined into an allowed output. In the parity example, thresholding all three marginals gives $111$, which violates the even-parity constraint. It is not a valid decision, even though it minimizes each coordinate risk considered separately.

The correction is to distinguish the unrestricted and constrained problems. With all coordinate combinations allowed, choose a marginal maximizer at every position. With a restricted prediction set, use the same marginal probabilities to calculate the risk of each valid candidate, then minimize over that set. Also, do not mistake this conclusion for a claim that the true coordinates are independent: additivity of the loss, not independence of the response, is what makes the conditional risk decompose.

Key takeaway: Hamming loss turns conditional risk into a sum of coordinatewise error probabilities. Marginal decoding is Bayes-optimal when the output space is unrestricted; under structural constraints, minimize that same sum over the valid predictions.

Check Your Understanding

Use conditional coordinate marginals and the allowed prediction set to answer each question.

For an unrestricted binary sequence with marginal probabilities of 1 equal to $0.2, 0.5,$ and $0.8$, give one Bayes prediction and its unnormalized conditional risk.
Why does the coordinatewise Hamming-risk calculation not require conditional independence of the response coordinates?
In the parity example, what is the unconstrained marginal prediction, and why can it not be used under the stated constraint?
For a constrained output set, explain why minimizing the sum of marginal match probabilities is equivalent to minimizing conditional Hamming risk.
If a coordinate has equal conditional probabilities for its two labels, what can be concluded about the two choices under unrestricted Hamming loss?

Hamming Loss and Marginal Decoding

What You'll Learn