Connectionist Temporal Classification

Connectionist temporal classification (CTC) is a loss function and output layer that lets a neural network learn to transcribe a sequence, such as a line of text, a handwritten word or an utterance, from pairs of inputs and transcriptions alone, without knowing which part of the input corresponds to which character. The network emits, at every input step, a distribution over the characters plus an extra “blank” symbol; CTC defines the probability of a transcription as the sum over every way of spreading it across the input steps, and computes that sum, and its gradient, with a dynamic program. Graves, Fernández, Gomez and Schmidhuber introduced it at ICML 2006 at IDSIA, demonstrating it on phonetic labelling of speech, and it is the training objective of many segmentation-free recognizers in optical character recognition, from handwriting line recognizers (Graves et al., 2009) to scene text models such as CRNN. The 2006 paper uses “temporal classification” for the task of labelling unsegmented sequences and “connectionist temporal classification” for doing it with recurrent networks; the name is also used for the loss itself, as in PyTorch’s CTCLoss.

Definition

CTC turns a network that outputs one probability distribution per input step into a model of $p(\mathbf{l} \mid \mathbf{x})$, the conditional probability of a label sequence $\mathbf{l}$ (a word, a line of characters, a phoneme string) given an input sequence $\mathbf{x}$ of length $T$, for every $\mathbf{l}$ no longer than $T$. It does so in three steps (Graves et al., 2006):

1. The output layer is a softmax over the label alphabet $L$ plus one extra unit, the blank, so that $y_k^t$ is the probability of label or blank $k$ at step $t$.
2. A path $\pi$ chooses one symbol of $L' = L \cup \{\text{blank}\}$ at every step; its probability is the product of the chosen outputs.
3. A many-to-one map $\mathcal{B}$ collapses each path to a label sequence by merging repeated symbols and then deleting blanks, and $p(\mathbf{l} \mid \mathbf{x})$ is the total probability of all paths that collapse to $\mathbf{l}$.

Training minimizes $-\ln p(\mathbf{z} \mid \mathbf{x})$ for the correct transcription $\mathbf{z}$, the maximum likelihood principle behind cross-entropy loss, here applied to whole sequences rather than single labels. Inference, which Graves et al. call decoding, looks for the most probable $\mathbf{l}$.

Intuition

A text recognizer that scans a line from left to right sees each character over several columns, and sees gaps, ligatures and half-characters in between. Training it as a per-column classifier, which Graves et al. call framewise classification, needs a label for every column, so the training lines would have to be segmented by hand or by a separate aligner, and the per-column outputs would still need post-processing into a string. The 2006 paper presents CTC as a way to remove both requirements.

CTC asks only that the network’s column labels, read left to right with repeats merged and blanks dropped, spell the transcription. The network may emit a character at any column where it has seen enough evidence, keep emitting it for a while (the repeats merge) and say “nothing here” with the blank everywhere else. Every such reading counts, so the loss rewards the total probability of all acceptable alignments rather than one alignment fixed in advance. Graves et al. (2006, Fig. 1) found that trained CTC networks predict the labels, phonemes in their figure, as a series of spikes separated by strongly predicted blanks, in contrast to framewise networks that try to cover each segment.

The blank does two jobs. It lets the network output nothing over gaps and transitions, and it separates genuine double letters: with blanks, “OO” can only be produced by a path such as O-O, while OO collapses to a single “O”. Graves (2012, §7.2.1) notes that the original formulation of CTC had no blank and collapsed only repeats; it could not output the same label twice in a row and forced the network to keep predicting one label until the next began, a burden when labelled segments are separated by unlabelled stretches such as pauses in speech.

Formal Definition

Paths and the collapsing map

Following Graves et al. (2006), let the network map an input $\mathbf{x}$ of length $T$ to outputs $y_k^t$, $t = 1, \dots, T$, $k \in L'$, each row summing to one. Then

$$p(\pi \mid \mathbf{x}) = \prod_{t=1}^{T} y_{\pi_t}^{t}, \qquad \pi \in L'^{\,T}.$$

The product assumes that the outputs at different steps are conditionally independent given the network’s internal state, which the paper ensures by allowing no feedback from the output layer into the network. The map $\mathcal{B}: L'^{\,T} \to L^{\leq T}$ removes repeated labels and blanks; the paper’s example is $\mathcal{B}(\texttt{a-ab-}) = \mathcal{B}(\texttt{-aa--abb}) = \texttt{aab}$. Graves (2012, §7.2) states the order explicitly, repeats first and then blanks, which the example requires. The probability of a labelling is

$$p(\mathbf{l} \mid \mathbf{x}) = \sum_{\pi \in \mathcal{B}^{-1}(\mathbf{l})} p(\pi \mid \mathbf{x}).$$

The number of paths in the sum grows exponentially with $T$. For a labelling of length $U$ without repeated adjacent labels, Hannun (2017) gives the count as $\binom{T+U}{T-U}$, about $2 \times 10^{40}$ for $T = 100$ and $U = 50$ (Hannun writes “almost $10^{40}$”); the example below checks this count by enumeration.

The forward–backward algorithm

The sum is computed by dynamic programming, in the manner of the forward–backward algorithm for hidden Markov models. The labelling is extended to $\mathbf{l}'$ by putting a blank $b$ at the start, at the end and between every pair of labels, so $|\mathbf{l}'| = 2|\mathbf{l}| + 1$. The forward variable $\alpha_t(s)$ is the total probability of all path prefixes of length $t$ that collapse to the first $\lfloor s/2 \rfloor$ labels and end at symbol $\mathbf{l}'_s$. Every valid path starts with a blank or with the first label:

$$\alpha_1(1) = y_b^1, \qquad \alpha_1(2) = y_{l_1}^1, \qquad \alpha_1(s) = 0 \;\; \text{for } s > 2.$$

At each later step a path may stay on the same symbol, advance by one, or skip a blank to reach the next label; the skip is forbidden when the current symbol is a blank and when it repeats the label two positions back, because a blank must then separate the two:

$$\alpha_t(s) = \begin{cases} \bar\alpha_t(s)\, y_{l'_s}^{t} & \text{if } l'_s = b \text{ or } l'_{s-2} = l'_s, \\[2pt] \big(\bar\alpha_t(s) + \alpha_{t-1}(s-2)\big)\, y_{l'_s}^{t} & \text{otherwise,} \end{cases} \qquad \bar\alpha_t(s) = \alpha_{t-1}(s) + \alpha_{t-1}(s-1).$$

A complete path ends on the last label or the final blank, so

$$p(\mathbf{l} \mid \mathbf{x}) = \alpha_T(|\mathbf{l}'|) + \alpha_T(|\mathbf{l}'| - 1).$$

The backward variable $\beta_t(s)$ is the mirror image, the total probability of path suffixes from $t$ to $T$ that complete the labelling from $\mathbf{l}'_s$, initialized at $\beta_T(|\mathbf{l}'|) = y_b^T$ and $\beta_T(|\mathbf{l}'|-1) = y^T_{l_{|\mathbf{l}|}}$ and computed by the same recursion run backwards, with the skip from $s$ to $s+2$ allowed under the reverse condition. Some variables are always zero: $\alpha_t(s) = 0$ for $s < |\mathbf{l}'| - 2(T-t) - 1$, since too few steps remain to finish the labelling, and $\beta_t(s) = 0$ for $s > 2t$. In our reading of the recursion, each step touches $2U + 1$ states, so computing $p(\mathbf{l} \mid \mathbf{x})$ costs $O(TU)$ operations instead of a sum over exponentially many paths.

Because both variables include the output at step $t$, their product divided by that output is the probability of all complete paths passing through $\mathbf{l}'_s$ at time $t$, and summing over $s$ gives the labelling probability at every $t$:

$$p(\mathbf{l} \mid \mathbf{x}) = \sum_{s=1}^{|\mathbf{l}'|} \frac{\alpha_t(s)\, \beta_t(s)}{y_{l'_s}^{t}} \qquad \text{for every } t.$$

Graves (2012, §7.3) defines $\beta$ without the output at step $t$, so the book’s version of this identity and of the gradient below has no division by $y$; the two conventions give the same gradient.

Log space

The products of probabilities underflow on long sequences. The 2006 paper rescales the forward and backward variables at every step by their sums $C_t$ and $D_t$, and recovers $\ln p(\mathbf{l} \mid \mathbf{x}) = \sum_t \ln C_t$. Graves (2012, §7.3.1) recommends instead running the whole recursion on logarithms, adding two log-probabilities with

$$\ln(a + b) = \ln a + \ln\!\big(1 + e^{\ln b - \ln a}\big),$$

and calls rescaling less robust, able to fail for very long sequences. Hannun (2017) gives the same advice, with the larger argument taken as $\ln a$, and adds that decoding should also be done in log space.

Loss and gradient

The CTC objective is the negative log-likelihood of the training transcriptions,

$$\mathcal{O} = -\sum_{(\mathbf{x}, \mathbf{z}) \in S} \ln p(\mathbf{z} \mid \mathbf{x}).$$

Differentiating the identity above with respect to $y_k^t$ involves only the positions $\mathrm{lab}(\mathbf{z}, k) = \{s : z'_s = k\}$ where label $k$ occurs in $\mathbf{z}'$. Through the softmax, the gradient with respect to the unnormalized output $u_k^t$ is (Graves et al., 2006, eq. 16, written here without rescaling)

$$\frac{\partial\, (-\ln p(\mathbf{z} \mid \mathbf{x}))}{\partial u_k^t} = y_k^t - \frac{1}{p(\mathbf{z} \mid \mathbf{x})\, y_k^t} \sum_{s \in \mathrm{lab}(\mathbf{z}, k)} \alpha_t(s)\, \beta_t(s).$$

The subtracted term is the posterior probability, under the model, that the alignment emits $k$ at step $t$ given the correct transcription. The gradient therefore has the form of the softmax cross-entropy gradient, prediction minus target, with a soft target that the network itself supplies by weighing all alignments; backpropagation through time carries it into the network. The 2006 paper (Fig. 4) shows the error signal of a network early in training determined by the target sequence alone, then localizing around the network’s spikes, then nearly vanishing once the labelling is predicted confidently.

Decoding

The ideal output is $\arg\max_{\mathbf{l}} p(\mathbf{l} \mid \mathbf{x})$. Graves et al. (2006) knew of no general tractable algorithm for it, and the methods in use are approximations.

Best path

Best-path decoding, also called greedy decoding, takes the most probable symbol at each step and collapses the result, $\mathbf{l} \approx \mathcal{B}(\pi^*)$ with $\pi^* = \arg\max_\pi p(\pi \mid \mathbf{x})$. Because the outputs are conditionally independent, $\pi^*$ is just the per-step argmax, so the method costs one pass over the outputs. It assumes that the most probable path belongs to the most probable labelling, which can fail: Graves (2012, Fig. 7.5) shows a case where the single best path is all blanks, while the many paths that emit a weakly predicted “A” over several steps add up to more. Hannun (2017) gives the same kind of example with paths of length three.

Prefix search

Prefix search decoding (Graves et al., 2006; Graves, 2012, Algorithm 7.1) is a best-first search through the tree of labelling prefixes. A modified forward recursion gives, for each prefix $\mathbf{p}$ and step $t$, the probability $\gamma_t(\mathbf{p}^{n})$ of having output $\mathbf{p}$ with a non-blank at $t$ and $\gamma_t(\mathbf{p}^{b})$ with a blank at $t$, and with them the probability of $\mathbf{p}$ as a complete labelling and the total probability of all its extensions. The search always expands the prefix whose extensions are most probable and stops when a complete labelling is more probable than every unexpanded prefix. Given enough time it finds the most probable labelling, but the number of prefixes can grow exponentially with $T$. For their experiments Graves et al. split the output sequence at steps where the blank probability exceeds a threshold (99.99% on TIMIT), decoded each section separately and concatenated the results; the heuristic can fail, for example when the same label is predicted weakly on both sides of a boundary.

On TIMIT phoneme labelling with 61 phonemes, the 2006 paper reported a label error rate (edit distance divided by the number of target labels) of 31.47 ± 0.21% for best path and 30.51 ± 0.19% for prefix search, means over five runs. With 39 phoneme classes on the TIMIT core test set, Graves (2012, Table 7.3) reports 25.2 ± 0.2% and 24.6 ± 0.2% over ten runs.

Prefix beam search

The CTC beam search of Graves and Jaitly (2014, Algorithm 1), often called prefix beam search, keeps the $W$ most probable collapsed prefixes at every step rather than individual paths. Each prefix $\mathbf{y}$ carries two probabilities, $\Pr^{-}(\mathbf{y}, t)$ for alignments ending in a blank and $\Pr^{+}(\mathbf{y}, t)$ for alignments ending in the prefix’s last label $y^e$, because the two extend differently. Emitting a blank or repeating $y^e$ leaves the prefix unchanged; emitting a new label $k$ creates $\mathbf{y} + k$ with probability

$$\Pr(k, \mathbf{y}, t) = y_k^t \,\Pr(k \mid \mathbf{y}) \begin{cases} \Pr^{-}(\mathbf{y}, t-1) & \text{if } y^e = k, \\ \Pr^{-}(\mathbf{y}, t-1) + \Pr^{+}(\mathbf{y}, t-1) & \text{otherwise,} \end{cases}$$

where $\Pr(k \mid \mathbf{y})$ is a transition probability for prior linguistic knowledge, set to 1 for plain CTC. Since a repeated label needs a blank between, only blank-ending alignments may extend $\mathbf{y}$ by its own last label. The beam width trades computation for search error; Hannun (2017) suggests checking an implementation by comparing the beam’s score for its output with the exact forward score, which it should approach from below. Graves, Mohamed and Hinton (2013) decoded CTC networks with the beam search of their transducer (below), with label probabilities that do not depend on the previous outputs and a beam width of 100, and found it both faster and more accurate than prefix search.

Lexicons and language models

Transcriptions of speech and handwriting are usually required to be dictionary words, and a language model is often used to weight word sequences. Graves (2012, §7.5.3) and Graves et al. (2009) condition the decoding on a grammar $G$ and, assuming that the input is independent of the grammar and that all labellings are equally probable a priori, reduce it to

$$\mathbf{l}^* = \arg\max_{\mathbf{l}}\; p(\mathbf{l} \mid \mathbf{x})\; p(\mathbf{l} \mid G).$$

The first assumption is acknowledged to be false in general, since inputs and grammar both depend on the language that generated them, but is defended when the language model is built from text corpora separate from the training inputs. A hard dictionary constraint sets $p(\mathbf{l} \mid G) = 0$ for non-words. The CTC token passing algorithm of Graves et al. (2009) and Graves (2012, Algorithm 7.2) solves the problem approximately for a dictionary of $W$ words with optional bigrams: each word gets its own blank-extended copy, tokens carrying a log score and a word history move through the copies by the CTC transitions, and bigram probabilities are applied when a token leaves one word and enters another. Its worst-case cost is $O(TW^2)$ with bigrams and $O(TW)$ without. When the output must be a single word, the constraint becomes a ranking of the dictionary by $p(w \mid \mathbf{x})$, each term computed exactly by the forward algorithm; the example below decodes this way. Graves and Jaitly (2014) put the constraint inside the beam search instead, setting $\Pr(k \mid \mathbf{y}) = 1$ if $\mathbf{y} + k$ is in the dictionary and 0 otherwise, and converting a word-level language model into label-level transition probabilities; their algorithm normalizes the final scores by length, which they find helpful with a language model, since otherwise sequences with fewer transitions are unfairly favoured, and of little effect without one. Hannun (2017) writes the combined score as $p(\mathbf{l} \mid \mathbf{x})\, p(\mathbf{l})^{\alpha}\, L(\mathbf{l})^{\beta}$, with a language model weight $\alpha$ and an insertion bonus $\beta$ on the number of words or characters $L(\mathbf{l})$, both usually set by cross-validation.

Graves (2012, §7.5.3) also notes a tension: a CTC network can learn some dependencies between labels from the data, which an external grammar would then distort; in his experiments a biphone model raised the error of a phoneme recognizer. He argues that CTC networks learn mainly local dependencies, such as frequent pairs or triples of labels, so a grammar that models long-range dependencies, such as which word follows which when the outputs are letters, does not interfere.

Properties

• Conditional independence. Given the input, the output at each step is independent of the outputs at other steps. Hannun (2017) calls this one of the most commonly cited shortcomings of CTC: a recognizer that has emitted one letter cannot use it to predict the next, so CTC models learn an output language model poorly, and an external language model usually improves accuracy. He also notes the advantage: the language model can be swapped when the domain changes. Graves et al. (2006) observe that the network still captures some dependencies implicitly, for instance by emitting labels that usually occur together as a double spike.
• Monotonic alignment. Paths visit the labels in order, so CTC suits tasks in which the output follows the input in order, such as reading a line left to right or transcribing speech, and does not suit tasks such as translation, where an output may depend on a later part of the input (Hannun, 2017).
• Output no longer than the input. Each step emits at most one label, so $U \leq T$, a condition stated in the 2006 paper’s problem definition. Repeats need more: a labelling with $r$ pairs of equal adjacent labels needs a blank between each pair, so in our reading of the recursion a path exists only if $T \geq U + r$. The example confirms this bound by enumeration. Hannun (2017) phrases the requirement as a margin of $2r - 1$ for “$r$ consecutive repeats”, which matches $U + r$ for one repeated pair but not for more under either reading of $r$ that we tried. The PyTorch documentation for its CTC loss states only that the target length must be at most the input length, and offers an option to zero the infinite losses of inputs too short to be aligned. For text recognizers, this sets a lower limit on the width of the feature sequence: Hannun notes that the encoder must not subsample the input so much that it becomes shorter than the output.
• Alignment-free, but not location-free. CTC never asks where labels occur, and in theory gives no positions. In practice it tends to emit each label close to where it occurs (Graves, 2012, §7.2): on keyword spotting in the Verbmobil corpus, requiring the predicted keyword to lie within 0.5 seconds of its true segment raised the keyword error rate only from 13.9 ± 0.7% to 15.5 ± 1.2% (Table 7.4). Bidirectional networks may emit a label before, during or after its segment, while unidirectional networks wait until the segment is complete (Graves, 2012, §7.2.2).
• No duration modelling. The loss depends only on the label sequence, not on how long each label lasts; Graves et al. (2006) contrast this with the hybrid HMM–network systems they compared against, whose best result needed an error signal reweighted to give long and short phonemes equal weight.
• Relation to HMMs. Hannun (2017) shows that CTC can be read as a special left-to-right HMM over the blank-extended labelling, with two start and two accepting states, uniform transition probabilities and a discriminatively trained network in place of emission densities, conditioned on the whole input. Graves (2012, §7.7) attributes the advantage of BLSTM-CTC over HMMs in his experiments to discriminative training, more flexible models of the input features than mixtures of diagonal Gaussians, continuous multivariate internal states, freedom from explicit segmentation, and observations that need not depend only on the current state.

Examples

The forward algorithm against brute force, and decoders on a synthetic text line

The NumPy code below renders capital-letter words from a $5 \times 7$ bitmap font at $2 \times 2$ pixels per font cell (glyphs 10 pixels wide, a pitch of 12 pixels, ink 1 on paper 0) and cuts each word image into frames 10 pixels wide at a stride of 4 pixels, so a word of $n$ letters gives $T = 3n$ frames and one frame in three is aligned with a glyph, the role windows play in sliding window detection. Two stand-ins for a network produce the per-frame distributions $y^t$. The first is a template matcher: the logit of each class is the negative squared distance (in font cells) between the frame and that glyph’s template, divided by a temperature $\tau$, with an empty template for the blank. The temperature sets how peaked the distributions are and no source fixes it, so the matcher is run at $\tau = 1$ and $\tau = 4$. The second is a linear classifier on the frame pixels trained only with word transcriptions through the CTC loss, using the gradient above.

The script then (1) enumerates all $4^{12}$ paths for the word “COOL” with the softmax restricted to the blank, C, O and L, and compares the summed probabilities with the forward algorithm, the forward–backward identity, the analytic gradient against finite differences, the path counts against $\binom{T+U}{T-U}$ and against a formula printed in the author’s preprint of Graves (2012, p. 55), and the shortest input that admits each of four labellings; (2) runs the forward algorithm on random letter strings of 10, 100 and 1,000 letters in linear float32 and float64, with the 2006 paper’s rescaling and in log space; (3) decodes 200 vocabulary words per noise level (Gaussian pixel noise with standard deviation $\sigma$) with best path, prefix beam search (beam 10, no language model, no length normalization) and lexicon decoding (the most probable of the 30 vocabulary words under the forward algorithm), scored by word accuracy and by the character error rate defined in the optical character recognition article; and (4) trains the linear classifier for 2,000 Adam steps (learning rate 0.01, eight strings per step) on random letter strings of 3–7 letters, not the vocabulary words, with three training seeds, and evaluates it the same way. It was run with NumPy 2.3.5 and takes about 46 seconds, most of it in the training and the Python beam search.

The script was planned before its first run, with the expectation that best-path decoding and the exact most probable labelling would “both give “COOL” for both tau” on the clean image and, for the noisy words, “lexicon > beam >= best path, with beam and best path within about 2 points of each other”. The first run stopped with an indexing error in the shortest-input loop, which looked up labellings longer than $T$; a bounds check was added and nothing else in sections 1–3 changed. Because the lexicon-free decoders then failed, section 4 was planned, with its model, data, optimizer, number of steps and seeds written down before it was run, and appended without later changes. Last, a line printing the template matcher’s per-frame labels was added, so that they can be compared with the trained classifier’s; it changes no computed value.

import numpy as np
from math import comb

# ---- A 5x7 bitmap font, rendered at S x S pixels per font cell; ink 1 on paper 0 ----------
FONT = """
A .###. #...# #...# ##### #...# #...# #...#
B ####. #...# #...# ####. #...# #...# ####.
C .###. #...# #.... #.... #.... #...# .###.
D ####. #...# #...# #...# #...# #...# ####.
E ##### #.... #.... ####. #.... #.... #####
F ##### #.... #.... ####. #.... #.... #....
G .###. #...# #.... #.### #...# #...# .###.
H #...# #...# #...# ##### #...# #...# #...#
I .###. ..#.. ..#.. ..#.. ..#.. ..#.. .###.
J ..### ...#. ...#. ...#. ...#. #..#. .##..
K #...# #..#. #.#.. ##... #.#.. #..#. #...#
L #.... #.... #.... #.... #.... #.... #####
M #...# ##.## #.#.# #.#.# #...# #...# #...#
N #...# #...# ##..# #.#.# #..## #...# #...#
O .###. #...# #...# #...# #...# #...# .###.
P ####. #...# #...# ####. #.... #.... #....
Q .###. #...# #...# #...# #.#.# #..#. .##.#
R ####. #...# #...# ####. #.#.. #..#. #...#
S .#### #.... #.... .###. ....# ....# ####.
T ##### ..#.. ..#.. ..#.. ..#.. ..#.. ..#..
U #...# #...# #...# #...# #...# #...# .###.
V #...# #...# #...# #...# #...# .#.#. ..#..
W #...# #...# #...# #.#.# #.#.# #.#.# .#.#.
X #...# #...# .#.#. ..#.. .#.#. #...# #...#
Y #...# #...# .#.#. ..#.. ..#.. ..#.. ..#..
Z ##### ....# ...#. ..#.. .#... #.... #####
"""
S = 2                                    # pixels per font cell
GLYPH = {}
for row in FONT.strip().splitlines():
    ch, *rows = row.split()
    GLYPH[ch] = np.kron(np.array([[c == "#" for c in r] for r in rows], float), np.ones((S, S)))
GW, PITCH, PAD, STRIDE = 5 * S, 6 * S, 4, 4   # glyph width, glyph pitch, padding, frame stride (px)
ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def render(word):
    img = np.zeros((7 * S, PITCH * len(word) - S + 2 * PAD))
    for i, ch in enumerate(word):
        img[:, PAD + i * PITCH: PAD + i * PITCH + GW] = GLYPH[ch]
    return img

def frame_logprobs(img, alphabet, tau):
    """Template matcher as a stand-in network: frame t is the GW-wide window at column STRIDE*t.
    Class 0 is the blank (empty-paper template); classes 1..K-1 are the glyphs of `alphabet`."""
    temps = np.stack([np.zeros((7 * S, GW))] + [GLYPH[c] for c in alphabet])
    T = (img.shape[1] - GW) // STRIDE + 1
    wins = np.stack([img[:, STRIDE * t: STRIDE * t + GW] for t in range(T)])
    d = ((wins[:, None] - temps[None]) ** 2).sum(axis=(2, 3)) / S**2      # squared distance in font cells
    u = -d / tau                                                            # logits
    return u - np.logaddexp.reduce(u, axis=1, keepdims=True), u             # log-softmax, logits

def extend(l, blank=0):
    ext = np.full(2 * len(l) + 1, blank)
    ext[1::2] = l
    return ext

def ctc_forward(logy, l, blank=0):
    """Log-space forward variables over l' (Graves et al. 2006, eqs. 5-8); returns log p(l|x), log alpha."""
    T, ext = len(logy), extend(l, blank)
    skip = np.zeros(len(ext), bool)                      # is the jump s-2 -> s allowed?
    skip[2:] = (ext[2:] != blank) & (ext[2:] != ext[:-2])
    la = np.full((T, len(ext)), -np.inf)
    la[0, :2] = logy[0, ext[:2]]
    for t in range(1, T):
        p = la[t - 1]
        a = np.logaddexp(p, np.r_[-np.inf, p[:-1]])
        a = np.where(skip, np.logaddexp(a, np.r_[-np.inf, -np.inf, p[:-2]]), a)
        la[t] = a + logy[t, ext]
    return np.logaddexp.reduce(la[-1, -2:]), la

def ctc_backward(logy, l, blank=0):
    """Log-space backward variables (2006, eqs. 9-11); like alpha, beta_t(s) includes y at time t."""
    T, ext = len(logy), extend(l, blank)
    skip = np.zeros(len(ext), bool)                      # is the jump s -> s+2 allowed?
    skip[:-2] = (ext[:-2] != blank) & (ext[:-2] != ext[2:])
    lb = np.full((T, len(ext)), -np.inf)
    lb[-1, -2:] = logy[-1, ext[-2:]]
    for t in range(T - 2, -1, -1):
        n = lb[t + 1]
        b = np.logaddexp(n, np.r_[n[1:], -np.inf])
        b = np.where(skip, np.logaddexp(b, np.r_[n[2:], -np.inf, -np.inf]), b)
        lb[t] = b + logy[t, ext]
    return lb

def ctc_loss_and_grad(u, l, blank=0):
    """-ln p(l|x) and its gradient w.r.t. the logits u: y - (1/p) sum_{s: l'_s = k} alpha beta / y."""
    logy = u - np.logaddexp.reduce(u, axis=1, keepdims=True)
    logp, la = ctc_forward(logy, l, blank)
    lb = ctc_backward(logy, l, blank)
    ext = extend(l, blank)
    occ = np.exp(la + lb - logy[:, ext] - logp)          # P(path passes through l'_s at t | l, x)
    grad = np.exp(logy)
    for s, k in enumerate(ext):
        grad[:, k] -= occ[:, s]
    return -logp, grad, occ.sum(1)

def collapse(path, blank=0):
    """The many-to-one map B: merge repeated labels, then remove blanks."""
    out, prev = [], None
    for k in path:
        if k != prev and k != blank:
            out.append(int(k))
        prev = k
    return tuple(out)

def brute_force(logy, blank=0, chunk_digits=2):
    """Enumerate all K**T paths. Each labelling is coded in base K with digits 1..K-1 (unique codes);
    returns the probability and the number of paths of every code."""
    T, K = logy.shape
    prob = np.zeros(K ** T); count = np.zeros(K ** T, np.int64)
    n_inner = K ** (T - chunk_digits)
    for c in range(K ** chunk_digits):
        idx = c * n_inner + np.arange(n_inner)
        code = np.zeros(n_inner, np.int64); lp = np.zeros(n_inner); prev = np.full(n_inner, -1)
        for t in range(T):
            k = (idx // K ** (T - 1 - t)) % K
            lp += logy[t, k]
            keep = (k != prev) & (k != blank)
            code = np.where(keep, code * K + k, code)
            prev = k
        prob += np.bincount(code, weights=np.exp(lp), minlength=K ** T)
        count += np.bincount(code, minlength=K ** T)
    return prob, count

def encode(l, K):
    c = 0
    for k in l:
        c = c * K + k
    return c

def decode_code(c, K):
    out = []
    while c:
        out.append(c % K); c //= K
    return tuple(out[::-1])

def best_path(logy, blank=0):
    return collapse(logy.argmax(1), blank)

def prefix_beam_search(logy, beam=10, blank=0):
    """CTC beam search over collapsed prefixes (Graves & Jaitly 2014, Alg. 1; Hannun 2017), no language model.
    Each prefix keeps log P(alignments so far end in blank) and log P(... end in its last label)."""
    beams = {(): (0.0, -np.inf)}
    for t in range(len(logy)):
        new = {}
        def add(pre, pb, pnb):
            ob, onb = new.get(pre, (-np.inf, -np.inf))
            new[pre] = (np.logaddexp(ob, pb), np.logaddexp(onb, pnb))
        for pre, (pb, pnb) in beams.items():
            ptot = np.logaddexp(pb, pnb)
            add(pre, ptot + logy[t, blank], -np.inf)                   # emit blank: prefix unchanged
            if pre:
                add(pre, -np.inf, pnb + logy[t, pre[-1]])              # repeat last label: collapses
            for k in range(1, logy.shape[1]):
                if pre and k == pre[-1]:
                    add(pre + (k,), -np.inf, pb + logy[t, k])          # a repeated label needs a blank between
                else:
                    add(pre + (k,), -np.inf, ptot + logy[t, k])
        beams = dict(sorted(new.items(), key=lambda kv: -np.logaddexp(*kv[1]))[:beam])
    pre, (pb, pnb) = max(beams.items(), key=lambda kv: np.logaddexp(*kv[1]))
    return pre, np.logaddexp(pb, pnb)

def edit_distance(a, b):
    d = np.arange(len(b) + 1)
    for i, ca in enumerate(a, 1):
        prev, d[0] = d[0], i
        for j, cb in enumerate(b, 1):
            prev, d[j] = d[j], min(d[j] + 1, d[j - 1] + 1, prev + (ca != cb))
    return d[-1]

print("NumPy", np.__version__)
# ---- 1. Brute force against the forward-backward algorithm: "COOL", alphabet {C, O, L} + blank ----
sub = "COL"
target = tuple(sub.index(c) + 1 for c in "COOL")
to_str = lambda l, alph: "".join(alph[k - 1] for k in l) or "(empty)"
for tau in (1.0, 4.0):
    logy, u = frame_logprobs(render("COOL"), sub, tau)
    T, K = logy.shape
    prob, count = brute_force(logy)
    logp_fw, _ = ctc_forward(logy, target)
    loss, grad, occ_sum = ctc_loss_and_grad(u, target)
    h, fd = 1e-5, np.zeros_like(u)
    for t in range(T):
        for k in range(K):
            up, dn = u.copy(), u.copy(); up[t, k] += h; dn[t, k] -= h
            fd[t, k] = (ctc_loss_and_grad(up, target)[0] - ctc_loss_and_grad(dn, target)[0]) / (2 * h)
    exact = decode_code(int(prob.argmax()), K)
    print(f"tau={tau:g}: T={T}, K={K}, {K**T:,} paths; sum of all labelling probs = {prob.sum():.12f}")
    print(f"  p(COOL|x): brute force {prob[encode(target, K)]:.12e}  forward {np.exp(logp_fw):.12e}")
    print(f"  max |sum_s alpha*beta/(y p) - 1| = {np.abs(occ_sum - 1).max():.1e};"
          f"  max |grad - finite diff| = {np.abs(grad - fd).max():.1e}")
    print(f"  best path: {to_str(best_path(logy), sub)}   exact argmax: {to_str(exact, sub)}"
          f" (p = {prob.max():.4f})   beam(10): {to_str(prefix_beam_search(logy)[0], sub)}")
    print("  per-frame argmax:", "".join("-" if k == 0 else sub[k - 1] for k in logy.argmax(1)))
    top = np.argsort(prob)[::-1][:4]
    print("  top labellings:", ", ".join(f"{to_str(decode_code(int(c), K), sub)} {prob[c]:.4f}" for c in top))
cnt = {w: int(count[encode(tuple(sub.index(c) + 1 for c in w), K)]) for w in ("COL", "COOL")}
U = 3
print(f"paths collapsing to COL: {cnt['COL']} (C(T+U,T-U) = {comb(T + U, T - U)};"
      f" book-preprint formula = {2.0 ** (T - U**2 + U * (T - 3)) * 3.0 ** ((U - 1) * (T - U) - 2):.3g});"
      f" to COOL: {cnt['COOL']}")
# shortest input for which a labelling has at least one path, by brute force over T = 1..8
for w in ("CO", "OO", "COOL", "OOO"):
    l = tuple(sub.index(c) + 1 for c in w)
    Tmin = next(T for T in range(1, 9)
                if encode(l, 4) < 4**T and brute_force(np.zeros((T, 4)), chunk_digits=1)[1][encode(l, 4)] > 0)
    print(f"  shortest T for {w}: {Tmin}  (U={len(w)}, adjacent repeats={sum(a == b for a, b in zip(w, w[1:]))})")

# ---- 2. Numerical range on long lines: linear float64 / float32, rescaled, log space -------------
def forward_linear(y, l, dtype, rescale=False):
    y, ext = y.astype(dtype), extend(l)
    skip = np.zeros(len(ext), bool); skip[2:] = (ext[2:] != 0) & (ext[2:] != ext[:-2])
    a = np.zeros(len(ext), dtype); a[:2] = y[0, ext[:2]]; logc = 0.0
    for t in range(1, len(y)):
        if rescale:
            c = a.sum(); logc += np.log(c); a = a / c
        a = (a + np.r_[0, a[:-1]] + np.where(skip, np.r_[0, 0, a[:-2]], 0)).astype(dtype) * y[t, ext]
    return np.log(a[-2:].sum()) + logc

rng = np.random.default_rng(0)
print("letters  frames  log p: linear-f32   linear-f64   rescaled     log-space   (tau=4)")
for n in (10, 100, 1000):
    word = "".join(rng.choice(list(ALPHABET), n))
    logy, _ = frame_logprobs(render(word), ALPHABET, 4.0)
    l = tuple(ALPHABET.index(c) + 1 for c in word)
    with np.errstate(divide="ignore"):
        r = [forward_linear(np.exp(logy), l, np.float32), forward_linear(np.exp(logy), l, np.float64),
             forward_linear(np.exp(logy), l, np.float64, rescale=True), ctc_forward(logy, l)[0]]
    print(f"{n:7d} {len(logy):7d}  " + "  ".join(f"{v:11.2f}" for v in r))

# ---- 3. Decoding under noise: best path, prefix beam search, lexicon ----------------------------
VOCAB = ("BOOK LETTER PIXEL IMAGE TEXT LINE PAGE READ WORD FONT SCAN EDGE BLUR NOISE GLYPH PRINT PAPER INK "
         "CODE DATA MODEL LIGHT SHAPE COLUMN ROW COOL BALL ACCESS ZOOM MIRROR").split()
lex = [tuple(ALPHABET.index(c) + 1 for c in w) for w in VOCAB]
print("tau  sigma | word acc %: best  beam  lexicon | CER %: best  beam | beam!=best  beam more probable"
      "  max(beam score - forward)")
for tau in (1.0, 4.0):
    for sigma in (0.0, 0.5, 1.0):
        rng = np.random.default_rng(0)
        acc = np.zeros(3); ed = np.zeros(2); nch = 0; differ = better = 0; gap = -np.inf
        for i in range(200):
            w = VOCAB[rng.integers(len(VOCAB))]
            img = render(w) + rng.normal(0, sigma, render(w).shape)
            logy, _ = frame_logprobs(img, ALPHABET, tau)
            truth = tuple(ALPHABET.index(c) + 1 for c in w)
            bp = best_path(logy); bs, score = prefix_beam_search(logy)
            lx = lex[int(np.argmax([ctc_forward(logy, l)[0] for l in lex]))]
            acc += [bp == truth, bs == truth, lx == truth]
            ed += [edit_distance(bp, truth), edit_distance(bs, truth)]; nch += len(truth)
            fw_bs = ctc_forward(logy, bs)[0]; gap = max(gap, score - fw_bs)
            if bp != bs:
                differ += 1; better += fw_bs > ctc_forward(logy, bp)[0]
        print(f"{tau:3g}  {sigma:5.1f} |      {acc[0]/2:6.1f} {acc[1]/2:5.1f} {acc[2]/2:7.1f} |"
              f"     {100*ed[0]/nch:5.1f} {100*ed[1]/nch:5.1f} | {differ:9d} {better:12d}   {gap:10.1e}")

# ---- 4. A linear frame classifier trained with the CTC loss (word transcriptions only) ----------
def frames(img):
    T = (img.shape[1] - GW) // STRIDE + 1
    return np.stack([img[:, STRIDE * t: STRIDE * t + GW].ravel() for t in range(T)])   # T x 140

def train_ctc(seed, steps=2000, batch=8, lr=0.01):
    rng = np.random.default_rng(seed)
    W, b = np.zeros((7 * S * GW, 27)), np.zeros(27)
    m = [np.zeros_like(W), np.zeros_like(b)]; v = [np.zeros_like(W), np.zeros_like(b)]
    losses = []
    for step in range(1, steps + 1):
        gW, gb, L = np.zeros_like(W), np.zeros_like(b), 0.0
        for _ in range(batch):
            w = "".join(rng.choice(list(ALPHABET), rng.integers(3, 8)))
            x = frames(render(w) + rng.normal(0, rng.choice([0.0, 0.5, 1.0]), render(w).shape))
            loss, gu, _ = ctc_loss_and_grad(x @ W + b, tuple(ALPHABET.index(c) + 1 for c in w))
            L += loss / batch; gW += x.T @ gu / batch; gb += gu.sum(0) / batch
        losses.append(L)
        for i, (p, g) in enumerate(((W, gW), (b, gb))):          # Adam
            m[i] = 0.9 * m[i] + 0.1 * g; v[i] = 0.999 * v[i] + 0.001 * g**2
            p -= lr * (m[i] / (1 - 0.9**step)) / (np.sqrt(v[i] / (1 - 0.999**step)) + 1e-8)
    return W, b, losses

print("CTC-trained linear classifier (random training strings; evaluated on the 200 vocabulary words per sigma)")
print("seed  loss@1-100  loss@1901-2000  sigma | word acc %: best  beam  lexicon | CER %: best  beam")
for seed in (1, 2, 3):
    W, b, losses = train_ctc(seed)
    if seed == 1:
        u = frames(render("COOL")) @ W + b
        print("  seed 1, per-frame argmax on clean COOL:", "".join("-" if k == 0 else ALPHABET[k - 1]
                                                               for k in u.argmax(1)))
    for sigma in (0.0, 0.5, 1.0):
        rng = np.random.default_rng(0)
        acc = np.zeros(3); ed = np.zeros(2); nch = 0
        for i in range(200):
            w = VOCAB[rng.integers(len(VOCAB))]
            img = render(w) + rng.normal(0, sigma, render(w).shape)
            u = frames(img) @ W + b
            logy = u - np.logaddexp.reduce(u, axis=1, keepdims=True)
            truth = tuple(ALPHABET.index(c) + 1 for c in w)
            bp = best_path(logy); bs, _ = prefix_beam_search(logy)
            lx = lex[int(np.argmax([ctc_forward(logy, l)[0] for l in lex]))]
            acc += [bp == truth, bs == truth, lx == truth]
            ed += [edit_distance(bp, truth), edit_distance(bs, truth)]; nch += len(truth)
        print(f"{seed:4d}  {np.mean(losses[:100]):10.2f}  {np.mean(losses[-100:]):14.2f}  {sigma:5.1f} |"
              f"      {acc[0]/2:6.1f} {acc[1]/2:5.1f} {acc[2]/2:7.1f} |     {100*ed[0]/nch:5.1f} {100*ed[1]/nch:5.1f}")

Output:

NumPy 2.3.5
tau=1: T=12, K=4, 16,777,216 paths; sum of all labelling probs = 1.000000000000
  p(COOL|x): brute force 2.888935586531e-02  forward 2.888935586531e-02
  max |sum_s alpha*beta/(y p) - 1| = 1.2e-15;  max |grad - finite diff| = 9.1e-11
  best path: COLOL   exact argmax: COLOL (p = 0.5207)   beam(10): COLOL
  per-frame argmax: -C--O-LO-LL-
  top labellings: COLOL 0.5207, COCOL 0.0714, COLOCL 0.0704, COOLOL 0.0700
tau=4: T=12, K=4, 16,777,216 paths; sum of all labelling probs = 1.000000000000
  p(COOL|x): brute force 7.592065238090e-03  forward 7.592065238090e-03
  max |sum_s alpha*beta/(y p) - 1| = 1.3e-15;  max |grad - finite diff| = 1.1e-10
  best path: COLOL   exact argmax: COLOL (p = 0.0152)   beam(10): COCOL
  per-frame argmax: -C--O-LO-LL-
  top labellings: COLOL 0.0152, COCOL 0.0152, CLOLOL 0.0099, COLOCL 0.0098
paths collapsing to COL: 5005 (C(T+U,T-U) = 5005; book-preprint formula = 4.62e+16); to COOL: 6435
  shortest T for CO: 2  (U=2, adjacent repeats=0)
  shortest T for OO: 3  (U=2, adjacent repeats=1)
  shortest T for COOL: 5  (U=4, adjacent repeats=1)
  shortest T for OOO: 5  (U=3, adjacent repeats=2)
letters  frames  log p: linear-f32   linear-f64   rescaled     log-space   (tau=4)
     10      30       -58.96       -58.96       -58.96       -58.96
    100     300         -inf      -569.70      -569.70      -569.70
   1000    3000         -inf         -inf     -5683.82     -5683.82
tau  sigma | word acc %: best  beam  lexicon | CER %: best  beam | beam!=best  beam more probable  max(beam score - forward)
  1    0.0 |         0.0   0.0   100.0 |     164.3 152.2 |       102          102      0.0e+00
  1    0.5 |         0.0   0.0   100.0 |     167.6 165.5 |        19           19      0.0e+00
  1    1.0 |         0.0   0.0    98.0 |     174.1 173.2 |        10           10      0.0e+00
  4    0.0 |         0.0   0.0   100.0 |     164.3 140.3 |       146          146      0.0e+00
  4    0.5 |         0.0   0.0   100.0 |     167.6 147.6 |       133          131      0.0e+00
  4    1.0 |         0.0   0.0    98.5 |     174.1 162.1 |       104          101      0.0e+00
CTC-trained linear classifier (random training strings; evaluated on the 200 vocabulary words per sigma)
seed  loss@1-100  loss@1901-2000  sigma | word acc %: best  beam  lexicon | CER %: best  beam
  seed 1, per-frame argmax on clean COOL: --C--D--D--L
   1       10.57            2.56    0.0 |        60.0  60.0   100.0 |      12.3  12.3
   1       10.57            2.56    0.5 |        56.0  56.0    99.5 |      12.8  12.7
   1       10.57            2.56    1.0 |         9.0   9.0    99.0 |      42.5  41.8
   2       10.84            2.78    0.0 |        83.5  83.5   100.0 |       3.7   3.7
   2       10.84            2.78    0.5 |        68.5  69.0   100.0 |       7.6   7.5
   2       10.84            2.78    1.0 |         9.0   9.5    98.5 |      41.5  41.4
   3       10.96            2.88    0.0 |        75.5  75.5   100.0 |       5.4   5.4
   3       10.96            2.88    0.5 |        56.5  56.5    99.5 |      12.6  12.3
   3       10.96            2.88    1.0 |        11.0  11.0    99.0 |      39.8  39.6

The first block confirms the mechanics. For both temperatures, the forward algorithm reproduces the brute-force sum over 16.8 million paths to all printed digits, the probabilities of all labellings sum to one, $\sum_s \alpha_t(s)\beta_t(s)/y^t_{l'_s}$ equals $p(\mathbf{l} \mid \mathbf{x})$ at every step to rounding error, and the analytic gradient agrees with finite differences to about $10^{-10}$. Exactly $\binom{15}{9} = 5{,}005$ paths collapse to “COL”, as Hannun’s count predicts, while the formula in the book preprint gives about $4.6 \times 10^{16}$, more than all $4^{12}$ paths of length 12 over the blank, C, O and L, the only symbols such paths can use, so it cannot be a count as printed (the Springer edition was not read). The shortest inputs are 2, 3, 5 and 5 frames for “CO”, “OO”, “COOL” and “OOO”, which is $U + r$ in each case.

The decoders show what CTC cannot do by itself. The template matcher’s per-frame labels on the clean image, -C--O-LO-LL-, are right on the four aligned frames, but a frame that straddles the two Os is matched to L, which inserts an L between them, and every decoder reads “COLOL” or a close variant; the exact most probable labelling, from the brute force, is “COLOL” as well. Decoding returns the most probable reading of the given per-frame distributions; it cannot correct distributions that put letters where a CTC-trained network would put blanks. On the noisy vocabulary words the same happens at scale: best path and beam search recover no word at either temperature, with character error rates above 100% because of the inserted letters, while lexicon decoding, which can only output vocabulary words, recovers 98–100%. This contradicts the plan’s expectation for the lexicon-free decoders and is reported as printed. Beam search changes the output for 10 to 146 of the 200 words per setting and, in all but five of those words, finds a more probable labelling than best path; in the remaining five, at $\tau = 4$, pruning made it miss the more probable best-path labelling. Its reported score never exceeds the exact forward score of its output, Hannun’s check.

The trained classifier behaves like the CTC networks Graves et al. describe. Its per-frame labels on the clean “COOL” image, --C--D--D--L, are single spikes every third frame separated by blanks, learned without any frame-level labels; the spikes fall one frame to the right of the glyph-aligned frames, a placement CTC leaves to the network, and the frames the matcher labelled L are blanks. It reads O as D, which differs from O in two font cells. Its lexicon-free word accuracy on clean images is 60.0%, 83.5% and 75.5% for the three training seeds, so the seed alone moves it by more than 20 points after 2,000 steps. The plan for section 4 guessed a clean best-path accuracy “> 80%” and expected that “Seeds differ by a few points”; one seed of three passed 80%, and the spread is far larger. Accuracy falls to 9–11% at $\sigma = 1$, where lexicon decoding still recovers 98.5–99%. Beam search and best path differ by at most half a point here, because the trained outputs are peaked, which is the condition under which best path approximates the most probable labelling well.

The second block shows the numerical range. The correct transcription’s probability, which is low under the template matcher, underflows to zero in float32 at 100 letters and in float64 at 1,000 letters, while the rescaled recursion and the log-space recursion agree at every length; at these lengths the rescaled version did not show the failure that Graves (2012) warns of for very long sequences.

Beyond CTC: Attention Decoders and Transducers

Two families of models drop the conditional independence assumption.

Attention-based decoders generate the output one symbol at a time, each conditioned on the previous symbols and on an attention-weighted summary of the encoded input, the encoder–decoder pattern of machine translation (see Bahdanau attention) and image captioning; transformer recognizers follow the same pattern. They need no monotonic alignment and no length condition, and learn a language model over the output. In scene text recognition, Baek et al. (2019) compared the two prediction modules inside one framework, with every combination trained on the same synthetic data (MJSynth and SynthText, 14.4 million images) and evaluated on the same 8,539 real word images drawn from seven benchmarks, five trials each. Averaged over the combinations that contain each module, accuracy on the regular-text benchmarks was 85.5% with CTC and 87.2% with attention, and on the irregular-text benchmarks 66.1% and 68.7%, while the prediction module’s own inference time was 0.1 and 17.1 ms per image (Table 2; NVIDIA Tesla P40). The last step of their accuracy–time frontier replaced CTC by attention, adding 1.1 points of total accuracy (82.9% to 84.0%) at 27.6 ms per image for the whole model instead of 10.9 ms. They attribute some gains of attention to its implicit character-level language model, which recovers occluded or missing characters.

The RNN transducer, which Graves, Mohamed and Hinton (2013) attribute to a 2012 workshop paper by Graves and extend, combines a CTC-like network over the input with a separate recurrent prediction network over the previous outputs. Instead of one distribution per input step, it defines a distribution $\Pr(k \mid t, u)$ for every pair of input step $t$ and output position $u$, over the labels and the blank, and sums over alignments with a forward–backward algorithm, so acoustic and linguistic models are trained jointly. The original formulation multiplied an acoustic distribution from the CTC network by a linguistic one from the prediction network and renormalized; in the 2013 version the two networks’ hidden states feed a separate output network instead. On the TIMIT core test set (39-class scoring, one run each), a three-layer bidirectional LSTM with 250 cells per layer reached a phoneme error rate of 18.6% with CTC, 18.3% as a transducer and 17.7% as a transducer initialized from pretrained CTC and prediction networks. Hannun (2017) notes that the transducer also allows the output to be longer than the input.

Common Misconceptions

• “$\mathcal{B}$ removes blanks and then repeats.” The order matters: deleting blanks first would merge O-O into “O” and make double letters impossible. Repeats are merged first, then blanks are deleted (Graves, 2012, §7.2).
• “CTC needs aligned training data.” It needs only the transcription; the alignment is summed out, and the network’s spikes emerge from training, as the trained classifier in the example shows.
• “Best path finds the most probable transcription.” It finds the most probable path, which can belong to a less probable labelling. It is reliable when one path dominates its labelling’s probability, which is common for well-trained, peaked networks.
• “A target no longer than the input is always feasible.” Each pair of equal adjacent labels needs an extra step for the blank between them, so “OOO” needs five frames, not three.
• “A language model contradicts CTC.” Combining an external language model with $p(\mathbf{l} \mid \mathbf{x})$ rests on independence assumptions that Graves (2012) calls false in general but reasonable when the language model comes from separate text; in practice dictionaries and language models gave large gains in the handwriting and speech results below.
• “CTC is a network architecture.” It is an output layer and loss. The 2006 paper used a bidirectional LSTM but stresses that any architecture could have been used; text recognizers put it on convolutional and recurrent feature sequences.

Where It Is Used

Text recognition. CTC is the transcription layer of segmentation-free line and word recognizers in optical character recognition, which covers the wider pipeline, including the LSTM recognizer of Tesseract. CRNN (Shi, Bai and Yao), which Baek et al. (2019) describe as a VGG feature extractor, a bidirectional LSTM and a CTC prediction stage, is one of the six earlier scene text recognizers they re-evaluate in a common framework, and three of the others (Rosetta, GRCNN and STAR-Net) also predict with CTC. The image columns of a convolutional neural network’s feature map play the role of the time steps, each with its own receptive field on the word. The benchmarks used in this area are described in the ICDAR article.

Handwriting recognition. Graves et al. (2009) applied bidirectional LSTM with CTC and token passing to unconstrained handwritten lines. In the book version of these experiments (Graves, 2012, Table 7.7), offline recognition on the IAM database with a 20,000-word dictionary and a bigram language model reached a word error rate of 25.9 ± 0.8%, against 35.5% for an HMM system; without the language model the network’s 34.6 ± 1.1% was not significantly better than the HMM, and its character error rate was 18.2 ± 0.6%. On online handwriting (IAM-OnDB) the book reports 20.4 ± 0.3% with preprocessed inputs and the language model, against 35.5% for an HMM (Table 7.6), whereas Table I of the authors’ copy of the journal paper gives word accuracies of 65.0% for the HMM and 79.7 ± 0.3% for the network, errors of 35.0% and 20.3%. Multidimensional LSTM networks extended the approach to transcribing raw handwriting images without preprocessing (Graves, 2012, Chapters 8–9).

Speech recognition. CTC was introduced on TIMIT phoneme recognition and moved to words and characters. Graves and Jaitly (2014) trained a deep bidirectional LSTM with CTC to output characters directly from spectrograms of the Wall Street Journal corpus; trained on 81 hours and evaluated on the evaluation set, it had a word error rate of 30.1% with no dictionary or language model and 24.0% with beam search constrained to a 146,000-word dictionary. Their 8.7% with a trigram language model came from rescoring the N-best lists of a baseline DNN–HMM system with the network, not from the beam search. The same paper adds a training variant that minimizes the expected word error rate.

Other sequences. Hannun (2017) lists lip-reading and action recognition from video and keyword detection in audio among other uses, and Graves (2012) reports keyword spotting on Verbmobil.

Implementations. Deep learning frameworks provide CTC as a built-in loss. PyTorch’s torch.nn.CTCLoss (version 2.14.1) takes log-probabilities of shape (input length, batch, classes), uses class 0 as the blank by default, and with its default 'mean' reduction divides each sequence’s loss by its target length before averaging over the batch, so reported loss values depend on that convention.