Non-Parametric Online Change-Point Detection with Kernel LMS By Relative Density Ratio Estimation

Change-points can be defined as the time instants at which the underlying properties of a time series change. Detecting such points can be very challenging, especially when no prior information is available on the data distribution and the nature of the change. This paper introduces an onlin e nonparametric kernel-based change-point detection method built upon the direct density ratio estimation of two consecutive segments of the time series. Algorithms operating in re-producing kernel Hilbert spaces have demonstrated superiority over their linear counterparts, mainly because of their ability to deal with nonlinear problems with few prior information. However their major drawback lies in the linear growth of the models order with the number of input data, which dramatically increases computational cost and memory requirement. In addition to selecting a reproducing kernel and estimating the model parameters, designing a kernel-based model requires to determine a dictionary in order to get a finite-order model. This dictionary has a significant impact on performance, and requires careful consideration. As each new data point arrives, our algorithm updates the dictionary used to approximate the density ratio based on the coherence criterion. Then it updates the parameters of the model using the kernel least mean squares algorithm. Conditions for mean stability and asymptotic unbiasedness of our method are obtained under the null hypothesis for Gaussian input data. Mean-squared error is also studied. Finally, detection performances are evaluated by computer simulations.