Templates and Warping.
Chenzi Xu · chenzi.xu@ntu.edu.sg
In the practical you build a working digit recognizer, then test it on a new speaker.
1. What does a classic recognizer actually hear on each frame?
39 numbers per frame: 13 MFCCs (the spectral envelope) plus 13 deltas and 13 delta-deltas; today's distances are between these vectors
2. Why are MFCCs almost blind to the speaker's pitch?
the DCT keeps only the first 13 coefficients: the hills (formants), not the pickets (harmonics, F0)
3. How do you measure the distance between two frames?
Euclidean distance between the two MFCC vectors
4. Praat’s pitch tracker: what do the window, the step and the best lag each stand for?
window = how much sound one estimate uses (three periods of the pitch floor, 75 Hz → 40 ms); step = how often an estimate is made (10 ms); best lag = the shift at which the signal matches itself, the period T, so F0 = 1/T
Vocal-tract length scales every formant; children, adults, and basses produce different /d/s.
Accents, dialects, sociolects: flapping, fronting, mergers. Whose /d/ is canonical? (Week 9 asks who decided.)
Hyper- to hypo-articulation (careful to casual speech): “probably” → [pɹɑbli]. Casual speech leaves little of the citation form.
/d/ before /i/ ≠ /d/ before /u/: every token's shape depends on the sounds around it.
Microphones, rooms, phone lines, background noise, all overlaid on the speech.
Listeners perceive /d/ effortlessly. The variability is lawful, and this course is about machines learning those laws.
A recognizer must treat different signals as the same word. Today: the simplest serious attempt.
Words with pauses between them, or running speech, where word boundaries are not in the signal.
Ten digits, or every word of English, new ones included (e.g. iPhone Duo).
Tuned to one voice, or expected to handle anyone.
Citation forms, or reduction, disfluency and overlap: still the hardest setting.
The historical arc follows the carving: digit recognizers (Bell Labs' Audrey, 1952) → dictation (1990s) → open conversation (still imperfect). Today: isolated digits, one speaker, where history started.
The immediate problem: two sayings of “seven” have different numbers of frames. Which frame compares to which?
templates = {
"one": [62 × 13],
"two": [48 × 13],
…
"nine": [71 × 13]
}
unknown: [55 × 13]
→ closest template wins
Vowels stretch a great deal; stop closures and bursts change little. So frame 40 of a slow “seven” does not correspond to frame 20 of a fast one: the mapping must bend locally. You knew this from articulatory phonetics; today an algorithm has to handle it.
Ten minutes.
Then the week's hardest idea.
So far: variability, stored templates, and the fact that time does not stretch uniformly. After the break, one algorithm makes every possible alignment cheap.
A a few dozen
B a few thousand
C astronomically many, far more than we could ever list
C: for 30 × 30 frames there are about 1.7 × 1021 monotonic paths, against 900 cells in the grid. Trying every alignment is hopeless; one trick, dynamic programming, makes the impossible cheap.
Astronomically many alignments.
One cheap sweep finds the best.
Dynamic time warping, and the dynamic-programming trick inside it, which returns as Viterbi (Week 6), as WER (today), and as unit selection (Week 10).
A’s frames along the bottom, B’s up the side. Each cell = the cost of matching that pair of frames. An alignment = a monotonic path corner to corner: no going back in time.
Edit distance, on two transcriptions or on cognates, is the same computation on symbols instead of frames: same grid, same logic.
The catch: the number of paths grows exponentially with length.
cost[i,j] = how different frame i of A is from frame j of B (one comparison). D[i,j] = the cheapest total of any path from the corner to this cell (the running bill).
The cheapest path to any cell can only arrive from one of three neighbours: D[i−1,j] above, D[i,j−1] to the left, or D[i−1,j−1] on the diagonal.
Fill the table once, corner to corner. Each cell asks only its three neighbours, so a 30 × 30 grid costs 900 comparisons, not one per path.
A = [1, 3, 4, 2]
B = [1, 2, 4, 4, 2]
cost = |a − b|
Fill row by row with the three-neighbor rule; the best total lands in the far corner: cost 1. Trace the backpointers (each cell's winning neighbour) back to the start for the alignment. The arrow marks the winning neighbour.
Note the horizontal step: A's [4] matches two of B's frames: that's a long vowel being absorbed. That step is the time warp.
Recognition = run DTW against all ten digit templates, take the minimum cost. One refinement: ignore cells far from the diagonal (a Sakoe–Chiba band). Real alignments stay near it anyway, silly ones are ruled out, and fewer cells means less work. The stretch task tries it.
Reference → hypothesis, aligned by minimum edit distance (substitution 0/1, insertion or deletion 1 each):
1 insertion + 1 substitution, 6 reference words → WER ≈ 33%
All errors weigh the same: “gonna”→“gotta” costs as much as “gonna”→“banana”.
WER can exceed 100%: insertions aren't capped by reference length.
Text normalization decides: casing, numerals, contractions. Week 9 opens with the full critique.
One template memorizes one production: one speaker, one rate, one style. It has no idea how a word can vary, only how it went once.
It doesn't scale to continuous speech or new speakers: the practical makes this concrete.
What we want instead: a statistical model of how a word can sound: distributions over many productions. That machine is next week's hidden Markov model.
Slide a spoken query along hours of untranscribed fieldwork recordings and let DTW find the repeats: spoken-term detection for languages with no trained ASR at all.
Not quaint history: a working tool for language documentation, usable on your own corpus.
Build a recognizer.
Then break it.
Open the Week 5 notebook (link on NTULearn). In the next hour you turn a cost matrix into a working digit recognizer, then test it on a new speaker.
Stretch (pick one): word-level edit distance + WER with S/D/I labels · k-nearest-templates vote (does it rescue speaker B?) · Sakoe–Chiba band: speed vs accuracy.
a real cost matrix with its optimal warping path: your recognizer's eye view
The WER labels, the k-nearest vote, and the Sakoe–Chiba band are the take-home stretch.
A working digit recognizer you wrote, one line of DTW at its heart, a cost-matrix valley plotted from your own audio, and a confusion matrix that worsens the moment the speaker changes.
If the recurrence cell is unfinished, a fallback keeps the recognizer running.
“The task of automatic speech recognition (ASR) is to map any waveform … to the appropriate string of words.”
Jurafsky & Martin, SLP 3rd ed., §16.1 (quoted; Aug 2026 draft).“Word Error Rate = 100 × (Insertions + Substitutions + Deletions) / (Total Words in Correct Transcript)” … “because the equation includes insertions, the error rate can be greater than 100%”.
Jurafsky & Martin, SLP 3rd ed., §16.6 (quoted; Aug 2026 draft).An algorithm that finds the minimum-cost alignment between two time series of possibly different lengths, letting the time axis stretch and compress locally, computed by dynamic programming.
Sakoe & Chiba (1978).The smallest number of insertions, deletions, and substitutions that turn one string into another: the very same dynamic-programming computation used to score WER.
Jurafsky & Martin, SLP 3rd ed., ch. 2, “Minimum Edit Distance” (paraphrased).Reference: “the dog ran home” (4 words). Hypothesis: “the dog run home fast”. Label each error as substitution / insertion / deletion, then compute the WER.
DTW on A = [1, 2] and B = [1, 3], with cost = |ai − bj| and D[i,j] = cost + min(D[i−1,j], D[i,j−1], D[i−1,j−1]). Fill the 2×2 table and give the total alignment cost and the path.
DTW already handles timing differences. Why, then, does a single stored template still fail to recognize a new speaker's “seven”?
Worked answers in the appendix at the end of this deck.
1. Variability is the problem: no single acoustic invariant for a word
2. The simplest recognizer is stored templates plus a distance
3. Time must warp, and dynamic programming makes every alignment cheap
4. Word error rate is that same dynamic programming, one level up, on words
Quiz radar: Quiz 1 takes the first 45 minutes of next week's session and covers Weeks 1 to 5, today included. The questions draw on the lectures and the weekly practicals, so the notebooks are the best revision.
§16.1 before lecture (dimensions of task difficulty, corpora); §16.6 before the practical's stretch task. Chapter numbers follow the Aug 2026 draft. web.stanford.edu/~jurafsky/slp3/16.pdf
Free interactive notebook with cost matrices and warping-path figures; read the prose and figures, the maths beyond the recurrence is optional. audiolabs-erlangen.de/resources/MIR/FMP/C3/C3S2_DTWbasic.html
The original paper, readable after this week. Free copy: jeffe.cs.illinois.edu/teaching/compgeom/refs/Sakoe-Chiba-DTW.pdf
A second pass at WER with worked examples and code; used again in Weeks 8 and 9. huggingface.co/learn/audio-course/chapter5/evaluation
Read through the Viterbi algorithm (§A.1 to §A.4); the forward algorithm and the training section are covered in class. web.stanford.edu/~jurafsky/slp3/A.pdf
The parts of the n-gram chapter skipped in Week 2; Week 6 puts the language model beside the acoustic model. 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.
A A 25 ms window resolves frequencies to within about ____ Hz. B In two sentences: why does a 5 ms window smear harmonics but sharpen a stop burst? C What does librosa.load(path, sr=16000) do to a 44.1 kHz file?
Time bends.
Distance decides.
That is template matching: simple, and defeated by variability. Next week, after Quiz 1: “From Distance to Probability”: hidden Markov models and Viterbi, the same table fill with probabilities in place of distances.
Jurafsky, D. & Martin, J. H. Speech and Language Processing, 3rd ed. (Aug 2026 draft). Ch 16, §16.1 (the ASR task) and §16.6 (word error rate); ch. 2 (minimum edit distance). Definitions quoted on the formal slide.
Sakoe, H. & Chiba, S. (1978). “Dynamic programming algorithm optimization for spoken word recognition.” IEEE TASSP 26(1), 43–49. Dynamic time warping and the band constraint.
Müller, M. & Zalkow, F. FMP Notebooks, C3S2 “Dynamic Time Warping”. audiolabs-erlangen.de/resources/MIR/FMP. Cost matrices and warping paths.
Davis, K. H., Biddulph, R. & Balashek, S. (1952). “Automatic recognition of spoken digits.” JASA 24(6), 637–642. Bell Labs’ Audrey.
Liberman, A. M., Cooper, F. S., Shankweiler, D. P. & Studdert-Kennedy, M. (1967). “Perception of the speech code.” Psychological Review 74(6), 431–461. No acoustic invariant for /d/.
Lindblom, B. (1990). “Explaining phonetic variation: a sketch of the H&H theory.” In Hardcastle & Marchal (eds), Speech Production and Speech Modelling, 403–439. Hyper- and hypo-articulation.
Park, A. S. & Glass, J. R. (2008). “Unsupervised pattern discovery in speech.” IEEE TASLP 16(1), 186–197. DTW for query-by-example search.
Hazen, T. J., Shen, W. & White, C. (2009). “Query-by-example spoken term detection using phonetic posteriorgram templates.” IEEE ASRU 2009, 421–426.
“ran” → “run” is a substitution; “fast” is an insertion; nothing deleted. Errors = 2, reference = 4 words → WER = 2 / 4 = 50%.
Cost matrix |ai − bj|: cost[1,1] = 0, cost[1,2] = 2, cost[2,1] = 1, cost[2,2] = 1. Cumulative D: D[1,1] = 0; D[1,2] = 2 + 0 = 2; D[2,1] = 1 + 0 = 1; D[2,2] = 1 + min(D[1,2], D[2,1], D[1,1]) = 1 + min(2, 1, 0) = 1. Total cost = 1, path = the single diagonal step (1,1) → (2,2).
DTW only fixes timing. A new speaker differs in spectrum (formant scaling, voice quality), so frame-to-frame distances stay large however well the paths align. One template encodes one production, not the distribution of how the word can sound. That gap is exactly what next week's HMM fills.