1CS 188: Artificial IntelligenceFall 2008Lecture 21: Speech / Viterbi11/13/2008Dan Klein – UC Berkeley12Announcements P5 up, due 11/19 W9 up, due 11/21 (note off-cycle date) Final contest: download and get started! Homework solution and review sessions coming23Hidden Markov Models An HMM is Initial distribution: Transitions: Emissions: Query: most likely seq:X5X2E1X1X3X4E2E3E4E594State Path Trellis State trellis: graph of states and transitions over time Each arc represents some transition Each arc has weight Each path is a sequence of states The product of weights on a path is the seq’s probability Can think of the Forward (and now Viterbi) algorithms as computing sums of all paths (best paths) in this graphsunrainsunrainsunrainsunrain105Viterbi Algorithmsunrainsunrainsunrainsunrain126Example137Digitizing Speech148Speech in an Hour Speech input is an acoustic wave forms p ee ch l a bGraphs from Simon Arnfield’s web tutorial on speech, Sheffield:http://www.psyc.leeds.ac.uk/research/cogn/speech/tutorial/“l” to “a”transition:159 Frequency gives pitch; amplitude gives volume sampling at ~8 kHz phone, ~16 kHz mic (kHz=1000 cycles/sec) Fourier transform of wave displayed as a spectrogram darkness indicates energy at each frequencys p ee ch l a bSpectral Analysis1610Adding 100 Hz + 1000 Hz WavesTime (s)0 0.05–0.96540.9901711Spectrum1001000Frequency in HzAmplitudeFrequency components (100 and 1000 Hz) on x-axis1812Part of [ae] from “lab” Note complex wave repeating nine times in figure Plus smaller waves which repeats 4 times for every large pattern Large wave has frequency of 250 Hz (9 times in .036 seconds) Small wave roughly 4 times this, or roughly 1000 Hz Two little tiny waves on top of peak of 1000 Hz waves1913Back to Spectra Spectrum represents these freq components Computed by Fourier transform, algorithm which separates out each frequency component of wave. x-axis shows frequency, y-axis shows magnitude (in decibels, a log measure of amplitude) Peaks at 930 Hz, 1860 Hz, and 3020 Hz.2014Acoustic Feature Sequence Time slices are translated into acoustic feature vectors (~39 real numbers per slice) These are the observations, now we need the hidden states X……………………………………………..e12e13e14e15e16………..2315State Space P(E|X) encodes which acoustic vectors are appropriate for each phoneme (each kind of sound) P(X|X’) encodes how sounds can be strung together We will have one state for each sound in each word From some state x, can only: Stay in the same state (e.g. speaking slowly) Move to the next position in the word At the end of the word, move to the start of the next word We build a little state graph for each word and chain them together to form our state space X2416HMMs for Speech2517Markov Process with BigramsFigure from Huang et al page 6182618Decoding While there are some practical issues, finding the words given the acoustics is an HMM inference problem We want to know which state sequence x1:Tis most likely given the evidence e1:T: From the sequence x, we can simply read off the words2719End of Part II! Now we’re done with our unit on probabilistic reasoning Last part of class: machine
View Full Document