Source-linked AI summary
Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation
Song Liu, Makoto Yamada, Nigel Collier, Masashi Sugiyama
TL;DR
Change-point detection seeks abrupt changes in time-series properties, but retrospective methods need effective distribution comparison without restrictive modeling assumptions. The paper proposes direct density-ratio estimation with uLSIF and RuLSIF, using relative Pearson divergence between consecutive retrospective segments. Experiments on artificial and real-world data, including human activity, speech, and Twitter messages, demonstrate the proposed method’s usefulness and favorable detection performance.
Problem
Retrospective change-point detection must compare distributions across time segments while avoiding difficult and potentially unreliable separate density estimation.
Method
The method compares consecutive retrospective segments using relative Pearson divergence estimated directly through density-ratio methods, including uLSIF and RuLSIF.
Results
Experiments on artificial and real-world datasets, including human activity, speech, and Twitter messages, demonstrate usefulness, superior uLSIF detection accuracy, and favorable RuLSIF comparisons.
Takeaways & Limitations
Direct density-ratio estimation provides a practical non-parametric basis for retrospective change-point detection across varied data types.
Takeaways & Limitations
Performance is affected by hyperparameters n and k, whose optimal values remain an open challenge.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper focuses on retrospective change-point detection and proposes non-parametric methods based on direct density-ratio estimation. It applies uLSIF and RuLSIF to improve detection accuracy and robustness across artificial and real-world datasets.
- Motivation: Retrospective detection trades longer reaction periods for more robust and accurate detection than real-time detection.The paper considers applications that tolerate delays, including climate monitoring, genetic analysis, signal segmentation, and intrusion detection.
- Related methods: Many existing change-point methods compare distributions or subspaces using pre-designed parametric models.Examples include probability, autoregressive, and state-space models.
- Limitations of existing methods: Non-parametric kernel density estimation avoids particular parametric assumptions but becomes less accurate in high-dimensional problems because of the curse of dimensionality.
- Proposed strategy: Direct density-ratio estimation avoids separate density estimation because estimating a ratio is substantially easier than recovering both densities.The density ratio does not uniquely determine its component densities, whereas the two densities determine their ratio.
- Contributions: uLSIF directly learns the density-ratio function and provides an analytically computable, theoretically stable, and robust basis for change-point detection.Experiments demonstrate superior detection accuracy for the uLSIF-based method.
- Contributions: RuLSIF uses bounded relative density ratios and is reported to estimate more accurately from small samples than plain uLSIF.Experiments show that the RuLSIF-based method compares favorably with other approaches.
2 Problem Formulation
The problem is formulated by representing time-series subsequences as samples and comparing two consecutive retrospective segments. Their dissimilarity serves as the plausibility of a change point.
- Data representation: A d-dimensional observation y(t) is grouped into a length-k subsequence Y(t) in R^dk.
- Data representation: The subsequence representation incorporates time-dependent information by treating Y(t), rather than y(t), as a sample.
- Retrospective segments: Y(t) contains n retrospective subsequence samples starting at time t.
- Retrospective segments: The samples form a Hankel matrix, which is also used in change-point detection based on subspace learning.
- Detection criterion: The method compares consecutive segments Y(t) and Y(t+n), using their dissimilarity as change-point plausibility.A higher dissimilarity indicates a point is more likely to be a change point.
- Detection criterion: The remaining design questions concern which dissimilarity measure to use and how to estimate it from data.
3 Change-Point Detection via Density-Ratio Estimation
This section defines the dissimilarity measure used for change-point detection and presents methods for estimating it.
- Section overview: The section first defines a dissimilarity measure and then describes methods for estimating that measure.
3.1 Divergence-Based Dissimilarity Measure and Density-Ratio Estimation
The paper compares probability distributions across consecutive time segments using a symmetrized f-divergence, estimated through direct density-ratio methods. It emphasizes relative density ratios to address instability and difficult density estimation.
- Dissimilarity measure: The dissimilarity measure compares distributions of samples from consecutive segments Y(t) and Y(t+n).
- Dissimilarity measure: The underlying divergence is an f-divergence, with convex f satisfying f(1)=0 and strictly positive probability densities.The f-divergence includes KL and Pearson divergences.
- Dissimilarity measure: Because f-divergence is asymmetric, the paper symmetrizes it for divergence-based dissimilarity measures.The paper reports that symmetrization substantially improves performance compared with the prior asymmetric measure.
- Methodological choice: Hypothesis-testing formulations are not used because computing non-parametric p-values is often time-consuming.The authors note that extending the approach to hypothesis testing is methodologically straightforward.
- Density-ratio estimation: Direct density-ratio estimation avoids plugging separately estimated densities into the divergence, addressing the unreliability of density estimation.The method learns the density ratio without estimating the two component densities separately.
- Density-ratio estimation: The paper reviews KLIEP, uLSIF, and RuLSIF as direct methods for estimating density ratios from samples.
3.2 KLIEP
KLIEP directly estimates the density ratio between two distributions by minimizing KL divergence, avoiding explicit probability-density estimation. Its convex constrained optimization yields a unique global solution and supports change-point detection.
- Density-ratio model: KLIEP directly estimates the density ratio p(Y)/p′(Y) using a kernel model rather than estimating the two probability densities separately.The model uses kernel basis functions, with Gaussian-kernel width selected by cross-validation.
- Optimization: The model parameters minimize the KL divergence from p(Y) to g(Y; θ)p′(Y).
- Optimization: KLIEP imposes normalization and non-negativity constraints so the estimated weighted denominator remains a probability density and the ratio remains non-negative.
- Optimization: The convex optimization problem has a unique global optimum obtainable by gradient-projection iteration.
- Properties: KLIEP achieves the optimal non-parametric convergence rate and has been applied successfully to change-point detection in previous work.
3.3 uLSIF
uLSIF estimates the density ratio directly by fitting a kernel model under squared loss, producing an analytically computable estimator for Pearson-divergence-based change-point detection. The method is described as numerically stable and robust relative to KLIEP.
- Density-ratio estimation: uLSIF directly estimates the density ratio for Pearson divergence by fitting a kernel model to the true ratio under squared loss.
- Optimization: The uLSIF optimization problem replaces integrals with empirical averages and adds λθ^⊤θ regularization, with λ chosen by cross-validation.
- Estimator: uLSIF’s solution can be obtained analytically, yielding a direct density-ratio estimator.
- Change-point score: The Pearson-divergence approximator is constructed from the estimated density ratio and the corresponding Pearson-divergence expression.
- Properties: uLSIF has optimal non-parametric convergence, optimal numerical stability, and greater robustness than KLIEP; experiments compare its change-point detector favorably with KLIEP.
3.4 RuLSIF
RuLSIF replaces the potentially unbounded plain density ratio with a smoother, bounded relative density ratio while retaining uLSIF’s estimation framework. The paper presents this design as improving estimation accuracy and experimentally tests its change-point performance against uLSIF.
- Motivation: Plain density ratios can become unbounded when the denominator density is poorly defined, limiting the convergence behavior of uLSIF.
- Relative density ratio: RuLSIF uses α-relative density ratios based on the mixture density αp(Y)+(1−α)p′(Y), which become smoother as α increases.
- Relative density ratio: For α>0, the α-relative density ratio is bounded above by 1/α even when the plain density ratio is unbounded.
- Learning algorithm: RuLSIF learns the relative ratio with the same kernel model and squared-loss strategy as uLSIF.
- Learning algorithm: RuLSIF has the same optimization form as uLSIF, differing only in the definition of matrix H, while retaining analytic-solution, stability, and robustness advantages.
- Change-point detection: The paper states that RuLSIF-based change-point detection performs even better than the plain uLSIF-based method in experiments.
4 Experiments
Experiments on artificial and real-world time-series evaluate the proposed RuLSIF-based detector against uLSIF and KLIEP. Across these settings, the method identifies inserted or real behavioral and news-related changes and generally achieves stronger performance than the alternatives.
- Experimental design: The experiments evaluate proposed and existing methods on artificial datasets plus human-activity, speech, and Twitter time-series.Artificial data include manually inserted changes in mean, variance, covariance, and frequency.
- Artificial Datasets: Symmetric PEα combines forward and backward divergences because each asymmetric direction can miss a different change point.The symmetric divergence is therefore used as the change-point score in subsequent experiments.
- Artificial Datasets: RuLSIF scores increased rapidly after changes in artificial datasets, including changes that were difficult for humans to identify.Figure 4 reports this behavior for the last 10 change points in the synthetic datasets.
- Artificial Datasets: RuLSIF outperformed uLSIF and KLIEP in ROC/AUC comparisons, while uLSIF tended to outperform KLIEP.The ROC curves were averaged over 50 runs, and the reported method ordering remained unchanged across tested n and k choices.
- Real-World Datasets: On HASC human-activity and speech data, RuLSIF generally performed better than other methods and produced clear indications of changing behaviors or speech segments.Some HASC changes were difficult even for humans, while the speech evaluation used averages over 10 datasets.
- Twitter Dataset: For Twitter messages about the Deepwater Horizon oil spill, RuLSIF score peaks corresponded to major events from the initial explosion through the spill cutoff.Reported peaks followed oil reaching Louisiana, BP’s leak estimate, President Obama’s visit, BP’s lowest stock price, and the spill cutoff.
5 Conclusion and Future Perspectives
The paper formulates retrospective change-point detection as comparing distributions over consecutive segments and proposes uLSIF- and RuLSIF-based methods. Experiments support their usefulness, while future work targets parameter selection, dimensionality reduction, efficiency, hypothesis testing, and Twitter keyword selection.
- Retrospective change-point detection is formulated as comparing two probability distributions over consecutive time segments.
- uLSIF provides an analytically solvable, robust density-ratio estimation component with optimal nonparametric convergence and numerical stability properties.
- Performance depends on hyperparameters n and k, and selecting their optimal values remains an open challenge.
- RuLSIF-based change-point detection performed better than plain uLSIF-based detection, although the practical implications of its theoretical convergence advantage remain unclear.
- Accuracy may improve through dimensionality reduction, while density-ratio methods remain computationally costly because model selection uses cross-validation.
- Future work includes efficient p-value computation for hypothesis testing and automatic keyword selection for analyzing Twitter topics.