Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization

By Sicco Verwer, Yingqian Zhang. 2017

71 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems, Statistical Learning Theory, Mathematical Optimization

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 Information Systems

In Statistical Learning Theory

In Mathematical Optimization

Citations in the corpus

Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making (2019, methodology): “…paper also relates to a nascent stream of research that leverages mixed-integer programming (MIP) to address ML tasks for which heuristics were traditionally employed (Bertsimas, King, and Mazumder 2015; Lou et al. 2013b; Mazumder and Radchenko 2015; Bertsimas and Dunn 2017; Verwer and Zhang 2017).”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “It has been observed that a more accurate representation of the data oﬀers better generalisation on unseen data (Bertsimas and Dunn (2017); Verwer and Zhang (2017, 2019)).”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, background): “Regression trees can be obtained via minor modiﬁcations of the formulation, see e.g., Verwer and Zhang (2017).”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “The performance of our methods on the other two datasets is consistently higher than DTIPs, although we ran the instances much shorter than theirs (10 instead of 30 minutes).”
Learning customized and optimized lists of rules with mathematical programming (2018, background): “Several recent works (Norouzi et al, 2015; Verwer and Zhang, 2017; Bertsimas and Dunn, 2017) aim at optimization of decision trees, but not for the sake of interpretability.”
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.”
Optimal Decision Trees for Nonlinear Metrics (2020, background): “Recently, Bertsimas and Dunn (2017) and Verwer and Zhang (2017) proposed novel mixed-integer programming formulations.”
Complete Search for Feature Selection in Decision Trees (2019, background): “Bertsimas and Dunn (2017) and Menickelly et al. (2016); Verwer and Zhang (2017) formulate tree induction as a mixed-integer optimization problem and as an integer programming problem respectively.”
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].”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “It has been observed that a more accurate representation of the data oﬀers better generalisation on unseen data (Bertsimas and Dunn (2017); Verwer and Zhang (2017, 2019)).”
Learning fuzzy decision trees using integer programming (2018, unknown): “The benefit of this approach is that one can take advantage of powerful MIP solvers and this is also reflected in the results in [11], [12].”
SAT-based Decision Tree Learning for Large Data Sets (2021, background): “Given a class c , for all e i ; e j 2 E such that C ( e i ) = c; C ( e j ) 6 = c , we add the clauses : g i;j;w , where w = d (cid:0) d ( c ) + d min is the allowed depth in regards to the weight of c .”
Column generation based heuristic for learning classification trees (2020, methodology): “[36], Bertsimas and Dunn [3], Verwer and Zhang [35], and Dash et al.”
Recent advances in decision trees: an updated survey (2022, methodology): “…can be easily formulated as linear constraints, the majority of MP approaches assume that all attributes are numerical, relying on transformations such as one-hot encoding to handle categorical data (Bertsimas and Dunn 2017; Verwer and Zhang 2017, 2019; Firat et al. 2020; Blanquero et al. 2021).”
Optimization Models for Machine Learning: A Survey (2019, background): “More generally, splits that span multiple variables can also be considered at each node as presented in [37, 205, 206].”
Constructing classification trees using column generation (2018, methodology): “One of the advantages of using mathematical optimization models to learn decision trees is that one can easily incorporate different optimization objectives and constraints into the learning process, as initially demonstrated by Verwer and Zhang (2017).”
On Explaining Decision Trees (2020, unknown): “[2,68,25,32,1,7,57,24,26,70,67,58,44,30,17,5,73,35,4,78,69,10,34,72,71,36,46,11,45].”