States and Priors.
Chenzi Xu · chenzi.xu@ntu.edu.sg
The weekly notebooks were the revision.
Break until 10:40; we go through the answers when we return.
Weight: 20% of the course grade.
The quiz is done.
Back at 10:40.
When we return: the answers to the quiz, then the lecture: the model that replaced the template.
In the practical you decode by hand with Viterbi, then let a language model overrule your acoustics.
1. What does a classic recognizer hear on each frame?
39 numbers: 13 MFCCs plus 13 deltas and 13 delta-deltas
2. How long is a frame, and how often is one taken?
25 ms of sound, a new frame every 10 ms
3. The DTW recurrence (the three-neighbour rule), in one line?
D[i,j] = cost + min(D[i−1,j], D[i,j−1], D[i−1,j−1]): above, left, diagonal; fill the table once, then backtrace
4. Word error rate: the formula, and can it exceed 100%?
WER = 100 × (S + D + I) / N, N = words in the reference; yes, because insertions are not capped
5. Why were templates abandoned?
one template stores one production; it cannot model how a word varies across speakers, rates and styles
Week 5 asked how far is this audio from my example?
This week asks how probable is this audio, if the word were “seven”? Distance becomes likelihood.
If the words were W, how probable is this stream of MFCC frames? Modelled this week by hidden Markov models.
Before hearing anything, how plausible is the word string W? Modelled by n-grams: Week 2's prior, now over whole word strings.
X = the sequence of MFCC frames; argmax (gloss) = the candidate W with the highest score. Bayes' rule gives P(W | X) ∝ P(X | W) · P(W); the divisor P(X) is the same for every candidate, so the argmax ignores it. In logs, the product becomes a sum of two scores.
States you never see.
Sound you do. One best path.
A word is modelled as a left-to-right chain of states, one MFCC frame per step.
Recognition = finding the most probable path through those states.
1. Draw a 2 × 3 grid: rows H and C, columns days 1 to 3. 2. Day 1: start × emission. 3. Each later cell: emission × the larger of the two (previous cell × transition) products; mark the winner. 4. Day 3: take the larger cell, follow the winners back.
Jurafsky & Martin, Appendix A, Fig. A.2 (the example is Eisner's). Worked answer in the appendix of this deck.
Every number from the previous slide sits on an arrow or a bar. The question is now a path: which route through H and C, one state per day, gives the diary 3 1 3 the highest probability? Viterbi fills a 2 × 3 trellis.
weather ↔ phone state · ice creams ↔ MFCC frame · the diary ↔ the recording · best weather sequence ↔ the segmentation
The practical works this trellis on paper, then relabels H/C as oral/nasal vowel and 1, 2, 3 as nasal-murmur levels; the arithmetic does not change.
Sum over all paths: P(X | word). Used to compare word candidates. The forward algorithm: the same table fill with a sum in place of the max.
The single best path: Viterbi. Today's main idea, and the reason DTW came first.
Baum-Welch (the forward-backward algorithm): start from guessed transition and emission probabilities; use them to work out how probably each frame belongs to each state; re-estimate the transition and emission probabilities from those fractional counts; repeat until they settle. Week 7 teaches training with gradient descent.
Vocabulary for the week: the model is written λ; its parameters are the start probabilities, the transition probabilities and the emission distributions.
The best path to any node can only arrive through one of its predecessors: the same insight that made Week 5's exponentially many alignments cheap to search.
Same table, now called a trellis: frames across as before, but the rows are the word's states. Same backtrace. Different arithmetic in the cells.
states /n/, /o/ (rows)
frames x1 x2 x3 (columns)
V(s, t): the probability of the best path that ends in state s at frame t
P(xt | s): emission: how likely frame xt (the frame at time t) is under state s
V(s′, t−1): the same, one frame earlier; s′ is the state the path was in at frame t−1: either s itself (stay) or the state before s (move on)
P(s′ → s): transition from s′ into s (stay, or move on)
max over s′: try both candidates for s′, keep the larger product; the winner is the backpointer
Real systems run this in logs, so the products become sums.
A print the acoustic winner; the sound is the evidence
B let a prior over word sequences overrule a small acoustic edge
C flag the audio as unrecognisable
The equation already answered: the argmax weighs both factors. A small likelihood edge loses to a large prior gap.
AM = acoustic model score, log10 P(X | W) · LM = language model score, log10 P(W) · total = AM + LM
1. The acoustic score alone ranks “wreck an ice beach” first, by 0.1
2. The language-model score: how probable is each string before any sound is heard?
3. Totals: “recognize speech” wins by 4.3 in log10, a factor of about 20,000
Scores are log10 probabilities, so the two scores add. Gloss: the acoustic model is the phonetician's opinion, the language model the corpus linguist's.
chain rule: P(w1 … wn) = the product over i of P(wi | history)
Markov assumption: P(wi | history) ≈ P(wi | wi−1)
estimate: P(see | can) = count(can see) / count(can)
The Week 2 practical's heatmaps were this table with letters, then phones, instead of words: same counting, same held-out evaluation.
i can see
i can go
can go lah
count(can) = 3
P(see | can) = 1/3
P(go | can) = 2/3
P(lah | go) = 1/2
P(makan | can)
counts: 0 / 3 = 0
add-one: (0+1) / (3+V) > 0
V = vocabulary size. With V = 6 words: 1/9 ≈ 0.11, small but no longer impossible; P(go | can) falls from 2/3 to 3/9.
The acoustic model scored the vowels correctly; the prior rejected the sentence. Errors that look phonetic are often caused by the lexicon or the language model.
Week 9 returns to this.
The lexicon is the third model: a pronouncing dictionary (CMUdict, for most classical English systems) mapping every word to phone states. If a word or a pronunciation is missing (makan; the Singapore English /ɛ/–/æ/ merger), the decoder cannot print it, whatever the audio says (Week 9).
Every arrow is a week you have already done: frames (Week 4), the table fill (Week 5), the two probability factors (Week 2, today). Nothing in the classical stack is unexplained.
Gaussian bells as emissions, n-gram priors, beam search: dictation, call centres, the HTK toolkit (Kaldi from 2011).
Neural networks replace the Gaussians as emission scorers; the HMM structure stays. Week 7 builds a first network.
One network maps audio to text directly; the separate modules are no longer needed. Week 8's topic, Whisper included.
What remains in use: Viterbi itself. Week 9's forced alignment, a standard phonetics-lab tool, is this exact machinery.
Decode it by hand.
Then let the prior overrule you.
Open the Week 6 notebook (link on NTULearn). In the next hour you write the Viterbi max line yourself, then swap a news bigram prior for a National Speech Corpus prior and see which transcript wins.
Stretch (pick one): add-one smoothing on and off + perplexity on a held-out Singlish line · sample 10 sentences from the bigram model and judge their grammaticality · add a third word to the decoder and see whether it takes any clip.
a decoded trellis with its best path: your first probabilistic recognizer
The stretch (pick one: smoothing + perplexity, sampling sentences, a third word) is take-home; the four stages above are the in-class core.
A Viterbi decoder with your own max line at its heart, a decoded boundary you found twice (paper and code), and a transcript whose winner changed when you swapped the news prior for the NSC prior.
If the max line is unfinished, a fallback keeps the decoder running.
“A hidden Markov model (HMM) allows us to talk about both observed events (like words that we see in the input) and hidden events (like part-of-speech tags) that we think of as causal factors in our probabilistic model.” Here the observed events are MFCC frames, the hidden events phone states.
Jurafsky & Martin, SLP 3rd ed., App. A, §A.2 (quoted; Aug 2026 draft); last sentence: course gloss.“Decoding: Given as input an HMM λ = (A, B) and a sequence of observations O = o1, o2, ..., oT, find the most probable sequence of states Q = q1q2q3 . . . qT.” Viterbi is the dynamic-programming algorithm that solves it: DTW's table fill with products of probabilities in place of summed costs.
Jurafsky & Martin, SLP 3rd ed., App. A, §A.4 (quoted; Aug 2026 draft); second sentence: course gloss. Viterbi (1967).“An n-gram is a sequence of n words: a 2-gram (which we'll call bigram) is a two-word sequence of words like The water, or water of, and a 3-gram (a trigram) is a three-word sequence of words like The water of, or water of Walden.” As a model: each word's probability is conditioned on the previous n−1 words, estimated from counts, with smoothing for unseen pairs.
Jurafsky & Martin, SLP 3rd ed., §3.1 (quoted; Aug 2026 draft); last sentence: course gloss (smoothing: §3.6).The framing of recognition as inference: the intended sentence passes through a noisy acoustic channel; the decoder searches for the sentence that best explains what came out, likelihood times prior.
Jelinek (1976), Proc. IEEE 64(4), 532–556 (paraphrased); the channel model: Shannon (1948).Corpus: “i can go” · “we can go” · “we go lah”. Estimate P(go | can), P(can | we), and P(lah | go) from bigram counts.
Two states /n/ and /o/; start in /n/. Emissions: /n/ gives x1 0.9, x2 0.2; /o/ gives x1 0.1, x2 0.8. All transitions 0.5. Fill the four Viterbi cells and give the best path.
A news-trained bigram model, whose training text never contains “can makan”, meets “the tourist can makan”. What probability does the chain rule assign, and why? Name the standard remedy and its cost.
(a) Which phonetic property does the self-loop probability encode, and which segments should have large ones? (b) Give two distinct reasons a news-trained decoder mangles “later we go makan lah”, one per model.
Worked answers in the appendix at the end of this deck.
1. Classical ASR is one equation: likelihood times prior, argmax over sentences
2. An HMM is states, transitions, emissions; “hidden” means the path is inferred, never observed
3. Viterbi is DTW's cumulative-cost table D filled with probabilities; the backtrace is a segmentation
4. The language model is a prior counted from a corpus; if the corpus is not the speakers' variety, the decoder rejects their sentences
Radar: Quiz 1 is done; Quiz 2 (start of Week 12) covers the weeks from today onward, so today is already in scope. Assignment 1 (ASR) is released next week; the brief is posted on NTULearn.
Markov chains, the HMM, the forward algorithm and Viterbi, all on the ice-cream example. §A.5 (forward-backward training) is optional. Chapter numbers follow the Aug 2026 draft. web.stanford.edu/~jurafsky/slp3/A.pdf
The two sections skipped in Week 2: perplexity as the held-out score; add-one smoothing and the refinements after it. web.stanford.edu/~jurafsky/slp3/3.pdf
Short and concrete; the spreadsheet does what the lecture does by hand. aclanthology.org/W02-0102
Sections I to III only: the three basic problems of an HMM, in the paper that made them standard.
Units, feedforward networks and training; skim the backpropagation maths. web.stanford.edu/~jurafsky/slp3/6.pdf
Layers and weights, then next week's hardest idea; watching the second video twice is a good use of time. youtube.com/watch?v=aircAruvnKk · youtube.com/watch?v=IHZwWFHWa-w
Required before Week 8; Week 7 introduces attention in one slide. 3blue1brown.com/lessons/attention
Watch decision boundaries form in the browser, no code. playground.tensorflow.org
Two scores, added.
The best sentence wins.
Likelihood times prior: that equation was classical ASR for thirty years. Next week, “A Matrix and a Squash”: neural networks, built from Week 4's matrix multiply, the model that replaced the Gaussian emissions.
Jurafsky, D. & Martin, J. H. Speech and Language Processing, 3rd ed. (Aug 2026 draft). Appendix A (hidden Markov models, the ice-cream example, Viterbi); ch. 3 (n-grams, perplexity, smoothing); ch. 18, §18.4 (the Viterbi trellis). Definitions quoted on the formal slide.
Shannon, C. E. (1948). “A mathematical theory of communication.” Bell System Technical Journal 27(3), 379–423 and 27(4), 623–656. The noisy channel.
Jelinek, F. (1976). “Continuous speech recognition by statistical methods.” Proceedings of the IEEE 64(4), 532–556. The noisy channel applied to speech.
Viterbi, A. J. (1967). “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.” IEEE Transactions on Information Theory 13(2), 260–269.
Baum, L. E., Petrie, T., Soules, G. & Weiss, N. (1970). “A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains.” Annals of Mathematical Statistics 41(1), 164–171. Baum–Welch training.
Rabiner, L. R. (1989). “A tutorial on hidden Markov models and selected applications in speech recognition.” Proceedings of the IEEE 77(2), 257–286. The three basic problems.
Eisner, J. (2002). “An interactive spreadsheet for teaching the forward-backward algorithm.” ACL-02 Workshop on Effective Tools and Methodologies for Teaching NLP and CL, 10–18. The ice-cream example.
Hinton, G., Deng, L., Yu, D., Dahl, G. E., Mohamed, A., Jaitly, N., Senior, A., Vanhoucke, V., Nguyen, P., Sainath, T. N. & Kingsbury, B. (2012). “Deep neural networks for acoustic modeling in speech recognition.” IEEE Signal Processing Magazine 29(6), 82–97. Networks replace the Gaussians.
Koh, J. X., Mislan, A., Khoo, K., Ang, B., Ang, W., Ng, C. & Tan, Y.-Y. (2019). “Building the Singapore English National Speech Corpus.” Proc. Interspeech 2019, 321–325.
Weide, R. L. (1998). The CMU Pronouncing Dictionary. Carnegie Mellon University. speech.cs.cmu.edu/cgi-bin/cmudict
count(can) = 2, count(can go) = 2, so P(go | can) = 1; count(we) = 2, count(we can) = 1, so P(can | we) = 1/2; count(go) = 3, count(go lah) = 1, so P(lah | go) = 1/3.
V(/n/,1) = 0.9; /o/ cannot start, so V(/o/,1) = 0. V(/n/,2) = 0.2 × (0.9 × 0.5) = 0.09; V(/o/,2) = 0.8 × (0.9 × 0.5) = 0.36. Best path /n/ → /o/ with probability 0.36: the state switch falls after frame 1.
P(makan | can) = 0 in the news counts, and the chain rule multiplies, so the whole sentence receives probability zero: not rare, impossible, whatever the acoustics say. The remedy is smoothing (add-one at its simplest), which gives unseen pairs a small probability; the cost is mass taken from seen pairs, and the check is held-out perplexity.
(a) The self-loop encodes duration: the probability of lingering another frame. Long, stretchable segments (vowels, nasals) should have large self-loops; stop bursts should not. (b) The language model assigns near-zero priors to “makan” and “lah” bigrams, and the lexicon may lack the word entirely, so the decoder substitutes frequent English words with similar phones (“Mark can”, “la”): two separate failures, one printed error.
day 1: v(H) = 0.8 × 0.4 = 0.32 · v(C) = 0.2 × 0.1 = 0.02
day 2: v(H) = 0.2 × max(0.32 × 0.6, 0.02 × 0.5) = 0.2 × 0.192 = 0.0384 (from H)
day 2: v(C) = 0.5 × max(0.32 × 0.4, 0.02 × 0.5) = 0.5 × 0.128 = 0.064 (from H)
day 3: v(H) = 0.4 × max(0.0384 × 0.6, 0.064 × 0.5) = 0.4 × 0.032 = 0.0128 (from C)
day 3: v(C) = 0.1 × max(0.0384 × 0.4, 0.064 × 0.5) = 0.1 × 0.032 = 0.0032 (from C)
Best final cell: 0.0128 in H. Backtrace: H ← C ← H, so the answer is H C H with probability 0.0128. The runner-up H H H scores 0.32 × 0.12 × 0.24 = 0.0092.
Appendix A's text names H H H as the sequence to find; with the numbers in Fig. A.2, H C H scores higher. Use the numbers.