TL;DR
This paper introduces "Basis-Function Trees" as a unifying framework for various local variable selection methods used in function approximation. It proposes a new algorithm, the "LMS Tree," which recursively builds these trees using an LMS learning rule, offering a fast and adaptive approach to handling high-dimensional data.
What Problem Does This Paper Address?
Approximating functions in high-dimensional spaces is a significant challenge due to the "curse of dimensionality" – the exponential increase in data required to adequately "fill" the space. This often leads to insufficient data or prohibitive computational costs. Local variable selection methods offer a solution by approximating functions using only a subset of input dimensions relevant to specific regions of the input space. However, existing methods like CART, ID3, MARS, and others, while effective, have different underlying structures and learning mechanisms, making it difficult to compare and generalize them. This paper aims to bridge this gap by presenting a unified framework and a novel, flexible algorithm.
Methods
The core contribution is the concept of Basis-Function Trees. This framework views function approximation as a tree structure where each node represents a computation based on separable basis functions. These basis functions are products of one-dimensional functions applied to individual input variables. The paper generalizes existing methods by allowing these one-dimensional basis functions to be arbitrary (e.g., step functions, splines, Fourier basis, Gaussians).
The paper then introduces the LMS Tree algorithm. This algorithm builds the tree recursively, one input dimension at a time. It uses the Widrow-Hoff LMS (Least Mean Squares) learning rule to learn the weights of the basis functions. Crucially, the LMS rule also provides a measure of weight change variance, which is used to determine where to grow new subtrees. This recursive approach allows the algorithm to adapt to nonstationary input distributions without needing to store the entire dataset. The paper also discusses tree pruning as a necessary step for managing the complexity of larger trees.
Datasets
Not discussed in the paper. The paper focuses on the theoretical framework and algorithmic development, using hypothetical examples and discussing general performance characteristics rather than specific empirical evaluations on named datasets.
Key Insights and Ideas
- Unifying Framework: Basis-Function Trees provide a powerful conceptual lens to understand and compare a wide range of existing local variable selection algorithms, revealing their common underlying structure.
- Arbitrary Basis Functions: The flexibility to use any one-dimensional basis function (not just step functions or splines) opens up possibilities for tailoring approximations to specific types of functions (e.g., using Fourier basis for bandlimited functions).
- Recursive LMS for Tree Growth: Using the LMS learning rule not only for weight updates but also for guiding tree growth (via weight change variance) is an elegant and efficient mechanism for adaptive tree construction.
- Decoupling of Layers: Basis-Function Trees differ from traditional multi-layer neural networks in that computations at one layer determine weights at the next, rather than providing input. This means input data only traverses a single level.
Key Results
The paper primarily presents a theoretical framework and a new algorithm. While specific quantitative results are not detailed, the paper highlights the advantages of the LMS Tree:
- Speed and Simplicity: The LMS Tree algorithm is described as "extremely fast and easy to program," with a 49-input network trained to 20 subtrees on 40,000 data samples in approximately 30 minutes on a Sun-4 computer.
- Adaptability: The recursive LMS rule allows trees to adapt to slowly-varying nonstationary environments.
- Memory Efficiency: The algorithm does not require storing the entire dataset at nodes, making it memory efficient.
Limitations and Future Work
- Tree Pruning Importance: The paper acknowledges that for the proposed additive approximation method, which can generate larger trees, tree pruning becomes very important to manage complexity.
- Generalization of Existing Methods: While the framework explains many algorithms, the paper notes that some aspects of methods like MARS (data-dependent spline locations) and GMDH (non-tree-like growth) are not perfectly captured by the tree structure.
- Future Work: The paper implicitly suggests exploring various combinations of basis functions and learning rules within the Basis-Function Tree framework for different application domains. The focus on speed and adaptability also points towards applications where real-time learning and handling of changing data are crucial.
Summary updated