im not smart enough to understand this intuitively from watching this video just once, but after some additional visualization on my own and reading the concept of "edit distance", it started to click
You mean it should be D_{1,3}, but you are right that there's a mistake! Thanks a ton for catching it. I added it to the Errate list in the video comments. You can check and see if you agree!
Great video! Very informative. Quick question - when dealing with two time-series, can one be on another scale? (example one being one having values 0-100 and another from 10,000 to 50,000)
Thanks a lot for this playlist and your good explanation! In 14:05, you mentioned that there could be two options as an optimal path for one cell. Here that cell wasn't in the main path, but in general, does it make a difference in the final alignment path? Should we consider this in the algorithm and the code?
Very good question! First, when you are dealing with real continuous signals (like) speech, this is actually very unlikely to happen. With discrete sequences (e.g. when you have the edit distance), it happens a lot more. Second, if it does happen, it will affect your path (you actually will have a choice now), but both paths will have the same overall cost. I had to sleep on it to get an example, but imagine x = [0, 1, 1] and y = [0, 3, 3, 3]. You can quickly build up the matrix for yourself, and you will see that there are two equivalent paths (both with an overall cost of 6). In the one path, the last one 1 in x is aligned with the last two 3's in y. In the other path, the second 1 in x is aligned to the first two 3's in y. But it doesn't matter which one you pick, since both have the same overall cost. Hope that helps!
Wow. Amazing video!!! I realized that (Sakoe and Chiba 1978) propose a symmetric step pattern with a weight coefficient of 2 for the diagonal direction (D[i-1, j-1] + 2 * d[x_i, y_j]). This is the default implementation in the "dtw-python" library (they call it: 'symmetric2' or 'symmetricP0'). Your video is a such a good explanation and will be my preferred reference for sure. I wonder how the weight coefficient of 2 in the dtw-python library changes how the distance is ultimately calculated (I'm still pondering...perhaps it penalizes diagonal steps). [fyi: I tried your example signals in the dtw-library with the symmetricP0 step pattern and there is no difference in the cost matrix but that may differ with other complicated signals I assume]. Would you by chance have any thoughts on this? Thanks!
I've quickly skimmed the paper but probably not enough detail since I don't have a concrete answer. But here's one intuitive way of thinking why this would be a good idea: doing this basically says that, if you want to move diagonally, then to do this should be better than to take the two move steps: right+up or up+right. Stated differently, when you have the times-2, a diagonal move is basically two moves where you pay d[x_i, y_j] for each individual move. Does that make sense (at an intuitive level)? I should also add that if d[x_i, y_j] = 0 (which rarely happens in practice but does happen in my example), then the times-2 multiplier won't have any effect (2*0 = 0), which might be why you get exactly the same output. Hope this helps! :) Let me know if not and I'll think about it even more.
Hey Paulo. In the "vanilla" DTW, the final DTW cost is just the sum of the costs along the DTW alignment path. But it is actually a good idea to normalize by the length of the path (in some way). I actually describe this in the last video in this "series" (check the playlist linked in the video comments); specifically, you can look at this video watching from around minute 11 onwards: czcams.com/video/QoL7drXt6EA/video.html.
by the way - what is the source of these versions of formulas you use in your presentation? I would like to cite it like this, because in other documents I feel like it is often described in much more complex way
Good question! I mostly formulated these myself, but at the end of the last video in this series I give the references that I used to make the videos: czcams.com/video/QoL7drXt6EA/video.html. Hope that helps!
You deserve an award for explaining such a complex thing in an understandable way. I wish you a long and beatufiful life.
I was trying to understand DTW and found this. Such a clear, beautiful explanation. Thank you very much!
Very happy it helped! :)
You have a gift for breaking complex topics into easy, clear chunks and explaining them! Kudos!
Such a beautiful explanation for such an intricately complex topic which has beautiful usages in real life world.
Thanks a lot!
Great video @Herman. Appreciate the effort!
Thanks a lot, by far the best explanation on the topic
Very happy it helps! :)
awesome video. I was learning dynamic programming, and glad to see a time series application.
Thank you very much. By far the best and detailed explanation I've seen (and understand :) ) so far.
Huge pleasure! :)
Wow, such a complex topic and yet such a beautiful explanation. Very patiently explained. Thanks!
Best explanation I saw so far. Thanks for making this video, now I really understand how this work and so I can finally describe it in my thesis.
I was kinda lost until 17:00 when the pin dropped! thank you for making this so understandable
Thank you for the effort and time you spend in this - it really explains DTW.
Great explanation, thanks!
Fantastic! Thank you so much! The clearest explanation I've seen!! Congrats!!
Excellent explanation, very clear! Thank you!
Super easy to understand. great explanation. thanks a lot :)
im not smart enough to understand this intuitively from watching this video just once, but after some additional visualization on my own and reading the concept of "edit distance", it started to click
Very very very well explained
Thanks a lot for the detailed and clear explanation!
Huge pleasure! :)
Thank you for such a great tutorial
Thank you for this very instructive video. At 12:54 I think D_i,j-1 should be D_1,4
You mean it should be D_{1,3}, but you are right that there's a mistake! Thanks a ton for catching it. I added it to the Errate list in the video comments. You can check and see if you agree!
@@kamperh sorry D_{1,3}.
This reminds me of Longest Common Subsequence problem
This is the first time I understand DTW ! very good and clear explanation. Thanks a lot.
Very very happy it helped! :)
Very well explained
Very happy it helped! :)
very good tutorial! thx
Great video! Very informative. Quick question - when dealing with two time-series, can one be on another scale? (example one being one having values 0-100 and another from 10,000 to 50,000)
Thanks a lot for this playlist and your good explanation!
In 14:05, you mentioned that there could be two options as an optimal path for one cell. Here that cell wasn't in the main path, but in general, does it make a difference in the final alignment path? Should we consider this in the algorithm and the code?
Very good question! First, when you are dealing with real continuous signals (like) speech, this is actually very unlikely to happen. With discrete sequences (e.g. when you have the edit distance), it happens a lot more. Second, if it does happen, it will affect your path (you actually will have a choice now), but both paths will have the same overall cost.
I had to sleep on it to get an example, but imagine x = [0, 1, 1] and y = [0, 3, 3, 3]. You can quickly build up the matrix for yourself, and you will see that there are two equivalent paths (both with an overall cost of 6). In the one path, the last one 1 in x is aligned with the last two 3's in y. In the other path, the second 1 in x is aligned to the first two 3's in y. But it doesn't matter which one you pick, since both have the same overall cost. Hope that helps!
@@kamperh Thank you very much! the example was very helpful🙏
Good 🎉
Thank you. Very well explained. Is there any algorithm that can compare pattern of matrices.
Does this algorithm work with negative instance? I mean can i use vectors with both negative and postive values?
Interesting algrithum.
Thank you very much. Can I use DTW as evaluation metric for time series forecast?
Wow. Amazing video!!! I realized that (Sakoe and Chiba 1978) propose a symmetric step pattern with a weight coefficient of 2 for the diagonal direction (D[i-1, j-1] + 2 * d[x_i, y_j]). This is the default implementation in the "dtw-python" library (they call it: 'symmetric2' or 'symmetricP0'). Your video is a such a good explanation and will be my preferred reference for sure. I wonder how the weight coefficient of 2 in the dtw-python library changes how the distance is ultimately calculated (I'm still pondering...perhaps it penalizes diagonal steps). [fyi: I tried your example signals in the dtw-library with the symmetricP0 step pattern and there is no difference in the cost matrix but that may differ with other complicated signals I assume]. Would you by chance have any thoughts on this? Thanks!
I've quickly skimmed the paper but probably not enough detail since I don't have a concrete answer. But here's one intuitive way of thinking why this would be a good idea: doing this basically says that, if you want to move diagonally, then to do this should be better than to take the two move steps: right+up or up+right. Stated differently, when you have the times-2, a diagonal move is basically two moves where you pay d[x_i, y_j] for each individual move. Does that make sense (at an intuitive level)? I should also add that if d[x_i, y_j] = 0 (which rarely happens in practice but does happen in my example), then the times-2 multiplier won't have any effect (2*0 = 0), which might be why you get exactly the same output. Hope this helps! :) Let me know if not and I'll think about it even more.
This is very helpful. Thanks so much! (sorry for the late reply) 😅
At the end of the matrix, the smallest DTW points will just be summed, or summed and divided by the length of the DTW point vector? Thanks
Hey Paulo. In the "vanilla" DTW, the final DTW cost is just the sum of the costs along the DTW alignment path. But it is actually a good idea to normalize by the length of the path (in some way). I actually describe this in the last video in this "series" (check the playlist linked in the video comments); specifically, you can look at this video watching from around minute 11 onwards: czcams.com/video/QoL7drXt6EA/video.html.
BEST EXPLANATION ON THE INTERNET! Please do one on the O(n) algorithm.
Can you link where I would find an O(n) for this?
Why do we initialize with infinity ?
by the way - what is the source of these versions of formulas you use in your presentation? I would like to cite it like this, because in other documents I feel like it is often described in much more complex way
Good question! I mostly formulated these myself, but at the end of the last video in this series I give the references that I used to make the videos: czcams.com/video/QoL7drXt6EA/video.html. Hope that helps!
@@kamperh Thank you very much!
Lopez Sharon Davis George Taylor Laura
do you have an email or linkedin? sir @Herman Kamper?