×

Piecewise affine regression via recursive multiple least squares and multicategory discrimination. (English) Zbl 1372.93221

Summary: In nonlinear regression choosing an adequate model structure is often a challenging problem. While simple models (such as linear functions) may not be able to capture the underlying relationship among the variables, over-parametrized models described by a large set of nonlinear basis functions tend to overfit the training data, leading to poor generalization on unseen data. PieceWise-Affine (PWA) models can describe nonlinear and possible discontinuous relationships while maintaining simple local affine regressor-to-output mappings, with extreme flexibility when the polyhedral partitioning of the regressor space is learned from data rather than fixed a-priori. In this paper, we propose a novel and numerically very efficient two-stage approach for PWA regression based on a combined use of (i) recursive multi-model least-squares techniques for clustering and fitting linear functions to data, and (ii) linear multi-category discrimination, either offline (batch) via a Newton-like algorithm for computing a solution of unconstrained optimization problems with objective functions having a piecewise smooth gradient, or online (recursive) via averaged stochastic gradient descent.

MSC:

93E24 Least squares and related methods for stochastic control systems
93B12 Variable structure systems
93C10 Nonlinear systems in control theory
62J02 General nonlinear regression

Software:

HIT; MSVMpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alexander, S. T.; Ghirnikar, A. L., A method for recursive least squares filtering based upon an inverse QR decomposition, IEEE Transactions on Signal Processing, 41, 1, 20-30 (1993) · Zbl 0774.93075
[2] Bako, L.; Boukharouba, K.; Duviella, E.; Lecoeuche, S., A recursive identification algorithm for switched linear/affine models, Nonlinear Analysis. Hybrid Systems, 5, 2, 242-253 (2011) · Zbl 1225.93112
[5] Bemporad, A.; Garulli, A.; Paoletti, S.; Vicino, A., A bounded-error approach to piecewise affine system identification, IEEE Transactions on Automatic Control, 50, 10, 1567-1580 (2005) · Zbl 1365.93100
[6] Bennett, K. P.; Mangasarian, O. L., Multicategory discrimination via linear programming, Optimization Methods & Software, 3, 27-39 (1994)
[7] Bottou, L., Stochastic gradient descent tricks, (Neural Networks: Tricks of the Trade (2012), Springer), 421-436
[9] Crammer, K.; Singer, Y., On the algorithmic implementation of multiclass kernel-based vector machines, Journal of Machine Learning Research (JMLR), 2, 265-292 (2002) · Zbl 1037.68110
[11] Ferrari-Trecate, G.; Muselli, M.; Liberati, D.; Morari, M., A clustering technique for the identification of piecewise affine systems, Automatica, 39, 2, 205-217 (2003) · Zbl 1011.93508
[12] Fung, G. M.; Mangasarian, O. L., Multicategory proximal support vector machine classifiers, Machine Learning, 59, 77-97 (2005) · Zbl 1101.68758
[14] Juloski, A. L.; Weiland, S.; Heemels, W. P. M. H., A bayesian approach to identification of hybrid systems, IEEE Transactions on Automatic Control, 50, 10, 1520-1533 (2005) · Zbl 1365.93526
[15] Lauer, F., On the complexity of piecewise affine system identification, Automatica, 62, 148-153 (2015) · Zbl 1329.93052
[16] Lauer, F.; Guermeur, Y., Msvmpack: a multi-class support vector machine package, Journal of Machine Learning Research (JMLR), 12, 2269-2272 (2011) · Zbl 1280.68175
[17] Lee, Y.; Lin, Y.; Wahba, G., Multicategory support vector machines, theory, and application to the classification of microarray data and satellite radiance data, Journal of American Statistical Association, 99, 67-81 (2004) · Zbl 1089.62511
[18] Nakada, H.; Takaba, K.; Katayama, T., Identification of piecewise affine systems based on statistical clustering technique, Automatica, 41, 5, 905-913 (2005) · Zbl 1093.93007
[19] Ohlsson, H.; Ljung, L., Identification of switched linear regression models using sum-of-norms regularization, Automatica, 49, 4, 1045-1050 (2013) · Zbl 1285.93100
[20] Paoletti, S.; Juloski, A. L.; Ferrari-Trecate, G.; Vidal, R., Identification of hybrid systems a tutorial, European journal of control, 13, 2, 242-260 (2007) · Zbl 1293.93219
[21] Roll, J.; Bemporad, A.; Ljung, L., Identification of piecewise affine systems via mixed-integer programming, Automatica, 40, 1, 37-50 (2004) · Zbl 1037.93023
[23] Vapnik, V., Statistical learning theory (1998), Wiley: Wiley New York · Zbl 0935.62007
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.