Stumpi with custom metric

[arainboldt]

Hi. Awesome library! Really enjoying reading through it! I would like to use the online stumpi method with a unique metric like dynamic time warping. Is this possible given Stump's implementation? If so, what would be the recommended approach?

Thanks

Andrew

[seanlaw]

@arainboldt Thank you for using STUMPY! While I am aware of DTW, I don't know what it would mean as a metric in this case since STUMPY is computing a matrix profile for subsequences within a time series. IIUC, DTW is related to computing a metric that described how similar two full time series are that may be of different lengths. Again, my knowledge of DTW is limited and, perhaps, you can provide a more concrete example of what it is that you want to do and I can direct you accordingly.

The main priority and scope of our package is to reproduce published work so I would be willing to take a look if you could point me to the relevant published resources.

[arainboldt]

Hi Sean, thanks for the quick response. DTW is a metric for similarity of time series of potentially different lengths. It's not necessary or common to use the entire time series.

I don't have any papers handy, but there are plenty available. Functionally, DTW can replace the euclidean distance as it is. I'm really curious hiw you would recommend doing that without compromising the optimizations that have been built into Stump. Keeping in mind of course that DTW is more costly computationally and memory wise than euclidean distance.

[arainboldt]

Hi Sean, here is another researcher with an implementation of MP with DTW in C++.

https://github.com/aafulei/matrix-profile-with-dtw

[arainboldt]

Actually, reading through the code I see that you're using Pearson's Corr and converting that to the distance. So incorporating a custom distance would require a bit of refactoring. It's not as modular as I had assumed.

In any case, if you've got any suggestions about how best to do this they'd be appreciated.

[seanlaw]

@arainboldt Let me start off by saying, sincerely, I want to help or be helpful where possible so please accept my line of questioning as coming from a place of "trying to understand". Your patience is appreciated.

I don't have any papers handy, but there are plenty available. Functionally, DTW can replace the euclidean distance as it is. I'm really curious hiw you would recommend doing that without compromising the optimizations that have been built into Stump. Keeping in mind of course that DTW is more costly computationally and memory wise than euclidean distance.

Maybe I'm misunderstanding here but, frankly, I don't think this is a "STUMPY" issue and is more about the fundamental differences between DTW and matrix profiles. In fact, both concepts come from Eamonn Keogh's group and I have yet to see Eamonn publish a clear paper that explains how to perform DTW in matrix profile parlance. The current optimizations in our code base come from the original matrix profile papers and this is how we try to limit the scope of our work. There's one rather tricky optimization from the published work that traverses the distance matrix along diagonals. This allows one to re-use a parts of a critical dot product (i.e., D[i, j] depends on D[i-1, j-1] or, more concretely, the dot product QT[i-1, j-1]). You would first need to see if DTW falls into this categorization of computation. I recommend reviewing Keogh's original papers on matrix profiles as they are an excellent and complete resource.

Actually, reading through the code I see that you're using Pearson's Corr and converting that to the distance.

So, it's not as simple as is being portrayed here. Yes, ultimately, we compute a Pearson correlation but this is the easy part. The harder part is ensuring that the current Pearson correlation (at [i, j]) is computed from the covariance from the last diagonal element (i.e., [i-1, j-1]). Again, this is based on the optimizations from the published matrix profile work (see StompOpt and Scrimp++).

So incorporating a custom distance would require a bit of refactoring. It's not as modular as I had assumed.

At the end of the day, what is exposed to the user is a single function stumpy.stump and everything else is abstracted away. We purposely keep everything as flat as possible. The only issue is that a different custom distance may have different diagonal dependencies. For example, I recommend comparing the stumpy.stump code and the stumpy.aamp code. The former computes the matrix profile using a z-normalized Euclidean distance and the latter computes the matrix profile using a non-normalized Euclidean distance (i.e., straight Euclidean distance). A large part of the two codes are very similar and, in the future, we may consider combining them by adding an additional abstraction layer that would allow the user to toggle between the two different distances (i.e., maybe something like a stumpy.matrix_profile(T, m, method="aamp"). Side note: aamp for Euclidean distance is not able leverage the Pearson correlation and so these small differences greatly affect the modularity of the code.

Having said that the current infrastructure only supports efficient diagonal-wise traversal of the distance matrix.

Hopefully, you can understand that it's not as straightforward as replacing the existing distance metric with a custom one. That "custom distance metric" needs to be one that can be constructed from the previous diagonal element. This is a strict requirement.

Let me know if that makes sense. Otherwise, I am happy to discuss this further as I'm still learning as well!

[seanlaw]

One additional thought. You may also be interested in something called mpdist which is somewhat similar to DTW for comparing time series of different lengths but, instead of DTW, uses the z-normalized Euclidean matrix profile to compare them. MPdist is not currently implemented in STUMPY but it is like less than 10 lines of code to compute once you have the matrix profile output from STUMPY.

Here's the MPdist paper by Eamonn Keogh's group.

[arainboldt]

Hi Sean, thanks again for following up so promptly. I appreciate your patience and explanation. I just started reading about Matrix Profiles yesterday and haven't worked through all the details of the algorithms yet. As I started reading through your code I realized that it was rather naive to assume the modular replacement of the metric function.

Thanks for pointing out the detail about the diagonal dependence of the distance function for efficient computation of the MP. I'll have to explore more to see if DTW can be made amenable to such a restriction. I'm assuming it is not in it's current forms.

Nevertheless, thanks much for your insight and the awesome package!

[seanlaw]

No worries and thank you for asking the question! Our community can only get better with open communication, knowledge sharing, and empathy for our users. I certainly don't know everything and I hope that you will consider contributing to STUMPY and sharing it with your friends and colleagues 😊

[seanlaw]

@arainboldt If you don't mind, I'll go ahead and close this issue for now but please feel free to re-open this issue or start a new one if you have any further questions. Thank you