Home > Research > Publications & Outputs > A computationally efficient nonparametric appro...

Electronic data

  • 1602.01254v1

    Rights statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s11222-016-9687-5

    Accepted author manuscript, 606 KB, PDF document

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

Links

Text available via DOI:

View graph of relations

A computationally efficient nonparametric approach for changepoint detection

Research output: Contribution to journalJournal article

Published

Standard

A computationally efficient nonparametric approach for changepoint detection. / Haynes, Kaylea; Fearnhead, Paul; Eckley, Idris A.

In: Statistics and Computing, Vol. 27, No. 5, 09.2017, p. 1293-1305.

Research output: Contribution to journalJournal article

Harvard

APA

Vancouver

Author

Bibtex

@article{a08a865ea309463b9f6cb0b9bc16b0b4,
title = "A computationally efficient nonparametric approach for changepoint detection",
abstract = "In this paper we build on an approach proposed by Zou et al. (2014) for nonpara- metric changepoint detection. This approach defines the best segmentation for a data set as the one which minimises a penalised cost function, with the cost function defined in term of minus a non-parametric log-likelihood for data within each segment. Min- imising this cost function is possible using dynamic programming, but their algorithm had a computational cost that is cubic in the length of the data set. To speed up computation, Zou et al. (2014) resorted to a screening procedure which means that the estimated segmentation is no longer guaranteed to be the global minimum of the cost function. We show that the screening procedure adversely affects the accuracy of the changepoint detection method, and show how a faster dynamic programming algorithm, Pruned Exact Linear Time, PELT (Killick et al., 2012), can be used to find the optimal segmentation with a computational cost that can be close to linear in the amount of data. PELT requires a penalty to avoid under/over-fitting the model which can have a detrimental effect on the quality of the detected changepoints. To overcome this issue we use a relatively new method, Changepoints Over a Range of PenaltieS (CROPS) (Haynes et al., 2015), which finds all of the optimal segmentations for multiple penalty values over a continuous range. We apply our method to detect changes in heart rate during physical activity.",
keywords = "stat.CO, Nonparametric maximum likelihood, PELT , CROPS, Activity tracking",
author = "Kaylea Haynes and Paul Fearnhead and Eckley, {Idris A.}",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s11222-016-9687-5",
year = "2017",
month = "9",
doi = "10.1007/s11222-016-9687-5",
language = "English",
volume = "27",
pages = "1293--1305",
journal = "Statistics and Computing",
issn = "0960-3174",
publisher = "Springer Netherlands",
number = "5",

}

RIS

TY - JOUR

T1 - A computationally efficient nonparametric approach for changepoint detection

AU - Haynes, Kaylea

AU - Fearnhead, Paul

AU - Eckley, Idris A.

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/s11222-016-9687-5

PY - 2017/9

Y1 - 2017/9

N2 - In this paper we build on an approach proposed by Zou et al. (2014) for nonpara- metric changepoint detection. This approach defines the best segmentation for a data set as the one which minimises a penalised cost function, with the cost function defined in term of minus a non-parametric log-likelihood for data within each segment. Min- imising this cost function is possible using dynamic programming, but their algorithm had a computational cost that is cubic in the length of the data set. To speed up computation, Zou et al. (2014) resorted to a screening procedure which means that the estimated segmentation is no longer guaranteed to be the global minimum of the cost function. We show that the screening procedure adversely affects the accuracy of the changepoint detection method, and show how a faster dynamic programming algorithm, Pruned Exact Linear Time, PELT (Killick et al., 2012), can be used to find the optimal segmentation with a computational cost that can be close to linear in the amount of data. PELT requires a penalty to avoid under/over-fitting the model which can have a detrimental effect on the quality of the detected changepoints. To overcome this issue we use a relatively new method, Changepoints Over a Range of PenaltieS (CROPS) (Haynes et al., 2015), which finds all of the optimal segmentations for multiple penalty values over a continuous range. We apply our method to detect changes in heart rate during physical activity.

AB - In this paper we build on an approach proposed by Zou et al. (2014) for nonpara- metric changepoint detection. This approach defines the best segmentation for a data set as the one which minimises a penalised cost function, with the cost function defined in term of minus a non-parametric log-likelihood for data within each segment. Min- imising this cost function is possible using dynamic programming, but their algorithm had a computational cost that is cubic in the length of the data set. To speed up computation, Zou et al. (2014) resorted to a screening procedure which means that the estimated segmentation is no longer guaranteed to be the global minimum of the cost function. We show that the screening procedure adversely affects the accuracy of the changepoint detection method, and show how a faster dynamic programming algorithm, Pruned Exact Linear Time, PELT (Killick et al., 2012), can be used to find the optimal segmentation with a computational cost that can be close to linear in the amount of data. PELT requires a penalty to avoid under/over-fitting the model which can have a detrimental effect on the quality of the detected changepoints. To overcome this issue we use a relatively new method, Changepoints Over a Range of PenaltieS (CROPS) (Haynes et al., 2015), which finds all of the optimal segmentations for multiple penalty values over a continuous range. We apply our method to detect changes in heart rate during physical activity.

KW - stat.CO

KW - Nonparametric maximum likelihood

KW - PELT

KW - CROPS

KW - Activity tracking

U2 - 10.1007/s11222-016-9687-5

DO - 10.1007/s11222-016-9687-5

M3 - Journal article

VL - 27

SP - 1293

EP - 1305

JO - Statistics and Computing

JF - Statistics and Computing

SN - 0960-3174

IS - 5

ER -