MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees

• URL: http://arxiv.org/abs/2309.15312v3
• Date: Wed, 20 Dec 2023 04:51:44 GMT
• Title: MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees
• Authors: Colin Sullivan, Mo Tiwari, Sebastian Thrun
• Abstract summary: We present a Bayesian approach to decision tree induction via maximum a posteriori inference of a posterior distribution over trees. We propose an AND/OR search algorithm, dubbed MAPTree, which is able to recover the maximum a posteriori tree.
• Score: 2.421336072915701
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Boosting-Based Sequential Meta-Tree Ensemble Construction for Improved Decision Trees [1.8749305679160366]
  A decision tree is one of the most popular approaches in machine learning fields. A meta-tree is recently proposed to solve the problem of overfitting caused by overly deepened trees. The meta-tree guarantees statistical optimality based on Bayes decision theory.
  arXiv  Detail & Related papers  (2024-02-09T13:08:21Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  We introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. We fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance.
  arXiv  Detail & Related papers  (2024-02-06T07:40:53Z)
• Bayesian Decision Trees via Tractable Priors and Probabilistic Context-Free Grammars [7.259767735431625]
  We propose a new criterion for training Bayesian Decision Trees. BCART-PCFG can efficiently sample decision trees from a posterior distribution across trees given the data. We find that trees sampled via BCART-PCFG perform comparable to or better than greedily-constructed Decision Trees.
  arXiv  Detail & Related papers  (2023-02-15T00:17:41Z)
• SoftTreeMax: Exponential Variance Reduction in Policy Gradient via Tree Search [68.66904039405871]
  We introduce SoftTreeMax, a generalization of softmax that takes planning into account. We show for the first time the role of a tree expansion policy in mitigating this variance. Our differentiable tree-based policy leverages all gradients at the tree leaves in each environment step instead of the traditional single-sample-based gradient.
  arXiv  Detail & Related papers  (2023-01-30T19:03:14Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  We introduce SoftTreeMax, the first approach that integrates tree-search into policy gradient. On Atari, SoftTreeMax demonstrates up to 5x better performance in faster run-time compared with distributed PPO.
  arXiv  Detail & Related papers  (2022-09-28T09:55:47Z)
• ForestPrune: Compact Depth-Controlled Tree Ensembles [7.538482310185135]
  We present ForestPrune, a novel framework to post-process tree ensembles by pruning depth layers from individual trees. We develop a specialized optimization algorithm to efficiently obtain high-quality solutions to problems under ForestPrune. Our experiments demonstrate that ForestPrune produces parsimonious models that outperform models extracted by existing post-processing algorithms.
  arXiv  Detail & Related papers  (2022-05-31T22:04:18Z)
• Social Interpretable Tree for Pedestrian Trajectory Prediction [75.81745697967608]
  We propose a tree-based method, termed as Social Interpretable Tree (SIT), to address this multi-modal prediction task. A path in the tree from the root to leaf represents an individual possible future trajectory. Despite the hand-crafted tree, the experimental results on ETH-UCY and Stanford Drone datasets demonstrate that our method is capable of matching or exceeding the performance of state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-26T12:18:44Z)
• Dive into Decision Trees and Forests: A Theoretical Demonstration [0.0]
  Decision trees use the strategy of "divide-and-conquer" to divide a complex problem on the dependency between input features and labels into smaller ones. Recent advances have greatly improved their performance in computational advertising, recommender system, information retrieval, etc.
  arXiv  Detail & Related papers  (2021-01-20T16:47:59Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.