An Incremental Method for Finding Multivariate Splits for Decision Trees

Paul E. Utgoff, Carla E. BrodleyMl 1990 · DOI

TL;DR

This paper introduces the PT2 algorithm, an incremental method for building decision trees that can use multivariate splits (tests involving multiple variables) at each node. This allows for more compact and expressive trees compared to traditional algorithms that only use univariate splits, leading to better generalization and concept representation.

What Problem Does This Paper Address?

Traditional decision tree algorithms like ID3 are limited to using univariate splits, meaning each node in the tree tests only a single variable. This limitation can lead to very large and complex trees, especially for concepts that are naturally expressed by relationships between multiple variables. For instance, a concept defined by a diagonal boundary in a 2D space cannot be represented succinctly by axis-aligned splits. This paper addresses the need for decision tree algorithms that can discover more expressive, multivariate tests at each node, thereby creating more compact and potentially better-generalizing trees. It also aims to handle ordered and unordered variables uniformly and to learn incrementally, meaning the tree can be updated as new data arrives without rebuilding from scratch.

Methods

The core of the paper is the PT2 algorithm, which incrementally builds and revises decision trees. At each decision node, PT2 searches for an optimal multivariate split using a Linear Threshold Unit (LTU). An LTU is a form of a perceptron that can learn a linear combination of input variables to define a hyperplane.

Key aspects of the PT2 method include:

  • Multivariate Splits: Instead of testing one variable, PT2 uses LTUs to test linear combinations of variables, allowing for splits with arbitrary orientations in the instance space.
  • Incremental Learning: The algorithm updates the tree as new training instances arrive, avoiding the need to retrain from scratch.
  • Uniform Variable Handling: Both ordered (numeric) and unordered (categorical) variables are encoded numerically and normalized to a common range [-0.5, 0.5]. This allows for a unified treatment of all variable types.
  • LTU Training: LTUs are trained using an absolute error correction procedure. The algorithm also maintains a "pocket vector" (P) which stores the best weight vector found so far, aiming to find a robust and accurate classifier.
  • Variable Elimination: PT2 includes a mechanism to identify and potentially remove variables that do not contribute significantly to the split, aiming for simpler and more efficient tests.
  • Split Comparison: A procedure based on Gallant's Pocket Algorithm is used to compare different LTU-based splits and select the best one, considering factors like pocket count and the number of variables used.
  • Missing Value Estimation: Missing values are handled by estimating them using the sample mean of the variable at that node.

Datasets

The paper evaluates PT2 on three standard learning tasks:

  • DNF Task: A Boolean function (ab V cde) used to illustrate the algorithm's ability to find multivariate tests.
  • Multiplexor Task: Both six-bit and three-bit versions are used. This task is known to be difficult for traditional decision trees because the "address bit" is not directly correlated with the classification.
  • Hyperthyroid Task: This task involves a mix of unordered and ordered attributes, with a significant number of missing values, testing the algorithm's robustness.

Key Insights and Ideas

  • Multivariate Splits Dramatically Improve Expressiveness: The paper strongly demonstrates that allowing multivariate splits significantly increases the expressive power of decision trees, enabling more compact representations of complex concepts.
  • LTUs as a Powerful Splitting Mechanism: Using LTUs provides a flexible way to define splits that are not constrained by axis-aligned boundaries, leading to more natural and efficient concept representations.
  • Incremental Learning is Crucial for Real-World Systems: The incremental nature of PT2 makes it suitable for applications where data arrives sequentially, avoiding costly retraining.
  • Uniform Encoding Simplifies Handling Mixed Variable Types: Encoding all variables numerically and normalizing them simplifies the algorithm's logic and allows it to treat diverse data types consistently.
  • The "Pocket" Mechanism Improves Robustness: Using a pocket vector to track the best LTU found so far helps in finding more stable and accurate classifiers, especially when instances are not linearly separable.

Key Results

  • DNF Task: PT2 found a tree with two tests and three leaves, logically equivalent to the one found by FRINGE. This is significantly more compact than the eight tests and nine leaves found by ID3.
  • Multiplexor Task: For the three-bit multiplexor, PT2 found a tree with two tests and three leaves, compared to ID3's five tests and six leaves. For the six-bit multiplexor, PT2 found a correct tree of ten tests and eleven leaves after 3,968 instances, with a total CPU time of 143 seconds.
  • Hyperthyroid Task: PT2 achieved 99.46% accuracy on the training data and 99.07% on the test data, classifying instances described by a mix of numeric and non-numeric attributes with missing values.

Limitations and Future Work

  • Costly Variable Elimination: The current mechanism for dropping variables from LTUs is computationally expensive, potentially training O(n²) LTUs at a node.
  • No Guarantee of Sequential Testing/Understandability: The algorithm does not guarantee that the resulting trees will be easily understandable or follow optimal sequential testing, as seen in the hyperthyroid task example.
  • Lack of Pruning: PT2 does not currently incorporate pruning techniques to prevent overfitting, and it can be subject to underfitting if too few unique instances are delivered to a node.
  • Limited to Two Classes: The current implementation can only discriminate between two classes.

Future work includes:

  • Developing a more efficient method for discarding variables based on weight magnitudes.
  • Extending the algorithm to handle multi-class problems, potentially by separating instances into superclasses.
  • Adding a pruning mechanism to prevent overfitting and underfitting.
  • Investigating strategies for detecting when the piecewise linear classification is performing poorly and adapting the approach (e.g., using hyperspheres or hyperellipses).

Summary updated

BibTeX
@inproceedings{utgoff1990incremental,
  author = {Paul E. Utgoff and Carla E. Brodley},
  title = {{An Incremental Method for Finding Multivariate Splits for Decision Trees}},
  booktitle = {Ml},
  year = {1990},
  doi = {10.1016/b978-1-55860-141-3.50011-0},
}
Figure