TL;DR
Quant-BnB is a novel branch-and-bound (BnB) algorithm designed to find globally optimal decision trees for both classification and regression tasks. By leveraging a clever quantile-based pruning strategy, it handles continuous features directly and achieves orders-of-magnitude speedups over existing state-of-the-art optimization methods.
The Challenge of Optimal Decision Trees
Decision trees are a staple of interpretable machine learning. However, the standard way we build them—using greedy algorithms like CART—does not guarantee the "best" or most optimal tree. These heuristics make local, short-sighted splits that can lead to suboptimal predictive performance.
While researchers have developed "optimal" methods using Mixed Integer Programming (MIP) or Dynamic Programming (DP), these approaches face two major hurdles:
- Scalability: They often struggle with datasets larger than a few thousand observations.
- Feature Constraints: Most current optimal algorithms only work with binary features. To handle continuous data, users must "binarize" it, which either loses information (if too few bins are used) or creates a massive number of features that slows the algorithm to a crawl.
The authors of Quant-BnB aim to bridge this gap by creating a method that is both globally optimal and natively supports continuous features at scale for both regression and classification.
The Quant-BnB Approach
The core of the paper is Quant-BnB, a discrete optimization method based on the Branch-and-Bound framework. The "Quant" refers to quantiles.
Instead of an exhaustive search over every possible split point for every feature—which is computationally explosive—the algorithm partitions the search space based on the quantiles of the feature distribution. This allows the researchers to:
- Generate Bounds: Derive mathematical upper and lower bounds for the training error within specific sub-regions of the search space.
- Prune Sub-optimal Regions: If the lower bound of a search region is higher than the best tree found so far (the upper bound), that entire region can be safely discarded without further checking.
The authors propose three different lower bounds ($W_0, W_{1,s'}, W_2$) that offer different trade-offs between computational cost and "tightness" (how close they are to the actual minimum error). They found that $W_{1,s'}$, which uses a subset of samples to estimate the loss, provides the best balance for practical use.
Key Insights and Results
The algorithm was evaluated on 27 datasets from the UCI Machine Learning Repository, spanning 16 classification tasks and 11 regression tasks. These datasets vary significantly in size (from hundreds to hundreds of thousands of observations), providing a robust test for the algorithm's scalability.
Continuous is Better than Binary: The paper demonstrates that tailored approaches for continuous features are far more efficient than converting everything to binary. Binarization creates a "curse of dimensionality" that chokes traditional MIP and DP solvers.
Dramatic Speedups: Quant-BnB shows dramatic performance gains over existing optimal methods like BinOCT, MurTree, and DL8.5.
- For depth-2 trees, Quant-BnB often finds the optimal solution in a few seconds, whereas competing methods might take minutes, hours, or run out of memory (OoM). On the
bankdataset, it was over 29,000 times faster than BinOCT. - It successfully handled the
skindataset (~196k observations), while many other optimal methods failed. - Even as the problem becomes much harder at depth 3, Quant-BnB outperformed competitors on 13 out of 16 classification datasets.
Limitations and Future Work
While Quant-BnB is a major step forward, it has its limits:
- Tree Depth: The algorithm is currently optimized for "shallow" trees (depth 2 or 3). As depth increases to 4 or more, the computational cost grows significantly, making it less practical for very deep architectures.
- Axis-Aligned Splits: Like most standard decision trees, it only considers splits on a single feature at a time (axis-aligned). It does not currently handle "oblique" splits (linear combinations of features).
Future work could involve extending these quantile-based bounds to deeper trees or integrating them into ensemble methods like Random Forests or Boosting to combine global optimality with high-depth predictive power.
Summary updated