Multiresolution Instance-Based Learning - Robotics Institute Carnegie Mellon University

Multiresolution Instance-Based Learning

Andrew Moore, Jeff Schneider, and Kan Deng
Conference Paper, Proceedings of 14th International Joint Conference on Artificial Intelligence (IJCAI '95), pp. 1233 - 1239, August, 1995

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 search the database for similar datapoints and build an on-line local 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 ot instance-based learning. Earlier attempts to combat the cost of instancebased learning have sacrificed the explicit retention of all data or been applicable only to instancebased predictions based on a small number of near neighbors, or have had to reintroduce 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.

BibTeX

@conference{Moore-1995-16170,
author = {Andrew Moore and Jeff Schneider and Kan Deng},
title = {Multiresolution Instance-Based Learning},
booktitle = {Proceedings of 14th International Joint Conference on Artificial Intelligence (IJCAI '95)},
year = {1995},
month = {August},
pages = {1233 - 1239},
}