MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees
This work addresses the need for more accurate and interpretable decision trees in machine learning, offering a novel method that provides certificates of optimality, though it is incremental in improving existing Bayesian tree methods.
The authors tackled the problem of decision tree induction by proposing MAPTree, a Bayesian approach using maximum a posteriori inference, which outperforms baselines on 16 real-world datasets with smaller trees and shows greater robustness to noise and better generalization on synthetic data.
Decision trees remain one of the most popular machine learning models today, largely due to their out-of-the-box performance and interpretability. In this work, we present a Bayesian approach to decision tree induction via maximum a posteriori inference of a posterior distribution over trees. We first demonstrate a connection between maximum a posteriori inference of decision trees and AND/OR search. Using this connection, we propose an AND/OR search algorithm, dubbed MAPTree, which is able to recover the maximum a posteriori tree. Lastly, we demonstrate the empirical performance of the maximum a posteriori tree both on synthetic data and in real world settings. On 16 real world datasets, MAPTree either outperforms baselines or demonstrates comparable performance but with much smaller trees. On a synthetic dataset, MAPTree also demonstrates greater robustness to noise and better generalization than existing approaches. Finally, MAPTree recovers the maxiumum a posteriori tree faster than existing sampling approaches and, in contrast with those algorithms, is able to provide a certificate of optimality. The code for our experiments is available at https://github.com/ThrunGroup/maptree.