Efficient Non-greedy Optimization of Decision Trees

By Mohammad Norouzi, Maxwell D. Collins, Matthew Johnson, David J. Fleet, Pushmeet Kohli. 2015

115 citations recorded by the source corpus.

Decision trees and randomized forests are widely used in computer vision and machine learning. Standard algorithms for decision tree induction optimize the split functions one node at a time according to some splitting criteria. This greedy procedure often leads to suboptimal trees. In this paper, we present an algorithm for optimizing the split functions at all levels of the tree jointly with the leaf parameters, based on a global objective. We show that the problem of finding optimal linear-combination (oblique) splits for decision trees is related to structured prediction with latent variables, and we formulate a convex-concave upper bound on the tree's empirical loss. Computing the gradient of the proposed surrogate objective with respect to each training exemplar is O(d2), where d is the tree depth, and thus training deep trees is feasible. The use of stochastic gradient descent for optimization enables effective training with large datasets. Experiments on several classification benchmarks demonstrate that the resulting non-greedy decision trees outperform greedy decision tree baselines.

Subfields: Artificial Intelligence, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

Citations in the corpus

Evasion and Hardening of Tree Ensemble Classifiers (2015, background): “We however note that oblique trees are seldom used in ensemble classifiers, partially because of their relatively high construction cost and complexity (Norouzi et al., 2015).”
Distilling a Neural Network Into a Soft Decision Tree (2017, methodology): “Other decision trees trained with gradient descent have been applied to this dataset [Norouzi et al., 2015] but were only able to achieve a maximum test accuracy of 76.50% at the equivalent depth of 8 and 77.45% at a depth of 20.”
Mathematical optimization in classification and regression trees (2021, methodology): “In Norouzi et al. (2015), and given the challenge of optimizing the empirical loss of the tree model, a convex–concave upper bound is optimized instead, using Stochastic Gradient Descent.”
Neural Prototype Trees for Interpretable Fine-grained Image Recognition (2020, methodology): “Such greedy algorithms however could lead to suboptimal trees [40], and are only applied to simple classification problems such as MNIST.”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, background): “( Norouzi et al. 2015) link the decision tree optimization problem with the problem of structured prediction with latent variables, and use stochastic gradient descent to optimize an upper bound on the empirical loss of the tree’s predictions.”
Learning customized and optimized lists of rules with mathematical programming (2018, background): “[51] creates a smooth surrogate from a fixed tree structure to optimize for the splits, whereas Verwer and Zhang [69] create an integer programming formulation for learning a full decision tree with a fixed depth that minimizes error rate, where each split involves one binary feature decision, and b”
Deep Neural Decision Trees (2018, background): “Some recent work explores alternative approaches to training decision trees which aim to achieve better performance with less myopic optimization, for example with latent variable structured prediction (Norouzi et al., 2015), or training an RNN splitting controller using reinforcement learning (Xion”
Optimal Generalized Decision Trees via Integer Programming (2016, methodology): “More recent work [15] has employed a stochastic gradient method to minimize a continuous upper bound on misclassification error made by a deep decision tree.”
Optimal randomized classification trees (2021, methodology): “A method for nongreedy learning of oblique trees is developed in [44], in which a convex-concave upper bound on the tree’s empirical loss is optimized using Stochastic Gradient Descent, enabling effective training with larger data sets.”
Optimal trees for prediction and prescription (2018, background): “Nevertheless, there have been many efforts previously to develop effective ways of constructing optimal univariate decision trees using a variety of heuristic methods for growing the tree in one step, including linear optimization [7], continuous optimization [8], dynamic programming [37, 99], genet”
Constructing classification trees using column generation (2018, methodology): “Other optimization techniques used in the literature to find decision trees are integer linear programming (shortly ILP), dynamic programming (Payne and Meisel 1977), and stochastic gradient descent based methods (Norouzi et al. 2015).”
Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization (2017, background): “[14] linked the decision tree optimization problem with the problem of structured prediction with latent variables.”
Optimal classification trees (2017, background): “1989; Payne and Meisel 1977), genetic algorithms (Son 1998), and more recently, optimizing an upper bound on the tree error using stochastic gradient descent (Norouzi et al. 2015).”
Sparsity in Optimal Randomized Classification Trees (2020, background): “Optimal classification trees have been grown with both orthogonal [4, 14, 18] and oblique cuts [3, 4, 6, 29, 37, 38].”
Optimal decision trees for categorical data via integer programming (2021, methodology): “More recent work [15] has employed a stochastic gradient method to minimize a continuous upper bound on misclassification error made by a deep decision tree.”
End-to-End Learning of Decision Trees and Forests (2019, methodology): “The red solidlines show the result of our proposed algorithm, the dashed lines represent results reported by Norouzi et al. (2015b).”
Recent advances in decision trees: an updated survey (2022, methodology): “There are exceptions to the soft splits solution.”
Column generation based heuristic for learning classification trees (2020, methodology): “Other optimization techniques used in the literature to find decision trees are integer linear programming (shortly ILP), dynamic programming [30], and stochastic gradient descent based methods [29].”
Learning fuzzy decision trees using integer programming (2018, background): “Previous work [8], [9], [10] and more recently [11], [12] has already considered such an approach for building crisp decision trees.”