Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation

By Song Liu, Makoto Yamada, Nigel Collier, Masashi Sugiyama. 2012

489 citations recorded by the source corpus.

The objective of change-point detection is to discover abrupt property changes lying behind time-series data. In this paper, we present a novel statistical change-point detection algorithm based on non-parametric divergence estimation between time-series samples from two retrospective segments. Our method uses the relative Pearson divergence as a divergence measure, and it is accurately and efficiently estimated by a method of direct density-ratio estimation. Through experiments on artificial and real-world datasets including human-activity sensing, speech, and Twitter messages, we demonstrate the usefulness of the proposed method.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Hanjun Dai
2. Le Song
3. Tom Diethe
4. Nicolas Vayatis
5. Laurent Oudre
6. Charles Truong
7. Shuang Li
8. Neil D. Lawrence

In Computer Vision and Pattern Recognition

1. Le Song
2. Hanjun Dai
3. Shuang Li
4. Neil D. Lawrence
5. Nikolay Pavlovich Laptev
6. Yoshinobu Kawahara
7. Nicolas Vayatis
8. Borja Balle

In Signal Processing

1. Shuang Li
2. Neil D. Lawrence
3. Nikolay Pavlovich Laptev
4. Yoshinobu Kawahara
5. Nicolas Vayatis
6. Borja Balle
7. Takehisa Yairi
8. Le Song

Citations in the corpus

• Continual Learning in Practice (2019, methodology): “An example of this is KL Importance Estimation Procedure (KLIEP) [29], which estimates the density ratio using KL divergence, and there have since been modifications to this method which improve scalability [30].”
• A review of change point detection methods (2018, background): “They are not directly estimated; instead, the statistics d ( (cid:98) P x , (cid:98) P z ) is computed [38, 57, 63, 95].”
• Selective review of offline change point detection methods (2020, background): “They are not directly estimated; instead, the statistics d(P̂x, P̂z) are 756 computed [11, 91, 99, 123].”
• A Survey of Deep Learning-Based Object Detection (2019, unknown): “Existing anomaly detection techniques [140]–[143] analyze the data on a point-wise basis.”
• M-Statistic for Kernel Change-Point Detection (2015, methodology): “In particular, many kernel based statistics have been proposed in the machine learning literature [5, 2, 18, 6, 7, 1] which typically work better in real data with few assumptions.”
• A Survey of Methods for Time Series Change Point Detection (2016, unknown): “As a result, it is more sensitive than SI to choices of parameter values and has demonstrated lower accuracies for some datasets [35,42].”
• Learning Koopman Invariant Subspaces for Dynamic Mode Decomposition (2017, methodology): “For comparison, we applied the novelty/change-point detection technique using one-class support vector machine (OC-SVM) [46] and direct density-ratio estimation by relative unconstrained least-squares importance fitting (RuLSIF) [47].”
• Generic and Scalable Framework for Automated Time-series Anomaly Detection (2015, background): “A common strategy for detecting change points in the literature is to move two side-by-side windows on the time-series and compute the difference between the behavior of the time-series in the two windows as a measure of the deviation metric [12, 31, 20, 23].”