A Comprehensive Approach to Universal Piecewise Nonlinear Regression Based on Trees
This provides a generic and efficient solution for adaptive nonlinear regression problems, though it appears incremental as an enhancement to existing tree-based methods.
The paper tackles adaptive nonlinear regression by introducing tree-based piecewise linear regression algorithms that achieve significantly improved performance with guaranteed upper bounds, achieving the performance of the best linear mixture of a doubly exponential number of partitions with only polynomial computational complexity.
In this paper, we investigate adaptive nonlinear regression and introduce tree based piecewise linear regression algorithms that are highly efficient and provide significantly improved performance with guaranteed upper bounds in an individual sequence manner. We use a tree notion in order to partition the space of regressors in a nested structure. The introduced algorithms adapt not only their regression functions but also the complete tree structure while achieving the performance of the "best" linear mixture of a doubly exponential number of partitions, with a computational complexity only polynomial in the number of nodes of the tree. While constructing these algorithms, we also avoid using any artificial "weighting" of models (with highly data dependent parameters) and, instead, directly minimize the final regression error, which is the ultimate performance goal. The introduced methods are generic such that they can readily incorporate different tree construction methods such as random trees in their framework and can use different regressor or partitioning functions as demonstrated in the paper.