Optimal decision trees for categorical data via integer programming

By Oktay Günlük, Jayant R. Kalagnanam, Minhan Li, Matt Menickelly, Katya Scheinberg. 2021

94 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Optimization & Training, 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 Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Mathematical optimization in classification and regression trees (2021, methodology): “In Günlük et al. (2019), an MILO formulation for combinatorial splitting rules for categorical variables is proposed, i.e., rules defined by a subset of categories that move individuals to the left child node if the rule is satisfied and to the right child node, otherwise, yielding a binary…”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “Following this work, using MIP to learn decision trees gained a lot of traction in the literature with the works of Günlük et al. (2018), Aghaei et al. (2019), and Verwer and Zhang (2019).”
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”
Optimal randomized classification trees (2021, methodology): “The approach in [47] focuses on categorical predictor variables by exploiting the resulting combinatorial structure of considering every possible subset of categories of a given predictor variable.”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, unknown): “ing (3) with respect to classification loss (Bertsimas & Dunn, 2017; Günlük et al., 2018; Verwer & Zhang, 2019; Hu et al., 2019; Aghaei et al., 2020).”
Optimization Models for Machine Learning: A Survey (2019, background): “Furthermore the formulation of [112] is restricted to binary classification and the tree topology is fixed, which lowers the required computational effort for solving the optimization problem to optimality.”
Sparsity in Optimal Randomized Classification Trees (2020, background): “As stated in the introduction of the paper, CARTs, as many other approaches that implement orthogonal cuts [4, 14, 18], are leaders in terms of local sparsity.”
Recent advances in decision trees: an updated survey (2022, methodology): “More sophisticated approaches include efficiently considering every possible threshold via specialized approaches (Lin et al. 2020), using supervised discretization algorithms (Demirović et al. 2021), or decile binning (Günlük et al. 2021).”
Learning Binary Trees via Sparse Relaxation (2020, result): “This resulted in a line of recent follow-up works (Günlük et al., 2018; Aghaei et al., 2019; Verwer & Zhang, 2019; Hu et al., 2019; Aghaei et al., 2020; Lin et al., 2020).”
Born-Again Tree Ensembles (2020, methodology): “On a similar note, G¨unl¨uk et al. (2018) presented an integer programming approach for optimal decision trees with categorical data, and Verwer & Zhang (2019) presented a binary linear program for optimal decision trees.”
A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees (2020, methodology): “The discrete nature of decisions involved in training a decision tree has inspired researchers in the field of Operations Research to encode the process using a mixed-integer programming (MIP) framework [5, 12, 19, 22, 23].”
Rule Covering for Interpretation and Boosting (2020, background): “[10] propose a binary classification tree formulation for only categorical features.”