Pitfalls in Label Encodings and Structured Decoding

Why Encoding and Decoding Choices Matter

A class name is often just a name. Replacing “case,” “control,” and “other” with different symbols should not change which class is most probable or which decision minimizes a stated loss. But an algorithm can treat labels as numbers, and numbers carry order and distance whether or not the labels have any meaningful order or distance. That can make an arbitrary coding choice affect the fitted rule.

A related issue arises in structured prediction. A model may produce sensible predictions for each component separately, yet the assembled output may violate constraints such as “exactly one label is active” or “the sequence must follow a valid transition.” Finally, a training loss and an evaluation loss need not prefer the same decision. These are distinct failure modes: a representation can introduce unintended geometry, a decoder can ignore feasibility, and an objective can target the wrong notion of error.

The central diagnostic question is: what is the set of allowable decisions, and which loss is the decision supposed to minimize? Once these are explicit, the effects of an encoding or decoding choice can be checked rather than assumed.

Nominal Labels Are Not Measurements

Let \(\mathcal{C}=\{c_1,\ldots,c_K\}\) be a finite set of classes. For a feature value \(x\), write \(p_k(x)=P(Y=c_k\mid X=x)\). Under zero-one loss, an incorrect class costs one and a correct class costs zero, so the conditional risk of predicting \(c_k\) is \(1-p_k(x)\). The Bayes decision is therefore any class attaining the largest conditional probability.

This invariance is a property of the zero-one Bayes decision, not a guarantee that every numerical algorithm will have it. For example, if labels \(0,1,2\) are treated as real-valued responses and squared error is minimized, the conditional mean is used. That operation regards the code differences as meaningful. Decoding the resulting mean to the nearest code then imposes a further geometry on the classes.

Proof. At a fixed \(x\), predicting class \(a\) incurs conditional loss \(0\) when \(Y=a\) and \(1\) otherwise. Thus its conditional risk is \(R(a\mid x)=0\cdot P(Y=a\mid x)+1\cdot P(Y\ne a\mid x)=1-p_a(x)\). Minimizing \(1-p_a(x)\) over \(a\) is equivalent to maximizing \(p_a(x)\). Let \(\pi\) be a bijection on the class names and define the relabeled probabilities by \(p'_{\pi(a)}(x)=p_a(x)\). Then \(p_a(x)\ge p_b(x)\) exactly when \(p'_{\pi(a)}(x)\ge p'_{\pi(b)}(x)\). Hence the maximizers are mapped to the corresponding relabeled maximizers, including any ties. \(\square\)

This result concerns the target Bayes rule. A particular training algorithm may still depend on label representation because of its parameterization, regularization, optimization, or a loss that assigns numerical distances to codes. The theorem does not say that every fitted model is automatically invariant; it identifies the behavior that a nominal-class decision under zero-one loss should have.

Valid Outputs and Componentwise Decoding

Structured prediction has an additional requirement: predictions must belong to the allowed output set. Let \(\mathcal{Y}\) be the set of valid outputs. For example, a structured label might be a sequence with allowed transitions, a matching, a tree, or a binary vector satisfying a cardinality constraint. A decoder that chooses components independently can return an element of a larger unconstrained space rather than an element of \(\mathcal{Y}\).

Marginal decoding can be appropriate for Hamming loss when each output coordinate is assessed separately. But that fact does not remove feasibility constraints. In particular, if marginal probabilities tie, different coordinatewise tie-breaking rules can yield different assembled outputs, some of which may be invalid.

A useful distinction is between estimating components and selecting an output. Marginal probabilities describe the separate components, while a structured decoder maps those probabilities or other model scores to one joint output. If the task requires feasibility, validity must be enforced by the decoder or by a representation whose outputs are guaranteed to be valid. It should not be assumed to follow automatically from accurate marginal estimation.

Training Loss and Evaluation Loss

A prediction rule is judged by its evaluation loss, not merely by the objective used to fit its parameters. In a finite decision problem, let \(\mathcal{A}\) be the allowed actions, \(\mathcal{Y}\) the possible truths, and \(L(a,y)\) the evaluation loss for taking action \(a\) when the truth is \(y\). Given \(X=x\), the conditional risk of action \(a\) is the posterior average loss.

Proof. For any measurable rule \(g\), conditioning on \(X\) gives \(E[L(g(X),Y)]=E[E[L(g(X),Y)\mid X]]=E[R_L(g(X)\mid X)]\). Because the action and outcome sets are finite and the conditional risks are measurable, fix an ordering of \(\mathcal{A}\) and choose the first action attaining the minimum at each \(X\). This produces a measurable rule \(g^*\). For every \(X\), by its construction, \(R_L(g^*(X)\mid X)\le R_L(g(X)\mid X)\). Taking expectations preserves the inequality, so \(E[L(g^*(X),Y)]\le E[L(g(X),Y)]\). Thus the pointwise Bayes action minimizes expected evaluation loss. \(\square\)

The distinction also applies to structured problems. A surrogate loss can be useful for fitting, but the final decision should be checked against the task loss and the feasible output set. Minimizing a surrogate objective does not, by itself, establish that the decoded prediction minimizes task risk. The connection requires conditions relating surrogate risk to task risk and a decoder that respects the decision problem.

Common Mistakes and Practical Checks

• Wrong reasoning: “The labels are numbers, so their differences are meaningful.” Correct the interpretation first: a code is only a name unless the problem supplies a meaningful order or distance. For nominal classes, check whether changing the code assignment changes predictions.
• Wrong reasoning: “Every marginal prediction is correct, so the assembled output must be valid.” Coordinatewise correctness does not enforce a joint constraint. Verify that each decoded output lies in \(\mathcal{Y}\), including outputs produced at ties.
• Wrong reasoning: “The model was trained with a loss, so its predictions minimize the evaluation loss.” Training and evaluation objectives can rank actions differently. Write down the conditional evaluation risks and compare them for the candidate actions.
• Wrong reasoning: “A well-calibrated probability model needs no task-specific decoder.” Probabilities describe uncertainty; a decision requires a loss and an action set. Use the evaluation costs and feasibility constraints when mapping probabilities to actions.