Sequence Losses and Dynamic Programming Decoders

Why Sequence Decisions Need More Than Token-Wise Choices

A sequence predictor returns a complete ordered string of labels, such as a sequence of clinical states over time or tags assigned to the words in a sentence. The best decision depends on the loss used to judge the whole string. If errors at individual positions are the only concern, conditional risks can be minimized position by position. But a loss may also penalize implausible or costly changes between adjacent predicted labels. Then the choice at one position affects the cost of its neighbors.

Dynamic programming handles this dependence by keeping track of the least conditional risk for each possible final label of a prefix. The method is exact when the sequence risk is additive over positions and adjacent pairs. It does not require the true labels at different positions to be independent.

Additive Sequence Loss and Conditional Risk

Let the sequence length be $T$, and let $\mathcal{Y}$ be a finite set of labels. Write $Y=(Y_1,\ldots,Y_T)$ for the true sequence and $a=(a_1,\ldots,a_T)\in\mathcal{Y}^T$ for a proposed prediction. Given observed features $X=x$, the conditional risk of $a$ is its expected loss under the conditional distribution of $Y$ given $X=x$.

Definition: An additive token-and-transition sequence loss has the form $$ L(a,Y)=\sum_{t=1}^{T} \ell_t(a_t,Y_t) +\sum_{t=2}^{T} \kappa_t(a_{t-1},a_t,Y_{t-1},Y_t), $$ where $\ell_t$ is the loss at position $t$, and $\kappa_t$ is the loss associated with the predicted and true adjacent labels at positions $t-1,t$. Define the conditional token risk and conditional transition risk by $$ q_t(a\mid x)=E[\ell_t(a,Y_t)\mid X=x],\qquad r_t(u,v\mid x)=E[\kappa_t(u,v,Y_{t-1},Y_t)\mid X=x]. $$ The conditional risk of the complete prediction is therefore $$ R(a\mid x)=\sum_{t=1}^{T}q_t(a_t\mid x) +\sum_{t=2}^{T}r_t(a_{t-1},a_t\mid x). $$

These expressions require the relevant conditional expectations to exist and be finite. Since the loss is a sum, conditional expectation distributes over its terms. This gives the displayed risk exactly; it does not require independence among the $Y_t$. In particular, a transition risk may depend on the joint conditional distribution of $(Y_{t-1},Y_t)$, not merely on separate one-position probabilities.

A common special case adds a penalty $\lambda\geq 0$ whenever adjacent predicted labels differ. In that case, $r_t(u,v\mid x)=\lambda\,\mathbf{1}\{u\ne v\}$, where $\mathbf{1}\{\cdot\}$ is one when its condition holds and zero otherwise. More general transition risks can distinguish particular label pairs or reflect uncertainty about the true adjacent labels.

Worked Example: A Switch Penalty in a Three-Position Sequence

Suppose the labels are $A$ and $B$, the sequence has three positions, and each change between consecutive predicted labels costs $\lambda=0.25$. At the observed $x$, the conditional token risks are

\begin{array}{c|cc} t & q_t(A\mid x) & q_t(B\mid x)\\ \hline 1 & 0.2 & 0.6\\ 2 & 0.7 & 0.1\\ 3 & 0.4 & 0.3 \end{array}

Let $D_t(v)$ be the minimum risk for positions $1,\ldots,t$, among sequences whose label at position $t$ is $v$. At the first position, $D_1(A)=0.2$ and $D_1(B)=0.6$. For position 2:

\begin{aligned} D_2(A)&=0.7+\min\{0.2,\;0.6+0.25\}=0.9,\\ D_2(B)&=0.1+\min\{0.2+0.25,\;0.6\}=0.55. \end{aligned}

The minimizing predecessor for $D_2(A)$ is $A$, and that for $D_2(B)$ is $A$. At position 3:

\begin{aligned} D_3(A)&=0.4+\min\{0.9,\;0.55+0.25\}=1.2,\\ D_3(B)&=0.3+\min\{0.9+0.25,\;0.55\}=0.85. \end{aligned}

The smaller final value is $D_3(B)=0.85$, and its predecessor is $B$; that $B$ has predecessor $A$. Backtracking gives $A,B,B$. Its token cost is $0.2+0.1+0.3=0.6$, and its one switch costs $0.25$, so its total risk is $0.85$. Independent token minimization would also choose $A,B,B$, with the same total risk. In this example the DP output agrees with independent token minimization; transition costs can, but need not, change the optimal sequence.

The Dynamic Programming Recurrence

For a fixed observed $x$, suppress $x$ from the notation. For each prefix ending in label $v$, define its minimum conditional risk by

D_t(v)=\min_{\substack{(a_1,\ldots,a_t)\in\mathcal{Y}^t\\a_t=v}} \left\{\sum_{s=1}^{t}q_s(a_s)+ \sum_{s=2}^{t}r_s(a_{s-1},a_s)\right\}.

At $t=1$, there are no transition terms, so $D_1(v)=q_1(v)$. For $t\geq 2$, any prefix ending at $v$ must have some preceding label $u$. The best prefix with that predecessor has risk $D_{t-1}(u)$, and appending $v$ adds $r_t(u,v)+q_t(v)$.

Theorem: For a finite label set and finite conditional risks, the minimum-risk sequence is obtained from $$ D_1(v)=q_1(v),\qquad D_t(v)=q_t(v)+\min_{u\in\mathcal{Y}}\{D_{t-1}(u)+r_t(u,v)\}, \quad t=2,\ldots,T. $$ The minimum conditional risk is $\min_{v\in\mathcal{Y}}D_T(v)$. Storing a minimizing predecessor at each step and tracing these predecessors backward returns a sequence attaining that risk.

Proof. The base case follows directly from the definition: a one-position prefix ending in $v$ consists only of $v$, with risk $q_1(v)$. Suppose the stated recurrence gives the minimum risk for every prefix of length $t-1$. Consider a prefix of length $t$ ending in $v$. Its preceding label is some $u$. The first $t-1$ positions then have risk at least $D_{t-1}(u)$, while the last transition and token contribute $r_t(u,v)+q_t(v)$. Thus every such prefix has risk at least the right side of the recurrence, minimized over $u$. Conversely, choose a minimizing $u$ and a prefix attaining $D_{t-1}(u)$, which exists because the set of prefixes is finite. Appending $v$ attains that right side. The recurrence therefore equals the minimum risk at length $t$. Induction proves the claim for every $t$. Finally, every complete sequence ends in some $v$, so minimizing $D_T(v)$ gives the best complete sequence. Following the stored minimizing predecessors reconstructs a prefix attaining each value, hence an optimal complete sequence. $\square$

Initialize.
Set $D_1(v)=q_1(v)$ for every possible first label.

Extend each prefix.
For each position $t$ and ending label $v$, minimize the preceding prefix risk plus the transition risk into $v$, then add $q_t(v)$.

Store predecessors.
Record a label $u$ attaining the minimum for each pair $(t,v)$; if there is a tie, any minimizer can be stored to obtain one optimal sequence.

Terminate and backtrack.
Choose a label minimizing $D_T(v)$, then follow the stored predecessors from position $T$ to position 1.

Worked Example: A Transition Penalty Changes the Decision

Use two labels $A,B$, two positions, and a switch penalty of $0.5$. Let the token risks be $q_1(A)=0.1,\ q_1(B)=0.3,\ q_2(A)=0.3,\ q_2(B)=0.1$. Independent minimization chooses $A$ first and $B$ second, but that sequence incurs a switch.

Initialization gives $D_1(A)=0.1$ and $D_1(B)=0.3$. The recurrence gives

\begin{aligned} D_2(A)&=0.3+\min\{0.1,\;0.3+0.5\}=0.4,\\ D_2(B)&=0.1+\min\{0.1+0.5,\;0.3\}=0.4. \end{aligned}

There is a tie: $A,A$ has risk $0.1+0.3=0.4$, and $B,B$ has risk $0.3+0.1=0.4$. The independently selected sequence $A,B$ has risk $0.1+0.1+0.5=0.7$; $B,A$ has risk $0.3+0.3+0.5=1.1$. Thus the transition term changes the set of optimal predictions. Both constant-label sequences are optimal, and backtracking with either tied final label returns one of them.

Transition Risks That Depend on the True Sequence

The recurrence is not limited to a penalty for predicted switches. If the transition loss itself depends on the true adjacent labels, its conditional expectation becomes an edge cost $r_t(u,v\mid x)$. The dynamic program needs these expected edge costs, but it does not need to retain the entire conditional distribution of the true sequence once those costs have been computed.

Worked Example: Expected Costs for Adjacent Label Pairs

Consider two positions and labels $0,1$. Suppose the conditional token risks are $q_1(0)=0.3,\ q_1(1)=0.2,\ q_2(0)=0.1,\ q_2(1)=0.4$. The conditional expected transition risks for the predicted pair are $r_2(0,0)=0,\ r_2(0,1)=0.2,\ r_2(1,0)=0.1,\ r_2(1,1)=0$. These can arise from a transition loss depending on both predicted and true adjacent labels; the listed values are already its conditional expectations.

Initialize $D_1(0)=0.3$ and $D_1(1)=0.2$. For a final label 0:

D_2(0)=0.1+\min\{0.3+0,\;0.2+0.1\}=0.4.

Both predecessors tie, so $00$ and $10$ each attain risk $0.4$. For a final label 1:

D_2(1)=0.4+\min\{0.3+0.2,\;0.2+0\}=0.6.

The minimum total risk is $0.4$; either $00$ or $10$ is optimal. The calculation uses the expected pairwise costs directly, so it remains valid whether or not the true labels at the two positions are conditionally independent.

For $K=|\mathcal{Y}|$ labels, the recurrence examines at most $K$ predecessors for each of $K$ possible current labels at each of $T-1$ positions. Its time complexity is $O(TK^2)$. Storing all predecessor choices uses $O(TK)$ memory; the risk values alone can be updated using $O(K)$ memory, though reconstruction then requires separately retaining or recomputing predecessor information. These bounds describe the dense case in which every adjacent label pair is allowed.

Common Pitfalls and Why the Loss Matters

The dynamic program minimizes the conditional risk specified by the task. It is not automatically a most-probable-sequence decoder: maximizing the joint conditional probability of a sequence is the appropriate rule for exact-match loss, whereas additive token-and-transition loss generally asks for a different optimization. The two can coincide in particular models, but neither objective should be substituted for the other without checking the loss.

Ignoring transition costs. Minimizing each $q_t$ separately is optimal only when the risk contains no coupling between positions, or when the resulting choices happen also to minimize the full objective. A switch penalty can make a slightly worse token choice preferable overall.
Greedily extending only one prefix. Keeping only the single best prefix at each position is not enough. A prefix that is currently more expensive may end in a label that makes later transitions much cheaper. The recurrence retains the best prefix for every possible ending label.
Assuming independence of the true labels. Additivity of the loss lets us sum conditional expectations, but it does not assert independence. Edge risks may require the conditional distribution of adjacent true-label pairs.
Dropping the final minimization or backtracking. The recurrence gives a value for each possible ending label. The smallest of those values determines the optimal risk; stored predecessors are needed to recover the sequence itself.

Key takeaway: When conditional sequence risk is a sum of token risks and adjacent-transition risks, a minimum-risk decoder can be found exactly by dynamic programming. The essential state is the final label of the prefix, because that label determines the transition cost of the next step.

Check Your Understanding

Work through these questions using the definitions and recurrence above.

Why can conditional expectation be applied term by term to an additive sequence loss without assuming that the true labels are independent?
For a sequence of length two, write the dynamic programming expression for the minimum risk among predictions whose second label is $v$.
In the two-position switch-penalty example, why is $A,B$ not optimal even though it uses the individually best token label at each position?
What information must be stored to reconstruct an optimal sequence after computing all the $D_t(v)$ values?
How would the recurrence change if there were an additional cost depending only on the final predicted label?