Constructing Optimal Binary Decision Trees is NP-Complete

By L. Hyafil, R. Rivest. 1976

Subfields: Statistical Learning Theory, 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 Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI (2019, neutral): “Decision trees are hierarchical structures for decision making used to support regression and classi-ﬁcation problems [132,180] .”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Full decision tree optimization is known to be an NP-complete problem [174], and heuristic greedy splitting and pruning procedures have been the major type of approach since the 1980s to grow decision trees [40, 239, 192, 205].”
Learning Optimal Decision Trees with SAT (2018, background): “On the negative side, the construction of optimal decision trees is well-known to be NP-hard, for different notions of optimality [Hyaﬁl and Rivest, 1976; Hancock et al. , 1996].”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, background): “While in general these algorithms learn models of good accuracy, their greedy nature, in combination with the NPhardness of the learning problem (Laurent and Rivest 1976), implies that the trees that are found are not necessarily optimal.”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, background): “Learning an optimal decision tree with a predeﬁned depth is NP-hard (Hyaﬁl and Rivest 1976).”
Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches (2019, background): “The production of compact and accurate decision trees is an NP-Hard problem (Hyafil and Rivest, 1976).”
Efficient Non-greedy Optimization of Decision Trees (2015, background): “Joint optimization of the split functions and leaf parameters according to a global objective is known to be extremely challenging [11] due to the discrete and sequential nature of the splitting decisions within the tree.”
Optimal Generalized Decision Trees via Integer Programming (2016, background): “set values of a categorical feature can be done again according to a sequential local heuristic. While ﬁnding an optimal DT (even without the combinatorial decisions) is known to be an NPhard problem [8], we show that with careful modeling, the resulting integer programs can be solved to optimality ”
Optimal randomized classification trees (2021, background): “Since constructing optimal binary decision trees is known to be an NP-complete problem [31], researchers have traditionally focused on the design of heuristic procedures.”
Learning optimal decision trees using constraint programming (2020, background): “The main challenge that these methods need to address is that the problem of inducing decision trees under constraints is NP-hard [10].”
Recursive Partitioning for Personalization using Observational Data (2016, background): “In the case of classiﬁcation and regression, Bennett & Blue (1996); Bertsimas & Dunn (2016) attempt to ﬁnd globally optimal prediction trees (while the problem is NP-hard; see Hyaﬁl & Rivest, 1976).”
A System for Induction of Oblique Decision Trees (1994, methodology): “This observation follows directly from the work of Hya l and Rivest (1976).”
SAT-Based Encodings for Optimal Decision Trees with Explicit Paths (2020, background): “However, despite this simplicity, minimization of decision trees is well-known to be an NPhard problem [16,10].”