Iterative Construction of Sparse Polynomial Approximations
Terence D. Sanger, Richard S. Sutton, Christopher J. Matheus · 1991
We present an iterative algorithm for nonlinear regression based on con-struction of sparse polynomials. Polynomials are built sequentially from lower to higher order. Selection of new terms is accomplished using a novel look-ahead approach that predicts whether a variable contributes to the remaining error. The algorithm is based on the tree-growing heuristic in LMS Trees which we have extended to approximation of arbitrary poly-nomials of the input features. In addition, we provide a new theoretical justification for this heuristic approach. The algorithm is shown to dis-cover a known polynomial from samples, and to make accurate estimates of pixel values in an image-processing task. 1