上QQ阅读APP看书，第一时间看更新

DTW

Despite its Sci-Fi name, DTW has little to do with time travel, except for the fact that this technique was popular for speech recognition back in the 1980s. Imagine two signals as two springs oriented along the time axis. We place them next to each other on the table, and want to measure how similar (or how different... what's the same?) they are. One of them will serve as a template. And we start stretching and compressing another one, piece by piece, until it looks exactly as the first one (or the most similar). Then we account for how much effort we put into align two springs—we sum up all tensions and stretches together, and get the DTW distance.

DTW distance between two sound signals tells us how similar to each other they are. For example, having the record of an unknown voice command, we can compare it to voice commands in the database, and find the most similar one. DTW can be used not only with audio, but with many other types of signals. We will use it to calculate distance between signals from motion sensors:

Figure 3.3: DTW alignment of two accelerometer signals. On the left: walking sample against another walking sample. On the right: brushing teeth against walking. The shorter the alignment is, the closer the two signals are to one another. Plots created using [1] and [2].

Let's demonstrate this with a simple example. Say we have two arrays: [5, 2, 1, 3] and [10, 2, 4, 3]. How do we calculate the distance between two arrays of length one: [5] and [10]? You can use squared difference as a measure; for example, (5 - 10)²= 25. Okay, now let's extend one of them: [5, 2] and [10], and calculate the cumulative difference:

Let's extend another array to have [5, 2] and [10, 2]. Now, how to calculate the cumulative difference is not as clear as it was before, but let's assume that we are interested in the simplest way to transform one array into another (minimal distance, in other words):

By extending arrays in such a way further, eventually we will get the following table:

The bottom-right cell of the table contains the quantity we're interested in: DTW distance between two arrays, the measure of how hard it is to transform one array into another. We've just checked all the possible ways to transform arrays, and found the easiest of them (marked with a gray shading in the table). Movement along the diagonal of the table indicates the perfect match between arrays, while horizontal direction stands for deletion of the elements from the first array, and vertical movement indicates insertion into it (compare with Figure 3.3). The final array alignment looks like this:

[5, 2, 1, 3, -]

[10, 2, -, 4, 3]

By the way, DTW can be applied not only to arrays of single numbers. Replace squared difference with Euclidean or Manhattan distance, and you can compare trajectories in a three-dimensional space or taxi routes.