Efficient Locally Weighted Polynomial Regression Predictions (1997)
Andrew Moore Jeff Schneider Kan Deng
Tags
Efficient Statistical Algorithms, Kd-trees and Ball-trees, Locally Weighted Learning, Memory-based Learning
Abstract
Locally weighted polynomial regression (LWPR) is a popular instance-based algorithm for learning continuous non-linear mappings. For more than two or three inputs and for more than a few thousand datapoints the computational expense of predictions is daunting. We discuss drawbacks with previous approaches to dealing with this problem, and present a new algorithm based on a multiresolution search of a quicklyconstructible augmented kd-tree. Without needing to rebuild the tree, we can make fast predictions with arbitrary local weighting functions, arbitrary kernel widths and arbitrary queries. The paper begins with a new, faster, algorithm for exact LWPR predictions. Next we introduce an approximation that achieves up to a two-ordersof -magnitude speedup with negligible accuracy losses. Increasing a certain approximation parameter achieves greater speedups still, but with a correspondingly larger accuracy degradation. This is nevertheless useful during operations such as the early stages of model selection and locating optima of a fitted surface. We also show how the approximations can permit real-time query-specific optimization of the kernal width. We conclude with a brief discussion of potential extensions for tractable instance-based learning on datasets that are too large to fit in a computer's main memory.
Full text
Download (application/pdf, 277.6 kB)
Approximate BibTeX Entry
@inproceedings{moore-efficientlocally,
Year = {1997},
Pages = {236-244},
Publisher = {Morgan Kaufmann},
Address = {340 Pine Street, 6th Fl., San Francisco, CA 94104},
Booktitle = {Proceedings of the Fourteenth International Conference on Machine Learning},
Editor = {D. Fisher},
Author = {Andrew Moore Jeff Schneider Kan Deng},
Title = {Efficient Locally Weighted Polynomial Regression Predictions}
}