Learning optimal decision trees using constraint programming

By Hélène Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, Pierre Schaus. 2020

97 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Information Systems, 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 Computational Theory and Mathematics

In Computer Networks and Communications

In Information Systems

In Algorithms & Complexity

Citations in the corpus

Optimal Decision Lists using SAT (2020, background): “There has been considerable investigation into producing the smallest possible optimal perfect decision trees (Narodytska et al. 2018; Verhaeghe et al. 2019), where the decision tree agrees perfectly with the training data, as well as producing the smallest possible sparse decision trees (Hu,…”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “…has been shown to largely outperform the other techniques based on generic optimisation modelling, such as integer programming (Verwer and Zhang (2019); Bertsimas and Dunn (2017)) and constraint programming (Verhaeghe et al. (2019)), when minimising the misclassiﬁcation score for full binary trees.”
Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost (2020, neutral): “Therefore, other methods [ Ni-jssen and Fromont, 2007; Bertsimas and Dunn, 2017; Verwer and Zhang, 2019; Verhaeghe et al. , 2019; Aglin et al. , 2020; Hu et al. , 2019 ] opt instead for optimizing accuracy (on the training set) subject to constraints on the maximum depth.”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, background): “Verhaeghe et al. (2019) recently proposed a Constraint Programming (CP) approach to solve the same problem.”
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).”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “…outperform the other techniques based on generic optimisation modelling, such as integer programming (Verwer and Zhang (2019); Bertsimas and Dunn (2017)) and constraint programming (Verhaeghe et al. (2019)), when minimising the misclassiﬁcation score given constraints on the depth of the tree.”
SAT-based Decision Tree Learning for Large Data Sets (2021, background): “…that correctly classify the data set, these approaches try to minimize the number of misclassiﬁcations subject to constraints on the depth (Bertsimas and Dunn 2017; Verwer and Zhang 2019; Verhaeghe et al. 2020) or with penalties on trees with a large number of leaves (Hu, Rudin and Seltzer 2019).”
Optimal Decision Trees for Nonlinear Metrics (2020, methodology): “Verhaeghe et al. (2019) approached the optimal classification tree problem by minimising the misclassifications using constraint programming.”
On Explaining Decision Trees (2020, background): “Motivated by this perception, there has been extensive work on learning DTs (and related logic ML models) with properties deemed important for interpretability, e.g. number of nodes, maximum/average depth, etc. [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] 2 .”
Machine Learning in Agriculture: A Comprehensive Updated Review (2021, background): “As regards leaf nodes, they stand for the final decision/prediction provided after following a certain rule [91,92].”
SAT-Based Encodings for Optimal Decision Trees with Explicit Paths (2020, methodology): “With the rise of powerful reasoning engines, recent research has tackled the problem by the use of SAT, CSP, or MILP solvers [1,27,37,38].”