Efficient Penalty Search for Multiple Changepoint Detection in Big Data

• Activity Number: 306
• Type: Topic Contributed
• Date/Time: Tuesday, August 11, 2015 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Graphics
• Author(s): Kaylea Haynes* and Idris Eckley and Paul Fearnhead
• Companies: Lancaster University and University of Lancaster and Lancaster University
• Keywords: Penalised-likelihood ; Structural-change ; Dynamic-programming ; Segmentation ; PELT

Abstract

In the multiple changepoint setting, established search methods, which involve optimising either a constrained or penalised cost function over the number and locations of changepoints using dynamic programming can be computationally expensive. Recent work on pruning the penalised optimisation problem gives, under certain conditions, an improved computational cost which is linear in the number of data points. The main challenge with this method is it requires a penalty value to be chosen, and that this choice can substantially effect the accuracy of the estimated changepoints. In this paper we present a method which avoids the need to specify a single penalty value, but instead allows one to obtain optimal segmentations of data sequences for all penalty values across a continuous range. 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.