W3｜The Alignment Problem: From HMM to CTC

Part I — Foundations · 對齊問題：從 HMM 到 CTC

▶ Slides for this week

Where This Fits

This is the first mathematically dense week of the course. The core difficulty of speech recognition is not classification but sequence supervision under an unknown alignment. At the end of W2 we hold 100 feature vectors per second; the training data is an audio clip paired with one line of text, and nothing tells us which frames belong to which symbol. This week puts the forward–backward algorithm of the HMM and that of CTC into one frame: both marginalise over a hidden alignment variable. They differ in the direction of the probability — the HMM is generative, P(\mathbf{X}\mid W); CTC is discriminative, P(\ell\mid\mathbf{X}) — and in whether transition probabilities exist at all. CTC was not invented from nothing: it is an HMM with a particular topology, no transition probabilities and full-sum training, moved onto the output layer of a neural network.

Where the three course-long axes sit this week. Supervision: historically CTC mattered because it removed the bootstrap “you need an alignment before you can train” — hybrid systems had to run forced alignment with a GMM-HMM before a DNN could be trained; with CTC, audio plus a transcript is enough. Representation: CTC requires T \geq |\ell| + r, so the choice of label unit (characters, phones, BPE) and the encoder’s subsampling factor constrain each other; the W2 question “who decides the frame rate” gets its first lower bound here. Latency: every frame emits independently, so a causal encoder makes CTC streamable for free — but there is no dependency between outputs, and that price is only paid back by the RNN-T in W4. The RNN-T lattice (W4), prefix beam search (W7) and the streaming dialogue state machines of W13 all rest on this week’s intuition.

The first half of the week also carries remedial duty: marginalisation, conditional independence, the chain rule and log-domain arithmetic are covered in four slides, before they are used.

Learning Objectives

  1. Write down the forward recursion and the Viterbi recursion of an HMM, explain that they differ only in the semiring (sum-product vs. max-product), and state that forward computes the probability of the sequence while Viterbi computes the probability of a single best alignment — the two are not interchangeable.
  2. Derive CTC forward–backward in full: the extended label sequence \ell', the many-to-one map \mathcal{B}, the condition on the third term of the recursion, the boundary conditions, and P(\ell\mid\mathbf{X}) = \alpha_T(S) + \alpha_T(S-1); and state the exact zero-probability condition T < |\ell| + r.
  3. Read \partial \mathcal{L}_{\text{CTC}} / \partial u^t_k = y^t_k - \gamma_t(k) as “CTC is a per-frame cross-entropy whose target is the soft alignment posterior”, and use that reading to relate CTC to hybrid training and to explain where peaky outputs come from.
  4. Explain the consequences of CTC’s conditional-independence assumption (no dependency between outputs, need for an external LM, homophones), and separate two different things: the encoder sees the whole acoustic context, but there is no dependency between the output layers.
  5. Write CTC as an HMM with a special topology, and compare on one table the inductive biases of frame-level alignment (hybrid), CTC (monotonic, many-to-one, no transition probabilities) and attention (soft, non-monotonic; developed in W4).

Demos

All three of this week’s demos are programs; they are published so that you can read them, re-run them, and change them — you are not required to run anything. Each folder’s README.md gives requirements, setup, commands, and what you should see; the index at demos/ explains the shared environment.

Slides What it shows Needs Runs on
Demo 1
the same sentence, twice as fast		 p6–p7 Why: the alignment problem on a real voice, before any equation — T frames in, U symbols out, nothing in between.
What you see: two takes of 今天天氣很好, normal and then fast, trimmed of silence and aligned at the start, one spectrogram column per 10 ms frame.
Result: T changes (199 → 134 in rehearsal: a ratio of 0.67, not 0.5, because vowels compress more than consonants), U = 6 does not, and nothing on the screen says which frames belong to which character		 numpy + scipy + matplotlib + sounddevice, a microphone; the lecturer’s takes are not published — record your own any laptop
Demo 2
CTC paths by brute force vs. the forward table		 p25–p26, p33, p39 Why: see the set that P(\ell \mid \mathbf{X}) sums over, then check the forward recursion against brute force.
What you see: terminal only — every path for “aa” and “aba” at T \leq 4 (on paper first), then one random \mathbf{y}^t summed over its 15 paths next to the forward table filled column by column, then T = 500 with 32 symbols.
Result: the two sums agree to 1.4 \times 10^{-17}; “aa” at T = 2 has no path at all; the linear-domain table is zero from t = 182, while the log domain gives \ln P = -2127.73		 numpy anything
Demo 3
a blank heat-map, and ctc_loss → inf		 p42–p43, p46, p49 Why: what a trained CTC model’s blank actually does in real speech, and what ctc_loss does when the text is too long for the audio.
What you see: facebook/wav2vec2-base-960h on one LibriSpeech dev-clean sentence: the posterior heat-map with the blank row enlarged and non-speech frames shaded, then the loss for the right transcript and for ever longer ones.
Result: blank is the argmax on 94 of the 232 frames inside speech (41 %) — blank is not silence; the loss is 53.95 for the right text, inf with a nan gradient once U + r exceeds T = 292, and 0 with a zero gradient under zero_infinity=True — hidden, not fixed		 torch 2.14.0 + transformers 5.17.0 + the model (downloaded by fetch); CPU any laptop

Tested on one machine only — an Apple M5 Max (64 GB, no CUDA), macOS 26.6 / 27.0, Python 3.12 — with the versions pinned in demos/versions.lock. Menus and labels are in Chinese; the keys are listed in each README.

References

  • Graves, Fernández, Gomez & Schmidhuber, Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks, ICML 2006, pp. 369–376 (DOI 10.1145/1143844.1143891) — the original paper. Note that its \beta includes y^t, so its gradient carries an extra 1/y^t_k; the slides use a different convention
  • Graves, Supervised Sequence Labelling with Recurrent Neural Networks, Springer, Studies in Computational Intelligence, 2012 (DOI 10.1007/978-3-642-24797-2) — Chapter 7 explains CTC more clearly than the paper; this week’s notation and \beta convention follow this book
  • Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE 77(2):257–286, 1989 — the standard tutorial on forward, Viterbi and Baum–Welch; its “three basic problems” framing is used directly
  • Gales & Young, The Application of Hidden Markov Models in Speech Recognition, Foundations and Trends in Signal Processing 1(3):195–304, 2008 (monograph 2007) — the authoritative summary of the hybrid era; read this for triphones and state tying
  • Zeyer, Beck, Schlüter & Ney, CTC in the Context of Generalized Full-Sum HMM Training, Interspeech 2017, pp. 944–948 — the source of “CTC is an HMM with a special topology”
  • Raissi, Zhou, Berger, Schlüter & Ney, HMM vs. CTC for Automatic Speech Recognition: Comparison Based on Full-Sum Training from Scratch, IEEE SLT 2022, pp. 287–294 — an empirical comparison of the two under one framework
  • Zeyer, Schlüter & Ney, Why does CTC result in peaky behavior?, arXiv:2105.14849 (2021) — the theoretical analysis of peaky outputs; cited as a preprint
  • Hannun, Sequence Modeling with CTC, Distill, 2017 (DOI 10.23915/distill.00008) — an interactive walkthrough; its drawings of the path set and the collapsing map are worth redrawing. Not a peer-reviewed paper: an editorially reviewed online journal article
  • Bain, Huh, Han & Zisserman, WhisperX: Time-Accurate Speech Transcription of Long-Form Audio, Interspeech 2023 (arXiv:2303.00747) — word-level alignment of Whisper output with a wav2vec 2.0 CTC model; evidence for “CTC can align”
  • Pratap et al., Scaling Speech Technology to 1,000+ Languages, arXiv:2305.13516 (2023) — MMS; its CTC forced aligner underlies the torchaudio alignment tutorial
  • JM3 App A Hidden Markov Models, Ch 16 Automatic Speech Recognition (the CTC section)
  • HAH Ch 8 (Hidden Markov Models), Ch 9 (Acoustic Modeling)
  • YD Ch 3–6 (DNN-HMM, sequence discriminative training)
  • The original decision-tree state-tying paper (further searching): tree-based state tying acoustic modelling Young Odell Woodland 1994
  • Entropy regularisation for CTC: connectionist temporal classification maximum entropy regularization NeurIPS 2018, CTC alignment entropy regularization
  • The implicit language model inside CTC: CTC internal language model estimation, does CTC learn a language model
回到頂端