M -Statistic for Kernel Change-Point Detection
Detecting the emergence of an abrupt change-point is a classic problem in statistics and machine learning. Kernel-based nonparametric statistics have been proposed for this task which make fewer assumptions on the distributions than traditional parametric approach. However, none of the existing kernel statistics has provided a computationally efficient way to characterize the extremal behavior of the statistic. Such characterization is crucial for setting the detection threshold, to control the significance level in the offline case as well as the average run length in the online case. In this paper we propose two related computationally efficient M -statistics for kernel-based change-point detection when the amount of background data is large. A novel theoretical result of the paper is the characterization of the tail probability of these statistics using a new technique based on change-ofmeasure. Such characterization provides us accurate detection thresholds for both offline and online cases in computationally efficient manner, without the need to resort to the more expensive simulations such as bootstrapping. We show that our methods perform well in both synthetic and real world data.
This paper proposes two M-statistics, for the offline and online settings, for change-point detection that are based on the kernel MMD B-test statistic for two-sample testing. The B-test statistic is a recently developed alternative to the MMD that is more efficient; it involves taking an average of the MMD over a partitioning of the data into N blocks. Since the blocks are independent, the B-statistic is asymptotically normal so it is simple to obtain thresholds without resorting to bootstrapping. This procedure is modified for the case of change point detection by averaging the MMDs computed from each of N blocks occurring before a potential change point with the block of data of the same size as each N occurring after the potential change point. To determine whether a change-point has occurred somewhere in a block of data, the above procedure is carried out for each potential change point location and a Z-statistic is obtained for each. The M-statistic proposed by the authors is a maximum over the standardized Z-statistics. The authors derive an expression for the variance of the Z-statistics (needed to standardize it) and for the significance threshold of the M-statistic (since the Z-statistics are not averages of independent blocks of data, they are not asymptotically normal like in the case of the B-test) and give a theoretical performance analysis which is also verified numerically. Finally, they apply their method to several real data sets, where it seems to perform slightly better than a baseline method in terms of AUC. The work is original and significant. Competing methods require bootstrapping, which is much less efficient with larger amounts of data. Furthermore, the theoretical work involved in deriving the variance of the Z-statistic and thresholds for the M-statistic may prove to be useful elsewhere. The theoretical work is rigorous and seems reasonable. I did not check the proofs in the appendix.   The presentation is generally good, but could probably be improved. I needed to read through section 3 several times before I understood the procedure. The fact that the data are being formed into blocks at two different levels (for each N and each B) make things difficult to understand when described casually in the body of the section. Figure 1 was somewhat helpful but I was still confused. If the procedure were described more formally, e.g. pseudocode, it might be easier to understand. In my opinion, some of the space given to details in sections 4 and 5 could be better used explaining the test procedure better in section 3 (and those details moved to the appendix). Additionally, it would be useful to have more of an explanation of the baseline procedures in section 6 and incorporate some of the results from the appendix. There are some minor typographical / editing errors in the paper; it should be proofread a few times. Line 111 begins with something that is not a sentence.