Cost-Sensitive Structured Decoding

Why Structured Predictions Need Cost-Sensitive Decisions

A structured prediction is an output with internal components: a sequence of labels, a set, a parse, or another object assembled under constraints. Two incorrect outputs can have very different consequences. In a sequence, confusing a clinically important label may be more costly than an error at another position; for a set, an extra element may have a different cost from a missed element. A decoder that always chooses the most probable entire output ignores these distinctions.

Cost-sensitive decoding uses the conditional distribution of the true output and a specified task loss. It chooses the feasible prediction with the smallest expected loss, conditional on the input. This is a decision rule, not a new probability model: the distribution describes uncertainty, while the loss describes the consequences of each possible prediction.

Definition: Let $\mathcal{Y}$ be a finite set of possible true structured outputs, and let $\mathcal{A}$ be a finite, nonempty set of feasible predictions. Given input $X=x$, write $p_x(y)=P(Y=y\mid X=x)$. A task loss is a function $\Delta:\mathcal{A}\times\mathcal{Y}\to\mathbb{R}$, where $\Delta(a,y)$ is the cost of predicting $a$ when the truth is $y$. The conditional risk of $a$ is $$ R(a\mid x)=\sum_{y\in\mathcal{Y}}\Delta(a,y)p_x(y). $$ A Bayes decoder is any rule $g^*(x)\in\arg\min_{a\in\mathcal{A}}R(a\mid x)$.

Usually, costs are finite and nonnegative, and a correct prediction has zero cost, but the minimization only requires the stated finite setting. If there is a tie, any minimizing action is Bayes-optimal. A fixed tie-breaking rule gives a definite decoder. Since the sets are finite, the conditional risks are finite sums; if the probabilities $p_x(y)$ are measurable in $x$, a fixed tie-breaking rule also gives a measurable decoder.

The Bayes Rule and Its MAP Special Case

The minimization defining a Bayes decoder can be understood directly: average the cost of each candidate prediction over all possible truths, weighted by their conditional probabilities. The first result states exactly why the smallest such average is the right choice.

Theorem: Suppose $\mathcal{A}$ and $\mathcal{Y}$ are finite, $\Delta$ is finite-valued, and the conditional distribution of $Y$ given $X=x$ is $p_x$. For any fixed $x$, a prediction $a^*$ minimizes conditional expected loss if and only if $$ \sum_{y\in\mathcal{Y}}\Delta(a^*,y)p_x(y) \leq \sum_{y\in\mathcal{Y}}\Delta(a,y)p_x(y) \quad\text{for every }a\in\mathcal{A}. $$

Proof. Conditional on $X=x$, the loss from choosing $a$ is the random quantity $\Delta(a,Y)$. Because $\mathcal{Y}$ is finite, its conditional expectation is the finite sum $$ E[\Delta(a,Y)\mid X=x]=\sum_{y\in\mathcal{Y}}\Delta(a,y)P(Y=y\mid X=x)=R(a\mid x). $$ Thus $a^*$ has the smallest conditional expected loss precisely when $R(a^*\mid x)\leq R(a\mid x)$ for every feasible $a$, which is the displayed condition. A minimizer exists because $\mathcal{A}$ is finite and nonempty. $\square$

The joint maximum a posteriori (MAP) decoder chooses an output of greatest conditional probability. It is a Bayes decoder for one particular loss, not a universal solution to every structured decision problem.

Theorem: If $\mathcal{A}=\mathcal{Y}$ and the task loss is exact-match loss, $$ \Delta(a,y)=\mathbf{1}\{a\ne y\}, $$ then the Bayes decoders are exactly the joint MAP decoders: $$ \arg\min_{a\in\mathcal{Y}}R(a\mid x) = \arg\max_{a\in\mathcal{Y}}P(Y=a\mid X=x). $$

Proof. For any $a\in\mathcal{Y}$, exact-match loss is zero when $Y=a$ and one otherwise. Therefore $$ R(a\mid x)=\sum_{y\ne a}P(Y=y\mid X=x)=1-P(Y=a\mid X=x). $$ Minimizing this risk over $a$ is equivalent to maximizing $P(Y=a\mid X=x)$. The two sets of optimal predictions are consequently equal, including any ties. $\square$

This identity also explains the limit of MAP decoding: it optimizes the probability of getting the entire output exactly right. If the task instead assigns different costs to different errors, its Bayes decoder must use those costs in the risk calculation.

Worked Cost-Sensitive Decoders

Worked Example: Unequal False-Positive and False-Negative Costs

Suppose the possible outputs are binary sequences $y=(y_1,y_2)\in\{00,01,10,11\}$, and the posterior probabilities at a given input are $P(00\mid x)=0.35$, $P(01\mid x)=0.30$, $P(10\mid x)=0.20$, and $P(11\mid x)=0.15$. The joint MAP output is $00$, since it has the largest probability.

Now charge cost 3 for predicting a positive first bit when its truth is negative, and cost 1 for missing a positive first bit. At the second bit, charge cost 1 for a false positive and cost 2 for a false negative. The loss is the sum of the two bitwise costs: $$ \Delta(a,y)=3\mathbf{1}\{a_1=1,y_1=0\} +\mathbf{1}\{a_1=0,y_1=1\} +\mathbf{1}\{a_2=1,y_2=0\} +2\mathbf{1}\{a_2=0,y_2=1\}. $$

The posterior probability that the first true bit is 1 is $P(Y_1=1\mid x)=0.20+0.15=0.35$. Predicting 0 at that position incurs expected false-negative cost $1(0.35)=0.35$; predicting 1 incurs expected false-positive cost $3(0.65)=1.95$. The second bit is 1 with probability $0.30+0.15=0.45$. Predicting 0 there costs $2(0.45)=0.90$, while predicting 1 costs $1(0.55)=0.55$.

Adding the two position-specific risks gives every feasible sequence’s risk: $$ \begin{aligned} R(00\mid x)&=0.35+0.90=1.25,\\ R(01\mid x)&=0.35+0.55=0.90,\\ R(10\mid x)&=1.95+0.90=2.85,\\ R(11\mid x)&=1.95+0.55=2.50. \end{aligned} $$ The cost-sensitive Bayes decoder is $01$, not the MAP output $00$. The second bit is worth predicting positive because its false-positive cost is low enough relative to its posterior probability; the first bit is not, given its much larger false-positive cost.

Worked Example: Asymmetric Costs Between Whole Structures

Let the possible outputs be three structures $\mathcal{Y}=\mathcal{A}=\{u,v,w\}$, with posterior probabilities $0.40,0.35,0.25$, respectively. MAP decoding selects $u$. Suppose the task’s costs depend on the particular confusion, as shown below. Rows are predictions and columns are truths.

Prediction	Truth $u$	Truth $v$	Truth $w$
$u$	0	4	1
$v$	1	0	1
$w$	3	1	0

The risk of predicting $u$ is $0(0.40)+4(0.35)+1(0.25)=1.65$. For $v$, it is $1(0.40)+0(0.35)+1(0.25)=0.65$. For $w$, it is $3(0.40)+1(0.35)+0(0.25)=1.55$. Thus $v$ is the unique Bayes prediction, even though $u$ is most probable. The cost of confusing $v$ with $u$ is large, while predicting $v$ has relatively modest cost under either alternative truth.

The entries need not have any symmetry: the cost of predicting $u$ when the truth is $v$ can differ from the cost of predicting $v$ when the truth is $u$. The decoder follows the supplied task loss, not a presumed symmetry between errors.

Worked Example: Respecting a Structural Constraint

Suppose feasible outputs are the even-parity binary sequences $\mathcal{Y}=\mathcal{A}=\{000,011,101,110\}$. At an input $x$, let their probabilities be $0.05,0.33,0.30,0.32$, respectively. The probability that each bit is 1 is $$ P(Y_1=1\mid x)=0.30+0.32=0.62,\quad P(Y_2=1\mid x)=0.33+0.32=0.65,\quad P(Y_3=1\mid x)=0.33+0.30=0.63. $$ An unconstrained coordinatewise choice would therefore be $111$, which is not a feasible output.

Under Hamming loss, the risk of a candidate sequence is the sum of its bitwise error probabilities. For $000$, this is $0.62+0.65+0.63=1.90$. For the feasible prediction $011$, it is $(1-0.62)+(1-0.65)+(1-0.63)=0.38+0.35+0.37=1.10$. For $101$, it is $0.38+0.65+0.37=1.40$; for $110$, it is $0.38+0.35+0.63=1.36$. Thus the constrained Bayes decoder is $011$. It is also MAP in this example, with probability $0.33$, but the coordinatewise output $111$ cannot be returned by a decoder restricted to feasible structures.

What Additive Costs Do—and Do Not—Simplify

A loss that adds up position-specific costs can simplify risk calculation without eliminating the need to respect the output space. The following identity makes the simplification precise.

Result: Let outputs have $m$ components and suppose $\Delta(a,y)=\sum_{j=1}^{m}\delta_j(a_j,y_j)$, with each component loss finite. Then $$ R(a\mid x)=\sum_{j=1}^{m}E[\delta_j(a_j,Y_j)\mid X=x]. $$ If every combination of component predictions is feasible, minimizing this risk can be done separately for each component. If the feasible set restricts combinations, the sum must instead be minimized over that constrained set.

Derivation. By the definition of conditional risk and the finite sum defining the loss, $$ \begin{aligned} R(a\mid x) &=\sum_{y\in\mathcal{Y}}\left(\sum_{j=1}^{m}\delta_j(a_j,y_j)\right)p_x(y)\\ &=\sum_{j=1}^{m}\sum_{y\in\mathcal{Y}}\delta_j(a_j,y_j)p_x(y)\\ &=\sum_{j=1}^{m}E[\delta_j(a_j,Y_j)\mid X=x]. \end{aligned} $$ The rearrangement is valid because both sums are finite. If all combinations are feasible, each term depends only on $a_j$, so choosing a minimizing $a_j$ for every component minimizes their sum. Under a constraint, those separate choices may not form an allowed output; the valid decision is the minimum of the same risk over feasible $a$. $\square$

The component expectations require only the relevant conditional marginals, even when the joint distribution of the structured output is dependent. But that fact does not authorize returning an infeasible combination. Also, an additive loss is not the only possible task loss: a cost for a whole structure may depend jointly on several components, as in the three-output example.

Common Pitfall: Treating MAP as a Universal Decoder

Wrong reasoning: “The most probable complete output is the best prediction, so I should always decode to the MAP structure.” That conclusion follows only when the task is exact-match accuracy (or when the particular posterior and cost matrix happen to make MAP cost-minimizing). It fails when the costs of errors differ.

Correction: Specify the feasible predictions and the task loss first. For each candidate, compute its posterior expected cost and choose a minimizer. MAP is the resulting rule for exact-match loss; asymmetric position costs, unequal structure-confusion costs, and other task losses generally require a different comparison. A second pitfall is to minimize each component separately when the task imposes global feasibility constraints. In that case, compare expected risks only among feasible outputs.

Key takeaway: A structured Bayes decoder minimizes conditional expected task loss over the feasible prediction set. Joint MAP decoding is the special case for exact-match loss, not a substitute for specifying what errors cost.

Check Your Understanding

Use the posterior distribution and task loss in each question to identify the decision rule that applies.

Why does exact-match loss make a Bayes decoder a joint MAP decoder?
If a loss assigns different costs to predicting 1 when the truth is 0 and predicting 0 when the truth is 1, what posterior quantities and costs determine the choice at one binary component?
For an arbitrary finite loss matrix, what quantity should be calculated for each feasible prediction before decoding?
Why can an unconstrained coordinatewise decision be unsuitable when structured outputs must obey a global constraint?
Does an additive componentwise loss require the components of the true output to be conditionally independent? Explain.

Prediction	Truth \(u\)	Truth \(v\)	Truth \(w\)
\(u\)	0	4	1
\(v\)	1	0	1
\(w\)	3	1	0