Connectionist Temporal Classification and Monotonic Alignment

Frame-level models are easy to train and hard to label. A recurrent network with a softmax over an alphabet at every step produces a distribution per frame, and the loss for such an output is a per-frame cross-entropy, which needs a target symbol for every frame. Speech recordings arrive with a transcript and no frame boundaries, handwriting arrives as a pen trajectory with a word sequence, and gesture streams arrive with no segmentation at all. Connectionist temporal classification defines a loss for exactly that setting: the input is a sequence of $T$ frames of features, the target is a sequence of $U$ labels with $U \le T$, and nothing else is known.

The alignment problem

The quantity that must be maximized is $p(y \mid x)$ for a target labelling $y$ and an input $x$, under a model that emits one symbol per frame. Introducing a latent alignment $\pi$ of length $T$ over the alphabet of labels plus a blank symbol makes the labelling a deterministic function of the alignment, and the conditional probability of the labelling is the sum of the probabilities of every alignment that maps to it:

$$p(y \mid x) = \sum_{\pi \in \mathcal{B}^{-1}(y)} p(\pi \mid x), \qquad p(\pi \mid x) = \prod_{t=1}^{T} p(\pi_t \mid x)$$

The number of alignments of length $T$ over an alphabet of size $|\Sigma| + 1$ grows as $(|\Sigma|+1)^{T}$, so enumerating them is not an option; for a vocabulary of 30 symbols and a 100-frame recording the count is astronomical. The product form of $p(\pi \mid x)$ is what makes the sum tractable, and it is also a modelling assumption: frames are conditionally independent given the input, so the network’s per-frame distributions carry no dependency on one another. Nothing in the loss requires the outputs to be consistent over time; consistency has to come from the input’s own context, which is why the frames fed to the softmax are the outputs of a recurrent or other contextual network rather than raw features.

Collapsing an alignment to a labelling

The map $\mathcal{B}$ removes the blanks and merges consecutive repeats. An alignment $a,a,_,a$ over the alphabet ${a, b, _}$ collapses to $a,a$, while $a,a,a$ collapses to a single $a$. The blank therefore does two jobs at once: it marks positions where the model is not committing to any label, and it separates two emissions of the same label, so a labelling containing a doubled letter requires at least one blank somewhere between the two occurrences. Two consequences follow immediately. The target length cannot exceed the input length, since collapsing only ever shortens a sequence, and a model that must emit repeated labels back to back has to learn to insert blanks at the right place.

The rule also fixes which alignments are counted. Because blanks are removed entirely, an alignment and the same alignment with extra blanks inserted are both valid representatives of the same labelling, and both contribute to the sum. This is the reason the probability of a labelling cannot be read off the highest-probability alignment: several distinct alignments share the same collapsed output, and their probabilities add.

The lattice recursion

The sum is computed on a lattice. The target labelling is extended to length $2U + 1$ by interleaving blanks: $\ell’ = _ , y_1, _ , y_2, \dots , y_U, _$. A forward variable $\alpha_t(s)$ is the total probability of all alignments of the first $t$ frames that end at position $s$ of the extended labelling, and it satisfies a recursion over three predecessors:

$$\alpha_t(s) = \big(\alpha_{t-1}(s) + \alpha_{t-1}(s-1) + [\ell’s \neq _ \text{ and } \ell’s \neq \ell’{s-2}], \alpha{t-1}(s-2)\big), p(\ell’_s \mid x_t)$$

The third term is the one that encodes the collapse rule, and the condition on it is exact: moving two positions in the extended labelling means skipping a symbol, which is only allowed when the current symbol is not a blank and is not a repetition of the symbol before the skipped one, because two identical symbols separated by a blank collapse to two labels while the same two symbols adjacent collapse to one. Evaluation costs $O(T \cdot U)$ time, since each of the $T \cdot (2U+1)$ lattice nodes reads three predecessors, and the same recursion can be run backwards to obtain the posterior probability of each lattice node given the target, which is what the gradient needs. Memory is $O(T \cdot U)$ if the forward and backward tables are both stored, and $O(U)$ if the recursion is run twice with the backward pass recomputing what it needs.

Storing the full tables also gives a by-product that costs nothing extra: the alignment distribution $p(\pi \mid x, y)$, obtained from the forward and backward variables, shows which frames and which label positions the model associates. The alignment is monotonic by construction, since the lattice only ever moves forward in the extended labelling, so a target whose realisation requires revisiting an earlier position cannot be represented at all.

Two details of the extended labelling are easy to get wrong. It begins and ends with a blank, so a valid path may start at either of the first two positions and must end at either of the last two; a recursion that lets a path begin directly at the first label position is computing a different quantity. The loss itself is the negative log of the total probability, summed over the batch and divided either by the number of frames or by the number of labels, depending on the convention. The choice changes the effective weight of long sequences and has to match between training and evaluation.

Decoding: the best path is not the best labelling

The frame-level posterior is not itself a decision. Taking the most probable symbol at each frame and collapsing the result is the best-path decode, and it minimizes the error at the frame level rather than the error at the labelling level, because two different paths that collapse to the same labelling are treated as competing decisions rather than as one. It is also the cheapest decode: $T$ argmax operations over the alphabet, one per frame.

Searching for the labelling with the largest total probability requires merging paths that share a collapsed prefix, which is what prefix beam search does. Each prefix keeps two accumulated probabilities, one for paths ending in a blank and one for paths ending in the last label of the prefix, and both matter when the next symbol equals that last label: extending a prefix that already ends in $a$ with another $a$ leaves the labelling unchanged if the previous frame was a blank and does not if the previous frame was an $a$. Merging the two cases at the wrong time silently drops probability mass, which is why the two values are carried separately and only combined where the collapse rule says they should be.

A language model can be combined with the acoustic scores during the search, but the combination is external to the training objective: the conditional independence between frames inside the loss means the model itself never learns the probability of a sequence of labels given other labels, it only learns which labels are plausible at which frames. That is the price of the tractable marginalization. The letters-and-blank formulation also has no notion of the target sequence predicting itself, so an extension that adds a prediction network over emitted labels and an output network over frames, computing $p(k \mid t, \text{label history})$, provides that dependency directly. Decoding either variant with a beam is the same search problem, with the same questions of pruning and length scoring described in beam search decoding.

Where the assumption binds

Conditional independence across frames is not the same as independence across the input, and the distinction matters for what a network trained with this loss can do. Context still enters through the input frames, so a bidirectional recurrent network over the whole recording can produce frame distributions that depend on both sides, and the alignment stays monotonic without requiring causality. Streaming applications cannot use that form, and the alternatives either accept a fixed lookahead or use a monotonic attention mechanism of the kind discussed in attention as content-based alignment, where the alignment is a learned distribution over positions rather than a sum over paths.

The length constraint is the second binding limit. Since the collapse step can only remove positions, a target longer than the input frame count has probability zero under the model, and frames that carry several labels apiece are unrepresentable. For speech this is not a practical constraint, because frame rates are far above label rates; for tasks where the input and output are of similar length, the formulation does not apply, and a per-position loss with explicit alignment supervision is more direct.