Standard binary classification trees, such as CART, typically split data using axis-aligned hyperplanes. While computationally efficient, these splits are often too restrictive for high-dimensional data where features are correlated. To approximate a diagonal boundary, an axis-aligned tree must "staircase" its way through the feature space, requiring many more splits and resulting in overly complex trees.
The alternative is to allow unrestricted orientations (linear combinations of features). However, searching the continuous space for the optimal orientation is computationally expensive, prone to local minima, and highly susceptible to overfitting due to the model's excessive degrees of freedom.
This paper introduces the "pole-pair" method for decision trees: a "Goldilocks" approach that provides more flexibility than axis-aligned splits but is more robust against overfitting than general hyperplanes, particularly when training data is scarce.
The Pole-Pair Method
The core idea of the pole-pair method is to generate candidate splits based on the geometry of the data itself, rather than searching an infinite space of arbitrary angles.
- Candidate Generation: For any two data points (the "poles"), there is a unique hyperplane that is orthogonal to the line joining them and perfectly bisects that line.
- Selection: The algorithm restricts its search to hyperplanes defined by pairs of points—specifically, pairs belonging to different classes.
- Efficiency: To decide which side of the split a new point $C$ falls on, the model simply compares its distance to pole $A$ and pole $B$. If $dist(C, A) < dist(C, B)$, it belongs to one side; otherwise, it belongs to the other.
- Complexity: While evaluating a general hyperplane requires $O(k)$ operations (where $k$ is the number of dimensions), the pole-pair method can route a point in constant time $O(1)$ if pairwise distances are precomputed.
- Regularization: Using the Minimum Description Length (MDL) framework, the authors argue that because there are only $N(N-1)/2$ possible pole-pair splits, it takes fewer "bits" to describe a split than a general hyperplane. This inherent constraint acts as a powerful regularizer against overfitting.
The remainder of the tree-building process—using Gini impurity for splitting, weakest-link pruning, and 10-fold cross-validation—follows standard CART methodology to ensure a fair comparison.
Experimental Setup
The study evaluated the method across 12 datasets: 11 from the UCI Machine Learning Repository (including Iris, Thyroid, Breast Cancer, and Glass) and one synthetic dataset ("waves" from the original CART book).
To test robustness, the authors evaluated two scenarios:
- Large Train: 2/3 of the data used for training.
- Small Train: 1/3 of the data used for training.
Key Results and Insights
By letting the data points themselves define the potential boundaries, the model naturally adapts to the distribution of the classes without needing a complex optimization routine. Restricting the search space to bisectors of points from different classes prevents the model from finding "lucky" but meaningless orientations that perfectly separate a small training set but fail on unseen data.
In both small and large training divisions, the pole-pair method achieved lower error rates than standard axis-aligned or linear CART on the majority of datasets.
Crucially, the advantage was most pronounced when training sets were small. For example, on the Thyroid (TR) dataset with a small training set, the relative error rate dropped from 36.6% (axis-aligned CART) to 14.6% (pole-pair). Using McNemar tests, the authors demonstrated that the pole-pair method was significantly better than at least one standard method in most tasks.
Limitations and Future Directions
While highly effective, the method does have limitations:
- Precomputation Cost: The method requires $O(kN^2)$ operations to compute all pairwise distances initially. While trivial compared to the tree-building savings for the tested datasets, this could become a bottleneck for extremely large datasets ($N$).
- Class Membership Reliance: The heuristic relies heavily on class labels being available and meaningful to select sensible poles.
Interestingly, the authors suggest that this underlying philosophy—selecting from a fixed set of sensible, data-driven candidates rather than searching a continuous space—could be applied to choosing weights in neural networks. This insight serves as an early precursor to ideas like Extreme Learning Machines or Random Vector Functional Link networks.
Summary updated