Optimal classification trees

By Dimitris J. Bertsimas, Jack Dunn. 2017

736 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Algorithms & Complexity

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 Algorithms & Complexity

Citations in the corpus

Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making (2019, methodology): “Our work most closely relates to the work in (Bertsimas and Dunn 2017) which designs optimal classiﬁcation trees using MIP, yielding average absolute improvements in out-of-sample accuracy over the state-of-art CART algorithm (Breiman et al. 1984) in the range 1–5%.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “As will be discussed, our experiments further confirm similar empirical findings (Verwer and Zhang (2019); Bertsimas and Dunn (2017)).”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, background): “The beneﬁts of optimal decision trees were discussed in (Bertsimas and Dunn 2017).”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “The BinOCT formulation of Verwer and Zhang (2019) is obtained by aggregating constraints from the OCT formulation of Bertsimas and Dunn (2017) (using big-M constants). As a consequence, its relaxation is weaker. Thus, it suffices to argue that the proposed formulation is stronger than OCT. In the fo”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “In addition, as in (Bertsimas and Dunn 2017; Verwer and Zhang 2017), BinOCT is solved by CPLEX with warm starts learned from CART to investigate whether this helps find better solutions.”
Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches (2019, neutral): “Recently, (Bertsimas and Dunn, 2017) proposed Integer Programming for producing optimal decision trees for classification.”
Optimal Sparse Decision Trees (2019, methodology): “Example figures from the OCT paper [5] show decision trees that are clearly suboptimal.”
Learning customized and optimized lists of rules with mathematical programming (2018, methodology): “The method of Bertsimas and Dunn [8] that uses integer programming to optimize trees is similarly extremely demanding, because the full set of splits need to be optimized.”
Boolean Decision Rules via Column Generation (2018, background): “Rule sets stand in contrast to decision lists [44, 35, 49, 3, 34, 53], where rules are ordered in an IF-ELSE sequence, and decision trees [11, 43, 6], where they are organized into a tree structure.”
Optimal Generalized Decision Trees via Integer Programming (2016, methodology): “In fact, in the computational results of [3], the depth is often fixed.”
Optimal randomized classification trees (2021, methodology): “This is the approach followed in recent papers such as [46, 47, 48, 49], which consider mixed-integer formulations.”
Efficient Policy Learning (2017, background): “, 1984) or optimal trees (Bertsimas and Dunn, 2017), and we refer to the above papers for further results on optimizing this type of objectives.”
On sparse ensemble methods: An application to short-term predictions of the evolution of COVID-19 (2021, neutral): “…such as Support Vector Machines ( Carrizosa & Romero Morales, 2013; Vapnik, 1995 ), Random Forests ( Breiman, 2001 ), Optimal Trees ( Bertsimas & Dunn, 2017; Blanquero, Carrizosa, Molero-Río, & Romero Morales, 2021; Carrizosa, Molero-Río, & Romero Morales, 2021 ), Deep Learning ( Gambella,…”
The Price of Interpretability (2019, methodology): “For example, by adapting the mixed-integer optimization formulation from Bertsimas and Dunn [3], we can compute the price of interpretability for decision trees of bounded depth by writing the following mixed-integer formulation of the inner minimization problem in (11):”
Learning optimal decision trees using constraint programming (2020, methodology): “Constraints can be added, as long as they are linear; this includes constraints on fairness [Aghaei et al., 2019] or on the number of examples in the leafs [Bertsimas and Dunn, 2017].”