Optimal dyadic decision trees

Gilles Blanchard, Christin Schäfer, Yves Rozenholc, Klaus-Robert MüllerMachine Learning 2007 · OpenReview

Abstract

We introduce a new algorithm building an optimal dyadic decision tree (ODT). The method combines guaranteed performance in the learning theoretical sense and optimal search from the algorithmic point of view. Furthermore it inherits the explanatory power of tree approaches, while improving performance over classical approaches such as CART/C4.5, as shown on experiments on artificial and benchmark data.

Introduction

Decision trees are a cornerstone of interpretable machine learning, favored for their transparency and ease of visualization. However, traditional algorithms like CART and C4.5 rely on greedy, top-down splitting strategies. While computationally efficient, these local heuristics often lead to suboptimal global structures. This paper introduces Optimal Dyadic Decision Trees (ODTs), a framework that achieves global optimality within a structured search space, providing both rigorous theoretical guarantees and high predictive performance without sacrificing interpretability.

Methodology: Global Search via Dyadic Constraints

The primary challenge in building globally optimal trees is the combinatorial explosion of possible partitions. ODT addresses this through three key innovations:

1. Dyadic Partitions

To make the search space manageable, the algorithm restricts splits to dyadic midpoints along any feature axis. While this constraint might seem limiting compared to the continuous split points used in CART, it allows the feature space to be represented as a hierarchy of cells.

An illustrative example of a dyadic partition. The optimal partition can include empty cells to maintain the required dyadic structure.

2. Bottom-Up Dynamic Programming

Rather than splitting nodes greedily from the top down, ODT uses dynamic programming to build the tree from the bottom up. It identifies optimal sub-trees for smaller cells and recursively combines them to minimize a penalized loss function:

$$Loss + \gamma \times |Leaves|$$

where the penalty term $\gamma$ controls the trade-off between model complexity and empirical fit.

3. Dictionary-Based Optimization

To handle high-dimensional spaces, the algorithm employs a dictionary-based search that tracks only non-empty cells (those containing at least one data point). This optimization makes global search feasible for datasets with a moderate number of features (typically up to 18).

Theoretical Foundations and Adaptivity

A significant contribution of this work is the proof that ODTs satisfy oracle inequalities. This theoretical framework ensures that the algorithm automatically balances approximation error (fitting the data) and estimation error (model complexity). Notably, ODTs exhibit adaptivity to anisotropy—they naturally allocate more splits along dimensions where the target function varies rapidly, creating elongated cells that efficiently capture the underlying structure.

Experimental Evaluation

The ODT algorithm was tested against standard benchmarks and synthetic challenges designed to stress-test its robustness.

ODT demonstrates versatility across various challenges: multi-class classification (left), handling unbalanced priors (middle), and adapting to anisotropic boundaries (right).

Benchmark Performance

On six classic UCI datasets (e.g., Breast Cancer, Diabetes, Titanic), ODT consistently matched or outperformed C4.5. By using cross-validation to tune the penalty parameter $\gamma$, the model achieves a stable balance between simplicity and accuracy.

Robustness to Noise

In experiments involving "checkerboard" patterns with added nuisance dimensions (pure noise), ODT proved exceptionally resilient. While the performance of Support Vector Machines (SVMs) often degraded significantly in the presence of irrelevant features, the global optimization in ODT allowed it to ignore noisy dimensions entirely, maintaining high classification accuracy.

Conclusion

Optimal Dyadic Decision Trees represent a powerful middle ground in machine learning. They provide the rigorous performance guarantees typically reserved for complex "black-box" models while maintaining the clear, actionable insights of a single decision tree. While currently limited by the curse of dimensionality to problems with fewer than 20 features, ODTs offer a robust, theoretically sound alternative to greedy tree induction for many real-world applications.

Summary updated

Abstract

We introduce a new algorithm building an optimal dyadic decision tree (ODT). The method combines guaranteed performance in the learning theoretical sense and optimal search from the algorithmic point of view. Furthermore it inherits the explanatory power of tree approaches, while improving performance over classical approaches such as CART/C4.5, as shown on experiments on artificial and benchmark data.
BibTeX
@article{blanchard2007optimal,
  author = {Gilles Blanchard and Christin Schäfer and Yves Rozenholc and Klaus-Robert Müller},
  title = {{Optimal dyadic decision trees}},
  journal = {Machine Learning},
  year = {2007},
  url = {https://openreview.net/forum?id=SlqMBWd1bv},
}
Figure