dtControl uses decision trees to represent controllers efficiently and explainably.
problem Representing controllers concisely and explainably.
method dtControl uses decision tree learning algorithms to represent controllers. Novel techniques for determinizing controllers are introduced.
result Novel techniques for determinizing controllers during decision tree construction are extremely efficient, yielding small decision trees.
Meta-learning interpretable decision trees with synthetic data.
problem Lack of efficient, scalable methods for generating synthetic data for decision tree meta-learning.
method Synthetic generation of near-optimal decision trees using the MetaTree transformer architecture.
result Meta-learning of decision trees achieves performance comparable to real-world data or optimal decision trees, with significant computational cost reduction.
Paper introduces algorithms for private decision tree learning.
problem Private decision tree learning in distributed settings.
method Proposes DP-TopDown, NoisyCounts, and LocalRNM.
result First utility guarantees for private decision tree learning.
Boosting meta-trees improve decision tree performance.
problem Overfitting in decision trees.
method Boosting approach to construct multiple meta-trees.
result Ensembles of meta-trees prevent overfitting.
Enhanced ODT with Feature Concatenation boosts learning efficiency.
problem Insufficient learning efficiency of ODT due to linear projections not being transmitted to child nodes.
method Feature Concatenation ( exttt{FC-ODT}) to transmit linear projections along decision paths.
result Experiments show exttt{FC-ODT} outperforms state-of-the-art decision trees with a limited tree depth.
Decision trees are ubiquitous in machine learning for their ease of use and interpretability. Yet, these models are not typically employed in reinforcement learning as they cannot be updated online via stochastic gradient descent. We overcome this limitation by allowing for a gradient update over the entire tree that i…
This paper improves Bayesian decision tree learning using HMC.
problem Bayesian decision tree learning is challenging due to a large parameter space.
method Develops and compares HMC-based algorithms for exploring Bayesian decision tree posteriors.
result HMC-based methods outperform existing methods in predictive accuracy and tree complexity.
Algorithm learns decision trees from noisy data.
problem Learning stochastic decision trees from corrupted samples.
method Quasipolynomial-time algorithm for adversarial noise.
result Returns a hypothesis with error within 2η+ε of optimal. While deep reinforcement learning has successfully solved many challenging control tasks, its real-world applicability has been limited by the inability to ensure the safety of learned policies. We propose an approach to verifiable reinforcement learning by training decision tree policies, which can represent complex p…
Proposes a simple neural network model similar to gradient boosted decision trees.
problem Building a neural network equivalent to gradient boosted decision trees.
method Converts an ensemble of decision trees to a neural network, relaxes properties, and trains a simple neural network model.
result The proposed Hammock model achieves similar performance to gradient boosted decision trees.
Trinary decision tree improves handling of missing data in machine learning.
problem Improving accuracy in decision tree algorithms when dealing with missing data.
method Introduces Trinary decision tree, which does not assume missing values contain information about the response.
result Trinary decision tree outperforms other algorithms in Missing Completely at Random settings, especially when data is only missing out-of-sample.
Treant creates evasion-resistant decision trees.
problem Evasion attacks on decision tree ensembles.
method Treant minimizes evasion-aware loss function, using robust splitting and attack invariance.
result Treant generates accurate, nearly evasion-insensitive decision trees.
New techniques optimize decision trees for interpretable machine learning.
problem Optimizing decision trees for interpretable machine learning.
method General framework for decision tree optimization addressing imbalanced data and continuous variables.
result Proves optimal decision trees for various objectives.
Evolutionary algorithms improve decision tree ensembles.
problem Improving predictive performance of decision trees.
method Real-valued vector representation of decision trees, evolutionary algorithms (Differential evolution, Evolution strategies).
result Proposed methods outperform classical decision tree induction algorithms.
Rectified decision trees improve machine learning interpretability and effectiveness.
problem Combining interpretability and effectiveness in machine learning models.
method Knowledge distillation and modified decision tree splitting criteria.
result Soft labels improve model performance and reduce model size.
Study explores loss design for decision trees to improve robustness against noisy labels.
problem Improving decision tree robustness to noisy labels.
method Investigated loss correction and symmetric losses, found ineffective.
result Other loss design directions need exploration for robust decision trees.
Optimal decision trees learned via dynamic programming and search.
problem Finding the best classification trees that are both accurate and compact.
method Dynamic programming and search techniques.
result Our algorithm learns optimal classification trees significantly faster and scales better than existing methods.
Decision trees can be biased towards minority class, contrary to belief.
problem Bias in decision trees towards minority class in imbalanced datasets.
method Critical evaluation of past literature, specific conditions analysis, tree-fitting adjustments, and post-hoc calibration methods.
result Decision trees can be biased towards minority class under specific conditions, not always towards majority.
Decision tree learning heuristics fail even in smoothed analysis for complex targets.
problem Greedy decision tree learning heuristics fail for complex target functions in the smoothed analysis model.
method Construct counterexamples and analyze the behavior of heuristics in the smoothed setting and agnostic setting.
result Greedy decision tree learning heuristics can build trees of exponential depth before achieving high accuracy for certain complex target functions.
Decision trees improve performance in various fields.
problem Improving performance in machine learning and data mining.
method Introduce tree-based models and training techniques.
result Highlight probabilistic characteristics and practical benefits.
Conventional decision trees have a number of favorable properties, including interpretability, a small computational footprint and the ability to learn from little training data. However, they lack a key quality that has helped fuel the deep learning revolution: that of being end-to-end trainable, and to learn from scr…
Neural models can realize decision trees with parameter sharing and improved performance.
problem Training and optimizing oblique decision trees.
method Locally constant networks based on ReLU gradients, parameter sharing, and neural tools.
result Locally constant networks can implicitly model oblique decision trees with fewer neurons.
A new decision tree variant improves linear model performance.
problem Improving decision tree performance on non-linear data.
method Extremely random tree with non-linear data transformation and linear observer.
result Outperforms linear models on benchmark dataset.
New method learns binary decision trees efficiently.
problem Learning binary decision trees for data partitioning.
method Argmin differentiation for discrete and continuous parameters.
result Produces competitive binary trees with fast training.
Transform ANNs into interpretable decision trees.
problem Lack of interpretability in ANNs.
method Developed two MDT algorithms: EC-DT and Extended C-Net.
result Extended C-Net generates the most compact and effective trees.
Paper proposes a probabilistic method to handle missing data in decision trees.
problem Handling missing data in decision trees.
method At deployment time, use density estimators to compute expected predictions. At learning time, fine-tune tree parameters to minimize expected prediction loss.
result Effective compared to baselines in experiments.
This work presents an approach to automatically induction for non-greedy decision trees constructed from neural network architecture. This construction can be used to transfer weights when growing or pruning a decision tree, allowing non-greedy decision tree algorithms to automatically learn and adapt to the ideal arch…
Decision tree classifiers are a widely used tool in data stream mining. The use of confidence intervals to estimate the gain associated with each split leads to very effective methods, like the popular Hoeffding tree algorithm. From a statistical viewpoint, the analysis of decision tree classifiers in a streaming setti…
Decision trees are an extremely popular machine learning technique. Unfortunately, overfitting in decision trees still remains an open issue that sometimes prevents achieving good performance. In this work, we present a novel approach for the construction of decision trees that avoids the overfitting by design, without…
ODTLearn learns optimal decision trees for predictive and prescriptive tasks.
problem Learning optimal decision trees for high-stakes predictive and prescriptive tasks.
method Mixed-integer optimization framework and object-oriented design.
result Implementation of optimal decision trees for various tasks.
A novel gradient-based method optimizes decision trees for complex tasks.
problem Training decision trees with arbitrary differentiable loss functions.
method Gradient-based optimization using first and second derivatives of loss functions.
result Improves accuracy and flexibility in decision tree optimization.
We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree---"Extremely Fast Decision Tree", a minor modification to the MOA implementat…
New algorithm learns decision trees faster than before.
problem Properly learning decision trees in polynomial time.
method Membership query algorithm with nO(loglogn) time complexity. result Achieved faster learning time for decision trees.
ID3 generates near-optimal decision trees for DNFs under product distributions.
problem Understanding the optimality of decision trees generated by ID3.
method Introducing a new metric (MIC) to measure the optimality of ID3-generated trees and comparing it with other algorithms.
result The TopDown variant of ID3 is near-optimal in learning read-once DNFs under product distributions, while another variant is not.
Proposes BehavDT model for context-aware user behavior prediction.
problem Building a context-aware predictive model based on diverse user behavioral activities.
method Introduces BehavDT, a behavioral decision tree that considers user behavior-oriented generalization.
result BehavDT model outperforms traditional machine learning approaches in predicting user diverse behaviors considering multi-dimensional contexts.
Max-Cut decision tree improves classification accuracy and reduces computation time.
problem Improving decision tree accuracy and efficiency for complex classification tasks.
method Alternative splitting metric (max cut) and PCA-based feature selection at each node.
result 49% improvement in accuracy with 94% reduction in CPU time on CIFAR-100 data.
VisRuler simplifies decision extraction from bagged and boosted trees.
problem Complexity and lack of interpretability in ensemble models.
method Visual analytics tool for selecting robust models, important features, and essential decisions.
result Users successfully extracted and explained decisions from ensemble models.
Decision Machines embeds decision trees into vector spaces for improved optimization.
problem Overfitting and difficulty in finding optimal decision tree structure.
method Embedding Boolean tests into a binary vector space and representing tree structure as matrices.
result Optimized decision trees with enhanced predictive power.
A new randomized tree classifier outperforms traditional CARTs.
problem Traditional greedy CARTs are slow and inaccurate.
method Optimal decision trees using continuous optimization.
result Randomized tree classifier outperforms traditional CARTs.
Kauri is a novel unsupervised binary tree for clustering that outperforms existing methods.
problem Learning a tree end-to-end for clustering without labels is an open challenge.
method Greedy maximization of the kernel KMeans objective without centroids.
result Kauri often outperforms existing unsupervised clustering methods, especially with non-linear kernels.
OLBoost improves online decision tree performance without increasing memory or time costs.
problem Improving predictive performance in online decision trees without high memory or time costs.
method OLBoost applies boosting to small regions of the instances space within online decision tree algorithms.
result OLBoost can significantly improve online learning decision tree performance without increasing tree size.
Recently proposed budding tree is a decision tree algorithm in which every node is part internal node and part leaf. This allows representing every decision tree in a continuous parameter space, and therefore a budding tree can be jointly trained with backpropagation, like a neural network. Even though this continuity …
Decision trees improve decision-making by optimizing predictions of unknown parameters.
problem Optimizing decisions based on predicted unknown parameters.
method SPO Trees (SPOTs) for training decision trees under the SPO loss function.
result SPOTs provide higher quality decisions and significantly lower model complexity compared to other machine learning approaches.
Decision tree learning is a popular approach for classification and regression in machine learning and statistics, and Bayesian formulations---which introduce a prior distribution over decision trees, and formulate learning as posterior inference given data---have been shown to produce competitive performance. Unlike c…
A new method for decision tree selection in recommendation systems.
problem Feature-based selection of a single tree from an ensemble for dynamic interpretation.
method A multi-armed contextual bandit recommendation framework that trains a system on top of Random Forests to identify the most relevant tree.
result The dynamic method outperforms an independent CART tree and is comparable to Random Forest in predictive performance.
Decision tree algorithms have been among the most popular algorithms for interpretable (transparent) machine learning since the early 1980's. The problem that has plagued decision tree algorithms since their inception is their lack of optimality, or lack of guarantees of closeness to optimality: decision tree algorithm…
FAHT improves fairness in online decision-making systems.
problem Discrimination in decision support systems due to biased data.
method FAHT is an adaptive fairness-aware decision tree classifier based on Hoeffding Tree algorithm.
result FAHT maintains fairness while maintaining moderate predictive performance in streaming environments.
Proposes regional tree regularization for interpretable deep models.
problem Lack of interpretability in deep neural networks.
method Encourages deep models to be well-approximated by separate decision trees for predefined regions of the input space.
result Regional tree regularization delivers more accurate predictions than training separate decision trees for each region, while producing simpler explanations.