Multiresolution Instance-based Learning (1995)
Tags
Cached Sufficient Statistics, Efficient Statistical Algorithms, Kd-trees and Ball-trees, Locally Weighted Learning, Memory-based Learning
Abstract
Instance-based learning methods explicitly remember all the data that they receive. They usually have no training phase, and only at prediction time do they perform computation. Then, they take a query, serch the database for similar datapoints and build an on-line model (such as a local average or local regression) with which to predict an output value. In this paper we review the advantages of instance-based methods for autonomous systems, but we also note the ensuing cost: hopelessly slow computation as the database grows large. We present and evaluate a new way of structuring a database and a new algorithm for accessing it that maintains the advantages of instance-based learning. Earlier attempts to combat the cost of instance-based learning have sacrificed the explicit retention of all data, or been applicable only to instance-based predictions based on a small number of near neighbors or have had to re-introduce an explicit training phase in the form of an interpolative data structure. Our approach builds a multiresolution data structure to summarize the database of experiences at all resolutions of interest simultaneously. This permits us to query the database with the same flexibility as a conventional linear search, but at greatly reduced computational cost.
Full text
Download (application/pdf, 91.8 kB)
Approximate BibTeX Entry
@inproceedings{deng-multiresolution,
Year = {1995},
Pages = {1233--1239},
Publisher = {Morgan Kaufmann},
Address = {San Francisco},
Booktitle = {Proceedings of the Twelfth International Joint Conference on Artificial Intellingence},
Author = {
Kan Deng, Andrew Moore
},
Title = {Multiresolution Instance-based Learning}
}