Connectionist Temporal Classification

The problem it solves

Many sequences that matter — speech, handwriting, gesture — arrive as a long stream of frames, while the answer we want is a much shorter string of labels. A recurrent neural network can read such a stream one step at a time, but training it is awkward: to compute an error you need to know which frames belong to which label, and that frame-level alignment is exactly the work human annotators would rather avoid. Segmentation is slow, inconsistent between annotators, and often ambiguous even in principle, since the boundary between two spoken words is not a sharp physical event.

How it works

CTC turns the alignment problem into something the network can average over. The output alphabet is extended with an extra "blank" symbol. At every frame the network predicts a probability distribution over letters plus blank, so the raw output is as long as the input. A simple collapsing rule then turns that long string into a short one: merge consecutive identical labels, then delete blanks.

A small example makes it concrete. Suppose the audio is a short recording of the word "cat". Over eight frames the network might emit `c c _ a _ t t _`, where `_` is blank; merging repeats and dropping blanks gives `c a t`. A different frame-by-frame path, say `_ c _ a a t _ _`, collapses to the same answer. The blank is what makes this work: without it, two identical letters in a row (the "ll" in "hello") would be indistinguishable from a single one.

Training uses the sum over all paths that collapse to the correct label sequence. The number of paths grows exponentially with length, so the sum is computed with a dynamic-programming recursion rather than enumerated, and the result is differentiated to give a gradient. Nothing else is required: no pre-segmented data, no separate alignment model, no decoder beyond a simple search.

Where it came from

Schmidhuber's retrospective dates CTC to 2006 and describes it as one of two methods developed in his research groups at TU Munich and IDSIA ^[1]. The other was long short-term memory, the recurrent architecture built to overcome the vanishing gradient problem that Sepp Hochreiter had analyzed in 1991 ^[1]. The two fit together: LSTM supplies a network that can carry information across many time steps, and CTC supplies the training objective that lets it be trained from sequence-level labels alone. The original paper is by Graves, Fernandez, Gomez and Schmidhuber, published in the Proceedings of ICML 2006, pages 369 to 376 ^[3].

Results

The combination was applied to speech as early as 2007, and IDSIA describes it as very different from the earlier hybrid methods that combined neural networks with hidden Markov models ^[1]. Handwriting recognition produced the clearest marker: a CTC-trained LSTM won the ICDAR connected handwriting recognition competition in 2009, the first time a recurrent network had won international competitions ^[3]. IDSIA's deep learning timeline records that on the faster computers of 2009 a stack of LSTM recurrent networks trained by CTC became the first RNN system ever to win an official international pattern recognition competition ^[2]. In the retrospective's phrasing, the CTC-trained LSTM was the first recurrent neural network to win any international contests ^[1].

Where it is used, and what it cannot do

Any task where the input is a long sequence and the target is a shorter label string is a candidate: speech recognition, handwriting and text-line recognition, and similar labelling problems. Its appeal is that it removes a whole annotation step — the network learns where the labels are at the same time as it learns what they are.

The cost is built into the design. CTC assumes that, given the input, labels at different frames are conditionally independent, so it cannot model a strong internal grammar of the output; the collapsing rule also requires the label sequence to be no longer than the input. Where a task genuinely needs explicit alignment or a language model, CTC is usually combined with other components, and later sequence-to-sequence methods that learn an alignment softly offer an alternative. Even so, the idea it introduced — training on all alignments at once instead of picking one — is what made unsegmented sequence data usable as training data.