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.
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.
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