Home > Research > Publications & Outputs > Computationally efficient changepoint detection...

Electronic data

  • JCGS_main_supp

    Rights statement: This is an Accepted Manuscript of an article published by Taylor & Francis Group in Journal of Computational and Graphical Statistics on 02/12/2015, available online: http://www.tandfonline.com/doi/abs/10.1080/10618600.2015.1116445

    Accepted author manuscript, 844 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

Computationally efficient changepoint detection for a range of penalties

Research output: Contribution to journalJournal article

Published

Standard

Computationally efficient changepoint detection for a range of penalties. / Haynes, Kaylea; A. Eckley, Idris; Fearnhead, Paul.

In: Journal of Computational and Graphical Statistics, Vol. 26, No. 1, 02.2017, p. 134-143.

Research output: Contribution to journalJournal article

Harvard

APA

Vancouver

Author

Haynes, Kaylea ; A. Eckley, Idris ; Fearnhead, Paul. / Computationally efficient changepoint detection for a range of penalties. In: Journal of Computational and Graphical Statistics. 2017 ; Vol. 26, No. 1. pp. 134-143.

Bibtex

@article{3c8909c4ee484a3289b48414122e4be6,
title = "Computationally efficient changepoint detection for a range of penalties",
abstract = "In the multiple changepoint setting, various search methods have been proposed which involve optimising either a constrained or penalised cost function over possible numbers and locations of changepoints using dynamic programming. Such methods are typically computationally intensive. Recent work in the penalised optimisation setting has focussed on developing a pruning-based approach which gives an improved computational cost that, under certain conditions, is linear in the number of data points. Such an approach naturally requires the specification of a penalty to avoid under/over-fitting. Work has been undertaken to identify the appropriate penalty choice for data generating processes with known distributional form, but in many applications the model assumed for the data is not correct and these penalty choices are not always appropriate. Consequently it is desirable to have an approach that enables us to compare segmentations for different choices of penalty. To this end we present a method to obtain optimal changepoint segmentations of data sequences for all penalty values across a continuous range. This permits an evaluation of the various segmentations to identify a suitably parsimonious penalty choice. The computational complexity of this approach can be linear in the number of data points and linear in the difference between the number of changepoints in the optimal segmentations for the smallest and largest penalty values. This can be orders of magnitude faster than alternative approaches that find optimal segmentations for a range of the number of changepoints.",
keywords = "stat.CO, stat.ML",
author = "Kaylea Haynes and {A. Eckley}, Idris and Paul Fearnhead",
note = "This is an Accepted Manuscript of an article published by Taylor & Francis Group in Journal of Computational and Graphical Statistics on 02/12/2015, available online: http://www.tandfonline.com/doi/abs/10.1080/10618600.2015.1116445",
year = "2017",
month = "2",
doi = "10.1080/10618600.2015.1116445",
language = "English",
volume = "26",
pages = "134--143",
journal = "Journal of Computational and Graphical Statistics",
issn = "1061-8600",
publisher = "American Statistical Association",
number = "1",

}

RIS

TY - JOUR

T1 - Computationally efficient changepoint detection for a range of penalties

AU - Haynes, Kaylea

AU - A. Eckley, Idris

AU - Fearnhead, Paul

N1 - This is an Accepted Manuscript of an article published by Taylor & Francis Group in Journal of Computational and Graphical Statistics on 02/12/2015, available online: http://www.tandfonline.com/doi/abs/10.1080/10618600.2015.1116445

PY - 2017/2

Y1 - 2017/2

N2 - In the multiple changepoint setting, various search methods have been proposed which involve optimising either a constrained or penalised cost function over possible numbers and locations of changepoints using dynamic programming. Such methods are typically computationally intensive. Recent work in the penalised optimisation setting has focussed on developing a pruning-based approach which gives an improved computational cost that, under certain conditions, is linear in the number of data points. Such an approach naturally requires the specification of a penalty to avoid under/over-fitting. Work has been undertaken to identify the appropriate penalty choice for data generating processes with known distributional form, but in many applications the model assumed for the data is not correct and these penalty choices are not always appropriate. Consequently it is desirable to have an approach that enables us to compare segmentations for different choices of penalty. To this end we present a method to obtain optimal changepoint segmentations of data sequences for all penalty values across a continuous range. This permits an evaluation of the various segmentations to identify a suitably parsimonious penalty choice. The computational complexity of this approach can be linear in the number of data points and linear in the difference between the number of changepoints in the optimal segmentations for the smallest and largest penalty values. This can be orders of magnitude faster than alternative approaches that find optimal segmentations for a range of the number of changepoints.

AB - In the multiple changepoint setting, various search methods have been proposed which involve optimising either a constrained or penalised cost function over possible numbers and locations of changepoints using dynamic programming. Such methods are typically computationally intensive. Recent work in the penalised optimisation setting has focussed on developing a pruning-based approach which gives an improved computational cost that, under certain conditions, is linear in the number of data points. Such an approach naturally requires the specification of a penalty to avoid under/over-fitting. Work has been undertaken to identify the appropriate penalty choice for data generating processes with known distributional form, but in many applications the model assumed for the data is not correct and these penalty choices are not always appropriate. Consequently it is desirable to have an approach that enables us to compare segmentations for different choices of penalty. To this end we present a method to obtain optimal changepoint segmentations of data sequences for all penalty values across a continuous range. This permits an evaluation of the various segmentations to identify a suitably parsimonious penalty choice. The computational complexity of this approach can be linear in the number of data points and linear in the difference between the number of changepoints in the optimal segmentations for the smallest and largest penalty values. This can be orders of magnitude faster than alternative approaches that find optimal segmentations for a range of the number of changepoints.

KW - stat.CO

KW - stat.ML

U2 - 10.1080/10618600.2015.1116445

DO - 10.1080/10618600.2015.1116445

M3 - Journal article

VL - 26

SP - 134

EP - 143

JO - Journal of Computational and Graphical Statistics

JF - Journal of Computational and Graphical Statistics

SN - 1061-8600

IS - 1

ER -