Bumptrees for efficient function, constraint, and classification learning

A new class of data structures called “bumptrees ” is described. These structures are useful for efficiently implementing a number of neural network related operations. An empirical comparison with radial basis functions is presented on a robot arm mapping learning task. Applica-tions to density estimation, classification, and constraint representation and learning are also outlined. 1 WHAT IS A BUMPTREE? A bumptree is a new geometric data structure which is useful for efficiently learning, rep-resenting, and evaluating geometric relationships in a variety of contexts. They are a natural generalization of several hierarchical geometric data structures including oct-trees, k-d trees, balltrees and boxtrees. They are useful for many geometric learning tasks including approximating functions, constraint surfaces, classification regions, and probability densi-ties from samples. In the function approximation case, the approach is related to radial basis function neural networks, but supports faster construction, faster access, and more flexibl