Whilst the video is playing, click on a line in the transcript to play the video from that point.
00:0000:17 This is the start of the speech recognition part of the course and we're on a journey towards a model called the hidden Markov model, the HMM. But we're going to get there in some small steps. We're going to start with something much simpler than a model, something called pattern matching. That's in this module.
00:1700:40 We'll then move on to thinking about the features that we extract from speech a bit more deeply and we'll do some feature engineering and then finally we'll get to the hidden Markov model which is a probabilistic generative model. Along the way we're going to learn an algorithm called dynamic programming and we're going to see that now in the form of dynamic time warping.
00:4004:38 We'll see that when we move from pattern matching to a probabilistic model we might have specific requirements for the features that we extract from speech so there's some interaction between the model we choose and the features that we choose. That's why we need to do feature engineering. And then we'll see dynamic programming again for the hidden Markov model in the form of the Viterbi algorithm. You should already know that the waveform is not the right representation for pattern recognition. For example it includes phase information which we know isn't particularly useful for discriminating for example one phone from another. You should have a reasonable idea of this concept of a feature vector but we're going to develop that a little bit more in this video. So we're going to throw away the waveform and replace it with a sequence of feature vectors and we're going to use a sequence of feature vectors for pattern matching using a very simple method with whole word templates. But even this very very simple and outdated method that we're going to talk about now already has to tackle the fundamental problem of dealing with sequences of different lengths. So you know the waveform is not a good representation because it combines source and filter and it includes phase. We only want the filter. So we want something like the spectral envelope. We know that speech waveforms change over time and that we can use short-term analysis to deal with that. And we're going to extract a feature vector from each frame in a short-term analysis of speech waveform. And to deal with this problem of sequences of different lengths we're going to need an algorithm and the core of the algorithm is going to be about finding an alignment between two sequences. In the previous videos we suggested that linear time warping would be one possible solution. Clearly that's too naive. Speech doesn't behave like that. And so now we're going to develop the real algorithm which is going to be a dynamic or nonlinear time warping to align two sequences of differing lengths. So here's what we're going to learn and it divides into two parts. In the first part we're going to extract features from frames of speech and the destination of that first part is a sequence of feature vectors to replace the waveform. And that will be our representation of speech for doing pattern matching. In the second part we'll take that sequence of feature vectors and we'll match one sequence that we know the label for against another sequence that we're trying to put a label on. In other words we're trying to do speech recognition and we'll find the distance between those two sequences of feature vectors. Let's start on the first part. And in the beginning of this course when we talked about signal processing and how speech was produced we took some inspiration from speech production. And that led us to a source filter model which we could use to explain speech signals and could be the basis for speech synthesis and all sorts of other things. That's still relevant but also relevant would be some understanding of speech perception. So let's start with that because we're going to take some inspiration from human speech perception to do feature extraction for automatic speech recognition. The cochlea is part of our hearing system. On this diagram it's this part here. And the cochlea acts like a bank of filters that respond to different bands of frequencies in this incoming audio. Of course sounds coming into the ear aren't all speech but we're only interested in speech here. So sound comes into the ear and it ends up in the cochlea. In our bodies the cochlea is coiled into a spiral but that's just to save space because we need to leave more room in our head for our brain. And so to understand it we don't need to worry about it being a spiral we can just draw it out as a straight structure like this.
04:3805:39 So sound comes into the ear as a sound wave and it propagates down the cochlea and different places along the cochlea, so this is place, respond to different frequencies in that incoming sound wave. They're effectively little resonating filters, each of them responding to a narrow band of frequencies. At some parts in the cochlea those little resonating filters respond to high frequencies and at the other end of the cochlea they respond to low frequencies. So we can understand the cochlea, which is the device in our bodies that converts sound pressure waves into nerve signals to be sent off for interpretation by the brain, as a bank of filters. The cochlea spreads frequency along its length, along its space. One of the most important features of this bank of filters in the cochlea is that it's not spaced linearly on a Hertz scale. It's spaced quite non-linearly.
05:3910:02 There's lots of mathematical functions that are used to approximate that non-linearity. The most common one in speech technology is called the Mell scale and the Mell scale looks like this. As we linearly increase in Hertz the Mell scale is compressive, it curves this way. So for example the difference in Hertz here, these high frequencies, is a relatively small difference in Mell. But down here the same difference in Hertz is a much larger difference in Mell. So it's this compressive nature to this curve that's important. What that means is that human hearing is less sensitive to frequency differences up here in the high frequency range than in the low frequency range. I'm going to use that when we extract features from speech signals for speech recognition. We're going to extract more or denser features in this sort of frequency range, which happens also to be where all the information in speech is, and fewer coarser features up in the higher frequency range. So the cochlea is like a bank of filters and they're spaced non-linearly in Hertz or linearly on some perceptual scales such as the Mell scale. And we can use those along with our knowledge of the spectral envelope to start extracting some useful features for automatic speech recognition. So let's see how a Mell scaled filter bank can be used to extract the spectral envelope from a speech signal. So here when I say auditory system I really just mean the peripheral part, the cochlea, the bit that's converting sound waves into nerve impulses. We're not talking about any processing in the brain. Let's remember what a bandpass filter is. It's something that has a lower frequency limit and an upper frequency limit and it extracts those frequencies from the input signal. And it's easiest to draw in the frequency domain where it rejects everything outside of its band and it accepts everything inside its band. So that will be an idealized perfect rectangular bandpass filter drawn in the frequency domain. The cochlea is like a set of such filters, a bank of filters, and they are spaced along a Mell scale so they get further and further apart in Hertz at higher frequencies and their widths also get wider. So a simplified idea of what the cochlea does will be that there are bandpass filters like that, that's one of them, and then another one a little wider, and then another one wider still, and so on. I've just simplified the cochlea as only having four bands, of course it's got many more than that, but we can see that the center frequencies of these filters get further and further apart as we go up in higher frequencies and that the widths of these filters also get wider, the bandwidths. These are bandpass filters, they pass through a band of frequencies. Now these idealized rectangular bandpass filters aren't actually possible physically, so the cochlea isn't like that. The cochlea has a set of overlapping filters that have some more realistic shape and a slightly better approximation than a bank of rectangular filters would be a bank of triangle filters that overlap. So we might have filters that look like this, getting wider and wider and further and further apart, and this spacing here is on a mel scale. Again I've just drawn four filters, we're going to use more than that to simulate what the cochlea does. So we've got a simplified model of the cochlea as a sequence of triangular filters, a bank of triangular filters, and we're going to use that now to extract features from speech waveforms.

Whilst the video is playing, click on a line in the transcript to play the video from that point.
00:0001:15 So what do we mean by a feature? Well, one possible set of features for speech recognition would be the raw waveform samples themselves, but we've already dismissed that as a representation that's not particularly useful. It includes phase and other things that we're not interested in. An alternative would be what we're seeing here, which is to discard phase and to just look at the magnitude spectrum. That's already better than the waveform because it's invariant to phase. So remember what we're seeing on this picture. This is the output of the discrete Fourier transform. There are bins here up to the Nyquist frequency, and that set of numbers could be a set of features for doing automatic speech recognition. So the raw DFT features, but just the magnitudes and not the phases. But we also know that this includes information that we're not interested in in general for doing speech recognition. We can see here that we can resolve all the harmonics of F0. And in general, F0 is not a useful feature for speech recognition. What we would like would be something that's this envelope.
01:1501:33 So an even more useful feature than a DFT bin would be the output of one of this bank of filters. So let's just draw one of the filters. It rejects everything, then it passes its band with some response shape. Here it's triangular. What is the output of this filter?
01:3302:06 Well, if we put the speech signal through this filter, it would pass through all of these frequencies and reject everything else. And what we're interested in is summing all of the energy in that band, summarizing that as a single number for a particular analysis frame. So it's the amount of energy in this frequency range in that analysis frame. And that's what we mean by the output of a filter. So each filter's output will be a useful feature for doing automatic speech recognition, even more useful than the DFT bins themselves.
02:0603:27 So we've got a bank of filters, and each filter for each analysis frame summarizes the amount of energy in its pass band and writes that out as a number. And what we're going to do now is we're going to just store them into a vector. So here's a speech signal, of course it's in the time domain. It's going to always be easier to think about everything in the frequency domain. So let's draw the magnitude spectrum. And what's this is? This is the magnitude spectrum for some analysis frame. So we've taken some section of the speech signal, we've cut it out, we've probably applied a tapered window, and we've taken the DFT to get the magnitude spectrum. So that's frequency. We're going to extract from this magnitude spectrum a set of features. The features are going to be the amount of energy falling inside each of the pass bands of a bank of overlapping triangular filters of some number of filters that we have to choose, but it's going to be something like 20 to 30 typically. And we're then going to store each of those in a vector. The first one is going to produce some output, and we'll store that in the first element of the vector.
03:2703:44 And then the next filter will summarize its energy into some output. We'll store that in the second element of the vector, and so on. So this vector stores the features for a single analysis frame, for this analysis frame here.
03:4404:39 Now speech changes its properties over time, and so we analyze it with a sequence of such analysis frames. So let's just talk a little more generally about this idea of sequences, because it's going to be the core problem we have to solve eventually. Sequences are everywhere in language. A waveform is a sequence of samples. We can analyze that sequence of samples with a sequence of overlapping analysis frames, and there's some correspondence between a frame and the samples that fall inside it. Back in speech synthesis, we could think about a sentence being a sequence of words, a spoken word being a sequence of phones, or a written word being a sequence of letters. Now we've gone from a waveform being a sequence of samples to being a sequence of overlapping analysis frames, and each frame giving rise to a feature vector that's extracted from it. So a waveform has become a sequence of feature vectors.
04:3904:56 Now what do all these sequences have in common? Well, they're all of variable length. There's some alignment between sequences at one level and sequences at another. For example, phones align with words, but it's not trivial because the number of phones per word is variable.
04:5605:56 Or we might also want to align sequences of the same type. If we were building a spelling correction system, we might need to align two letter sequences, the sequence of letters somebody typed and the sequence of letters of all the words in our dictionary, and compute something called the minimum edit distance or the Levenstein distance to find the word that's closest to what they typed and correct it. Or we might have the output of a speech recognition system, which gets some words right and some words wrong, and we'd like to compute its accuracy or its word error rate. That's something we'll need to do later in the course, and that will involve aligning two word sequences, which are potentially of different length and have a non-trivial alignment. But what we're going to do here and now is we're going to align two speech signals represented by sequences of feature vectors, and we're going to measure how similar they are. We're going to use that to do pattern matching and therefore to label unlabeled sequences with the label of the closest stored pattern that we already have.
05:5606:31 Now in spoken language processing, most of the time, the alignments between these sequences are monotonic. That is, as we advance through, for example, a sequence of words, we also advance through the sequence of phones that correspond to that sequence of words. In a left to right fashion, we don't backtrack, there's no reordering. But the alignment isn't linear. We don't just move proportionally to the two sequences. It's nonlinear, it's dynamic. For example, the number of phones in a word varies word by word. And this dynamic alignment is also going to be true when we align two sequences of feature vectors.
06:3106:59 So let's get back on track after talking rather abstractly about sequences. What we really care about then here are sequences of feature vectors. So let's see how that works. We've already seen that a single analysis frame, we extract its magnitude spectrum, we put a bank of triangular filters on it, and we write the outputs of those filters into our feature vector and store them. And that gives us one feature vector for one analysis frame.
06:5907:06 And then we'll just move the analysis frame forward and repeat and move it forward and repeat in the usual way.
07:0607:24 I'm going to start drawing my vectors vertically because I'm going to have a sequence of them and it will become clearer. And so we'll have a sequence of analysis frames giving rise to a sequence of feature vectors.
07:2407:41 This analysis frame, we go to the magnitude spectrum and then we do some filter bank analysis, give it a feature vector, next one, next one, and so on.
07:4108:22 This is the first step in almost every automatic speech recognition system that's ever been built is to get away from the waveform and extract from it salient features, which are at a frame rate. So they're every, for example, 10 milliseconds instead of 16,000 times per second in the time domain. So much lower rate in time. So there's far fewer of them and that they have a relatively low dimension here. So we've done the first and most important step in every automatic speech recognition system, get rid of the inconvenient waveform, distill it down into a sequence of feature vectors. And that is the representation we're going to work with from now on.

Whilst the video is playing, click on a line in the transcript to play the video from that point.
00:0000:05 So in this module, we're not going to develop any fancy probabilistic model for doing that.
00:0500:07 We're going to do something very, very simple.
00:0700:19 We're going to do pattern matching, but we're going to do this old-fashioned method for a very good reason, because it helps us understand the dynamic programming algorithm, which we're going to need again when we do do Hidden Markov Models.
00:1900:32 So if I take a sequence of feature vectors for a recorded, say, spoken word that I knew the label for, I'm going to call that an exemplar, a stored example with a label.
00:3200:34 It looks like this.
00:3400:37 I've got somebody to record the word three.
00:3700:42 I've got the waveform, and from that, I've extracted the feature vectors.
00:4200:46 And that is what I'm going to call an exemplar.
00:4600:53 If I want to do speech recognition for just the digits, I'll store one exemplar for each digit that I want to recognize.
00:5300:57 So one, two, three, and so on.
00:5701:02 I'll store them, and all I will store are their sequences of feature vectors.
01:0201:07 So that's an exemplar of the word three, and we can throw away the waveform.
01:0701:16 Going to restrict everything to whole words in isolation, so we're just going to build an isolated word recognizer.
01:1601:18 That sounds a bit restrictive, but it won't be.
01:1801:24 It'll actually be very easy to generalize that, but we won't do that generalization until we get to Hidden Markov Models.
01:2401:32 For the purposes of dynamic time warping, we'll completely restrict ourselves to isolated whole words, and let's just assume we're doing digits to keep things simple.
01:3201:44 So I've stored an exemplar of every word that is in my vocabulary, and I'm going to have an incoming speech signal from which I'll extract a sequence of feature vectors, and I would like to put a label on that.
01:4401:46 I would like to do automatic speech recognition to it.
01:4601:54 I'm going to do that by measuring the distance between that incoming unlabeled sample and all of my stored exemplars.
01:5401:59 So we need to think about how you measure the distance between two sequences of feature vectors.
01:5902:04 Here's my exemplar, and I always get rid of the waveform.
02:0402:15 So an exemplar is a label and a sequence of feature vectors stored, and that's stored inside my speech recognizer, and I'm going to measure the distance between that and some unknown incoming speech.
02:1502:25 So of course I do the same feature extraction for that and throw away its waveform, and now I want to measure the distance between these two things.
02:2502:28 The distance is going to be the dissimilarity.
02:2802:31 So a big distance means they're very unlike each other.
02:3102:35 They're unlikely to be repetitions of the same word.
02:3502:44 If there's a small distance, that's a small dissimilarity or a high similarity, which means they're more likely to be repetitions of the same word.
02:4502:59 I'm going to use this distance to decide for some incoming unlabeled sample of speech which of all my exemplars is closest, which has the smallest distance, and I'm going to put that label onto this unknown incoming speech.
02:5903:04 So how could we measure the distance between these two sequences?
03:0403:10 The simplest way I can think of is to define it as a sum of local distances.
03:1003:28 I will measure how similar the start of this thing, the exemplar on the top, sometimes we call that a template, is with the start of the unknown, and I'll measure how far apart the middles are and how far apart the ends are.
03:2803:44 So what I'm going to do is I'm going to measure local distances, and I'm going to define the total or global distance between the sequences as the sum of all of those local differences or distances.
03:4404:01 So you'll hear me using terms distance and difference, that's the same thing, and this global distance between this exemplar and this unknown is just equal to the sum of these things.
04:0104:06 Now how did I know that those particular local distances are the right ones to add up?
04:0604:08 Well, I don't yet know that.
04:0804:22 What we need to do is form some correspondence, which I'm going to call an alignment between the sequence of feature vectors for the exemplar and the sequence for the unknown, and there are many possible alignments.
04:2204:34 So the hard problem isn't one of computing distance, because I'm just going to keep a very simple local distance for now, I'm going to use the Euclidean distance between the two vectors, so a simple geometric distance, that's easy.
04:3404:43 The hard problem is exploring all of these possible alignments and deciding which one is the one to use to compute the global distance as the sum of local distances.
04:4304:46 So which local distances are the right ones to add up?
04:4604:58 We had earlier proposed that we'll simply make this as linear as possible, so we'll just stretch in some uniform way, perhaps like that, and always use that.
04:5805:02 That's clearly too naive, because speech isn't like that.
05:0205:18 We want to do something better than that, we want to dynamically stretch the sequences, and what we're going to do is we're going to make sure that the most similar parts in the exemplar are compared to their most similar parts in the unknown, and compare like with like.
05:1805:21 It's the only obvious thing to do, I think.
05:2105:27 So the hard problem is finding the alignment from amongst the many, many possible alignments.
05:2705:31 Let's just check how my diagrams relate to the way that they're drawn in Holmes and Holmes.
05:3205:33 So that you can relate this to the reading.
05:3305:42 This is a picture from Holmes and Holmes, and this is a bit like a spectrogram, but it's actually a sequence of feature vectors, and they're very similar to each other.
05:4205:58 In this diagram, this is time in frames, and this is the index of the feature vector, which is the same as which filter it is in the filter bank, and that's on a frequency scale, ascending in frequency.
05:5806:09 So each column of this picture is one of my feature vectors, and so this picture from Holmes and Holmes corresponds exactly to my picture.
06:0906:12 That's how Holmes and Holmes are drawing it, that's how I'm drawing it.
06:1206:16 I'm drawing the vectors out explicitly.
06:1606:19 So we'll use this diagram from now on.

Whilst the video is playing, click on a line in the transcript to play the video from that point.
00:0000:13 So we've talked about storing exemplars, which are just sequences of feature vectors extracted from known recordings with labels, and the idea of computing a distance to the unknown, the thing we're trying to recognize.
00:1300:24 And we've realized that the only hard part of that distance computation is aligning these two variable length sequences with each other so that we know which local distances to add up.
00:2400:40 So we're going to have to find some efficient way of considering, exploring every possible way of aligning the two sequences, but we should do that in the most efficient way possible because there might be a very large number of such alignments.
00:4000:46 And there's going to be a beautiful and elegant algorithm to do that called dynamic programming.
00:4600:50 Dynamic programming is the general term for this whole family of algorithms that have the same property.
00:5001:00 As it's applied here, because these are two time sequences, we're going to be warping them in a nonlinear way, and so this is known as dynamic time warping.
01:0001:05 So I used the term pattern matching earlier, let's just be clear what those words mean.
01:0501:13 These are the patterns, and the matching is trying to find the global distance between these two patterns.
01:1301:19 And the global distance will be the one that gives the most favorable alignment of the two frames and then sums up all the local distances.
01:1901:26 We're going to develop a dynamic programming algorithm, a special form called dynamic time warping.
01:2601:28 So how do you develop an algorithm?
01:2801:30 That sounds pretty hard.
01:3001:44 It's usually easiest to start when you're developing an algorithm with some step that's actually in the middle of the algorithm, once it's running, the standard iterative step that runs again and again, the one that repeats over and over, and understand that step.
01:4401:47 And then after that, deal with the special cases of starting and ending.
01:4701:49 Let's do that then.
01:4901:56 We're aligning these two sequences, there are many, many possible alignments, but we've got partway through the alignment, and we're doing the following.
01:5602:04 We're working our way through the template one at a time, and we're working through the unknown and finding the alignment between the two.
02:0402:10 And I keep this example simple, I'm going to assume my algorithm works through the template one frame at a time.
02:1002:19 So each iteration of my algorithm will go one step through the template, and it will decide whether to make a step through the unknown or not, so that the two eventually align.
02:1902:22 That's not fully general, but we'll generalize that in a moment.
02:2202:35 So let's imagine I've got to a state in my algorithm, where I've decided to consider comparing or aligning the fourth frame in the template with the third frame in the unknown.
02:3502:40 So I'm going to say, what about the cases where these two align?
02:4002:53 One way of doing that, one way of arriving at that point in the alignment, would be to align like this, and I could write that out as follows.
02:5303:04 The first number is the frame in the template, so frames are just counting through in time, like this, 1 to 7, and the second number is the frame in the unknown, counting through the unknown.
03:0403:11 So I've done 1 1, 2 2, 3 3, 4 3.
03:1103:19 Now let's think about all the other alignments between these two sequences, that also align 4 and 3.
03:1903:22 There's this one, and there's this one.
03:2203:30 Remember, I'm making this simple assumption that I'm just counting 1 to 7 through the template, and I decide how fast to move through the unknown.
03:3003:36 So I'm dynamically moving through the unknown, as I just advance through the template, in this simplifying case.
03:3603:40 These are the only possible alignments, given those constraints.
03:4003:44 See that I have not yet done the computation for what happens next.
03:4403:52 There are three possible alignments all arrive in this state here, of aligning 4 with 3.
03:5203:57 One of these three will be the best alignment.
03:5703:58 What's the best alignment?
03:5804:02 Well, it's the one that sums up local distances.
04:0204:09 For example, sums up this one, this one, this one, and this one, that would be the first case.
04:0904:13 And the local distance is just the Euclidean distance between the corresponding frames.
04:1304:27 Or I might consider this one, and I'd sum up those four local distances, to find the distance so far of getting to here.
04:2704:38 Or I might consider this one, and I'd sum up those four local distances, and get the distance so far of getting to here.
04:3804:49 In general, these three things will have a different distance so far of arriving at this point in the alignment.
04:4904:53 One of them will be the smallest, and that'll be the best one.
04:5304:57 And here comes the dynamic programming insight.
04:5705:07 Without going any further in the alignment, without doing any of the remaining computation that I need to get to align the two ends of the sequence, I can already choose which of these is best.
05:0705:10 Let's imagine that one's the best.
05:1005:15 And I can abandon these two.
05:1505:17 Why is that?
05:1705:24 It's because whatever happens after this point here is completely independent of what happened beforehand.
05:2405:25 Let's write that out.
05:2505:40 If I assume that these two align, then how the frames before it align, and how the frames after it align, have no interaction, they're independent of each other.
05:4005:48 The best alignment to the left, and the best alignment to the right, can be computed independently.
05:4806:10 In other words, if I was to do the dumb thing of computing all three of these all the way through to the end, so I kept on going and computed them, and there's, of course, many possibilities here, there's more than one way of going forward, so there's lots of computation still to do, the best way of aligning the remaining frames has got nothing to do with how I align so far.
06:1006:18 In other words, the computation required here is identical to it required here and here, because they're all starting from the same place.
06:1806:22 So I'd be wasting my time.
06:2206:41 If I know that this gives the lowest distance so far, summed across those four local distances, there's no point wasting my time doing this computation, because it's just the same computation as I'm going to do here anyway, and since we know they're not winning at this point, they're not going to win by the end either.
06:4106:51 That's the insight of dynamic programming, that we can save computation because we see that there's repeated computation, there's repeated subparts to the problem.
06:5106:56 Let's just state that again, because this is the key, key point of dynamic programming.
06:5607:16 The state of the algorithm at which frame 4 and frame 3 align makes everything to the left independent of everything to the right, and we can cut the problem into two parts, two halves, and we can compute this part and this part quite separately.
07:1607:20 We don't need to repeat all the possible combinations.
07:2007:31 That's conceptually quite hard, and you probably won't get it first time, but we're going to go through that through the full algorithm in a moment, and then we're going to come back to it and do it all again with Hidden Markov Models.
07:3107:42 So what I really want you to be able to do is to understand dynamic time warping as a form of dynamic programming, as an algorithm, and that's already getting harder than average for this course.
07:4207:49 Being able to see that dynamic programming can be applied to a particular problem, such as sequence alignment, is really quite difficult.
07:4908:12 If I presented you with a new problem and said, could you apply dynamic programming to this, that'd be really quite difficult, but I'd like you to be able to get to that point that you can see it is applicable to two sequences of feature vectors, and later it will be applicable for Hidden Markov Models, and what's super hard, and I don't expect you to be able to do, is to actually devise the data structure required for doing dynamic programming.
08:1208:19 And I'm just going to present the solutions to that, first for dynamic time warping, and later for Hidden Markov Models.
08:1908:27 So we'll never ask you in this course to devise a new data structure and write out a new dynamic programming algorithm for some new problem.
08:2708:47 We just really want you to see that dynamic programming works as an algorithm, what the core insight is, that we can make the past independent of the future by knowing the present, being able to see that dynamic programming is applicable, but not going that extra step of actually deriving it for a new problem.
08:4709:05 We're now going to spell out dynamic time warping as an algorithm, and the algorithm is going to need a data structure in which it stores the information as it proceeds, and that data structure is going to be very simple in fact, it's actually going to be something we'll call a grid.
09:0509:06 Here's the problem.
09:0609:23 We're exploring all possible alignments between these two sequences, a template or an exemplar with 7 frames, an unknown with 5 frames, and we'd like to consider all possible ways of aligning each of the 7 frames with each of the 5 frames.
09:2309:28 So the core operation in that is considering a pairing of frames, an alignment.
09:2809:33 For example here, the 6th frame of the template aligns with the 3rd frame of the unknown.
09:3309:41 That's the key element, the little building block of the algorithm, is this alignment between a frame in one sequence and a frame in the other sequence.
09:4109:43 So how many possible such pairings are there?
09:4309:50 We've got 7 things, each of which can align with 5 things, how many possible pairs?
09:5009:54 You could pick one thing from here and one thing from here and pair them up.
09:5409:56 How many such pairs are there?
09:5609:58 Well they're just 7 times 5.
09:5810:01 Each of the 7 things could align with each of the 5 things.
10:0110:06 So our data structure is going to need 7 times 5 elements.
10:0610:11 The obvious thing then would be to make a grid that's 7 by 5.
10:1110:12 That's what we'll do.
10:1210:16 So I'm going to draw out the template on the vertical axis.
10:1610:24 Remember this is a sequence of feature vectors, so that's time and that's frequency moving up through the filters in the filter bank.
10:2410:27 So you could think of those as little spectrograms if you prefer.
10:2710:31 Just space them out a bit because I want to draw my grid as big as possible.
10:3110:36 So that's the grid, that's the data structure that the algorithm is going to use.
10:3610:46 We've got 2 sequences of feature vectors, one that has a label and one that we're considering whether to give it the same label if it's sufficiently similar, if its distance is small enough.
10:4610:58 And we're trying to compute that distance as a sum of local distances and we want the smallest possible sum of local distances, the most optimistic one, because this is the only sensible thing to do.
10:5811:01 So we've got global distances and local distances going on in this grid.
11:0111:04 Let's just spell that out.
11:0411:05 What's a local distance?
11:0611:17 Well, at some cell which represents aligning this feature vector with this feature vector, there is some local distance we could compute.
11:1711:26 We could take these 2 vectors and we could compute the Euclidean distance between them and that would be the local distance of that cell in the grid.
11:2611:32 We've also got the global distance, which is a sum of local distances, for a particular alignment of the 2 frames.
11:3211:35 So let's just draw that out for one particular alignment.
11:3511:42 Imagine that we always align the first and the first frame, the last and the last frame.
11:4211:45 An alignment would be a path through the grid.
11:4511:47 It might look like this.
11:4711:55 We'll align those 2 and take their local distance and then we'll move here and we'll add the local distance between these 2.
11:5512:03 And then we might go here, here, here, here and here.
12:0312:16 And the global distance of this path, of this way of aligning the 2 sequences, is this local distance plus this one, plus this one, plus this one, plus this one, plus this one, plus this one.
12:1612:29 What we're trying to do is to explore every possible way of getting from here to here and find the one that adds up local distances to make the smallest possible global distance.
12:2912:31 There are many, many paths through this grid.
12:3212:36 I'm not going to draw them all out because we don't have time, but let's start drawing a few to give you the idea.
12:3612:41 There could be really, really stupid ones like this.
12:4112:51 That's really unlikely, that the first frame of the unknown aligns with all of the frames of the template and then we stay at the end of the template and align that last frame with all the remaining frames of the unknown.
12:5113:03 Or we could go like this, or we could go like this, or we could go like this, and so on.
13:0313:04 You get the point.
13:0413:06 All the way to the one that does this.
13:0613:08 A very large number of those.
13:0813:11 We're trying to do that in an efficient way.

Whilst the video is playing, click on a line in the transcript to play the video from that point.
00:0000:07 Let's just relate that back to the picture we had before when we drew the two sequences out on top of each other.
00:0700:14 That was one of the possible sequences, and that would be like moving through the grid in this fashion.
00:1400:28 And so the distance so far of arriving at this point, and assuming that this is an alignment, would be this local distance plus this local distance plus this local distance plus this local distance.
00:2900:39 And what we'll store in this cell of the grid would be the distance so far of coming from the beginning to that cell in the grid.
00:3900:40 So let's develop the full algorithm.
00:4000:49 So I'm going to generalize now, and I'm going to say that as we move through the two sequences, we have to move monotonically.
00:4900:58 In other words, as we've advanced through the frames in this one, we can't go back and consider a previous frame, because speech certainly never does that, it's monotonic.
00:5801:06 But we can advance through one frame here, or one frame here, or one in each at the same time.
01:0601:07 What does that mean on the grid?
01:0701:10 Well, let's always assume that the first two align.
01:1001:19 It means that the allowable moves in the grid are to go this way, this way, or this way at any time.
01:1901:20 That's all we're going to allow.
01:2001:22 So let's write the rules of the game.
01:2201:24 We have to start here at 1, 1.
01:2401:30 We have to get here at 7, 5, and we want to find the lowest distance path between those two points.
01:3001:32 And that's just the sum of local distances.
01:3201:43 We've got to visit grid cells along the way, and every time we visit a cell, for example, if we visit this cell, we have to accumulate the local distance between this frame and this frame.
01:4301:47 If we step on that cell, it costs us that amount of local distance.
01:4701:59 We've got to get from here to here, stepping on the cells as we go, accumulating local distances, and try and get there by accumulating the smallest amount of total distance or global distance along the way.
01:5902:03 Draw those two in because we're always going to align first with the first and last with the last.
02:0302:10 And I just showed you that we could enumerate every single possible path from the start to the end.
02:1002:13 Compute its global distance and write it down.
02:1302:17 After having done all of them, pick the one with the lowest distance.
02:1702:18 That would work.
02:1802:19 You'll get the right answer.
02:1902:21 But there'd be a lot of repeated computation.
02:2102:23 Those paths would have an awful lot in common.
02:2302:29 Many, many sub-sequences or sub-paths would be the same, and that's wasting computation.
02:2902:32 So dynamic programming gets us around that.
02:3202:34 It avoids repeating any computation.
02:3402:41 Everything is computed just once, and that computation is shared between all the different paths that require that bit of computation.
02:4102:44 Let's just do the algorithm from the beginning, see how that works.
02:4402:48 So I'm going to start here.
02:4802:52 And the distance so far is the local distance between this and this.
02:5202:55 So that's the partial path cost or distance.
02:5502:58 We often see the word cost used in the literature.
02:5803:01 So cost and distance are the same thing.
03:0103:02 A high cost means a high distance.
03:0203:03 It's a bad thing.
03:0303:05 So we've accumulated some distance.
03:0503:12 So the partial distance at this cell is just the local distance because we've only accumulated one.
03:1203:14 Now what can I do in my algorithm?
03:1403:18 Well, I said the allowable moves were to go this way.
03:1803:24 So I could move here, and I would accumulate a second local distance between this frame and this frame.
03:2403:32 And I would add that to what I'd already had from the previous cell, and that would be my partial distance so far.
03:3203:37 So I could write into this cell that distance, which is just going to be this local distance plus this local distance.
03:3703:38 That's it.
03:3803:41 I could do the same for the other moves.
03:4103:48 I'm allowed to go here, and I would accumulate the local distance between this pair of frames and add it in.
03:4803:53 And I'd write into that cell that partial path distance.
03:5303:57 That's the cost or the distance of getting to that cell from the beginning.
03:5704:03 And finally, I would do this one, get a local distance and write that in there.
04:0304:04 So far so good.
04:0404:05 That's really very simple.
04:0504:08 Now things get interesting in the next step of the algorithm.
04:0804:14 Let's imagine extending this path this way.
04:1404:16 What's the partial total distance now?
04:1604:21 Well, it's that local distance plus that local distance, which we'd already written into the cell.
04:2104:24 So it's whatever was in this cell plus this local distance.
04:2404:27 And I write that into that cell.
04:2704:30 But there's another way of getting to the same cell.
04:3004:37 I could start here with the accumulated distance so far and move here.
04:3704:45 I've now got two competing paths arriving in this cell, and one of them will be cheaper than the other.
04:4504:47 You'll have a lower distance than the other.
04:4704:52 Dynamic programming tells me I just take the lowest of those and write that in the cell.
04:5205:05 So if I computed this purple one first and wrote it in the cell, and then I computed the green one and I could get there more cheaply, then I would just overwrite that value with the lower value.
05:0505:07 I'd take the minimum of all the values.
05:0705:12 So I take the cheapest way of getting to that cell and just write that value into the cell.
05:1205:15 And that's the core step of dynamic programming.
05:1505:17 How has that saved us computation?
05:1705:25 Let's consider starting from this cell and finding the best path to the end, which is going to involve repeating that operation over and over again.
05:2505:38 Well, we do not have to take the purple path and find it to the end, and take the green path and find it to the end, because one of them's already won at this cell.
05:3805:45 So we only have to pick the winner and propagate that one forward, and we're effectively abandoning the other one.
05:4506:08 So the core operation in dynamic time warping happens at a cell that we can arrive at from multiple directions, and the global distance so far that we write into that cell is just equal to the minimum of these plus the local distance here.
06:0806:10 And that's it.
06:1006:21 And we just repeat this operation for every single cell in the grid until we do it for this cell, which of course we could arrive at in this direction, this direction, and this direction.
06:2106:41 So we take the minimum of these three things, add the last local distance in, and then in that cell is a number, let's just call it big D for global distance, and that number is the cheapest way of getting from the beginning to the end, accumulating the smallest amount of local distance on the way.
06:4106:50 So that's the core operation, and all you need to do is just visit the cells of the grid in an appropriate order, such that all the computation you need has been done by the time you get there.
06:5007:23 And that would be very easily achieved by, for example, visiting them row by row in this order, that would work, or visiting them in this order, that would work, or any other order that you can think of, such that whenever you get to a cell, you've previously visited all the cells here before you get there, so that the partial distances are available for you to take the min of and to write it into this cell plus that local distance.
07:2307:30 So the amount of computation in this algorithm is to do with the length of this sequence times the length of this sequence.
07:3007:36 So there are 35 operations to be done to compute this total distance.
07:3607:43 You've just got to visit each cell once, compare that to enumerating all the paths out one by one.
07:4307:48 That would involve this much computation, and don't worry, I'm not going to write them all out because we'll be here for hours.
07:4807:55 It would involve adding this to this, to this, to this, to this, to this, to this, to this, to this, to this, to this.
07:5508:00 So that's already 11 computations to do that one path.
08:0008:31 And then we'd forget that we'd done that, and we do one, two, three, four, five, six, seven, eight, nine, nine more computations, one, two, three, four, five, six, seven, eight, nine, ten, another nine computations, et cetera, et cetera, for all of the paths until you get to one, two, three, four, five, six, seven, eight, nine, ten, another plus 11 here.
08:3108:38 So you add all of those together, and you don't have to enumerate them out to see that that's much, much bigger than 35.
08:3808:44 It's much, much bigger because we're visiting the same cells over and over again.
08:4408:46 Dynamic programming avoids that.
08:4608:49 It visits each cell once, it does each computation once.
08:4908:55 And that's the key idea, sharing computation between all the subparts of the problem.
08:5509:09 And that was allowed because knowing that we visit this cell in an alignment makes everything before then independent of what happens going forwards.
09:0909:21 In other words, it doesn't matter how you got here, you could have come from any of these directions, you don't need to remember that because it doesn't change how you get to the end.
09:2109:24 There's no dependency between them.
09:2409:33 So the future is independent of the past given the state or the current cell.
09:3309:38 So we might state that as saying the past and the future become independent when we know the present.
09:3809:41 The present is everything we need to know.
09:4109:43 There's no memory in the system.
09:4309:47 This is conceptually a little hard, but we'll see it again with Hidden Markov Models.
09:4709:55 And the key of the Hidden Markov Model will be to make sure it has no memory so that the past and the future become independent given the present.
09:5509:57 And then we get to do dynamic programming.
09:5710:02 So it'll turn out that we'll invent a model specifically so that we can do dynamic programming with it.
10:0210:19 So we start with the idea of the distance between two sequences of feature vectors and realize that the only difficult part of that is deciding how to align them with each other so we know which local distances to add up, to make a global distance, to announce as the distance between the two sequences.
10:1910:25 And we just repeat that dynamic programming for each of the templates, each of the exemplars we have.
10:2510:32 One of them will have the lowest global distance and that will be announced as the label of the incoming word we're recognizing.
10:3210:42 We develop the algorithm and in the heart of the algorithm really is a very simple operation of taking the minimum and we had a very simple data structure in which to store the results of that operation, a grid.
10:4210:51 I'm going to go off and do some feature engineering in the next module and then come back to this idea and realize that dynamic time warping has many flaws.
10:5110:55 That's why it's no longer used for speech recognition, but we're going to fix them all.
10:5510:58 I'm going to fix all of that with a Hidden Markov Model.
10:5811:02 We're going to understand what this word hidden means.
11:0211:03 It's its state sequence that's hidden.
11:0311:13 That's another hard concept to come, but we'll find that the data structure that we might use to do dynamic program with a Hidden Markov Model is something quite like a grid.
11:1311:14 We're going to call it something different.
11:1411:18 We're going to call it a lattice, something more general than a grid.
11:1811:27 And on that data structure, we'll also be able to do almost exactly what we just did with dynamic time warping, the same sort of dynamic programming.
11:2711:30 It's going to get given a different name because it's applied to a different model.
11:3011:35 It's going to be called the Viterbi algorithm.
11:3511:45 So to summarize that, then dynamic time warping, and in particular, this local distance measure, which we didn't say very much about today, this Euclidean distance is poor.
11:4511:47 It doesn't account for variability.
11:4711:50 So it doesn't have any idea of natural variance in speech.
11:5011:51 So we better fix that.
11:5111:59 And we're going to replace it with a probabilistic model, which will be learned from multiple exemplars, multiple ones to capture the amount of natural variation.
11:5912:12 So we won't learn a model from a single recording of someone saying three, we'll get them to say three lots of times, or get lots of people to say three lots of times, and we'll form a probability distribution of the feature vectors for that word.
12:1212:17 That variability will be captured using Gaussian probability density functions.
12:1712:29 The Gaussian has not just a mean, but also a variance to capture variability, but also potentially something called covariance, which is how one element of a feature vector covaries with the other elements.
12:2912:33 And that covariance is going to turn out to be a rather awkward thing.
12:3312:36 We'd like to pretend there was no covariance.
12:3612:44 So we're actually going to do some pretty heavy duty processing to our feature vectors to try and make sure that isn't any covariance between the elements of the vector.
12:4412:49 In other words, that they become statistically independent of each other, they do not covary.
12:4913:00 So we're going to do feature engineering, motivated by our desire to use Gaussian probability density functions, and our very strong desire not to have to model covariance.
13:0013:02 So we're going to try and remove covariance.
13:0213:07 And the filter bank features are going to exhibit a lot of covariance, and are not going to be suitable.
13:0713:10 We're going to do some further steps on them.
13:1013:14 So in fact, we're going to do that feature engineering first, in the next module.
13:1413:22 We'll develop these features, which for very many years were the state of the art in automatic speech recognition, called Mel Frequency Cepstral Coefficients.
13:2213:24 We see mel still in there.
13:2413:30 The mel filter bank is going to be the first stage in extracting those features, but we're going to go further to remove covariance.
13:3013:43 When we've got those features, they will be suitable for modeling with Gaussians that can model the mean and the variance of each element of the feature vector, but assume there's no covariance between the elements.
13:4313:45 And that will then be the core of our Hidden Markov Model.
13:4513:52 We'll put those Gaussian probability density functions into the states of a finite state machine, and that will be the Hidden Markov Model.