Detecting the emergence of abrupt property changes in time series is a challenging problem. Kernel two-sample test has been studied for this task which makes fewer assumptions on the distributions than traditional parametric approaches. However, selecting kernels is non-trivial in practice. Although kernel selection for the two-sample test has been studied, the insufficient samples in change point detection problem hinder the success of those developed kernel selection algorithms. In this paper, we propose KL-CPD, a novel kernel learning framework for time series CPD that optimizes a lower bound of test power via an auxiliary generative model. With deep kernel parameterization, KL-CPD endows kernel two-sample test with the data-driven kernel to detect different types of change-points in real-world applications. The proposed approach significantly outperformed other state-of-the-art methods in our comparative evaluation of benchmark datasets and simulation studies. Detecting changes in the temporal evolution of a system (biological, physical, mechanical, etc.) in time series analysis has attracted considerable attention in machine learning and data mining for decades BID3 BID7 . This task, commonly referred to as change-point detection (CPD) or anomaly detection in the literature, aims to predict significant changing points in a temporal sequence of observations. CPD has a broad range of real-world applications such as medical diagnostics BID12 , industrial quality control BID4 , financial market analysis BID31 , video anomaly detection ) and more.Figure 1: A sliding window over the time series input with two intervals: the past and the current, where w l , w r are the size of the past and current interval, respectively. X (l) , Xconsists of the data in the past and current interval, respectively.As shown in Fig. 1 , we focus on the retrospective CPD BID36 BID23 , which allows a flexible time window to react on the change-points. Retrospective CPD not only enjoys more robust detection BID9 ) but embraces many applications such as climate change detection BID32 , genetic sequence analysis BID37 , networks intrusion detection BID41 , to name just a few. Various methods have been developed BID17 , and many of them are parametric with strong assumptions on the distributions BID3 BID16 , including auto-regressive models BID40 and state-space models BID20 for tracking changes in the mean, the variance, and the spectrum.Ideally, the detection algorithm should be free of distributional assumptions to have robust performance as neither true data distributions nor anomaly types are known a priori. Thus the parametric assumptions in many works are unavoidably a limiting factor in practice. As an alternative, nonparametric and kernel approaches are free of distributional assumptions and hence enjoy the advantage to produce more robust performance over a broader class of data distributions.Kernel two-sample test has been applied to time series CPD with some success. For example, BID18 presented a test statistic based upon the maximum kernel fisher discriminant ratio for hypothesis testing and BID23 proposed a computational efficient test statistic based on maximum mean discrepancy with block sampling techniques. The performance of kernel methods, nevertheless, relies heavily on the choice of kernels. BID13 BID14 conducted kernel selection for RBF kernel bandwidths via median heuristic. While this is certainly straightforward, it has no guarantees of optimality regarding to the statistical test power of hypothesis testing. BID15 show explicitly optimizing the test power leads to better kernel choice for hypothesis testing under mild conditions. Kernel selection by optimizing the test power, however, is not directly applicable for time series CPD due to insufficient samples, as we discuss in Section 3.In this paper, we propose KL-CPD, a kernel learning framework for time series CPD. Our main contributions are three folds.• In Section 3, we first observe the inaptness of existing kernel learning approaches in a simulated example. We then propose to optimize a lower bound of the test power via an auxiliary generative model, which aims at serving as a surrogate of the abnormal events.• In Section 4, we present a deep kernel parametrization of our framework, which endows a data-driven kernel for the kernel two-sample test. KL-CPD induces composition kernels by combining RNNs and RBF kernels that are suitable for the time series applications.• In Section 5, we conduct extensive benchmark evaluation showing the outstanding performance of KL-CPD in real-world CPD applications. With simulation-based analysis in Section 6, in addition, we can see the proposed method not only boosts the kernel power but also evades the performance degradation as data dimensionality of time series increases.Finally, our experiment code and datasets are available at https://github.com/ OctoberChang/klcpd_code. We propose KL-CPD, a new kernel learning framework for two-sample test by optimizing a lower bound of test power with a auxiliary generator, to resolve the issue of insufficient samples in changepoints detection. The deep kernel parametrization of KL-CPD combines the latent space of RNNs with RBF kernels that effectively detect a variety of change-points from different real-world applications. Extensive evaluation of our new approach along with strong baseline methods on benchmark datasets shows the outstanding performance of the proposed method in retrospective CPD. With simulation analysis in addition we can see that the new method not only boosts the kernel power but also evades the performance degradation as data dimensionality increases.A CONNECTION TO MMD GAN Although our proposed method KL-CPD has a similar objective function as appeared in MMD GAN BID22 , we would like to point out the underlying interpretation and motivations are radically different, as summarized below.The first difference is the interpretation of inner maximization problem max k M k (P, G). MMD GANs BID22 treat whole maximization problem max k M k (P, G) as a new probabilistic distance, which can also be viewed as an extension of integral probability metric (IPM). The properties of the distance is also studied in BID22 ; . A follow-up work by combining BID29 push max k M k (P, G) further to be a scaled distance with gradient norm. However, the maximization problem (4) of this paper defines the lower bound of the test power, which also takes the variance of the empirical estimate into account, instead of the distance.Regarding the goals, MMD GAN aims to learn a generative model that approximates the underlying data distribution P of interests. All the works BID11 BID24 BID34 BID22 use MMD or max k M k (P, G) to define distance, then try to optimize G to be as closed to P as possible. However, that is not the goal of this paper, where G is just an auxiliary generative model which needs to satisfies Eq. (3). Instead, we aim to find the most powerful k for conducting hypothesis test. In practice, we still optimize G toward P because we usually have no prior knowledge (sufficient samples) about Q, and we want to ensure the lower bound still hold for many possible Q (e.g. Q can be also similar to P). However, even with this reason, we still adopt early stopping to prevent the auxiliary G from being exactly the same as P.
In this paper, we propose KL-CPD, a novel kernel learning framework for time series CPD that optimizes a lower bound of test power via an auxiliary generative model as a surrogate to the abnormal distribution.  Describes a novel approach to optimising the choice of kernel towards increased testing power and shown to offer improvements over alternatives.