Connectionist temporal classification (CTC)
Optional · supplementary note 1 of 1 for PR 06 · Template Matching and Structured Recognition. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
A speech recognizer listens to 200 audio frames and must write “cat”, but nobody marked which frame is the “c”. CTC lets the network say, at every frame, either a letter or “nothing new yet” (a blank), and then scores a transcript by adding up every frame-by-frame story that reads out as that transcript. It is the HMM forward algorithm with the emission model replaced by network outputs [20].
Let be an input of frames, let be the label alphabet plus a blank , and let be the network’s probability (a softmax output computed from ) of symbol at frame . An alignment assigns one symbol to every frame; it plays the role of the HMM’s hidden state sequence. CTC assumes the frame outputs are independent given , so
The collapsing map first merges consecutive repeats and then deletes blanks, for example . The blank is what allows a doubled letter: but . The probability of a label sequence and the training loss are
where the sum runs over all alignments that collapse to and is the loss to minimize. The number of such alignments grows exponentially with , so we use a dynamic program, as in the HMM forward algorithm. Write the extended label sequence of length by putting a blank before, between and after the labels: . Let be the total probability that the first frames have been read as the first symbols of , with frame at position . Then
with for indices outside and all other . The three terms are “stay on the same symbol”, “advance by one” and “jump over a blank”; the indicator allows the jump only between two different labels, because jumping between equal labels would merge them into one. Finally , since the alignment may end on the last label or on the final blank. The cost is . A mirror-image backward recursion gives the gradient, though in practice automatic differentiation of the forward pass is enough.
Decoding. Greedy (best-path) decoding takes the arg max symbol at every frame and applies ; it is cheap but need not give the most probable label sequence, because that sequence sums over many alignments [20]. Prefix beam search instead grows label prefixes one frame at a time, keeping for each prefix its probability of ending in a blank and of ending in a label (so alignments that collapse to the same prefix are merged) and retaining only the best prefixes; the exact prefix search of [20] is the same idea without the beam limit.
The snippet implements the recursion on a 5-frame toy with symbols blank, “a” (1) and “b” (2), and checks it against brute-force enumeration of all alignments.
Code · Python · 57 lines
import itertools
import numpy as np
rng = np.random.default_rng(1)
T, V = 5, 3 # 5 frames; symbols 0 = blank, 1 = "a", 2 = "b"
logits = rng.normal(size=(T, V))
probs = np.exp(logits) / np.exp(logits).sum(axis=1, keepdims=True) # probs[t, k] = p(k | x, t)
def collapse(path):
"""The map B: merge repeats, then drop blanks."""
out = [k for i, k in enumerate(path) if i == 0 or k != path[i - 1]]
return tuple(k for k in out if k != 0)
def ctc_forward(probs, y):
"""p(y | x) by the alpha recursion over the blank-extended label sequence."""
ext = [0]
for k in y:
ext += [k, 0] # blank, y1, blank, y2, ..., yL, blank
T, S = len(probs), len(ext)
if T == 0:
return float(len(y) == 0)
alpha = np.zeros((T, S))
alpha[0, 0] = probs[0, 0]
if S > 1:
alpha[0, 1] = probs[0, ext[1]]
for t in range(1, T):
for s in range(S):
a = alpha[t - 1, s] + (alpha[t - 1, s - 1] if s >= 1 else 0.0)
if s >= 2 and ext[s] != 0 and ext[s] != ext[s - 2]:
a += alpha[t - 1, s - 2] # skip a blank only between different labels
alpha[t, s] = a * probs[t, ext[s]]
return alpha[-1, -1] + (alpha[-1, -2] if S > 1 else 0.0)
assert np.isclose(ctc_forward(probs, ()), np.prod(probs[:, 0]))
assert ctc_forward(probs[:2], (1, 1)) == 0.0 # two frames cannot spell "aa"
assert ctc_forward(probs[:0], ()) == 1.0
assert ctc_forward(probs[:0], (1,)) == 0.0
# Brute force: enumerate all V**T = 243 alignments and group them by B(path).
paths = list(itertools.product(range(V), repeat=T))
for y in [(1, 2), (1, 1)]:
good = [p for p in paths if collapse(p) == y]
brute = sum(np.prod([probs[t, k] for t, k in enumerate(p)]) for p in good)
fwd = ctc_forward(probs, y)
assert np.isclose(fwd, brute)
print(f"y={y}: {len(good)} alignments, brute={brute:.6f}, forward={fwd:.6f}, loss={-np.log(fwd):.4f}")
best = tuple(int(k) for k in probs.argmax(axis=1)) # greedy (best-path) decoding
print("greedy path:", best, "->", collapse(best))
# Exact best label sequence by grouping all alignments (feasible only for tiny T).
score = {}
for p in paths:
score[collapse(p)] = score.get(collapse(p), 0.0) + np.prod([probs[t, k] for t, k in enumerate(p)])
top = max(score, key=score.get)
print("best label sequence:", top, "p =", round(score[top], 6))
print("greedy sequence p :", round(score[collapse(best)], 6))For the target “ab”, 35 of the 243 alignments collapse to it, and the forward recursion and brute force both give , a loss of 1.6914. For “aa”, only 15 alignments qualify, because every one of them needs a blank between the two letters; and the loss is 2.9204. Greedy decoding picks the path , which collapses to “aba”; exhaustive search over label sequences also finds “aba”, with , so the two agree on this toy but are not guaranteed to in general.
An empty transcript is a valid boundary case: every frame must emit blank, so its probability is . The code handles this separately from an impossible nonempty transcript and checks both. These are probability-space calculations for a tiny example; for long sequences use a scaled or log-space recursion to avoid underflow.
When the assumptions fail. Conditional independence means the output at frame cannot look at what the model emitted earlier, except through the network’s internal features; linguistic knowledge must come from the encoder’s context or from an external language model combined at decoding time, and models that feed previous labels back into the prediction drop this assumption. Monotonic alignment means output order must follow input order, which rules out tasks where order changes, such as translation. It also needs enough frames: at least plus the number of adjacent equal labels, so “aa” needs and a shorter input has and an infinite loss.
References
- S. Theodoridis and K. Koutroumbas, Pattern Recognition, 4th ed., Academic Press, 2009, Chapters 8 and 9. publisher page
- C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, Sections 8.1–8.4 and 13.1–13.3. official book page and PDF
- J. P. Lewis, “Fast Normalized Cross-Correlation,” Vision Interface, 1995. paper
- N. S. Hashemi, R. B. Aghdam, A. S. B. Ghiasi, and P. Fatemi, “Template Matching Advances and Applications in Image Analysis,” arXiv:1610.07231, 2016. arXiv
- H. Sakoe and S. Chiba, “Dynamic Programming Algorithm Optimization for Spoken Word Recognition,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 26, no. 1, pp. 43–49, 1978. doi:10.1109/TASSP.1978.1163055
- T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh, “Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping,” Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 262–270, 2012. doi:10.1145/2339530.2339576
- R. A. Wagner and M. J. Fischer, “The String-to-String Correction Problem,” Journal of the ACM, vol. 21, no. 1, pp. 168–173, 1974. doi:10.1145/321796.321811
- D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty Years of Graph Matching in Pattern Recognition,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 18, no. 3, pp. 265–298, 2004. doi:10.1142/S0218001404003228
- P. Foggia, G. Percannella, and M. Vento, “Graph Matching and Learning in Pattern Recognition in the Last 10 Years,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 28, no. 1, 1450001, 2014. doi:10.1142/S0218001414500013
- L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition,” Proceedings of the IEEE, vol. 77, no. 2, pp. 257–286, 1989. doi:10.1109/5.18626
- A. J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Transactions on Information Theory, vol. 13, no. 2, pp. 260–269, 1967. doi:10.1109/TIT.1967.1054010
- L. E. Baum, T. Petrie, G. Soules, and N. Weiss, “A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains,” The Annals of Mathematical Statistics, vol. 41, no. 1, pp. 164–171, 1970. doi:10.1214/aoms/1177697196
- R. E. Kalman, “A New Approach to Linear Filtering and Prediction Problems,” Journal of Basic Engineering, vol. 82, no. 1, pp. 35–45, 1960. doi:10.1115/1.3662552
- J. D. Lafferty, A. McCallum, and F. C. N. Pereira, “Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data,” Proceedings of the 18th International Conference on Machine Learning (ICML), pp. 282–289, 2001. paper page
- C. Sutton and A. McCallum, “An Introduction to Conditional Random Fields,” Foundations and Trends in Machine Learning, vol. 4, no. 4, pp. 267–373, 2012. doi:10.1561/2200000013
- A. Bagnall, J. Lines, A. Bostrom, J. Large, and E. Keogh, “The Great Time Series Classification Bake Off: A Review and Experimental Evaluation of Recent Algorithmic Advances,” Data Mining and Knowledge Discovery, vol. 31, pp. 606–660, 2017. doi:10.1007/s10618-016-0483-9
- M. Middlehurst, P. Schäfer, and A. Bagnall, “Bake Off Redux: A Review and Experimental Evaluation of Recent Time Series Classification Algorithms,” Data Mining and Knowledge Discovery, vol. 38, pp. 1958–2031, 2024. doi:10.1007/s10618-024-01022-1
- H. Ismail Fawaz, G. Forestier, J. Weber, L. Idoumghar, and P.-A. Muller, “Deep Learning for Time Series Classification: A Review,” Data Mining and Knowledge Discovery, vol. 33, pp. 917–963, 2019. doi:10.1007/s10618-019-00619-1
- M. Cuturi and M. Blondel, “Soft-DTW: A Differentiable Loss Function for Time-Series,” ICML, 2017. arXiv:1703.01541
- A. Graves, S. Fernández, F. Gomez, and J. Schmidhuber, “Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks,” Proceedings of the 23rd International Conference on Machine Learning (ICML), pp. 369–376, 2006. doi:10.1145/1143844.1143891
- P. Krähenbühl and V. Koltun, “Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials,” NIPS, 2011. arXiv:1210.5644
- S. Zheng, S. Jayasumana, B. Romera-Paredes, V. Vineet, Z. Su, D. Du, C. Huang, and P. H. S. Torr, “Conditional Random Fields as Recurrent Neural Networks,” ICCV, 2015. arXiv:1502.03240
- G. Lample, M. Ballesteros, S. Subramanian, K. Kawakami, and C. Dyer, “Neural Architectures for Named Entity Recognition,” NAACL, 2016. arXiv:1603.01360
- A. Gu and T. Dao, “Mamba: Linear-Time Sequence Modeling with Selective State Spaces,” arXiv:2312.00752, 2023. arXiv