Born-Again Tree Ensembles

• URL: http://arxiv.org/abs/2003.11132v3
• Date: Thu, 27 Aug 2020 15:52:50 GMT
• Title: Born-Again Tree Ensembles
• Authors: Thibaut Vidal, Toni Pacheco, Maximilian Schiffer
• Abstract summary: Tree ensembles offer a good prediction quality in various domains, but the concurrent use of multiple trees reduces the interpretability of the ensemble. We study the process of constructing a single decision tree of minimum size that reproduces the exact same behavior as a given tree ensemble in its entire feature space. This algorithm generates optimal born-again trees for many datasets of practical interest.
• Score: 9.307453801175177
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The use of machine learning algorithms in finance, medicine, and criminal justice can deeply impact human lives. As a consequence, research into interpretable machine learning has rapidly grown in an attempt to better control and fix possible sources of mistakes and biases. Tree ensembles offer a good prediction quality in various domains, but the concurrent use of multiple trees reduces the interpretability of the ensemble. Against this background, we study born-again tree ensembles, i.e., the process of constructing a single decision tree of minimum size that reproduces the exact same behavior as a given tree ensemble in its entire feature space. To find such a tree, we develop a dynamic-programming based algorithm that exploits sophisticated pruning and bounding rules to reduce the number of recursive calls. This algorithm generates optimal born-again trees for many datasets of practical interest, leading to classifiers which are typically simpler and more interpretable without any other form of compromise.

Related papers

• Terminating Differentiable Tree Experts [77.2443883991608]
  We propose a neuro-symbolic Differentiable Tree Machine that learns tree operations using a combination of transformers and Representation Products. We first remove a series of different transformer layers that are used in every step by introducing a mixture of experts. We additionally propose a new termination algorithm to provide the model the power to choose how many steps to make automatically.
  arXiv  Detail & Related papers  (2024-07-02T08:45:38Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• 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)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Bound is a convenient approach to solving optimization tasks in the form of Mixed Linear Programs. The efficiency of the solver depends on the branchning used to select a variable for splitting. We propose a reinforcement learning method that can efficiently learn the branching.
  arXiv  Detail & Related papers  (2023-06-09T14:01:26Z)
• New Linear-time Algorithm for SubTree Kernel Computation based on Root-Weighted Tree Automata [0.0]
  We propose a new linear time algorithm based on the concept of weighted tree automata for SubTree kernel computation. Key idea behind the proposed algorithm is to replace DAG reduction and nodes sorting steps. Our approach has three major advantages: it is output-sensitive, it is free sensitive from the tree types (ordered trees versus unordered trees), and it is well adapted to any incremental tree kernel based learning methods.
  arXiv  Detail & Related papers  (2023-02-02T13:37:48Z)
• Linear TreeShap [16.246232737115218]
  Decision trees are well-known due to their ease of interpretability. To improve accuracy, we need to grow deep trees or ensembles of trees. This paper presents a more efficient and straightforward algorithm: Linear TreeShap.
  arXiv  Detail & Related papers  (2022-09-16T23:17:15Z)
• 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)
• Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
  We learn binary decision trees that partition data for some downstream task. We do so by relaxing a mixed-integer program for the discrete parameters. We derive customized algorithms to efficiently compute the forward and backward passes.
  arXiv  Detail & Related papers  (2020-10-09T15:11:28Z)
• 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.