Full search page →

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 xx be an input of TT frames, let V\mathcal V be the label alphabet plus a blank ∅\varnothing, and let qt(k)q_t(k) be the network’s probability (a softmax output computed from xx) of symbol k∈Vk \in \mathcal V at frame tt. An alignment z1:Tz_{1:T} 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 xx, so

p(z1:T∣x)=∏t=1Tqt(zt).p(z_{1:T}\mid x)=\prod_{t=1}^{T} q_t(z_t).

The collapsing map B\mathcal B first merges consecutive repeats and then deletes blanks, for example B(a a ∅ a b b)=a a b\mathcal B(a\,a\,\varnothing\,a\,b\,b)=a\,a\,b. The blank is what allows a doubled letter: B(a ∅ a)=aa\mathcal B(a\,\varnothing\,a)=aa but B(a a)=a\mathcal B(a\,a)=a. The probability of a label sequence y=(y1,…,yL)y=(y_1,\dots,y_L) and the training loss are

p(y∣x)=∑z1:T: B(z1:T)=y ∏t=1Tqt(zt),L(x,y)=−log⁡p(y∣x),p(y\mid x)=\sum_{z_{1:T}:\ \mathcal B(z_{1:T})=y}\ \prod_{t=1}^{T} q_t(z_t), \qquad \mathcal L(x,y) = -\log p(y\mid x),

where the sum runs over all alignments that collapse to yy and L\mathcal L is the loss to minimize. The number of such alignments grows exponentially with TT, so we use a dynamic program, as in the HMM forward algorithm. Write the extended label sequence y′y' of length S=2L+1S = 2L+1 by putting a blank before, between and after the labels: y′=(∅,y1,∅,y2,…,yL,∅)y' = (\varnothing, y_1, \varnothing, y_2, \dots, y_L, \varnothing). Let αt(s)\alpha_t(s) be the total probability that the first tt frames have been read as the first ss symbols of y′y', with frame tt at position ss. Then

α1(1)=q1(∅),α1(2)=q1(y1),αt(s)=qt(ys′)[αt−1(s)+αt−1(s−1)+1[ ys′≠∅, ys′≠ys−2′ ]  αt−1(s−2)],\alpha_1(1)=q_1(\varnothing),\quad \alpha_1(2)=q_1(y_1),\quad \alpha_t(s)=q_t(y'_s)\Big[\alpha_{t-1}(s)+\alpha_{t-1}(s-1)+\mathbf 1[\,y'_s\neq\varnothing,\ y'_s\neq y'_{s-2}\,]\;\alpha_{t-1}(s-2)\Big],

with αt(s)=0\alpha_t(s)=0 for indices outside 1,…,S1,\dots,S and all other α1(s)=0\alpha_1(s)=0. 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 p(y∣x)=αT(S)+αT(S−1)p(y\mid x)=\alpha_T(S)+\alpha_T(S-1), since the alignment may end on the last label or on the final blank. The cost is O(TL)O(TL). 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 B\mathcal B; 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 BB 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 35=2433^5=243 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 p(y∣x)=0.184257p(y\mid x) = 0.184257, a loss of 1.6914. For “aa”, only 15 alignments qualify, because every one of them needs a blank between the two letters; p=0.053912p = 0.053912 and the loss is 2.9204. Greedy decoding picks the path 1,1,1,2,11,1,1,2,1, which collapses to “aba”; exhaustive search over label sequences also finds “aba”, with p=0.191437p = 0.191437, 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 ∏tqt(∅)\prod_t q_t(\varnothing). 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 tt 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 LL plus the number of adjacent equal labels, so “aa” needs T≥3T \ge 3 and a shorter input has p(y∣x)=0p(y\mid x)=0 and an infinite loss.

References

  1. S. Theodoridis and K. Koutroumbas, Pattern Recognition, 4th ed., Academic Press, 2009, Chapters 8 and 9. publisher page
  2. 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
  3. J. P. Lewis, “Fast Normalized Cross-Correlation,” Vision Interface, 1995. paper
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. M. Cuturi and M. Blondel, “Soft-DTW: A Differentiable Loss Function for Time-Series,” ICML, 2017. arXiv:1703.01541
  20. 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
  21. P. Krähenbühl and V. Koltun, “Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials,” NIPS, 2011. arXiv:1210.5644
  22. 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
  23. G. Lample, M. Ballesteros, S. Subramanian, K. Kawakami, and C. Dyer, “Neural Architectures for Named Entity Recognition,” NAACL, 2016. arXiv:1603.01360
  24. A. Gu and T. Dao, “Mamba: Linear-Time Sequence Modeling with Selective State Spaces,” arXiv:2312.00752, 2023. arXiv