Whilst the video is playing, click on a line in the transcript to play the video from that point. We've been on a journey towards the Hidden Markov Model, and finally we've arrived. We started by talking about pattern matching, and we did that with an algorithm called dynamic time warping, in which we stored a template, which is just a recorded example of some speech we'd like to recognize, perhaps an isolated word, called an exemplar, and we matched that against some unknown speech that we would like to label. And we measured distance between the stored template and the unknown. We then realized that this lacks any way of modeling the natural variability of speech. The template is just a single stored example, it doesn't express how much we can vary from that example and still be within the same class. So we decided to solve that by replacing the exemplar with a probabilistic model, and we looked in our toolbox of probabilistic models and found the Gaussian as the only model that we can use. It has the right mathematical properties and it's very simple. We're going to use the Gaussian as the core of our probabilistic model, and that led us into a little bit of a detour to worry about the sort of features that we could model with a Gaussian. And we spent some time doing feature engineering to come up with features called MFCCs that are suitable for modeling with diagonal covariance Gaussians. So now, armed with the knowledge of dynamic time warping and knowing its shortcomings, and knowing that we've now got these excellent features called Mel Frequency Cepstral coefficients, we're ready to build a probabilistic generative model of sequences of MFCC vectors, and that model is going to be the Hidden Markov Model. We're going to have to understand what's hidden about it and what's Markov about it. So to orient ourselves in our journey, this is what we know so far. We talked about distances between patterns. We saw that there's an interesting problem there of aligning sequences of varying length. We found a very nice algorithm for doing that called dynamic programming and the instantiation of that algorithm, dynamic time warping, and we saw that we could do dynamic time warping. We could perform the algorithm of dynamic programming on a data structure called a grid. And that's just a place to store partial distances. We're now going to invent the Hidden Markov Model. We'll understand what's hidden about it. It's its state sequence, and that's connected to the alignment between templates and unknowns. The state sequence is a way of expressing the alignment. And then we'll develop an algorithm for doing computations with the Hidden Markov Model that deals with this problem of the hidden state sequence, and that data structure is going to be called a lattice, and it's very similar to the grid in dynamic time warping. Think of it as a generalization of the grid. And so we're now going to perform dynamic programming on the different data structure, on the lattice, and that will be doing dynamic programming for Hidden Markov Models, and the algorithm gets a special name again. It's called the Viterbi algorithm. That's the connection between dynamic time warping, as we know it so far, and hidden Markov models as we're about to learn them. So we know that the single template in dynamic time warping doesn't capture variability. There were many solutions proposed to that before someone invented the HMM, for example, storing multiple templates to express variability. That's a reasonable way to capture variability, is to have a variety of natural exemplars. The HMM is going to leverage that idea too, but it's not going to store multiple exemplars. It's going to summarize their properties in statistics. Essentially that just boils down to the means and variances of Gaussians. So although there are ways of dealing with variability in dynamic time warping, we're not going to cover them. We're going to go straight into using statistical models, where in some abstract feature space, let's draw a slice of Cepstral feature space, 4th versus the 7th Kepstral coefficient, so some slice through this Cepstral feature space. We're going to have multiple recorded examples of a particular class, and rather than store those, we're going to summarize them as a distribution, which has a mean and a standard deviation along each dimension, or a variance if you prefer. So here's what we're going to cover in this module, module 8. So we already know about the multivariate Gaussian as a generative model. A multivariate Gaussian generates vectors, and we're going to start calling them observations because they're emitted from this generative model. We know that speech changes its properties over time, so we're going to need a sequence of Gaussians to generate speech. So we need a mechanism to do that sequencing, and that amounts to dealing with duration. And we're going to come up with a very simple mechanism for that, which is a finite state network. And so when we put these Gaussian generative models into the states of a finite state network, we get the Hidden Markov Model. We're going to see when the model generates data, it could take many different state sequences to do that, and that's why we say the state sequence is hidden. It's unknown to us, and we have to deal with that problem. One way of doing that is to draw out a data structure, which is the Hidden Markov Model replicated at every time instant, that's called a lattice. We're also going to see that we can perform dynamic programming directly on a data structure that is the Hidden Markov Model itself, and that's an implementational difference. Both of those are dynamic programming for the Hidden Markov Model, and both of those ways of doing things, either the lattice or this computation directly on the hidden Markov model itself, are the Viterbi algorithm. When we finish all of that, we'll finally remember that we don't yet have a way of estimating the parameters of the model from the data. So everything here in module 8, we're going to assume that someone's given us the model, some pre-trained model. So we don't have the algorithm for training the model yet. So at the very end, we'll make a first step towards that, and we'll just remind ourselves how we can train a single Gaussian on some data. We might call that fitting the Gaussian to the data, or estimating the mean and variance of the Gaussian given some data. And we'll see that that is easy, but the hidden state sequence property of the HMM makes it a little harder to do that for a Hidden Markov Model and a sequence of observations. But that's coming in the next module. So we know already that a single Gaussian, a multivariate Gaussian, can generate feature vectors, and we're going to call them observations. That's just to remind ourselves that they are generated by a model. Let's just make sure we fully understand that. Again, I'll draw some part of our feature space. I can't draw in 12-dimensional MFCC space or higher, so I'm always going to draw just two of the dimensions. Any two, it doesn't matter. Two of the MFCC coefficients. How does a Gaussian generate? Well, the Gaussian is a mean, and a mean is just a point in the space. And we have a variance along each of the feature dimensions. We're going to assume there's no covariance, and so there's some variance, a standard deviation in this direction, perhaps some in this direction. So one way of drawing that is to draw a contour line, one standard deviation from the mean. Like that. This model can generate data points. What does that mean? It means we can randomly sample from the model, and it will tend to generate samples nearer the mean. And just how spread they are from the mean is governed by the parameter variance. So if I press the button on the model to randomly sample, it generates a data point, or another data point, or another data point, and just occasionally, a data point far from the mean. More often than not, they're near the mean, and so it generates data points that have this Gaussian distribution. So that's the model being a generative model. But we're not doing generation. We're not doing synthesis of speech. We're doing recognition of speech. So what does it mean when we say there's a generative model? Well, it says we are pretending, we're assuming that the feature vectors extracted from speech that we observe coming into our speech recognizer were really generated by a Gaussian. We just don't know which Gaussian, and the job of the classifier is to determine which of the Gaussians is the most probable Gaussian to have generated a feature vector. Now, of course, the feature vectors weren't generated by a Gaussian. They're extracted from speech, and the speech was generated by the human vocal tract. But we're making an assumption. We're assuming that their distribution is Gaussian, and that we can model with a generative model that has a Gaussian distribution. So it's an assumption. Now since these blue data points were extracted from natural speech, and what we're trying to do is decide whether they were generated by this Gaussian, we don't really generate from the Gaussian. We just take the Gaussian's parameters. We take one of these data points, and we compute the probability that this observation came from this Gaussian. And we just read that off the Gaussian curve as the probability density, and we'll take that as proportional to the probability. So the core operation that we're going to do with our Gaussian generative model whilst doing speech recognition is to take a feature vector and compute the probability that it was emitted by a particular Gaussian. And that's what the Gaussian equation tells us. It's the equation of the curve. That's the equation that describes probability density in one dimension. We've got the Gaussian distribution. Along comes some data point, and we just read off the value of probability density. It's that simple. When we do that in multiple dimensions with an assumption of no covariance, we'll just do the one-dimensional case separately for every dimension and multiply all the probability densities together to get the probability of the observation vector. And that's an assumption of independence between the features in the vector. So that mechanism of the multivariate Gaussian as a generative model is going to be right in the heart of our HMM that we're about to invent. It solves the problem of the Euclidean distance measure being too naive. How does it solve it? Because it learns the amount of variability in each dimension of the feature vector and captures that as part of the model. The Euclidean distance measure only knows about distance from the mean. It doesn't have a standard deviation parameter. So we cast our minds back to dynamic time warping and just remember how that works. This is the unknown, and that's the time running through the unknown. This is a template that we've stored. We'll assume that the first frame of each always align with each other because speech has been carefully end-pointed. There's no leading silence. So we'll align this frame with this frame, and then dynamic time warping just involves finding a path to here that sums up local distances along the way. And those local distances are Euclidean distances here. So the Gaussian is going to solve the problem of the local distance. Let's take a local distance in this cell between this vector and this vector, and it's going to capture variability. Storing a single frame of an exemplar doesn't capture variability. That's the main job of the Gaussian. But there's another problem of templates. It doesn't capture variability in duration either. There's a single example, an arbitrarily chosen example of a recording of a digit, say. Maybe this is a recording of me saying three. The duration of that is arbitrary. It doesn't model the variation in duration we might expect. The template might also be a little bit redundant. It might be that all of these frames sound very similar. They're the vowel at the end of the word three, and we don't need to store three frames for that. We could just store one, or even better, we could store the mean and the variance of those frames. So we're going to get rid of the stored exemplar, and we're going to get to choose the temporal resolution of the thing that's replacing it. The thing that's replacing it is going to be not an example, but a model. And so my exemplar had seven frames, but maybe I don't need seven frames to capture the word three. Maybe it's made of just three different parts, three different sounds. So at the same time as getting rid of the exemplar, I'm going to gain control over the temporal resolution, the granularity of my model. And for now, let's choose three. This is a design choice. We're going to get to choose this number here, and we can choose it on any basis we like, but probably we should choose it to give the best accuracy of recognition by experimentation. So where I used to have frames of an exemplar, I'm now going to instead store the average and the variance of those. And I'm going to do that separately for each of the three parts. So for this part here, I'm going to store a multivariate Gaussian in the same dimensions as the feature space, and it's going to store a mean and a variance. And for the purpose of this module, I'm not going to worry about where they come from. I'm just going to assume that we will later devise some mechanism, some algorithm for training this model. We're always going to assume for the rest of this module that the model has been pre-trained, it was given to us. So instead of storing an exemplar, here I'm going to store a Gaussian. I'm just going to draw one in one dimension, because I can't draw in this many dimensions. It's going to be a mean and a standard deviation, or we could store the variance. For the middle part, I'm going to store another one. It's going to be potentially a different mean and a different standard deviation. And for the final one, the third one would be at another mean and another standard deviation. So where there used to be a sequence of feature vectors for each of these three parts, there is now a statistical description of what that part of the word sounds like. So this axis is the model, and the model is in three parts, it models the beginning of the word, the middle of the word, and the end of the word. And we'll just leave it like that as a little abstract. Certainly we're not claiming that these are going to be phonemes, and we've already said that it doesn't have to be three, it's a number of our choosing, and we'll worry about how to choose it another time. So the model so far is a sequence of three Gaussian distributions. I've drawn them in one dimension, but in reality, of course, they're multivariate. And all we need now is to put them in some mechanism that makes sure we go through them in the correct order, that we go from the beginning to the middle to the end, and a mechanism that also tells us how long to spend in each of those parts. The duration of the unknown is going to be variable. Every time we do recognition, that might be a different number. As we'll see when we develop the model, the length of the observation sequence here is generally going to be longer than the number of parts in the model. And so we've got to decide whether this Gaussian generates just this frame, or the first two, or maybe the first three. And then how do we move up to the next Gaussian to start generating the next frames? And when do we move up to the next Gaussian to start generating the remaining frames? So we need some mechanism to decide when to transition from the beginning of a word to a middle of a word, and from the middle of the word to the end of the word. The simplest mechanism that I know to do that is a finite state network. So let's draw a finite state network. We're going to be able to transition between the states, and these transitions say that we have to go from left to right through the model. We don't go backwards. Speech doesn't reverse. And we now need a mechanism that says that you can, from each of these states, generate more than one observation. Remember, these are the observations. And that's just going to be a self-transition on the state. And inside the states are the multivariate Gaussians that I had before, with their means and variances. So we started with a generative model of a single feature vector, a multivariate Gaussian, and we've put it into a sequencing mechanism, a finite state network, that simply tells us in what order to use our various Gaussians. And we have some transitions between those states that controls that, and we have some self-transitions on the state that allow us to emit more than one observation from the same Gaussian. So those transitions are our model of duration, and we just invented the Hidden Markov Model.
Hidden Markov Models for ASR
Intro to Hidden Markov Models, comparison to DTW
Log in if you want to mark this as completed
|
| ||||||||||||||||||||||||||||||||||||||||||