TwoSample using sliding windows for X if N=1 ?!

[KlausGlueckert]

I reviewed the TwoSample class.

I fail to understand why you would loop thru all the iterations of sliding windows of the vector X in your process_batch function:

When printing where you collect the test-statistics you seem to compare sliding windows of N=1 ?!.
That does not make sense, even though the changepoint detection seems to work, besides it is very slow run time due to the permutations.

Can you mabye comment on this, what is the statistical reasoning behind it? I was looking into refactoring this to make it faster an leaner.

while self.t < len(X):
        Dkn = []
        for k in range(1, self.t):
                x, y = X[tau:k], X[k:self.t]
                # Different syntax for each Scipy test
                print(f"X[{tau}:{k}] vs X[{k}:{self.t}]")

X[0:1] vs X[1:2]
X[0:1] vs X[1:3]
X[0:2] vs X[2:3]
X[0:1] vs X[1:4]
X[0:2] vs X[2:4]
X[0:3] vs X[3:4]
X[0:1] vs X[1:5]
X[0:2] vs X[2:5]
X[0:3] vs X[3:5]
X[0:4] vs X[4:5]
X[0:1] vs X[1:6]
X[0:2] vs X[2:6]
X[0:3] vs X[3:6]
X[0:4] vs X[4:6]

[vkhamesi]

The original method and reasoning behind using two-sample testing for changepoint detection is taken from Ross (2015). Last time I read this paper was some time ago so my intuition may be incorrect, to me the implementation for this set of methods provided in ocpdet is correct, which explains your "seems to work" but (very) inefficient as you are pointing out.

At each time step, the algorithm looks back up to the previous changepoint, i.e. taking the batch of data X[tau:self.t]. Then, the idea is to try for all possible splits (hence the for loop on k) if they would be good splits by computing the test statistic, as if you were doing offline changepoint detection within this batch. The best split is the corresponding value of k which maximises the test statistic, from which you detect changepoints if it is greater than some pre-defined threshold. Note that a difference with the cpm package in R is that in my implementation the values of the test statistic are not normalised through time, which explains the differences in thresholds for each testing methodology.

As you are pointing out, this implementation looks correct in terms of statistical reasoning but is not computationally efficient. One could think of a solution to update more efficiently the test statistic than by re-computing all possible splits at each time step. I don't know how this was implemented in the cpm package in R, it may be interesting to have a look. Overall, this would explain why you think the method is working but is very slow.

Please correct me if I wrote something wrong, it has been a long time since I read the original paper. Happy to fix bugs or to improve efficiency if you want to contribute!