Connectionist Temporal Classification (CTC)

Connectionist temporal classification is a training loss and decoding rule for sequence models whose input has at least as many frames as the output has labels, usually far more, and whose alignment is unknown. A speech encoder might emit 250 frame vectors for a transcript of 8 tokens, and the training data says nothing about which frame belongs to which token. CTC lets the model be trained from (input, transcript) pairs alone by summing over every alignment that could produce the transcript.

Blank symbol and collapse rule

CTC extends the output vocabulary with a special blank symbol, written - below. At every frame the network outputs a softmax over the vocabulary plus blank. A choice of one symbol per frame is a path \(\pi\) of length \(T\). A collapse function \(\mathcal{B}\) maps a path to a transcript in two steps: merge adjacent repeats, then delete blanks.

• aaab collapses to ab, so a sound that lasts several frames is not a problem.
• a-ab collapses to aab, and aab is not the same as ab: the blank between two a frames keeps them as separate letters.
• aa-a collapses to aa, while aaa collapses to a. A transcript with a doubled letter, such as “hello”, therefore needs a blank frame between the two l tokens.

The blank also absorbs silence and frames that carry no new label.

Probability and loss

The probability of a transcript \(y\) is the sum over all paths that collapse to it, where each path’s probability is the product of its per-frame probabilities:

\[ p(y \mid x) = \sum_{\pi \in \mathcal{B}^{-1}(y)} \prod_{t=1}^{T} p(\pi_t \mid x). \]

Here \(p(\pi_t \mid x)\) is the network’s softmax output at frame \(t\), conditioned on the encoder input \(x\). The encoder may use the full sequence or an allowed streaming context; the factorization does not require raw-frame-only features. The loss is \(-\log p(y \mid x)\). Summing over alignments instead of picking one is why no alignment labels are needed: the gradient pushes probability toward every path that is consistent with the transcript, in proportion to how likely each already is.

A small enumeration

Take the alphabet \(\{-, a, b\}\), four frames, and a hypothetical network output (each row sums to 1):

frame	P(-)	P(a)	P(b)
1	0.1	0.7	0.2
2	0.6	0.2	0.2
3	0.2	0.2	0.6
4	0.5	0.1	0.4

Enumerating all \(3^4 = 81\) paths and keeping those that collapse to ab leaves 15, among them a-b- (0.7 × 0.6 × 0.6 × 0.5 = 0.126), a-bb (0.1008), aab- (0.0420) and abb- (0.0420). Adding all 15 gives \(p(\text{ab} \mid x) = 0.4668\) and a loss of 0.7619. The single best path, a-b-, carries only 27% of that probability mass, which is the point of summing.

Forward algorithm

Enumeration is exponential in \(T\). The sum can be computed by dynamic programming. Write the label sequence \(y\) of length \(U\) with a blank inserted before, between and after the labels, giving an extended sequence \(z\) of length \(2U+1\). Let \(\alpha_t(s)\) be the total probability of all path prefixes of length \(t\) that end in state \(s\) of \(z\) and are consistent with \(y\). A state can be reached by staying in \(s\), by advancing from \(s-1\), or by skipping from \(s-2\). The skip is allowed only when \(z_s\) is not a blank and differs from \(z_{s-2}\), so the blank between two identical labels cannot be skipped. At the end, \(p(y \mid x) = \alpha_T(2U+1) + \alpha_T(2U)\), the two states that finish the sequence with a label or a trailing blank. The cost is \(O(T \cdot U)\). On the example above the recursion returns 0.4668, matching the enumeration.

A backward recursion of the same shape gives gradients, and deep-learning frameworks provide the whole loss as a built-in.

Conditions and limits

• The model needs at least \(U\) frames, and \(U + r\) frames when the transcript has \(r\) adjacent repeated labels. Over two frames the transcript aa has probability 0, because the only path with two a frames is aa, which collapses to a. Over the four frames of the table above it is possible (\(p = 0.0620\)).
• Frames are conditionally independent given the input. The network cannot condition its output at frame \(t\) on what it emitted before, so linguistic dependence between tokens has to come from the encoder or an external language model.
• Alignments are monotonic: output order follows input order. That suits speech and handwriting and does not suit tasks like translation.
• Decoding can be greedy (take the best symbol per frame, then collapse), which is fast and streaming-friendly but only approximates the best transcript, since the best transcript is a sum over paths. Prefix beam search sums the paths that share a prefix.

Neighbors

RNN-T keeps the alignment-free sum but adds a prediction network that conditions on previous labels, removing the independence assumption at higher training cost. Attention encoder-decoders learn a soft, non-monotonic alignment and need the whole input (or a windowed version) before emitting output. CTC is the simplest of the three and the common baseline for streaming recognition.