Raise warning when it is not feasible to get at least one pair of non-trivial motif

[NimaSarajpoor]

As explained here, it is possible to have T and m that result in 0 subsequence that satisfy the exclusion rule, i.e. |i - j| > excl_zone, where i and j are the start index of two subsequences T[i, i + m] and T[j : j + m].

See Example below:

import numpy as np
import stumpy

T = np.random.rand(10)
m = 8

out = stumpy.stump(T, m)

# out
[[inf -1 -1 -1]
 [inf -1 -1 -1]
 [inf -1 -1 -1]]

In this example, len(T) is 10, and m = 8, and the start index of subsequences are 0, 1, 2. However, since the [default] excl_zone is 2, then it means there is no i,j in {0, 1, 2} that satisfies the exclusion rule. It would be a good idea to raise warning in such scenario. As suggested here, core.check_window_size seems to be a good place for raising that warning.

[NimaSarajpoor]

What should we check?
(1) Only check if there exists at least one pair of subsequences that satisfies |i - j| > excl_zone. So, we are trying to see if this condition can be satisfied when i==0 and j == n - m. In other words, check if n - m > excl_zone.

(2) Another (additional?) check we can do is to see if there exists at least one non-trivial neighbour for each subsequence. In other words, for a given i, we need to find the max |i-j|, and we need to find it for ALL subsequences, and then take the minimum value among them, and that should satisfy the exclusion rule. This does not seem to be difficult but I feel it is not necessary and (1) should suffice.

@seanlaw
Any thoughts?

[seanlaw]

I started writing a long response and ultimately came to the same conclusion as you did:

if 0 + excl_zone + m > n:

To me, this is the same as testing whether the first subsequence (index 0) in the time series has a non-trivial nearest neighbor.

Relating to your second point, we don't ever need to check all subsequences. If the first and last both have non-trivial neighbors, then all other subsequences must have one too. Having said that, the if condition to check the last subsequence turns out to be identical to checking the first subsequence! So, I think we're good to do:

if excl_zone + m > n:

[NimaSarajpoor]

To me, this is the same as testing whether the first subsequence (index 0) in the time series has a non-trivial nearest neighbor.

Good point! Right!!

Relating to your second point, we don't ever need to check all subsequences. If the first and last both have non-trivial neighbors, then all other subsequences must have one too.

Not necessarily. Example:

import numpy as np
import stumpy

seed = 0
np.random.seed(seed)
T = np.random.rand(10)
m = 7

out = stumpy.stump(T, m)
print(out)

# out
[[3.796291238545278 3 -1 3]
 [inf -1 -1 -1]
 [inf -1 -1 -1]
 [3.796291238545278 0 0 -1]]

Here, the index 1 has no non-trivial neighbour.

the if condition to check the last subsequence turns out to be identical to checking the first subsequence!

Correct. This is because we are looking at the problem from right to left this time: Let's list the subsequences: [S_0, S_1, S_2, ....., S_{n-m}], where S_i is T[i, i + m]. The inequality for both S_0 and S_{n-m} should be the same. Similarly, the check for S_1 and S_{n -m - 1} should be the same...and their index-wise distance to their non-trivial furthest neighbour is one unit shorter compared to the previous case. Eventually, when we reach the middle of the list of subsequences, i.e. idx = (n - m + 1) // 2, that is where the subsequence has SHORTEST index-wise distance to its furthest neighbour considering both left/right neighbours. If we check for that middle subsequence and realize it has at least one non-trivial neighbour, then we should be good for ALL other subsgeuqneces.

[NimaSarajpoor]

This does not seem to be difficult but I feel it is not necessary and (1) should suffice.

And by this, I meant if we should just have a check to ensure there is at least one finite value in mp (The first check where we check first and last subsequences). But, not sure from user's perspective, if this is okay or they prefer to get warning when there will be at least one non-finite value in their mp (second check where we check the middle subsequence).

---

Update: Okay... I think the second check because having just one pair is meaningless when we talk about motifs. What do you think?

[seanlaw]

Since it would be fast anyways, what if we checked both cases:

1. Check first and last subsequences
2. Check middle

I think the more important question is what would the warning message be fore each of these? I would assume that it wouldn't be the exact same message for both, right? And it wouldn't be about whether or not there is a finite/non-finite value because that's not a helpful warning. What do we want to communicate?

[NimaSarajpoor]

And it wouldn't be about whether or not there is a finite/non-finite value because that's not a helpful warning.

That is true!

I think the more important question is what would the warning message be fore each of these?

What do we want to communicate?

If (1) is not satisfied, then. the message can be something like: "All subsequences are trivial neighbours of each other. Try reducing the window size m".

and If (2) fails, then something like: "There is at least one subsequence whose all neighbours are trivial. try reducing the window size m."

For each case, we should calculate the maximum window size m and let user know in the warning message. However, reducing exclusion zone can help as well but I feel that it can become confusing if it is mentioned in the message.

[seanlaw]

What if (in either case), we simply said:

f"The window size, 'm = {m}', may be too large and could lead to meaningless results. Consider reducing 'm' where necessary"

[NimaSarajpoor]

Sounds good! Its advantage is that the warning message is simple and does not confuse user. On the other hand, users may need to run it for several time to figure out the maximum window size that results in no such warning but this situation is rarely going to happen.

With my rough calculation, m needs to be at least 80% and 66% of len(T) to get such warning in case1 and case2 respectively, and that is a very large m! So, the chance of getting to such situation is rare and I think simple warning message is better!! And I think the term "may be" is a good choice here!