Learning a Decision Tree Algorithm with Transformers
- URL: http://arxiv.org/abs/2402.03774v1
- Date: Tue, 6 Feb 2024 07:40:53 GMT
- Title: Learning a Decision Tree Algorithm with Transformers
- Authors: Yufan Zhuang, Liyuan Liu, Chandan Singh, Jingbo Shang, Jianfeng Gao
- Abstract summary: We introduce MetaTree, which trains a transformer-based model on filtered outputs from classical algorithms to produce strong decision trees for classification.
We then train MetaTree to produce the trees that achieve strong generalization performance.
- Score: 80.49817544396379
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decision trees are renowned for their interpretability capability to achieve
high predictive performance, especially on tabular data. Traditionally, they
are constructed through recursive algorithms, where they partition the data at
every node in a tree. However, identifying the best partition is challenging,
as decision trees optimized for local segments may not bring global
generalization. To address this, we introduce MetaTree, which trains a
transformer-based model on filtered outputs from classical algorithms to
produce strong decision trees for classification. Specifically, we fit both
greedy decision trees and optimized decision trees on a large number of
datasets. We then train MetaTree to produce the trees that achieve strong
generalization performance. This training enables MetaTree to not only emulate
these algorithms, but also to intelligently adapt its strategy according to the
context, thereby achieving superior generalization performance.
Related papers
- Online Learning of Decision Trees with Thompson Sampling [12.403737756721467]
Decision Trees are prominent prediction models for interpretable Machine Learning.
We devise a new Monte Carlo Tree Search algorithm, able to produce optimal Decision Trees in an online setting.
arXiv Detail & Related papers (2024-04-09T15:53:02Z) - 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) - MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees [2.421336072915701]
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.
arXiv Detail & Related papers (2023-09-26T23:43:37Z) - 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) - Tree in Tree: from Decision Trees to Decision Graphs [2.2336243882030025]
Tree in Tree decision graph (TnT) is a framework that extends the conventional decision tree to a more generic and powerful directed acyclic graph.
Our proposed model is a novel, more efficient, and accurate alternative to the widely-used decision trees.
arXiv Detail & Related papers (2021-10-01T13:20:05Z) - 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) - Convex Polytope Trees [57.56078843831244]
convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary.
We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
arXiv Detail & Related papers (2020-10-21T19:38:57Z) - 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) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
We present techniques that produce optimal decision trees over a variety of objectives.
We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
arXiv Detail & Related papers (2020-06-15T19:00:11Z)
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.