Connectionist Temporal Classification

Connectionist temporal classification (CTC) is a loss function and output layer design for training neural networks to label unsegmented sequences, such as transcribing an audio recording into characters when nobody has marked where each character begins and ends. It was introduced by Alex Graves, Santiago Fernandez, Faustino Gomez and Jurgen Schmidhuber of the Swiss AI lab IDSIA in a paper at the 23rd International Conference on Machine Learning (ICML) in Pittsburgh in 2006 ^[1]. The method adds an extra "blank" output symbol, treats every possible frame-by-frame alignment between input and output as a hidden variable, and sums the probability of all alignments that produce the target labeling using a forward-backward dynamic programming recursion borrowed from hidden Markov model training ^[1].

CTC removed the main obstacle that had kept recurrent neural networks out of sequence transcription: standard network objectives were defined per time step, so training data had to be pre-segmented and outputs post-processed into label sequences ^[1]. By making the network trainable directly on (audio, transcript) pairs, CTC became the foundation of the first wave of end-to-end speech recognition, including Baidu's Deep Speech system in 2014 ^[5], and of record-setting handwriting recognizers ^[2]. Attention-based encoder-decoder models and the RNN transducer (RNN-T), both of which relax CTC's independence assumptions, later displaced it at the top of many benchmarks and in production dictation systems ^[3][6][10]. CTC never went away, though. It remains the standard fine-tuning objective for self-supervised speech models such as wav2vec 2.0 and Meta's Massively Multilingual Speech models, and encoder-only CTC models are still built where inference speed matters more than the last fraction of accuracy ^[11][12][13].

The alignment problem

Sequence labeling tasks such as speech, handwriting and gesture recognition map a long, noisy input stream (audio frames, pen coordinates) to a much shorter string of discrete labels. In 2006 the dominant tools were graphical models: hidden Markov models (HMMs), conditional random fields, and their variants. The CTC paper listed their drawbacks: they need task-specific design work such as HMM state models, they impose questionable independence assumptions to keep inference tractable, and standard HMM training is generative even though labeling is a discriminative problem ^[1].

Recurrent networks looked like a natural alternative, but their objective functions scored each time step separately. A network could only be trained to make independent per-frame classifications, which required manually segmented training data and a post-processing step to turn frame labels into a final transcript. The practical workaround was the hybrid approach, in which an HMM segmented the data and an RNN supplied local classifications, inheriting many HMM weaknesses in the process ^[1]. Graves and colleagues borrowed the term "temporal classification" from Mohammed Waleed Kadous's 2002 thesis for the general task of labeling unsegmented sequences, and named their RNN-based solution connectionist temporal classification, in contrast to "framewise" classification of individual time steps ^[1].

How CTC works

The blank symbol and the collapse mapping

A CTC network ends in a softmax layer with one more unit than there are labels. For an alphabet L, the first |L| outputs give the probability of each label at each time step; the extra unit gives the probability of a blank, meaning no label ^[1]. A path is one output symbol per input time step, drawn from the extended alphabet. Assuming the outputs at different time steps are conditionally independent given the network's internal state, the probability of a path is just the product of the per-step output probabilities ^[1].

A many-to-one collapse mapping, written B in the paper, turns paths into labelings: first merge consecutive repeats of the same symbol, then delete the blanks. The paper's example is B("a-ab-") = B("-aa--abb") = "aab", where "-" is the blank ^[1]. The blank is what makes repeated letters expressible at all: to output "aab", some blank must separate the two a's in the path, otherwise they collapse into one. The probability of a labeling given the input is the sum of the probabilities of every path that collapses to it ^[1].

In practice a trained CTC network behaves distinctively: it emits a series of sharp spikes, one per label, separated by stretches of confidently predicted blank, rather than spreading each label across its whole acoustic duration the way a framewise classifier does ^[1].

Training with the forward-backward algorithm

Naively summing over all paths for a labeling is intractable, since their number grows exponentially with sequence length. The CTC forward-backward algorithm solves this with dynamic programming, in the same spirit as the forward-backward algorithm for HMMs ^[1]. The target labeling l is expanded into a modified sequence l' with blanks inserted at the start, at the end, and between every pair of labels, giving length 2|l| + 1. Forward variables track the total probability of every prefix of l' at each time step, backward variables do the same for suffixes, and each is computed by a simple recursion over the previous step. The product of forward and backward variables at any position gives the total probability of all paths passing through that symbol at that time, which yields both the sequence probability and its derivatives with respect to every network output ^[1]. The paper also describes rescaling the variables at each step to avoid numerical underflow ^[1].

The training objective is maximum likelihood: minimize the negative log probability of the correct labelings over the training set. Because this loss function is differentiable with respect to the network outputs, the gradient flows through the softmax and the rest of the network by ordinary backpropagation through time, and any gradient-based optimizer applies ^[1]. Early in training the error signal simply reflects the target sequence; as the network starts to make predictions, the error localizes around them, and once the network confidently predicts the right labeling the error signal nearly vanishes ^[1].

Decoding

Decoding means finding the most probable labeling for a new input. No exact, generally tractable algorithm is known, and the original paper offered two approximations ^[1]:

• Best path decoding takes the single most active output at every time step and collapses the result. It is trivial to compute but can miss the best labeling, because a labeling's probability is spread over many paths.
• Prefix search decoding reuses the forward-backward machinery to grow the most promising labeling prefixes. Given enough time it always finds the most probable labeling, but the number of prefixes can grow exponentially, so the paper made it practical with a heuristic: split the output at points where the blank probability exceeds a threshold (99.99 percent in the experiments) and decode each section separately ^[1].

Later practice settled on a CTC-specific variant of beam search that keeps a set of output prefixes, merges all alignments that collapse to the same prefix, and tracks separate scores for prefixes ending in blank and non-blank so that repeated characters are handled correctly. A language model can be folded into the search by weighting prefix extensions with word or character probabilities ^[9]. Deep Speech, for example, decoded with a beam of 1,000 to 8,000 candidates against an N-gram language model trained on 220 million phrases ^[5].

The 2006 TIMIT experiment

The original paper evaluated CTC on phonetic labeling of the TIMIT speech corpus, which provides 4,620 training and 1,680 test utterances with a lexicon of 61 phonemes. The CTC network was a bidirectional long short-term memory (BLSTM) network with 100 memory blocks in each direction, 26 acoustic features per 10 ms frame, a 62-unit softmax output (61 phonemes plus blank), and 114,662 weights in total ^[1]. It was compared against HMM baselines built with the HTK toolkit (over 900,000 parameters) and against a hybrid HMM-BLSTM system of nearly identical network size. The score is label error rate: the total edit distance between predicted and reference phoneme strings, normalized by the total number of reference labels ^[1].

Scroll sideways for more →

CTC and hybrid figures are means over five runs with standard errors; all differences were statistically significant except weighted-error hybrid versus CTC with best path decoding ^[1]. CTC needed no phonetic segmentation, no task-specific error weighting and no linguistic knowledge to beat both baselines ^[1].

Applications

Handwriting recognition

CTC's first headline results outside speech came in handwriting. A system by Graves, Marcus Liwicki, Fernandez, Roman Bertolami, Horst Bunke and Schmidhuber, published in IEEE Transactions on Pattern Analysis and Machine Intelligence in 2009, combined bidirectional LSTM with CTC to recognize lines of unconstrained handwritten text, in both online form (pen trajectories) and offline form (images). It reached word accuracies of 79.7 percent on online data and 74.1 percent on offline data across two large handwriting databases, significantly ahead of a state-of-the-art HMM system, and introduced a CTC token passing algorithm for decoding with dictionaries and language models ^[2].

End-to-end speech recognition

In 2014 Graves and Navdeep Jaitly trained a deep bidirectional LSTM with CTC to transcribe audio directly to text with no intermediate phonetic representation, reporting a word error rate of 8.2 percent on the Wall Street Journal corpus with a trigram language model (27.3 percent with no linguistic information at all) ^[4]. The same year, Baidu Research's Silicon Valley AI Lab released Deep Speech, a system built around a five-layer network with a single bidirectional recurrent layer, trained with CTC on spectrograms to emit characters (letters, space, apostrophe and blank) ^[5]. Trained on thousands of hours of collected and synthesized audio across multiple GPUs, Deep Speech reached 16.0 percent word error rate on the full Switchboard Hub5'00 test set, then the best published result, and 19.1 percent on a noisy evaluation set on which the best commercial systems scored 30.5 percent ^[5]. Deep Speech required no phoneme dictionary and no concept of a phoneme, and its authors credited the Graves et al. loss with "enabling neural networks to easily consume unaligned, transcribed audio during training" ^[5]. Baidu followed a year later with Deep Speech 2, which extended the end-to-end recipe to both English and Mandarin ^[17].

Text recognition and other sequence tasks

CTC transferred cleanly to optical character recognition. The widely used CRNN architecture for scene text recognition (Shi, Bai and Yao, 2015) feeds convolutional features into a bidirectional LSTM and adopts "the conditional probability defined in the Connectionist Temporal Classification (CTC) layer proposed by Graves et al.", which lets it train on images labeled only with their text strings, no per-character positions required ^[7]. Surveys of the technique also list lip reading from video, action recognition and keyword spotting among its uses ^[9]. Deep learning frameworks ship native implementations; PyTorch exposes the loss as torch.nn.CTCLoss, documented as summing "over the probability of possible alignments of input to target" ^[14].

Limitations and successors

CTC's efficiency rests on assumptions that limit it. The output sequence cannot be longer than the input sequence, which rules out tasks such as text-to-speech, and the per-step conditional independence assumption means the model cannot directly condition one output label on another; any linguistic dependency has to come from the network's internal state or an external language model ^[3]. CTC alignments are also inherently monotonic, which suits transcription but not reordering tasks like machine translation ^[9].

Graves addressed the first two limitations himself in 2012 with the RNN transducer, which couples the CTC-style acoustic network with a separate prediction network over previous outputs, "and by jointly modelling both input-output and output-output dependencies" defines a distribution over output sequences of all lengths ^[3]. A second line of successors abandoned alignment variables entirely: attention-based sequence-to-sequence models such as Listen, Attend and Spell (2015) generate characters with an attention-equipped decoder "without making any independence assumptions between the characters", which its authors called the key improvement over CTC models ^[6]. The two approaches were also combined: joint CTC-attention training, proposed in 2016, uses the CTC loss as an auxiliary multi-task objective whose left-to-right constraint regularizes the attention model's alignments, improving character error rates by 5.4 to 14.6 percent relative on the Wall Street Journal and CHiME-4 tasks ^[8]. This hybrid recipe became the core design of the ESPnet toolkit, which adopts hybrid CTC/attention training and decoding ^[18].

Production systems moved with the research. In March 2019 Google shipped an all-neural on-device recognizer for Gboard built on RNN-T, which its researchers described as "a generalization of CTC"; CTC had earlier "helped halve the latency" of Google's production recognizer, and the RNN-T model streamed character-by-character output from an 80 MB quantized model on the phone ^[10]. OpenAI's Whisper (2022) went the other way entirely, using an encoder-decoder Transformer trained on 680,000 hours of weakly supervised audio with no CTC involved ^[15].

Continued use

The self-supervised era gave CTC a second life as a fine-tuning objective. wav2vec 2.0 (2020) pretrains a Transformer encoder on unlabeled audio, then adds a randomly initialized linear projection over characters and is "optimized by minimizing a CTC loss" during fine-tuning ^[11]. The combination proved extremely label-efficient: 1.8/3.3 percent word error rate on LibriSpeech test-clean/test-other with the full 960 hours of labels, and 4.8/8.2 percent with just ten minutes of labeled audio plus 53,000 hours of unlabeled pretraining data ^[11]. Meta AI scaled the recipe in its 2023 Massively Multilingual Speech project, fine-tuning wav2vec 2.0 models "with the Connectionist Temporal Classification (CTC) criterion" to build a single speech recognizer covering 1,107 languages ^[12].

Encoder-only CTC models also persist as the fast option. Because decoding is non-autoregressive (the encoder is run once and outputs are read off in parallel), CTC models avoid the sequential decoder passes of attention models. OWSM-CTC (2024), an encoder-only, CTC-based open speech foundation model trained on 180,000 hours of public audio for multilingual recognition, translation and language identification, runs three to four times faster at inference than its attention-based encoder-decoder counterpart while improving translation results by up to 24 percent relative, and its authors note that autoregressive decoders carry "potential risks of hallucination" that CTC sidesteps ^[13]. NVIDIA's NeMo Parakeet family likewise includes CTC variants; parakeet-ctc-1.1b, a 1.1 billion parameter FastConformer trained on 64,000 hours of English speech, reaches 1.83 percent word error rate on LibriSpeech test-clean with plain greedy decoding and no external language model ^[16].

Twenty years after ICML 2006, the division of labor is roughly stable: transducers and attention decoders hold most production dictation and best-accuracy leaderboards, while CTC remains the default where training simplicity, streaming throughput or strict inference budgets dominate, and as the standard head bolted onto pretrained speech encoders.

Timeline

Scroll sideways for more →

See also

• Recurrent neural network
• Long short-term memory
• Speech recognition
• Hidden Markov model
• wav2vec 2.0
• Beam search

References

1. ^Graves, A., Fernandez, S., Gomez, F., Schmidhuber, J. "Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks." Proceedings of the 23rd International Conference on Machine Learning (ICML), Pittsburgh, 2006. cs.toronto.edu/...icml_2006.pdf
2. ^Graves, A., Liwicki, M., Fernandez, S., Bertolami, R., Bunke, H., Schmidhuber, J. "A Novel Connectionist System for Unconstrained Handwriting Recognition." IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009. cs.toronto.edu/...tpami_2009.pdf
3. ^Graves, A. "Sequence Transduction with Recurrent Neural Networks." arXiv:1211.3711, November 2012. arxiv.org/...1211.3711
4. ^Graves, A., Jaitly, N. "Towards End-To-End Speech Recognition with Recurrent Neural Networks." Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1764-1772, 2014. proceedings.mlr.press/...graves14
5. ^Hannun, A., Case, C., Casper, J., Catanzaro, B., Diamos, G., Elsen, E., Prenger, R., Satheesh, S., Sengupta, S., Coates, A., Ng, A. Y. "Deep Speech: Scaling up end-to-end speech recognition." arXiv:1412.5567, December 2014. arxiv.org/...1412.5567
6. ^Chan, W., Jaitly, N., Le, Q. V., Vinyals, O. "Listen, Attend and Spell." arXiv:1508.01211, August 2015. arxiv.org/...1508.01211
7. ^Shi, B., Bai, X., Yao, C. "An End-to-End Trainable Neural Network for Image-based Sequence Recognition and Its Application to Scene Text Recognition." arXiv:1507.05717, July 2015. arxiv.org/...1507.05717
8. ^Kim, S., Hori, T., Watanabe, S. "Joint CTC-Attention based End-to-End Speech Recognition using Multi-task Learning." arXiv:1609.06773, September 2016 (ICASSP 2017). arxiv.org/...1609.06773
9. ^Hannun, A. "Sequence Modeling with CTC." Distill, 2017. distill.pub/...ctc
10. ^Schalkwyk, J. "An All-Neural On-Device Speech Recognizer." Google Research Blog, March 12, 2019. research.google/...ral-on-device-speech-recognizer
11. ^Baevski, A., Zhou, H., Mohamed, A., Auli, M. "wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations." NeurIPS 2020, arXiv:2006.11477. arxiv.org/...2006.11477
12. ^Pratap, V., Tjandra, A., Shi, B., et al. "Scaling Speech Technology to 1,000+ Languages." arXiv:2305.13516, May 2023. arxiv.org/...2305.13516
13. ^Peng, Y., Sudo, Y., Shakeel, M., Watanabe, S. "OWSM-CTC: An Open Encoder-Only Speech Foundation Model for Speech Recognition, Translation, and Language Identification." ACL 2024, arXiv:2402.12654. arxiv.org/...2402.12654
14. ^PyTorch documentation. "CTCLoss." docs.pytorch.org/...torch.nn.CTCLoss
15. ^Radford, A., Kim, J. W., Xu, T., Brockman, G., McLeavey, C., Sutskever, I. "Robust Speech Recognition via Large-Scale Weak Supervision." arXiv:2212.04356, December 2022. arxiv.org/...2212.04356
16. ^NVIDIA. "parakeet-ctc-1.1b" model card. Hugging Face. huggingface.co/...parakeet-ctc-1.1b
17. ^Amodei, D., Anubhai, R., Battenberg, E., et al. "Deep Speech 2: End-to-End Speech Recognition in English and Mandarin." arXiv:1512.02595, December 2015. arxiv.org/...1512.02595
18. ^Watanabe, S., Hori, T., Karita, S., et al. "ESPnet: End-to-End Speech Processing Toolkit." Interspeech 2018, arXiv:1804.00015. arxiv.org/...1804.00015