Learning Accurate Decision Trees with Bandit Feedback via Quantized
Gradient Descent
- URL: http://arxiv.org/abs/2102.07567v1
- Date: Mon, 15 Feb 2021 14:10:07 GMT
- Title: Learning Accurate Decision Trees with Bandit Feedback via Quantized
Gradient Descent
- Authors: Ajaykrishna Karthikeyan, Naman Jain, Nagarajan Natarajan, Prateek Jain
- Abstract summary: Decision trees provide a rich family of highly non-linear but efficient models.
But learning trees is a challenging problem due to their highly discrete and non-differentiable decision boundaries.
We propose a reformulation of the tree learning problem that provides better conditioned gradients.
- Score: 18.7724096545556
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision trees provide a rich family of highly non-linear but efficient
models, due to which they continue to be the go-to family of predictive models
by practitioners across domains. But learning trees is a challenging problem
due to their highly discrete and non-differentiable decision boundaries. The
state-of-the-art techniques use greedy methods that exploit the discrete tree
structure but are tailored to specific problem settings (say, categorical vs
real-valued predictions). In this work, we propose a reformulation of the tree
learning problem that provides better conditioned gradients, and leverages
successful deep network learning techniques like overparameterization and
straight-through estimators. Our reformulation admits an efficient and {\em
accurate} gradient-based algorithm that allows us to deploy our solution in
disparate tree learning settings like supervised batch learning and online
bandit feedback based learning.
Using extensive validation on standard benchmarks, we observe that in the
supervised learning setting, our general method is competitive to, and in some
cases more accurate than, existing methods that are designed {\em specifically}
for the supervised settings. In contrast, for bandit settings, where most of
the existing techniques are not applicable, our models are still accurate and
significantly outperform the applicable state-of-the-art methods.
Related papers
- Optimizing Interpretable Decision Tree Policies for Reinforcement Learning [10.68128849363198]
Decision trees have gained increased attention in supervised learning for their inherent interpretability.
This paper considers the problem of optimizing interpretable decision tree policies to replace neural networks in reinforcement learning settings.
arXiv Detail & Related papers (2024-08-21T14:04:00Z) - Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning [53.241569810013836]
We propose a new framework based on large language models (LLMs) and decision Tree reasoning (OCTree)
Our key idea is to leverage LLMs' reasoning capabilities to find good feature generation rules without manually specifying the search space.
Our empirical results demonstrate that this simple framework consistently enhances the performance of various prediction models.
arXiv Detail & Related papers (2024-06-12T08:31:34Z) - Learning accurate and interpretable decision trees [27.203303726977616]
We develop approaches to design decision tree learning algorithms given repeated access to data from the same domain.
We study the sample complexity of tuning prior parameters in Bayesian decision tree learning, and extend our results to decision tree regression.
We also study the interpretability of the learned decision trees and introduce a data-driven approach for optimizing the explainability versus accuracy trade-off using decision trees.
arXiv Detail & Related papers (2024-05-24T20:10:10Z) - Blending gradient boosted trees and neural networks for point and
probabilistic forecasting of hierarchical time series [0.0]
We describe a blending methodology of machine learning models that belong to gradient boosted trees and neural networks families.
These principles were successfully applied in the recent M5 Competition on both Accuracy and Uncertainty tracks.
arXiv Detail & Related papers (2023-10-19T09:42:02Z) - Optimal Decision Diagrams for Classification [68.72078059880018]
We study the training of optimal decision diagrams from a mathematical programming perspective.
We introduce a novel mixed-integer linear programming model for training.
We show how this model can be easily extended for fairness, parsimony, and stability notions.
arXiv Detail & Related papers (2022-05-28T18:31:23Z) - Automated Decision-based Adversarial Attacks [48.01183253407982]
We consider the practical and challenging decision-based black-box adversarial setting.
Under this setting, the attacker can only acquire the final classification labels by querying the target model.
We propose to automatically discover decision-based adversarial attack algorithms.
arXiv Detail & Related papers (2021-05-09T13:15:10Z) - An Approach to Evaluating Learning Algorithms for Decision Trees [3.7798600249187295]
Low or unknown learning ability algorithms does not permit us to trust the produced software models.
We propose a novel oracle-centered approach to evaluate (the learning ability of) learning algorithms for decision trees.
arXiv Detail & Related papers (2020-10-26T15:36:59Z) - Rectified Decision Trees: Exploring the Landscape of Interpretable and
Effective Machine Learning [66.01622034708319]
We propose a knowledge distillation based decision trees extension, dubbed rectified decision trees (ReDT)
We extend the splitting criteria and the ending condition of the standard decision trees, which allows training with soft labels.
We then train the ReDT based on the soft label distilled from a well-trained teacher model through a novel jackknife-based method.
arXiv Detail & Related papers (2020-08-21T10:45:25Z) - 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) - Learning to Stop While Learning to Predict [85.7136203122784]
Many algorithm-inspired deep models are restricted to a fixed-depth'' for all inputs.
Similar to algorithms, the optimal depth of a deep architecture may be different for different input instances.
In this paper, we tackle this varying depth problem using a steerable architecture.
We show that the learned deep model along with the stopping policy improves the performances on a diverse set of tasks.
arXiv Detail & Related papers (2020-06-09T07:22:01Z)
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.