Weighted Oblique Decision Trees

Bin-Bin Yang, Song-Qing Shen, Wei GaoAAAI 2019 · OpenReview

Abstract

Decision trees have attracted much attention during the past decades. Previous decision trees include axis-parallel and oblique decision trees; both of them try to find the best splits via exhaustive search or heuristic algorithms in each iteration. Oblique decision trees generally simplify tree structure and take better performance, but are always accompanied with higher computation, as well as the initialization with the best axis-parallel splits. This work presents the Weighted Oblique Decision Tree (WODT) based on continuous optimization with random initialization. We consider different weights of each instance for child nodes at all internal nodes, and then obtain a split by optimizing the continuous and differentiable objective function of weighted information entropy. Extensive experiments show the effectiveness of the proposed algorithm.

Introduction

Decision trees are fundamental tools in machine learning, prized for their interpretability and efficiency. Traditionally, these models are "axis-parallel," meaning they partition data using a single feature at each node (e.g., "Is feature $X_i > c$?"). While effective, axis-parallel trees can become excessively deep and complex when the underlying data distribution requires diagonal or "oblique" boundaries.

Oblique Decision Trees (ODTs) address this by using linear combinations of features to create slanted decision hyperplanes. Despite their potential for smaller and more accurate trees, ODTs have historically been difficult to train. The standard "information gain" metric is discrete and non-differentiable, forcing researchers to rely on computationally expensive heuristic searches or "warm starts" using axis-parallel initializations. This paper introduces the Weighted Oblique Decision Tree (WODT), a novel approach that leverages continuous optimization to bypass these limitations.

Methodology

The core innovation of WODT is the transformation of the discrete tree-building process into a continuous, differentiable optimization problem.

Soft Splitting and Weighted Entropy

Instead of a "hard" binary split during the training phase, WODT employs a sigmoid function, $\sigma(-\theta^T x)$, to assign a probabilistic weight to each data point. This weight represents the likelihood of a point belonging to the left or right child node. By redefining the splitting criterion (information entropy) using these weights, the authors create a smooth objective function.

Optimization and Initialization

Because the objective function is differentiable, the L-BFGS algorithm—a high-performance quasi-Newton method—can be used to find the optimal split parameters ($\theta$). This continuous landscape is significantly more robust than the discrete search spaces of previous ODTs. Consequently, WODT can be initialized with random vectors, eliminating the dependency on pre-calculated axis-parallel splits that plagues other oblique methods.

Experimental Results

The researchers evaluated WODT against several state-of-the-art methods across 20 benchmark datasets from the UCI and LIBSVM repositories, including low-dimensional sets like Iris and high-dimensional sets like MNIST (780 features) and Protein (357 features).

Computational Efficiency

WODT demonstrates remarkable scalability. As shown in Figure 1, WODT (represented by the white bars) is significantly faster than competing methods, particularly as the dimensionality of the data increases. On datasets with more than 200 features, WODT achieved speedups of up to 100x compared to traditional oblique tree algorithms like OC1 or CO2.

Training time comparison across 20 benchmark datasets. WODT (white bar) demonstrates significant speedups, particularly on high-dimensional datasets like MNIST and USPS.

Accuracy and Generalization

WODT not only trains faster but also produces more accurate and compact models. A key finding is that WODT reaches peak accuracy at much shallower depths (typically between 4 and 8) compared to other methods. This suggests that the continuous optimization approach finds more meaningful decision boundaries that generalize better without the need for excessive tree depth.

Training accuracy vs. tree depth for four high-dimensional datasets. WODT (blue diamonds) consistently achieves higher accuracy at shallower depths compared to other oblique tree methods.

Conclusion and Future Directions

WODT represents a significant step forward in decision tree research by proving that continuous optimization can effectively train oblique trees from random initializations. While the resulting oblique splits can be more complex to interpret in very high dimensions, the reduction in tree depth and the massive gains in training efficiency make WODT a compelling alternative to standard axis-parallel trees.

Future work will explore the integration of $L_1$ regularization to encourage "sparse" splits, which would improve interpretability by selecting only the most relevant features for each hyperplane. Additionally, the authors suggest that WODT could serve as a powerful base learner for ensemble methods like Random Forests or Gradient Boosting.

Summary updated

Abstract

Decision trees have attracted much attention during the past decades. Previous decision trees include axis-parallel and oblique decision trees; both of them try to find the best splits via exhaustive search or heuristic algorithms in each iteration. Oblique decision trees generally simplify tree structure and take better performance, but are always accompanied with higher computation, as well as the initialization with the best axis-parallel splits. This work presents the Weighted Oblique Decision Tree (WODT) based on continuous optimization with random initialization. We consider different weights of each instance for child nodes at all internal nodes, and then obtain a split by optimizing the continuous and differentiable objective function of weighted information entropy. Extensive experiments show the effectiveness of the proposed algorithm.
BibTeX
@inproceedings{yang2019weighted,
  author = {Bin-Bin Yang and Song-Qing Shen and Wei Gao},
  title = {{Weighted Oblique Decision Trees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=udMwAb8Hq1jd},
}
Figure