Minimising Decision Tree Size as Combinatorial Optimisation

By Christian Bessiere, Emmanuel Hebrard, Barry O'Sullivan. 2009

81 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, 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 Computational Theory and Mathematics

In Information Systems

In Mathematical Optimization

Citations in the corpus

Learning Optimal Decision Trees with SAT (2018, methodology): “The ﬁrst row shows results reported in [Bessiere et al. , 2009].”
Computing Optimal Decision Sets with SAT (2020, methodology): “We follow the notation used in earlier work [8, 31, 34, 44].”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, background): “Encodings of decision trees using propositional logic (SAT) and constraint programming have been initially devised by Bessiere et al. (2009).”
Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost (2020, neutral): “For instance, some approaches (e.g., [ Bessiere et al. , 2009; Narodytska et al. , 2018; Avellaneda, 2020 ] ) minimize some size criterion, either number of nodes or maximum depth, subject to the constraint that the tree is perfectly accurate on the training set.”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, methodology): “In our experiments, we consider three: the original order of the attributes in the data, in increasing or in decreasing order of information gain (such as used in C4.5 and CART).”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “This power has led to interesting new approaches for learning models and rules, see e.g., (Bessiere, Hebrard, and OSullivan 2009; De Raedt, Guns, and Nijssen 2010; Narodytska et al. 2018; Verwer, Zhang, and Ye 2017).”
IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules (2019, background): “The study of designing interpretable machine learning clas-siﬁers can ﬁnd its root in the development of popular models such as decision trees (Bessiere, Hebrard, and OSullivan 2009; Quinlan 2014), decision lists (Rivest 1987), classiﬁ-cation rules (Cohen 1995) etc.”
MLIC: A MaxSAT-Based Framework for Learning Interpretable Classification Rules (2018, background): “There is a long history of learning interpretable classification models from data, including popular approaches such as decision trees [5,29], decision lists [30], and classification rules [10].”
Efficient Inference of Optimal Decision Trees (2020, methodology): “Many machine learning models exist to solve this problem, such as support vector machines (Cortes and Vapnik 1995), artiﬁcial neural networks (McCulloch and Pitts 1943), decision trees (Breiman et al. 1984).”
SAT-based Decision Tree Learning for Large Data Sets (2021, background): “The result of our encoding is a propositional formula ’ ( I; d ) .”
On Explaining Decision Trees (2020, methodology): “Figure 2 exempliﬁes that redundancy may occur even in Feature Name Domain Values Meaning The DT was obtained with the optimal decision tree package from Interpretable AI [10,28] 11 , where the ⊖ and the leftmost ⊕ are predicted with 75% and 83.3% conﬁdence, respectively.”
Recent advances in decision trees: an updated survey (2022, background): “…by similar technical considerations, other algorithms assume that all attributes are categorical (Günlük et al. 2021) or, more often, binary (Bessiere et al. 2009; Nijssen and Fromont 2010; Narodytska et al. 2018; Verwer and Zhang 2019; Aglin et al. 2020; Janota and Morgado 2020; Demirović…”
SAT-Based Encodings for Optimal Decision Trees with Explicit Paths (2020, methodology): “Earlier work for minimization of decision tree using Constraint Programming (CP) exists [2].”
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].”
Finding Cost-Efficient Decision Trees (2014, methodology): “Bessiere et al.[5] show this by finding three exact methods for finding optimal decision trees do not scale well to anything but the smallest data sets.”
A SAT-Based Approach to Learn Explainable Decision Sets (2018, methodology): “Recent approaches include the computation of (smaller or smallest) rule lists [2,42], the computation of decision sets [21], but also the computation of decision trees [3].”
Parameterized Complexity of Small Decision Tree Learning (2021, methodology): “In view of this complexity barrier, several constrained-based and SAT-based methods have been proposed for learning small decision trees (Bessiere, Hebrard, and O’Sullivan 2009; Narodytska et al. 2018; Avellaneda 2020; Schidler and Szeider 2021).”
Constructing classification trees using column generation (2018, background): “Bessiere et al. (2009) focus on the problem of finding the smallest size decision tree that best separates the training data.”
Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization (2017, background): “Researcher have previously investigated using solvers for learning diﬀerent kinds of models and rules, see e.g., [4, 6, 8, 10].”