Finding Multivariate Splits in Decision Trees Using Function Optimization

George H. JohnAAAI 1994

Introduction

Traditional decision tree algorithms, such as ID3 and C4.5, rely on univariate splits—partitioning data based on a single feature at a time. While computationally efficient and highly interpretable, this approach often fails to capture complex, diagonal relationships between variables, leading to excessively large "staircase" trees that generalize poorly. Multivariate (or oblique) decision trees address this by using linear combinations of features for splitting. However, finding the optimal hyperplane is historically difficult because standard splitting criteria like entropy are discrete and non-differentiable, necessitating complex heuristic searches.

This paper introduces the Soft Entropy Hyperplane (SEH) algorithm, which transforms the discrete search for a splitting hyperplane into a continuous optimization problem. By employing a differentiable "soft entropy" objective, the algorithm uses gradient descent to efficiently find robust, high-performance splits.

The Soft Entropy Hyperplane (SEH) Approach

The core innovation of this work is the replacement of traditional "hard" entropy with a continuous approximation. In a standard split, a data point's contribution to the entropy changes abruptly as it crosses the decision boundary. In contrast, "soft" entropy provides a smooth gradient, indicating not just whether a point is correctly classified, but how "comfortably" it sits on its side of the boundary.

Figure 1: Illustration of the "softness" principle. While multiple hyperplanes (lines) might achieve zero error under a "hard" entropy criterion, soft entropy favors the split that maximizes the margin between classes.

As illustrated in Figure 1, many hyperplanes can perfectly separate two classes. Standard entropy treats all these valid splits as equal. The SEH objective, however, is minimized when the hyperplane is positioned to maximize the "soft" separation, a principle closely related to the large-margin concept later popularized by Support Vector Machines (SVMs). Because this objective is differentiable, the algorithm can utilize standard gradient descent to optimize hyperplane weights at each node, bypassing the need for the randomized or greedy search heuristics used in other multivariate methods like OC1.

Regularization via Iterative Re-filtering

To maintain generalizability and prevent overfitting, the SEH framework incorporates a novel pruning technique called iterative re-filtering. This process acts as a form of regularization during the tree induction phase, identifying and removing nodes that may be capturing noise rather than underlying patterns. This ensures that the resulting multivariate trees remain parsimonious without sacrificing predictive power.

Experimental Results

The SEH algorithm was benchmarked against standard univariate (C4.5) and multivariate (OC1) algorithms across four classic datasets: the Congressional Vote records and the synthetic Monks logic problems.

Figure 3: Performance comparison of SEH variants against OC1 and C4.5. Accuracy is shown with the number of tree nodes in parentheses.

As shown in the results table (Figure 3), SEH consistently outperformed its counterparts in both accuracy and model size:

  • Monks2: This dataset represents a complex logical structure where SEH achieved a perfect 100% accuracy using only 9 nodes. In comparison, C4.5 required 39 nodes and only reached 75.9% accuracy, demonstrating the power of oblique splits in simplifying complex decision boundaries.
  • Vote: SEH produced a highly compact tree of just 3 nodes with 98.5% accuracy, significantly smaller and more accurate than the trees generated by C4.5.

Discussion and Limitations

While SEH offers significant improvements in accuracy and tree compression, it is not without trade-offs. On the Monks3 dataset, the iterative re-filtering mechanism proved overly aggressive, pruning critical data points as noise and resulting in lower accuracy than C4.5. Furthermore, while the overall tree structure is simpler, the individual nodes are more complex to interpret as they involve linear combinations of multiple features.

Conclusion

The SEH algorithm demonstrates that treating decision tree induction as a continuous optimization problem can yield significantly more efficient and accurate models. By leveraging differentiability, SEH finds superior multivariate splits that univariate methods cannot replicate, paving the way for more robust and compact machine learning models.

Summary updated

BibTeX
@inproceedings{john1994finding,
  author = {George H. John},
  title = {{Finding Multivariate Splits in Decision Trees Using Function Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure