×

Adaptively refined dynamic program for linear spline regression. (English) Zbl 1305.90403

Summary: The linear spline regression problem is to determine a piecewise linear function for estimating a set of given points while minimizing a given measure of misfit or error. This is a classical problem in computational statistics and operations research; dynamic programming was proposed as a solution technique more than 40 years ago by R. Bellman and R. Roth [ J. Am. Stat. Assoc. 64, 1079–1084 (1969; Zbl 1302.90239)]. The algorithm requires a discretization of the solution space to define a grid of candidate breakpoints. This paper proposes an adaptive refinement scheme for the grid of candidate breakpoints in order to allow the dynamic programming method to scale for larger instances of the problem. We evaluate the quality of solutions found on small instances compared with optimal solutions determined by a novel integer programming formulation of the problem. We also consider a generalization of the linear spline regression problem to fit multiple curves that share breakpoint horizontal coordinates, and we extend our method to solve the generalized problem. Computational experiments verify that our nonuniform grid construction schemes are useful for computing high-quality solutions for both the single-curve and two-curve linear spline regression problem.

MSC:

90C39 Dynamic programming
62J05 Linear regression; mixed models
90C11 Mixed integer programming

Citations:

Zbl 1302.90239

Software:

CMARS; UCI-ml
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aronov, B., Asanov, T., Katoh, N., Mehlhorn, K.: Polyline fitting of planar points under min-sum criteria. Int. J. Comput. Geom. Appl. 16(2&3), 97-116 (2006) · Zbl 1098.65011
[2] Bache, K., Lichman, M.: UCI machine learning repository. School of Information and Computer Sciences, University of California, Irvine (2013). http://archive.ics.uci.edu/ml · Zbl 1254.65020
[3] Bai, J., Perron, P.: Computation and analysis of multiple structural change models. J. Appl. Econom. 18, 1-22 (2003) · Zbl 0343.62058
[4] Bellman, R., Roth, R.: Curve fitting by segmented straight lines. J. Am. Stat. Assoc. 64, 1079-1084 (1969) · Zbl 1302.90239
[5] Ertel, J.E., Fowlkes, E.B.: Some algorithms for linear spline and piecewise multiple linear regression. J. Am. Stat. Assoc. 71(355), 640-648 (1976) · Zbl 0343.62058
[6] Friedman, J.H.: Multivariate adaptive regression splines. Ann. Stat. 19(1), 1-141 (1991) · Zbl 0765.62064
[7] Guthery, S.B.: Partition regression. J. Am. Stat. Assoc. 348, 945-947 (1974) · Zbl 0296.62059
[8] Hannah, L.A., Dunson, D.B.: Multivariate convex regression with adaptive partitioning. J. Mach. Learn. Res. 14, 3261-3294 (2013) · Zbl 1318.62225
[9] Kehagias, A., Nidelkou, E., Petridis, V.: A dynamic programming segmentation procedure for hydrological and environmental time series. Stoch. Environ. Res. Risk Assess. 20(1), 77-94 (2005) · Zbl 1096.62084
[10] Toriello, A., Vielma, J.P.: Fitting piecewise linear continuous functions. Eur. J. Oper. Res. 219(1), 89-95 (2012) · Zbl 1244.90166
[11] Weber, G.-W., Batmaz, I., Köksal, G., Taylan, P., Yelikaya-Özkurt, F.: CMARS: a new contribution to nonparametric regression with multivariate adaptive regression splines supported by continuous optimization. Inverse Probl. Sci. Eng. 20(3), 371-400 (2012) · Zbl 1254.65020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.