Structural Break Estimation for Nonstationary Time Series Models

Richard A. Davis, Thomas C. M. Lee, Gabriel A. Rodriguez‐YamJournal of the American Statistical Association 2006 · DOI

TL;DR

This paper introduces Auto-PARM, a novel method for automatically identifying structural breaks in nonstationary time series by modeling them as piecewise autoregressive (AR) processes. By combining the Minimum Description Length (MDL) principle with a genetic algorithm, Auto-PARM effectively finds the optimal number of segments, their lengths, and the AR orders, outperforming existing methods in simulations and real-world applications.

What Problem Does This Paper Address?

Many real-world time series are nonstationary, meaning their statistical properties (like mean, variance, or dependence structure) change over time. Identifying when and how these changes occur (structural breaks) is crucial for understanding and modeling such data. Traditional methods often struggle with unknown segment lengths, unknown numbers of breaks, and unknown orders of the underlying processes. This paper tackles the challenge of simultaneously estimating all these unknown quantities for time series that can be modeled as a sequence of distinct autoregressive (AR) processes.

Methods

The core of the proposed method, Auto-PARM, lies in its two main components:

  • Minimum Description Length (MDL) Principle: This information-theoretic criterion is used to select the "best" model. The idea is that the best model is the one that allows for the shortest description of the data, balancing model complexity with how well it fits the data. The paper derives an MDL criterion for piecewise AR models.
  • Genetic Algorithm (GA): The search space for the optimal combination of segment number, break locations, and AR orders is enormous. To navigate this complex space efficiently, the authors employ a GA. This algorithm mimics natural selection, evolving a population of potential solutions (chromosomes representing model structures) through processes like crossover and mutation to find the one that minimizes the MDL criterion. The paper details a specific chromosome representation and initialization strategy tailored for this problem.

Datasets

The paper evaluates Auto-PARM using:

  • Simulated Datasets: Several simulated time series are generated to test the method's performance under various conditions, including:
  • Piecewise stationary processes with dyadic structures (segment lengths as powers of 2).
  • Processes with slowly varying AR(2) models (no true breaks but changing spectrum).
  • Processes with ARMA and MA segments (violating the pure AR assumption).
  • Processes with short segments.
  • A time-varying MA(2) process.
  • Real-World Datasets:
    • UK Seat Belt Legislation Data: Monthly data on road deaths and serious injuries to assess the impact of legislation.
  • Speech Signal: A recording of the word "greasy" to analyze its time-varying spectral characteristics.
  • EEG Data: Bivariate electroencephalogram data from a patient with temporal lobe epilepsy to detect seizure events.

The authors also compare their results with the Auto-SLEX procedure, using code provided by Dr. Hernando Ombao, on several of these datasets.

Key Insights and Ideas

  • Unified Approach for Unknowns: The paper elegantly combines the MDL principle with a GA to address the simultaneous estimation of multiple unknown model components (number of breaks, locations, and AR orders), a significant challenge in time series analysis.
  • MDL as a Powerful Criterion: Using MDL provides a principled way to balance model fit and complexity, leading to robust model selection even when the true underlying process is not perfectly captured by the assumed piecewise AR structure.
  • GA's Effectiveness in High-Dimensional Search: The GA proves to be a powerful tool for navigating the vast search space of possible segmentations and AR orders, demonstrating its utility in complex statistical optimization problems.
  • Piecewise AR as a Flexible Model: The piecewise AR model, while seemingly restrictive, is shown to be effective in approximating more complex nonstationary processes, including those with ARMA or MA components, by using higher-order AR models.
  • Consistency for Breakpoint Estimation: Theoretical results are provided to show that the estimated breakpoint locations converge to the true locations under certain conditions, lending strong theoretical support to the empirical findings.

Key Results

  • High Accuracy in Simulations: Auto-PARM consistently outperformed the Auto-SLEX method in identifying the correct number of segments and breakpoint locations across various simulated scenarios, particularly for piecewise stationary processes. For example, it correctly identified the number of segments for 96% of realizations in one simulation, compared to 73% for Auto-SLEX.
  • Accurate Parameter Estimation: The method also demonstrated good performance in estimating the AR parameters within each segment.
  • Effective for Non-AR Processes: Even when segments were not strictly AR processes (e.g., ARMA or MA), Auto-PARM could approximate them well with higher-order AR models, still accurately detecting structural breaks.
  • Real-World Applications:
    • In the Seat Belt Legislation data, Auto-PARM identified a structural change coinciding with the introduction of legislation.
  • For the speech signal, it segmented the signal into meaningful phonetic components.
  • In the EEG data, it accurately detected a seizure event, with breakpoints closely matching expert estimates.
  • Computational Efficiency: The GA-based approach, while computationally intensive, provided good results within reasonable timeframes (e.g., 2.34 seconds for a realization on a 1.6-GHz processor).

Limitations and Future Work

  • Assumed AR Structure: While Auto-PARM can approximate non-AR processes with higher-order AR models, its fundamental assumption is that segments are piecewise AR. For highly complex, non-AR processes, performance might be limited.
  • Theoretical Proofs for Number of Breaks: While consistency for breakpoint locations is proven when the number of breaks is known, the paper notes that a formal proof for the consistency of estimating the number of breaks is lacking, though simulations suggest it performs well.
  • Multivariate Extension: The paper introduces a multivariate extension, but detailed simulation studies for this case are not presented, suggesting it as an area for future work.
  • Future Work: The authors suggest exploring the multivariate extension further and potentially investigating other optimization algorithms or model classes.

Summary updated

Abstract

AbstractThis article considers the problem of modeling a class of nonstationary time series using piecewise autoregressive (AR) processes. The number and locations of the piecewise AR segments, as well as the orders of the respective AR processes, are assumed unknown. The minimum description length principle is applied to compare various segmented AR fits to the data. The goal is to find the “best” combination of the number of segments, the lengths of the segments, and the orders of the piecewise AR processes. Such a “best” combination is implicitly defined as the optimizer of an objective function, and a genetic algorithm is implemented to solve this difficult optimization problem. Numerical results from simulation experiments and real data analyses show that the procedure has excellent empirical properties. The segmentation of multivariate time series is also considered. Assuming that the true underlying model is a segmented autoregression, this procedure is shown to be consistent for estimating the location of the breaks.KEY WORDS: ChangepointGenetic algorithmMinimum description length principleNonstationarity
BibTeX
@article{davis2006structural,
  author = {Richard A. Davis and Thomas C. M. Lee and Gabriel A. Rodriguez‐Yam},
  title = {{Structural Break Estimation for Nonstationary Time Series Models}},
  journal = {Journal of the American Statistical Association},
  year = {2006},
  doi = {10.1198/016214505000000745},
}
Figure