Add M-dimensional Motif Discovery

[seanlaw]

Given that there is interest for 1-D discord/motif search, it may be useful to have M-dimensional motif/discord search capabilities.

According to the last paragraph in Section IV E of the mSTAMP paper:

In the case where multiple semantically meaningful k-dimensional motifs are presented in the multidimensional time series (e.g., Fig. 5), we can just interactively apply the MDL-based method to discover the motif. There are two steps in each iteration: 1) apply the MDL-based method to find the k-dimensional motif with the minimum bit size and 2) remove the found k-dimensional motif by replacing the matrix profile values of the found motif (and its trivial match) to infinity. If we apply the two steps above to the time series shown in Fig. 5, the 3-dimensional motif would be discovered in the first iteration, and the 2-dimensional motif would be discovered in the second iteration. In terms of the terminal condition for the iterative method, it can be either be an input for the user or a more advanced technique could be applied. Due to space limitations, we will have to leave the discussion on termination condition to future works. An example of applying such iterative algorithm on real-world physical activity monitoring time series is shown
in Section V.E.

So, this means that it is possible to find different motifs at the same index location but with a different subset of dimensions!

[seanlaw]

In order to accomplish this, we'll first need a way to re-compute the Matrix Profile Subspace (see this issue)

The work on MDL and supsaces is now complete!

[seanlaw]

@SaVoAMP said:

Since k can be selected automatically now, shouldn't we generalize the functions stumpy.motifs and stumpy.matches to the multidimensional case for our motif discovery tutorial?

@SaVoAMP Would you be open to tackling this first (and I can assist)? So, this would be adding multi-dimensional support to stumpy.motifs and stumpy.match while the tutorial in #518 would come after this issue is resolved.

[SaVoAMP]

Sure, I could try!

So you want that the already existing functions can be generalized to the multidimensional case somehow? Or do you want something like stumpy.Mmotifs and stumpy.Mmatch that is only working together with MStump?

And how should I proceed then? Should I open a new Python script or write into the predefined functions and add a variable like multi_dim that is False per default, but True if I want to use stumpy.motifs and stumpy.match together with mStump for the multidimensional motif discovery?

[seanlaw]

So you want that the already existing functions can be generalized to the multidimensional case somehow? Or do you want something like stumpy.Mmotifs and stumpy.Mmatch that is only working together with MStump?

So, instead of forcing ourselves to perfect things upfront, I think it would be more pragmatic to simply work on writing an analogous, stumpy.Mmotifs and stumpy.Mmatch function that resemble the logic of stumpy.motifs and stumpy.match as close as possible. I think that once we see those functions then we can move toward integrating them together if it makes sense. However, if it doesn't make sense (e.g., if it would make it too complicated to jam everything together) then we could modify stumpy.motifs a tiny bit by adding a special decorator to it that simply detects the dimensions of the matrix profile and it will automatically hand over the work to stumpy.Mmotifs. However, let's worry about this part later! First, let's write a stumpy.Mmotifs and stumpy.Mmatch function that mimics stumpy.motifs and stumpy.match, repsectively.

And how should I proceed then? Should I open a new Python script or write into the predefined functions and add a variable like multi_dim that is False per default, but True if I want to use stumpy.motifs and stumpy.match together with mStump for the multidimensional motif discovery?

I think you can modify motifs.py and add two new functions there called def Mmotifs() and def Mmatch() for now. In fact, in the best case scenario (I don't know if this is even possible), maybe Mmotifs does the mdl work but just ends up calling motifs() once Mmotifs determines the subspace to use. Again, it's hard to know ahead of time what is "better" so we need to be okay with taking the first few rounds just to learn "good vs. bad" and treat them as "throw away". Then, as wiser people, we can try it again. How does that sound to you?

[SaVoAMP]

First, let's write a stumpy.Mmotifs and stumpy.Mmatch function that mimics stumpy.motifs and stumpy.match, repsectively.

Alright, I will start today with the stumpy.Mmotifs function and will then continue to work on it whenever I have some time besides phyics! After my last exam in February at the latest, I will have enough time to work on it.

[seanlaw]

Sounds good @SaVoAMP! Thank you for letting me know

[SaVoAMP]

Note that you'll need to clone the latest development version of STUMPY to use it.

Stupid question: "Where can I find the development branch?" 😄
I only see the main branch there.

I have already forked it like the tutorial suggested (I am quite knew to git).

[seanlaw]

Stupid question: "Where can I find the development branch?"

Not a stupid at all (and likely something we should clarify in the contribution guide)! So, the "development version" is what currently sits at https://github.com/TDAmeritrade/stumpy. So, this is the latest most up-to-date version that is actively being developed. You've forked this development version (which is a copy of the entire repository and this fork sits in your personal space) and so you will then clone your own fork (i.e., you copy from your fork to your local computer). Then, to start working on your local clone (it will start off on the "main" branch), but you'll want to create a new working branch (maybe call it "multi_motif_match"), switch to that new branch, and then do work on that new branch.

Let me know if you have more questions or want to check your understanding. If you'd like, you might consider starting by creating a new branch for updating the contributor guide (with any missing or unclear explanation) and submitting a quick PR just to see how things work.

[SaVoAMP]

Ahh, I think I have already done it, but didn't recognize that stumpy.mdl is located in mstump.py. I was searching for it under stumpy and have therefore thought that I have done something wrong.
Thank you!

[SaVoAMP]

Today I finished the first short version of Mmotifs using MDL.

I don't know why, but I get different results when I try to find k manually and compute the subspace with stumpy.subspace afterwards and then I tried to find k and the subspace with 'stumpy.mdl'.

If I manually compute k as shown I would suggest that k=9. But MDL returns k=6.
If I still choose k=6 and compute the subspace afterwards, I also get different subspaces compared to the subspace resulting after calling stumpy.motifs. Therefore I also get completely different motifs and nearest neighbors. I think one of the two subspace computations might cause the trouble. Any ideas on how to narrow it down?

Of course I might have missed something in my code, but I didn't do anything else with the subspaces and therefore I think they should be the same if I choose the same k. If you want to take a look at the code, I have just pushed it on my branch of the fork.