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.
PILOT is a fast algorithm for linear model trees that outperforms existing methods.
problem Fitting linear model trees to large datasets efficiently and accurately.
method Greedy training with L2 boosting and model selection rule. result PILOT outperforms standard decision trees and other linear model trees on various datasets.
Decision tree learning is a popular classification technique most commonly used in machine learning applications. Recent work has shown that decision trees can be used to represent provably-correct controllers concisely. Compared to representations using lookup tables or binary decision diagrams, decision trees are sma…
This paper develops a new method to model treatment effects that are heterogeneous across different quantiles.
problem Modeling treatment effects that vary across different quantiles of the outcome distribution.
method The paper combines quantile classification with local polynomial estimation to build a decision tree and forest.
result The proposed QLPRT and QLPRF methods provide a new way to estimate and infer heterogeneous treatment effects.
Develops a new method for decision trees using categorical variable structure.
problem Lack of structure in treating categorical variables as predictors.
method Introduces a mathematical framework to represent categorical structure and generalizes decision trees to utilize this structure.
result Improves prediction accuracy on weather data using the new method.
FoLDTree improves oblique decision trees with ULDA, enhancing accuracy and feature selection.
problem Axis-orthogonal splits limit traditional decision trees' performance on oblique decision boundaries.
method Integrates ULDA into decision tree structure for efficient oblique splits, feature selection, and handling missing values.
result FoLDTree outperforms other methods in accuracy and feature selection, comparable to random forest.
We show how neural models can be used to realize piece-wise constant functions such as decision trees. The proposed architecture, which we call locally constant networks, builds on ReLU networks that are piece-wise linear and hence their associated gradients with respect to the inputs are locally constant. We formally …
Novel algorithm optimizes decision trees for nonlinear metrics.
problem Optimizing decision trees for nonlinear metrics like F1-score.
method Bi-objective optimisation approach to find optimal trees on Pareto frontier.
result The optimal tree for nonlinear metrics lies on the Pareto frontier.
Convex polytope trees expand decision trees with interpretable boundaries.
problem High accuracy often requires many nodes in decision trees, reducing interpretability.
method CPT uses logical disjunction of weighted linear decision-makers, geometrically a convex polytope.
result CPT achieves high accuracy with fewer nodes compared to existing methods.
The paper proposes a new variant of a decision tree, called an Extreme Learning Tree. It consists of an extremely random tree with non-linear data transformation, and a linear observer that provides predictions based on the leaf index where the data samples fall. The proposed method outperforms linear models on a bench…
We present a detailed analysis of the class of regression decision tree algorithms which employ a regulized piecewise-linear node-splitting criterion and have regularized linear models at the leaves. From a theoretic standpoint, based on Rademacher complexity framework, we present new high-probability upper bounds for …
DTE uses tree leaf means to embed data, balancing accuracy and speed.
problem High variance in decision tree splits and computational inefficiency of ensembles.
method DTE constructs an interpretable feature representation using leaf means of a trained tree.
result DTE strikes a balance between accuracy and computational efficiency, outperforming ensembles.
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.
Two algorithms for interpreting and boosting tree-based models using rule covering.
problem Interpreting and boosting tree-based ensemble methods.
method Mathematical programming models constructed from decision tree rules.
result Selects a few rules that closely match the accuracy of the model.
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.
We study the robustness verification problem for tree-based models, including decision trees, random forests (RFs) and gradient boosted decision trees (GBDTs). Formal robustness verification of decision tree ensembles involves finding the exact minimal adversarial perturbation or a guaranteed lower bound of it. Existin…
AGBoost uses attention weights to improve GBM for regression problems.
problem Improving gradient boosting machine for regression tasks.
method Attention-based modification of GBM with trainable attention weights.
result AGBoost achieves better performance on regression datasets.
Oblique BART improves tree-based predictions.
problem Axis-aligned decision rules in BART can be suboptimal.
method Developed an oblique version of BART using data-adaptive hyperplane partitions.
result Oblique BART outperformed axis-aligned BART and other tree methods on benchmarks.
Enhances GBDT robustness with one-hot encoding and regularization.
problem Low robustness of GBDT models against covariate perturbation.
method One-hot encoding to linear framework, risk decomposition, L1 or L2 regularization. result Regularization enhances GBDT robustness.
Decision trees perform well in complex interactions, even when interactions are not fully accounted for.
problem Interpreting complex interactions in machine learning models.
method Experiments on datasets and two methods for robust GLMs.
result Tree depth compensates for model misspecification, enhancing performance in complex scenarios.
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.
Linear algebra algorithms are used widely in a variety of domains, e.g machine learning, numerical physics and video games graphics. For all these applications, loop-level parallelism is required to achieve high performance. However, finding the optimal way to schedule the workload between threads is a non-trivial prob…
We learn sensor trees from training data to minimize sensor acquisition costs during test time. Our system adaptively selects sensors at each stage if necessary to make a confident classification. We pose the problem as empirical risk minimization over the choice of trees and node decision rules. We decompose the probl…
New framework detects model weaknesses in decision tree ensembles.
problem Detecting feature sensitivity in decision tree ensembles.
method Data-aware sensitivity framework using MILP and SMT.
result Realistic and interpretable examples of model weaknesses.
Sparse oblique decision tree improves security rules for renewable power systems.
problem Identifying secure operating conditions in power systems with high renewable energy.
method Sparse weighted oblique decision tree to learn and embed linear security rules.
result The method significantly increases secure states and reduces solution time.
Enhances explainability of AI models without sacrificing accuracy.
problem Lack of interpretability in black-box models like Deep Neural Networks and Gradient Boosting.
method Co-supervised Local Model Synthesis (SynthTree) using Mixture of Linear Models (MLM).
result Statistical models significantly enhance explainability of AI models.
Proposes a method to speed up model selection for classification.
problem Time-consuming model selection process and lack of dataset-specific insights.
method Relaxes decision boundaries of neural decision trees to find equivalent or better models.
result Reduces the scope of exploration needed for model selection.
Despite outstanding contribution to the significant progress of Artificial Intelligence (AI), deep learning models remain mostly black boxes, which are extremely weak in explainability of the reasoning process and prediction results. Explainability is not only a gateway between AI and society but also a powerful tool t…
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.
Optimal sparse recovery with decision stumps achieves strong feature selection guarantees.
problem Sparse recovery of active features from high-dimensional data.
method Analysis of single-depth decision trees (decision stumps) for feature selection in linear regression.
result Tight sample performance guarantees for O(slogp), improving upon previous bounds. 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.
Technology and collaboration enable dramatic increases in the size of psychological and psychiatric data collections, but finding structure in these large data sets with many collected variables is challenging. Decision tree ensembles like random forests (Strobl, Malley, and Tutz, 2009) are a useful tool for finding st…
In AI research and industry, machine learning is the most widely used tool. One of the most important machine learning algorithms is Gradient Boosting Decision Tree, i.e. GBDT whose training process needs considerable computational resources and time. To shorten GBDT training time, many works tried to apply GBDT on Par…
Novel approach for creating interpretable classifiers using bilevel optimization of split-rules in NLDTs.
problem Creating highly accurate and easily interpretable classifiers for practical applications.
method Representing classifiers as assemblies of simple mathematical rules using NLDTs with evolutionary bilevel optimization.
result The approach ensures interpretability while achieving high accuracy on various classification problems.
This paper explores the use of Column Generation (CG) techniques in constructing univariate binary decision trees for classification tasks. We propose a novel Integer Linear Programming (ILP) formulation, based on root-to-leaf paths in decision trees. The model is solved via a Column Generation based heuristic. To spee…
We consider the problem of learning decision rules for prediction with feature budget constraint. In particular, we are interested in pruning an ensemble of decision trees to reduce expected feature cost while maintaining high prediction accuracy for any test example. We propose a novel 0-1 integer program formulation …
In this paper we propose a synergistic melting of neural networks and decision trees (DT) we call neural decision trees (NDT). NDT is an architecture a la decision tree where each splitting node is an independent multilayer perceptron allowing oblique decision functions or arbritrary nonlinear decision function if more…
Decision trees and shallow neural networks have different geometric complexities, impacting their interpretability and accuracy.
problem The geometric simplicity of decision boundaries in decision trees conflicts with the approximation capabilities of shallow neural networks.
method Analysis of the Radon total variation (RTV) seminorm to compare geometric complexity of decision regions and neural network approximations.
result Smooth barrier scores can approximate decision regions with finite RTV, but their performance depends on the tube-mass condition near the decision boundary.
Both neural networks and decision trees are popular machine learning methods and are widely used to solve problems from diverse domains. These two classifiers are commonly used base classifiers in an ensemble framework. In this paper, we first present a new variant of oblique decision tree based on a linear classifier,…
The study analyzes when Bayesian averaging over decision trees is reliable.
problem When do Bayesian model averaging weights over decision trees provide reliable information?
method Closed-form solution for Bayesian decision trees with Catalan-exponential priors.
result Established a complete non-asymptotic theory of rational commitment thresholds.
Although adversarial examples and model robustness have been extensively studied in the context of linear models and neural networks, research on this issue in tree-based models and how to make tree-based models robust against adversarial examples is still limited. In this paper, we show that tree based models are also…
Decision forests, including Random Forests and Gradient Boosting Trees, have recently demonstrated state-of-the-art performance in a variety of machine learning settings. Decision forests are typically ensembles of axis-aligned decision trees; that is, trees that split only along feature dimensions. In contrast, many r…
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.
Improves local model explanations using GANs and Linear Model Trees.
problem Need for accurate and intuitive explanations of complex machine learning models.
method Generative Adversarial Network (GAN) for synthetic data generation and Linear Model Trees for surrogate model training.
result Significantly improved local model explanations with contextual information.
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.
The paper improves decision tree stability for health care applications.
problem Stability of decision trees in health care applications.
method Introducing a new distance metric to determine tree stability and proposing a novel training methodology.
result On average, a 4.6% decrease in predictive power yields a 38% increase in model stability.
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.
Several classification methods assume that the underlying distributions follow tree-structured graphical models. Indeed, trees capture statistical dependencies between pairs of variables, which may be crucial to attain low classification errors. The resulting classifier is linear in the log-transformed univariate and b…