autonlab.org

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}
}

Copyright 2010, Carnegie Mellon University, Auton Lab. All Rights Reserved.