Degrees-of-freedom penalized piecewise regression

Abstract

Many popular piecewise regression models rely on minimizing a cost function on the model fit with a linear penalty on the number of segments. However, this penalty does not take into account varying complexities of the model functions on the segments potentially leading to overfitting when models with varying complexities, such as polynomials of different degrees, are used. In this work, we enhance on this approach by instead using a penalty on the sum of the degrees of freedom over all segments, called degrees-of-freedom penalized piecewise regression (DofPPR). We show that the solutions of the resulting minimization problem are unique for almost all input data in a least squares setting. We develop a fast algorithm which does not only compute a minimizer but also determines an optimal hyperparameter -- in the sense of rolling cross validation with the one standard error rule -- exactly. This eliminates manual hyperparameter selection. Our method supports optional user parameters for incorporating domain knowledge. We provide an open-source Python/Rust code for the piecewise polynomial least squares case which can be extended to further models. We demonstrate the practical utility through a simulation study and by applications to real data. A constrained variant of the proposed method gives state-of-the-art results in the Turing benchmark for unsupervised changepoint detection.

29 pages (40 including supplementary), 19 figures, accepted for publication in "Information and Inference: a Journal of the IMA"

References in corpus (19)

• Optimal detection of changepoints with a linear computational cost
• Selective review of offline change point detection methods
• Wild binary segmentation for multiple change-point detection
• An Algorithm for Optimal Partitioning of Data on an Interval
• Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
• Nonparametric maximum likelihood approach to multiple change-point problems
• An Evaluation of Change Point Detection Algorithms
• Consistencies and rates of convergence of jump-penalized least squares estimators
• Jump-sparse and sparse recovery using Potts functionals
• Generalized Methods and Solvers for Noise Removal from Piecewise Constant Signals
• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Segmentation of the mean of heteroscedastic data via cross-validation
• Mumford-Shah and Potts Regularization for Manifold-Valued Data with Applications to DTI and Q-Ball Imaging
• The L1-Potts functional for robust jump-sparse reconstruction
• Random Forests for Change Point Detection
• Bayesian selection for the l2-Potts model regularization parameter: 1D piecewise constant signal denoising
• Smoothing for signals with discontinuities using higher order Mumford-Shah models
• Smoothing splines for discontinuous signals
• Adaptive Online Estimation of Piecewise Polynomial Trends