Highly efficient nonlinear regression for big data with lexicographical splitting. Issue 3 (March 2017)

• Record Type: Journal Article
• Authors: Mohaghegh Neyshabouri, Mohammadreza; Demir, Oguzhan; Delibalta, Ibrahim; Kozat, Suleyman
• Is Part Of: Signal, image and video processing. Volume 11:Issue 3(2017)
• Page Start: 391
• Page End: 398
• Publication Date: 2017-03
• Subjects: Online learning -- Nonlinear regression -- Piecewise linear -- Lexicographical splitting; Signal processing -- Digital techniques -- Periodicals; Image processing -- Digital techniques -- Periodicals; Digital video -- Periodicals; 621.3822
• DOI: 10.1007/s11760-016-0972-8
• Languages: English
• ISSNs: 1863-1703

Abstract

Abstract This paper considers the problem of online piecewise linear regression for big data applications. We introduce an algorithm, which sequentially achieves the performance of the best piecewise linear (affine) model with optimal partition of the space of the regressor vectors in an individual sequence manner. To this end, our algorithm constructs a class of $$2^D$$ 2 D sequential piecewise linear models over a set of partitions of the regressor space and efficiently combines them in the mixture-of-experts setting. We show that the algorithm is highly efficient with computational complexity of only $$O(mD^2)$$ O ( m D 2 ), wherem is the dimension of the regressor vectors. This efficient computational complexity is achieved by efficiently representing all of the $$2^D$$ 2 D models using a "lexicographical splitting graph." We analyze the performance of our algorithm without any statistical assumptions, i.e., our results are guaranteed to hold. Furthermore, we demonstrate the effectiveness of our algorithm over the well-known data sets in the machine learning literature with computational complexity fraction of the state of the art.