Multi-rules mining algorithm for combinatorially exploded decision trees with modified Aitchison-Aitken function-based Bayesian optimization

• URL: http://arxiv.org/abs/2310.02633v1
• Date: Wed, 4 Oct 2023 07:55:51 GMT
• Title: Multi-rules mining algorithm for combinatorially exploded decision trees with modified Aitchison-Aitken function-based Bayesian optimization
• Authors: Yuto Omae, Masaya Mori, Yohei Kakimoto
• Abstract summary: "MAABO-MT" and "GS-MRM" algorithms that strategically construct trees with high estimation performance. Experiments are conducted using several open datasets to analyze the effectiveness of the proposed method.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decision trees offer the benefit of easy interpretation because they allow the classification of input data based on if--then rules. However, as decision trees are constructed by an algorithm that achieves clear classification with minimum necessary rules, the trees possess the drawback of extracting only minimum rules, even when various latent rules exist in data. Approaches that construct multiple trees using randomly selected feature subsets do exist. However, the number of trees that can be constructed remains at the same scale because the number of feature subsets is a combinatorial explosion. Additionally, when multiple trees are constructed, numerous rules are generated, of which several are untrustworthy and/or highly similar. Therefore, we propose "MAABO-MT" and "GS-MRM" algorithms that strategically construct trees with high estimation performance among all possible trees with small computational complexity and extract only reliable and non-similar rules, respectively. Experiments are conducted using several open datasets to analyze the effectiveness of the proposed method. The results confirm that MAABO-MT can discover reliable rules at a lower computational cost than other methods that rely on randomness. Furthermore, the proposed method is confirmed to provide deeper insights than single decision trees commonly used in previous studies. Therefore, MAABO-MT and GS-MRM can efficiently extract rules from combinatorially exploded decision trees.

Related papers

• A Unified Approach to Extract Interpretable Rules from Tree Ensembles via Integer Programming [2.1408617023874443]
  Tree ensemble methods are known for their effectiveness in supervised classification and regression tasks. Our work aims to extract an optimized list of rules from a trained tree ensemble, providing the user with a condensed, interpretable model.
  arXiv  Detail & Related papers  (2024-06-30T22:33:47Z)
• 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)
• 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)
• 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)
• Permutation Decision Trees [3.089408984959925]
  Effort-To-Compress (ETC) is a complexity measure, for the first time, as an alternative impurity measure. We conduct a performance comparison between Permutation Decision Trees and classical decision trees across various real-world datasets.
  arXiv  Detail & Related papers  (2023-06-05T06:31:14Z)
• Regularized impurity reduction: Accurate decision trees with complexity guarantees [20.170305081348328]
  We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity. The enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.
  arXiv  Detail & Related papers  (2022-08-23T13:15:19Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  adversarial attacks on tree based ensembles such as gradient boosting decision trees (DTs) and random forests (RFs) We show that our method can be thousands of times faster than the previous mixed-integer linear programming (MILP) based approach. Our code is available at https://chong-z/tree-ensemble-attack.
  arXiv  Detail & Related papers  (2020-10-22T10:59:49Z)
• 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)
• Rule Covering for Interpretation and Boosting [0.0]
  We propose two algorithms for interpretation and boosting of tree-based ensemble methods. First algorithm uses the collection of decision trees obtained from a trained random forest model. Second algorithm uses a rule generation scheme for boosting decision trees.
  arXiv  Detail & Related papers  (2020-07-13T13:42:57Z)

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.