Optimal Decision Trees

By TreesKristin P. Bennett, Jennifer A. BlueDepartment. 1996

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Efforts to fully optimize decision trees, solving problems related to (2), have been made since the 1990s (Bennett and Blue, 1996; Dobkin et al., 1996; Farhangfar et al., 2008; Nijssen and Fromont, 2007, 2010; Hu et al., 2019; Lin et al., 2020).”
Learning Certifiably Optimal Rule Lists (2017, background): “The optimal decision tree problem is computationally hard, though since the late 1990’s, there has been research on building optimal decision trees using optimization techniques [2, 13, 14].”
Mathematical optimization in classification and regression trees (2021, methodology): “Nevertheless, tackling the optimization of oblique cuts is already at the seminal papers of Bennett (Bennett 1992; Bennett and Blue 1996).”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “Solvers have been used from the 1990’s (Bennett, 1992; Bennett & Blue, 1996) to the present (Verwer & Zhang, 2019; Blanquero et al., 2018; Nijssen et al., 2020; Bertsi-mas & Dunn, 2017; Rudin & Ertekin, 2018; Menickelly et al., 2018; Vilas Boas et al., 2019), but these generic solvers tend to be…”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “(Bennett and Blue 1996) construct binary classification trees with fixed structure and labels.”
Optimal Sparse Decision Trees (2019, background): “Problems with greedy splitting and pruning have been known since the early 1990’s, when mathematical programming tools had started to be used for creating optimal binary-split decision trees [3, 4], in a line of work [5, 6, 16, 18] until the present [20], however, these techniques use all-purpose to”
Learning customized and optimized lists of rules with mathematical programming (2018, background): “There is a (mostly older) body ofwork on optimality in decision trees using dynamic programming [7,18,19,50].”
Scalable Bayesian Rule Lists (2016, background): “There are a series of works from the mid-1990’s on ﬁnding optimal decision trees using dynamic programming and search techniques (e.g., Bennett & Blue, 1996; Auer, Holte, & Maass, 1995; Dobkin, Fulton, Gunopulos, Kasif, & Salzberg, 1996), mainly working with only ﬁxed depth trees.”
Optimal decision trees for categorical data via integer programming (2021, methodology): “In particular, in [1], a large-scale linear optimization problem, which can be viewed as a relaxation, is solved to global optimality via a specialized tabu search method over the extreme points of the linear polytope.”
Recursive Partitioning for Personalization using Observational Data (2016, background): “In the case of classiﬁcation and regression, Bennett & Blue (1996); Bertsimas & Dunn (2016) attempt to ﬁnd globally optimal prediction trees (while the problem is NP-hard; see Hyaﬁl & Rivest, 1976).”
A Fast Way to Produce Optimal Fixed-Depth Decision Trees (2008, methodology): “The GTO system (Bennett & Blue 1996) learns a decision tree by simultaneously optimizing a set of (cid:147)disjunctive linear inequalities(cid:148) (cid:151) minimizing a nonlinear error function over a polyhedral region, whose extreme points contain the optimum solution.”
Optimal classification trees (2017, methodology): “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 (Bennett 1992), continuous optimization (Bennett and Blue 1996), dyna”
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.”
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].”
Born-Again Tree Ensembles (2020, background): “Bennett & Blue (1996) focused on building global optimal decision trees to avoid overﬁtting, while Nijssen & Fromont (2007) presented an exact algorithm to build a decision tree for speciﬁc depth, accuracy, and leaf requirements.”