NDLI: A computationally efficient nonparametric approach for changepoint detection

Content Provider	Springer Nature Link
Author	Haynes, Kaylea Fearnhead, Paul Eckley, Idris A.
Copyright Year	2016
Abstract	In this paper we build on an approach proposed by Zou et al. (2014) for nonparametric 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. Minimising 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 (Haynes et al. 2016), 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.
Starting Page	1293
Ending Page	1305
Page Count	13
File Format	PDF
ISSN	09603174
Journal	Statistics and Computing
Volume Number	27
Issue Number	5
e-ISSN	15731375
Language	English
Publisher	Springer US
Publisher Date	2016-07-28
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Nonparametric maximum likelihood PELT CROPS Activity tracking Statistics and Computing/Statistics Programs Artificial Intelligence (incl. Robotics) Statistical Theory and Methods Probability and Statistics in Computer Science
Content Type	Text
Resource Type	Article
Subject	Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics Statistics, Probability and Uncertainty

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A computationally efficient nonparametric approach for changepoint detection

Efficient computation of nonparametric survival functions via a hierarchical mixture formulation

On optimal multiple changepoint algorithms for large data

Efficient Bayesian analysis of multiple changepoint models with dependence across segments

Computationally tractable approximate and smoothed Polya trees

Erratum to: Computationally tractable approximate and smoothed Polya trees

Avoiding spurious local maximizers in mixture modeling

A two-sample empirical likelihood ratio test based on samples entropy

Stable and visualizable Gaussian parsimonious clustering models

A computationally efficient nonparametric approach for changepoint detection

Similar Documents

A computationally efficient nonparametric approach for changepoint detection

Efficient computation of nonparametric survival functions via a hierarchical mixture formulation

On optimal multiple changepoint algorithms for large data

Efficient Bayesian analysis of multiple changepoint models with dependence across segments

Computationally tractable approximate and smoothed Polya trees

Erratum to: Computationally tractable approximate and smoothed Polya trees

Avoiding spurious local maximizers in mixture modeling

A two-sample empirical likelihood ratio test based on samples entropy

Stable and visualizable Gaussian parsimonious clustering models

A computationally efficient nonparametric approach for changepoint detection