IDEAS home Printed from https://ideas.repec.org/a/spr/compst/v33y2018i2d10.1007_s00180-017-0756-9.html
   My bibliography  Save this article

A pruned recursive solution to the multiple change point problem

Author

Listed:
  • Eric Ruggieri

    (College of the Holy Cross)

Abstract

Long time series are often heterogeneous in nature. As such, the most appropriate model is one whose parameters are allowed to change through time. The exponential number of solutions to the multiple change point problem requires an efficient algorithm in order to be computationally feasible. Exact Bayesian solutions have at best quadratic complexity in the number of observations, which still can be too slow for very large data sets. Here, a pruned dynamic programming algorithm is proposed to fit a piecewise regression model with unknown break points to a data set. The algorithm removes unessential calculations, reducing the complexity of the most time consuming step of the algorithm from quadratic in the number of observations to quadratic in the average distance between change points. A distance measure is introduced that can be used to determine the divergence of the approximate joint posterior distribution from the exact posterior distribution. Analysis of two real data sets shows that this approximate algorithm produces a nearly identical representation of the joint posterior distribution on the locations of the change points, but with a significantly faster run time than its exact counterpart.

Suggested Citation

  • Eric Ruggieri, 2018. "A pruned recursive solution to the multiple change point problem," Computational Statistics, Springer, vol. 33(2), pages 1017-1045, June.
    • Handle: RePEc:spr:compst:v:33:y:2018:i:2:d:10.1007_s00180-017-0756-9
    DOI: 10.1007/s00180-017-0756-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00180-017-0756-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00180-017-0756-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Western, Bruce & Kleykamp, Meredith, 2004. "A Bayesian Change Point Model for Historical Time Series Analysis," Political Analysis, Cambridge University Press, vol. 12(4), pages 354-374.
    2. Paul Fearnhead & Zhen Liu, 2007. "On‐line inference for multiple changepoint problems," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 69(4), pages 589-605, September.
    3. Ruggieri, Eric & Antonellis, Marcus, 2016. "An exact approach to Bayesian sequential change point detection," Computational Statistics & Data Analysis, Elsevier, vol. 97(C), pages 71-86.
    4. Bradley P. Carlin & Alan E. Gelfand & Adrian F. M. Smith, 1992. "Hierarchical Bayesian Analysis of Changepoint Problems," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 41(2), pages 389-405, June.
    5. Zeileis, Achim & Leisch, Friedrich & Hornik, Kurt & Kleiber, Christian, 2002. "strucchange: An R Package for Testing for Structural Change in Linear Regression Models," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 7(i02).
    6. Chib, Siddhartha, 1998. "Estimation and comparison of multiple change-point models," Journal of Econometrics, Elsevier, vol. 86(2), pages 221-241, June.
    7. Jushan Bai & Pierre Perron, 2003. "Computation and analysis of multiple structural change models," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 18(1), pages 1-22.
    8. Peter Guttorp & Stephan R. Sain & Christopher K. Wikle & Colin Gallagher & Robert Lund & Michael Robbins, 2012. "Changepoint detection in daily precipitation data," Environmetrics, John Wiley & Sons, Ltd., vol. 23(5), pages 407-419, August.
    9. Paul Fearnhead & Peter Clifford, 2003. "On‐line inference for hidden Markov models via particle filters," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 65(4), pages 887-899, November.
    10. Nicolas Chopin, 2007. "Dynamic Detection of Change Points in Long Time Series," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 59(2), pages 349-366, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Rui Qiang & Eric Ruggieri, 2023. "Autocorrelation and Parameter Estimation in a Bayesian Change Point Model," Mathematics, MDPI, vol. 11(5), pages 1-22, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ruggieri, Eric & Antonellis, Marcus, 2016. "An exact approach to Bayesian sequential change point detection," Computational Statistics & Data Analysis, Elsevier, vol. 97(C), pages 71-86.
    2. Rui Qiang & Eric Ruggieri, 2023. "Autocorrelation and Parameter Estimation in a Bayesian Change Point Model," Mathematics, MDPI, vol. 11(5), pages 1-22, February.
    3. Chao Du & Chu-Lan Michael Kao & S. C. Kou, 2016. "Stepwise Signal Extraction via Marginal Likelihood," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(513), pages 314-330, March.
    4. Daniel Felix Ahelegbey & Monica Billio & Roberto Casarin, 2020. "Modeling Turning Points In Global Equity Market," DEM Working Papers Series 195, University of Pavia, Department of Economics and Management.
    5. Ardia, David & Dufays, Arnaud & Ordás Criado, Carlos, 2023. "Linking Frequentist and Bayesian Change-Point Methods," MPRA Paper 119486, University Library of Munich, Germany.
    6. M. Hashem Pesaran & Davide Pettenuzzo & Allan Timmermann, 2006. "Forecasting Time Series Subject to Multiple Structural Breaks," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 73(4), pages 1057-1084.
    7. Tian, Guo-Liang & Ng, Kai Wang & Li, Kai-Can & Tan, Ming, 2009. "Non-iterative sampling-based Bayesian methods for identifying changepoints in the sequence of cases of Haemolytic uraemic syndrome," Computational Statistics & Data Analysis, Elsevier, vol. 53(9), pages 3314-3323, July.
    8. Ricardo C. Pedroso & Rosangela H. Loschi & Fernando Andrés Quintana, 2023. "Multipartition model for multiple change point identification," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 32(2), pages 759-783, June.
    9. Smith, Simon C., 2017. "Equity premium estimates from economic fundamentals under structural breaks," International Review of Financial Analysis, Elsevier, vol. 52(C), pages 49-61.
    10. Simon C. Smith, 2020. "Equity premium prediction and structural breaks," International Journal of Finance & Economics, John Wiley & Sons, Ltd., vol. 25(3), pages 412-429, July.
    11. Jian He & Asma Khedher & Peter Spreij, 2021. "A Kalman particle filter for online parameter estimation with applications to affine models," Statistical Inference for Stochastic Processes, Springer, vol. 24(2), pages 353-403, July.
    12. John M. Maheu & Stephen Gordon, 2008. "Learning, forecasting and structural breaks," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 23(5), pages 553-583.
    13. Jinho Bae & Chang-Jin Kim & Dong Kim, 2012. "The evolution of the monetary policy regimes in the U.S," Empirical Economics, Springer, vol. 43(2), pages 617-649, October.
    14. Patrik Nosil & Zachariah Gompert & Daniel J. Funk, 2024. "Divergent dynamics of sexual and habitat isolation at the transition between stick insect populations and species," Nature Communications, Nature, vol. 15(1), pages 1-15, December.
    15. James Nolan & Zoe Laulederkind, 2022. "Plane to See? Empirical Analysis of the 1999–2006 Air Cargo Cartel," Advances in Airline Economics, in: The International Air Cargo Industry, volume 9, pages 241-262, Emerald Group Publishing Limited.
    16. Zeileis, Achim, 2004. "Econometric Computing with HC and HAC Covariance Matrix Estimators," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 11(i10).
    17. Michael W. Robbins & Colin M. Gallagher & Robert B. Lund, 2016. "A General Regression Changepoint Test for Time Series Data," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(514), pages 670-683, April.
    18. Amey Sapre, 2014. "Madhya Pradesh: Does Agriculture Determine the State’s Growth Trajectory?," Margin: The Journal of Applied Economic Research, National Council of Applied Economic Research, vol. 8(1), pages 39-57, February.
    19. Jung, R.C. & Maderitsch, R., 2014. "Structural breaks in volatility spillovers between international financial markets: Contagion or mere interdependence?," Journal of Banking & Finance, Elsevier, vol. 47(C), pages 331-342.
    20. Ashok Chanabasangouda Patil & Shailesh Rastogi, 2020. "Multifractal Analysis of Market Efficiency across Structural Breaks: Implications for the Adaptive Market Hypothesis," JRFM, MDPI, vol. 13(10), pages 1-18, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:compst:v:33:y:2018:i:2:d:10.1007_s00180-017-0756-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.