Whilst the video is playing, click on a line in the transcript to play the video from that point. Hidden-Markov model comprises a set of states. In each state is a multivariate Gaussian, and that Gaussian can emit observations. Each time we arrive in a state of the model, we emit an observation, and then we must leave the state. And we must leave along one of a set of transitions that dictates what sequences of states are allowed. The model we just saw was a very simple model with a topology, a shape called left to right. So the transitions, the arcs between the states govern that. And because there are transitions from a state to itself, we can end up back in the same state and thus emit more than one observation from the same state. That's a very simple model of duration. So here's the model we just invented. This one's now got five emitting states. I've drawn a one-dimensional Gaussian in each state, just to show you that there is a Gaussian there, but of course there will be multivariate. So let's have this model emit, or generate, a sequence of observation vectors. These are our observation vectors. For example, our MFCCs. These lines indicate emission, generation, two words for the same thing. And this picture shows a five-state Hidden Markov Model emitting a sequence of observations in a particular way. The first emitting state emits the first observation in the sequence. And then we go around the self-transition and emit the second. And then we go around the self-transition again and emit the third. And then we leave. We arrive in the second emitting state. And then we generate the next observation in the sequence. We go around the self-transition and emit the next one. We go around the self-transition and emit the next one. And then we leave. And then we emit the next observation in the sequence. So every time we arrive in a state we must emit an observation and then leave. So this time we leave along the self-transition, and emit another one from that state, and then we leave. We emit this one, we leave. Back in the same state for one more time. Back in the same state again, another observation. And then we leave. We emit an observation. Go around, emit an observation, and we're done. Hopefully it's already immediately obvious that there might have been another way of going through the model to generate this observation sequence. What I just drew there was one particular state sequence. For this particular state sequence, we can compute the probability of this observation sequence given the model. And it's just going to be the product of all the emission probabilities. So of this Gaussian generating the first observation, multiplied by the probability of this Gaussian generating the next observation, multiplied all the way through the sequence. And we could also put some probabilities on the transitions. So as we go around the transition, there might be a probability on that. Let's write one. There's quite a high probability of going down this transition. So we'll multiply by all the transition probabilities. Transition probabilities leaving any one state have to sum up to one because it's a probability distribution over all the subsequent states. So the probability of this model emitting this observation sequence and using this particular state sequence is just the product of all the emission probabilities and all the transition probabilities. And it's that very simple product because the model assumes that the probability of emitting this observation sequence only depends on the state that you emit it from, and that's all. So the probability of this state emitting this observation and then emitting this observation and then emitting the next observation is just computed independently as the product of those three probabilities. The model doesn't know, it doesn't remember what it did in the previous time step. And that lack of memory, that independence of one observation in the sequence from the next given the HMM state is the Markov assumption. That's where Markov in the word Hidden Markov Model comes from. This model has no memory. Now that's a very strong assumption, and it might not be entirely true about this particular observation sequence, but that's the assumption the model makes. Now this picture is the most common way of drawing a picture of a Hidden Markov Model. It's the one you'll see in textbooks, but it's actually potentially really confusing. That's a model and that's an observation sequence. Quite clearly, this is time in frames, for example, 10 milliseconds apart. That much is clear. This is not time. This particular model happens to have a topology, a shape, in other words, a set of allowable transitions that is left to right, so we're clearly going to move through the model in that order, but this is a perfectly valid model. This is a completely valid Hidden Markov Model. Now it might not be particularly useful for doing speech recognition with, but it's a valid model, and so any algorithms that we develop must work for this model as well as for this model. So this picture is potentially extremely confusing because the model on the top and the sequence of observations on the bottom are not both along the same time axis. Only the observations have a time axis. The model is just a finite state model. We could draw the model on its side, upside down, back to front. It would be the same model. The layout on the page has no meaning. We should draw a picture that's much clearer. The model is a model. It always exists. It exists now, exists in the past, and exists in the future, and it exists every time step of the observation sequence. So let's draw a picture that makes that completely explicit. I'm going to draw a copy of the model at every time step. This is time in frames. So we're stepping through that one frame at a time. So I'm just going to draw out a copy of the model. I'm going to duplicate it or unroll it over time. I'll just draw the states. That's the model at time one, at time two, at time three, and so on. I'll draw a copy of this model at every time frame. This is just a statement that the model always exists. It's always there. For this particular model, this is the starting state. And so the first observation in my observation sequence is always going to have to be emitted by that state because that's where we are at time one. And so that says we must be here. And we can't be in any of these other states because we haven't had time to go down the transitions to get there. I'm going to also assume that we must finish in this state. So I'm going to define that as the end state of the model. When the model has generated an observation sequence, it must always end up in that state and no other state. And that means that that state must always generate the last observation in the sequence. That's a statement that we must be here and not here. And so we've got to get from here to here. We've got to get through the model following the allowable transitions as we go through the observation sequence, and the model generates the observation sequence while we do that. This is starting to look quite like dynamic time warping, and that's deliberate. So our generative model of sequences is the Hidden Markov Model, which is made of a finite state machine and those states contain Gaussians. And now we need to deal with a problem of this model. And it's the same problem we had in dynamic time warping, that the alignment between the model and the observation sequence is not known to us. Here's the potentially confusing version of the picture again. We've got the model on the top, we've got the observation sequence along the bottom. I showed you earlier one particular state sequence, one particular way of going through the model and generating this observation sequence, but there are many, many more ways of doing that. Just like there are many, many possible alignments between a template and an unknown in dynamic time warping. So we can draw an alignment on this picture. Let's just make one up. And if I number these states, let's just number them this way, 1, 2, 4, and 5. Now I've drawn a state sequence that is 1, 1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 5. But you can go away and work out all the other state sequences that are possible. They have to start with 1, and they have to end with 5, but there are many, many permutations there. Remember what we're doing when we're using a Hidden Markov Model to do pattern recognition. We're assuming that one of our Hidden Markov Models that we've stored did generate this observation sequence, and our only task is to work out which one can do it with the highest probability, which was the most likely model to have generated it. It will be one of the models, but we don't know what state sequence that model used to generate this observation sequence. And so we say that the state sequence of the Hidden Markov Model is hidden from us. And that's the definition of hidden in Hidden Markov Model. It's that many possible state sequences could have been used to generate the observation sequence, and we don't know which one it was. On the left is what I really want to compute. I want to compute the probability of an observation sequence given a particular model, and I'm going to repeat that for all the models I've got, and pick the model that gives me the highest value, and use that to label the observation sequence O. On the right is what we've already seen how to compute. We can compute the probability of an observation sequence, and taking a particular state sequence Q. So Q is a random variable, and it says state sequence. For example, Q might take the value 1, 1, 1, 2, 2, 2, 3, 4, 5. And if we know the state sequence, we can compute the probability of the observation sequence in that state sequence. So we can compute this joint probability here. So how can we get P of O, given the joint probability of P and O and Q, both conditioned on the model, given this particular model? Well, there's an easy way to do that, and we just sum over all the possible values of Q. That's a simple rule of probability. This operation is called marginalising, or summing away Q. Now I just told you that there might be a lot of possible values of Q. Q is the state sequence. And the longer the model gets, and the longer the observation sequence gets, the more values of Q are possible. It could be a very, very large number. So this summation could be a very large summation. It could be computationally expensive to do this summation. But this is the correct thing to do for the Hidden Markov Model. If we really want to compute the probability of an observation sequence given that model, we must sum over all possible state sequences the probability of the observation in that state sequence. So we must sum it away, marginalise it out. Because that computation is potentially very expensive, we very often make an approximation to it. And we say that it's approximately equal to finding the best Q, the best single value of Q. So we just take the maximum over all possible values of Q of this thing here. So pick one state sequence, the one that gives you the highest probability, and assume that that's so much better than all the rest that that is a good enough approximation to the sum. That turns out to be empirically a very reasonable thing to do. This works well in practice, we could do the summation, we could replace it with this maximisation operation, and our speech recogniser will work just as well. It'll give just as low a word error rate. How do you find the Q that maximises this probability? We've got to search amongst all the values of Q. But we don't want to enumerate them out because then we might as well just do the summation. We want a very efficient algorithm for exploring all the different values of Q, the state sequence, and minimising the amount of computation needed to find the best state sequence. Well, that sounds awfully familiar. So we define the Hidden-Markov model, and we said it has this property, state sequence, that's the journey we need to take through the model to emit an observation sequence. And we don't know what state sequence our model took when it generates a particular observation sequence. And so the correct thing to do is to treat the state sequence as a random variable, and to marginalise it away, to sum over it. The summation could be very expensive, so we'll make an approximation, we'll take a shortcut, and we'll just say, just find the most likely single state sequence, and compute the probability of that state sequence generating the observations, and we'll take that as the probability that this model generated this observation sequence. So we need a data structure on which to do that computation, that computation of finding a single most likely state sequence. Whenever I say state sequence, you could also hear alignment between the model and the data. And then you could think, that's just the same as dynamic time warping. We're going to now create a data structure for doing that computation, and it's going to have to generalise to any shape of Hidden-Markov model, any topology, any pattern of transitions of connections between the states. It mustn't be restricted to the case of very simple models that move from left to right, although for speech, almost all our models will be like that. We don't want an algorithm that's in the restricted case, we want a general algorithm, and we want a data structure on which we can do that algorithm. So that's what we're going to invent now. So we'll start again with dynamic time warping. In dynamic time warping, we had an algorithm, called dynamic programming, and to store the computations whilst doing the algorithm, we needed a data structure, and we made a data structure called the grid. That's the grid, and each cell in the grid stores the partial path distance from the beginning to this point that's the best so far. We saw that the core computation in dynamic time warping was to find all the different ways of arriving in a cell on the grid, and to only keep the best one. So the core operation here was a min over distances, to take the minimum. Well, minimum over distances and maximum over probabilities, that's the same thing. Just think of one as being one over the other. So min over distances and max over probabilities are the same thing, and so this suggests the sort of data structure that we might use for a Hidden Markov Model might look something like the grid. The grid is a bit too restrictive, because it requires us to go left to right through this sequence, and left to right through this sequence. That's fine for a template and an unknown, but we're going to replace this with a finite state network that could have any topology. It might not necessarily go left to right. So the data structure we're going to use is called a lattice. So on the right is a lattice for this Hidden Markov Model here with three emitting states. I'm now going to start drawing my Hidden Markov Models in a way that matches the way that HTK implements them. It's going to turn out to be extremely convenient later when we need to join models to other models. So I'm going to add non-emitting start and end states, and I'm going to start numbering that as number one. The first emitting state is number two, and so on through the model. We're going to switch now to HTK style models. This is an implementational detail, but it's going to make something later much easier. So I must start in my non-emitting state in the lattice, and I must end in my final non-emitting state. So they're the definitions of where we must start and end. In dynamic time warping, we had a rule, a rule that we had to invent about how you can move through the grid. We said that the rule was this one. Other rules are available. If you go and read the old literature or rather old textbooks, you'll find that there are other possible patterns of moving through a grid, but this is the one we stuck with, the simplest. The counterpart of that in the Hidden Markov Model is that the model topology connections and the lack of connections between certain pairs of states tells us how we can move through the lattice. So this model says that from the non-emitting start state, you must always go to the first emitting state. That's that one there. When you arrive there, you must emit the first observation. That's done. And then time advances one step. We must take a transition at every time step, and then you arrive at a state and generate an observation. The topology of this model says that you could stay in the same state when time moves forward, or you could move to the next state when time moves forward. So you could stay in the same state, or you could move to the next state. So it's impossible to get to this state to emit the first observation, or to this one. So these will never be visited in the lattice. And then we generate this observation. Now we could generate it from this state or this state. So we do both and we store both computations separately. Those are two partial paths through the lattice. We don't know which one is best yet, they're in different states, so we store them both. We have two parallel paths. So we're doing computation in parallel. We're exploring all possible alignments between model and observation sequence. And this says that there's two different paths alive at the moment, and we can't get there. And we've generated this observation sequence, first one and the second one. And then we move forward in time again. The topology of the model says that from this state, you can stay in the same state or move forward. And if you're still here, then you can move forward and it will stay in the same state. And so on. So we just use the topology of the model to fill up the lattice. Now we have to end up here. So these paths that leave the model too early are no good. That's equivalent to coming out of the end of the model, but not having generated all the observation sequences. So you haven't accounted for them all. So that's not a valid path through the model. These ones we already said you can't even get there. And we can see that this one is a dead end. There's no way to get to the end in time. And so is this one. And so the lattice is this picture here. And this lattice is the exact counterpart to the grid in dynamic time warping. And we would do computation on it in exactly the same way.
Hidden state sequences and alignment
Hidden state sequence, Trellis (i.e. lattice) representation of an HMM, aligning observations to states
Log in if you want to mark this as completed
|
| ||||||||||||||||||||||||||||||||||||||||||