Recap From Day 054
Day 054, we looked at working with time; how dynamic time warping works. We learned that dynamic time warping doesn’t only allow us to compute meaningful distance when one sequence is shifted earlier or later in time. Dynamic time warping also allows us to compute meaningful distance when the two sequences have different lengths in time.
Today, we will continue from where we left off in day 054
Working with time
How Dynamic Time Warping Works continued
Dynamic time warping can be thought of as solving an optimization problem. Here, our objective function is the distance between our two sequences once we’ve warped one to match the other the best we can, and our task is to find the warping that minimizes this distance.
In order to solve this optimization problem, we’ll use a technique called dynamic programming. This is why the algorithm is called dynamic time warping. This basic pattern of solving an optimization problem using dynamic programming appears in all sort of applications areas, from creating spell checkers to aligning DNA sequences.
Let’s look at a few remarks of the computational efficiency of this algorithm and on some related practical considerations. Recall that when we talked about neural networks and support vector machines, we had to solve our optimization problem during training time.
Here, however, we’re solving the optimization problem during running time whenever we’re trying to compute our degree of match to a new sequence. Granted, this is usually a much simpler optimization problem than we encounter in training neural networks or SVMs, but it can still get computationally expensive.
In particular, this problem is gonna get harder and harder to solve as our sequences get longer. If we’re not careful we can find that dynamic time warping takes so long to compute its distance calculations that it can’t keep up with new features coming in in real-time. In practice, it’s common to adapt the dynamic time warping algorithms slightly to make computation faster.
Many implementation of dynamic time warping imposes additional constraints on the warping process, preventing points in one sequence from being matched to points that are very far in time from the other sequence.
That’s all for day 055. I hope you found this informative. Thank you for taking time out of your schedule and allowing me to be your guide on this journey. And until next time, be legendary.
Reference