Changepoint detection in non-exchangeable data

Karl L. Hallgren, Nicholas A. Heard, Niall M. AdamsStat. Comput 2022 · DOI

TL;DR

This paper introduces a novel Bayesian changepoint detection model designed for data that isn't exchangeable within segments, meaning the order of observations matters. This "moving-sum" model can capture temporal dependencies within segments, leading to more accurate changepoint detection in complex time series data, as demonstrated on network traffic and financial data.

What Problem Does This Paper Address?

Traditional changepoint detection models often assume that data within a segment are independent and identically distributed (i.i.d.), a property known as exchangeability. This assumption is violated when data exhibit temporal dependencies, such as autocorrelation or seasonality. In such cases, standard models can incorrectly identify numerous spurious changepoints, obscuring true structural breaks. This is particularly problematic in fields like network security, where temporal patterns are crucial indicators of anomalies, or in financial markets, where trends and dependencies evolve. The paper addresses the need for a changepoint model that can flexibly handle these non-exchangeable data structures within segments, allowing for varying levels of dependence across different segments.

Methods

The core contribution is the moving-sum changepoint model. This model extends standard changepoint approaches by allowing data within each segment to be m-dependent. This means that an observation only depends on the previous m observations, where m can vary between segments and is unknown. The model is built upon a stochastic difference equation that relates observed data to latent variables.

Key methodological aspects include:

  • Bayesian Framework: The model is fully Bayesian, allowing for uncertainty quantification.
  • Reversible Jump MCMC (RJ-MCMC): A novel RJ-MCMC algorithm is developed to sample from the posterior distribution of changepoints and segment parameters (including the order of dependence m). This algorithm is designed to handle the varying dimensionality of the segment parameter space.
  • Parameter Space Analysis: The paper dedicates significant effort to analyzing the constraints on the parameter space for m and the latent variables, which depend on the observed data. This analysis is crucial for designing efficient proposals within the RJ-MCMC framework.
  • Segment Model: The segment model is based on convolution-closed infinitely divisible distributions, which include common distributions like Normal, Gamma, and Negative Binomial, making it applicable to various data types.

Datasets

The paper uses two real-world datasets for evaluation:

  • Computer Network Traffic Data: Second-by-second counts of network events from the Los Alamos National Laboratory enterprise network. This data is used to demonstrate changepoint detection in count data.
  • Financial Time Series Data: Daily closing prices of Sainsbury plc (SBRY.L) stock. This data is used to demonstrate changepoint detection in continuous time series.

The paper also includes synthetic data generated from the proposed model to systematically evaluate its performance under controlled conditions.

Key Insights and Ideas

  • Order Matters: The core insight is that for many real-world time series, the order of observations within a segment is informative and cannot be ignored. Assuming exchangeability can lead to over-segmentation and missed insights.
  • Varying Dependencies: The ability of the model to infer different orders of dependence (m) for different segments is crucial. This reflects how temporal dynamics can change across distinct periods or market regimes.
  • Parameter Space Constraints: The dependence of the valid parameter space for m on the observed data is a critical finding. This necessitates careful algorithm design to navigate this data-dependent space.
  • RJ-MCMC for Dynamic Dimensions: The development of an RJ-MCMC sampler that can handle the unknown and data-dependent dimensionality of segment parameters is a significant technical achievement.

Key Results

  • Improved Segmentation: In simulations and applications, the moving-sum model consistently outperforms standard changepoint models and the DeCAFS model in detecting true changepoints, especially when data exhibit temporal dependencies.
  • Network Traffic: The model successfully identifies significant changepoints in network traffic data, distinguishing them from minor fluctuations that would erroneously trigger changepoints in standard models. This leads to a more interpretable segmentation for network monitoring.
  • Financial Time Series: For stock prices, the model captures market trends and temporal dynamics more effectively, avoiding over-segmentation caused by smooth drifts. It detects shifts in both price levels and dependency structures.
  • Simulation Performance: The simulation study shows that the moving-sum model achieves high F1 scores across various scenarios, outperforming standard and DeCAFS models, particularly as temporal dependencies increase.
  • Sampler Convergence: The proposed RJ-MCMC sampler, especially with the suggested initialisation strategy, demonstrates efficient convergence to the correct number of changepoints.

Limitations and Future Work

  • Computational Cost: While the RJ-MCMC algorithm is designed for efficiency, changepoint detection in complex models can still be computationally intensive, especially for very long time series or high dependency orders.
  • Prior Choice: As with any Bayesian model, the choice of priors can influence results, although the paper uses standard conjugate priors where possible.
  • Future Work: The authors suggest exploring extensions to more complex dependency structures beyond m-dependence and investigating the model's performance on other types of non-exchangeable data. Further research into more efficient sampling strategies for high-dimensional dependency structures could also be beneficial.

Summary updated

BibTeX
@article{hallgren2022changepoint,
  author = {Karl L. Hallgren and Nicholas A. Heard and Niall M. Adams},
  title = {{Changepoint detection in non-exchangeable data}},
  journal = {Stat. Comput.},
  year = {2022},
  doi = {10.1007/s11222-022-10176-1},
}
Figure