Robust and efficient change point detection using novel multivariate rank-energy GoF test

Shoaib Bin Masud, Shuchin AeronarXiv 2021 · OpenReview

Abstract

In this paper, we use and further develop upon a recently proposed multivariate, distribution-free Goodness-of-Fit (GoF) test based on the theory of Optimal Transport (OT) called the Rank Energy (RE), for non-parametric and unsupervised Change Point Detection (CPD) in multivariate time series data. We show that directly using RE leads to high sensitivity to very small changes in distributions (causing high false alarms) and it requires large sample complexity and huge computational cost. To alleviate these drawbacks, we propose a new GoF test statistic called as soft-Rank Energy (sRE) that is based on entropy regularized OT and employ it towards CPD. We discuss the advantages of using sRE over RE and demonstrate that the proposed sRE based CPD outperforms all the existing methods in terms of Area Under the Curve (AUC) and F1-score on real and synthetic data sets.

Introduction

Change Point Detection (CPD) is the critical task of identifying the exact moments when a data stream—such as sensor readings, financial tickers, or physiological signals—shifts from one underlying state to another. While CPD is well-understood for one-dimensional data, it presents significant challenges in multivariate settings where multiple variables may change simultaneously in complex ways.

Recently, the Rank Energy (RE) method emerged as a promising approach. By leveraging Optimal Transport (OT) theory to define a "multivariate rank," RE offers a mathematically elegant, distribution-free framework for CPD. However, practical application reveals three major flaws: its hyper-sensitivity to irrelevant jitters, high computational complexity ($O(n^3 \log n)$), and high sample complexity in high-dimensional spaces.

Methodology: The soft-Rank Energy (sRE) Approach

To address these limitations, researchers at Tufts University developed soft-Rank Energy (sRE). The core innovation lies in transitioning from "hard" optimal transport to entropy-regularized optimal transport.

Instead of a rigid, one-to-one mapping between data points and a reference grid, sRE employs the Sinkhorn algorithm to create a "diffused" or "soft" mapping. This transition is governed by a regularization parameter, $\epsilon$. By tuning $\epsilon$, practitioners can control the "blurriness" of the transport plan. A small $\epsilon$ approximates the original RE, while a larger $\epsilon$ smooths out noise and irrelevant micro-shifts. Furthermore, the Sinkhorn algorithm reduces computational complexity to $O(n^2 \log n)$, making it feasible for large-scale datasets.

Experimental Setup

The authors evaluated the sRE method against synthetic "toy" data and three established real-world benchmarks:

  • HASC-PAC2016 & HASC2011: Large-scale corpora of human pedestrian activity captured via smartphone accelerometers.
  • Beedance: A dataset tracking honeybee movements to identify specific communication patterns.
  • Toy Dataset: 3D Gaussian distributions with varying means and covariances designed to test sensitivity to specific types of distributional shifts.

Results and Discussion

The sRE method consistently outperformed existing state-of-the-art methods, including the univariate Wasserstein test (W2T) and the M-Statistic (MMD-based).

Effect of regularization parameter ε on signal amplitude and change point detection sensitivity.

As shown in Figure 1, the choice of $\epsilon$ is crucial. While standard RE (where $\epsilon \approx 0$) produces "spiky" statistics prone to false alarms, increasing $\epsilon$ produces a smoother signal that clearly highlights actual change points while ignoring noise. This controlled sensitivity allows practitioners to ignore micro-shifts while catching major state transitions.

Performance comparison (AUC and F1-score) of sRE against existing CPD methods on real-world datasets.

Quantitatively, sRE achieved the highest Area Under the Curve (AUC) scores across all three real-world datasets. For instance, on HASC-PAC2016, sRE reached an AUC of 0.747, significantly higher than the 0.689 achieved by the next best method (W2T). Similarly, sRE provided a superior balance of precision and recall, hitting an F1-score of 0.745 on the Beedance dataset, compared to the standard RE's 0.672.

Conclusion and Future Work

The introduction of soft-Rank Energy represents a significant step forward in robust multivariate CPD. By incorporating entropy regularization, the method breaks the curse of dimensionality and provides a tunable balance between sensitivity and robustness. Future research will focus on automated parameter selection for $\epsilon$ and providing more rigorous theoretical foundations for the smoothing effects observed in practice.

Summary updated

Abstract

In this paper, we use and further develop upon a recently proposed multivariate, distribution-free Goodness-of-Fit (GoF) test based on the theory of Optimal Transport (OT) called the Rank Energy (RE) [1], for non-parametric and unsupervised Change Point Detection (CPD) in multivariate time series data. We show that directly using RE leads to high sensitivity to very small changes in distributions (causing high false alarms) and it requires large sample complexity and huge computational cost. To alleviate these drawbacks, we propose a new GoF test statistic called as soft-Rank Energy (sRE) that is based on entropy regularized OT and employ it towards CPD. We discuss the advantages of using sRE over RE and demonstrate that the proposed sRE based CPD outperforms all the existing methods in terms of Area Under the Curve (AUC) and F1-score on real and synthetic data sets.
BibTeX
@misc{masud2021robust,
  author = {Shoaib Bin Masud and Shuchin Aeron},
  title = {{Robust and efficient change point detection using novel multivariate rank-energy GoF test}},
  year = {2021},
  eprint = {2111.00047},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.00047},
}
Figure