Part of Advances in Neural Information Processing Systems 3 (NIPS 1990)
Stephen Omohundro
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 ann mapping learning task. Applica(cid:173) 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(cid:173) 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(cid:173) 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 flexible modification. We provide empirical data comparing bumptrees with radial basis functions in section 2. A bumptree is used to provide efficient access to a collection of functions on a Euclidean space of interest. It is a complete binary tree in which a leaf corresponds to each function of interest There are also functions associated with each internal node and the defining constraint is that each interior node's function must be everwhere larger than each of the