Using Errors to Create Piecewise Learnable Partitions

Abstract

In this paper we describe an algorithm which exploits the error distribution generated by a learning algorithm in order to break up the domain which is being approximated into piecewise learnable partitions. Traditionally, the error distribution has been neglected in favor of a lump error measure such as RMS. By doing this, however, we lose a lot of important information. The error distribution tells us where the algorithm is doing badly, and if there exists a "ridge" of errors, also tells us how to partition the space so that one part of the space will not interfere with the learning of another. The algorithm builds a variable arity k-d tree whose leaves contain the partitions. Using this tree, new points can be predicted using the correct partition by traversing the tree. We instantiate this algorithm using memory based learners and cross-validation. 1 Motivation Traditionally, the use of error in learning algorithms has been limited to improving the learner (through gradient descen...