An Algorithm for Constructing Optimal Binary Decision Trees

By H. Payne, W. Meisel. 1977

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Generalized and Scalable Optimal Sparse Decision Trees (2020, background): “Decision tree learning has served as a foundation for interpretable artiﬁcial intelligence and machine learning for over half a century (Morgan & Sonquist, 1963; Payne & Meisel, 1977; Loh, 2014).”
Optimal constraint-based decision tree induction from itemset lattices (2010, methodology): “In 1977, it was shown by Payne and Meisel (1977) that Meisel’s algorithm can also be applied for ﬁnding optimal decision trees under many other types of optimization criteria, for instance, for ﬁnding trees of minimal height or minimal numbers of nodes.”
Constructing classification trees using column generation (2018, methodology): “Other optimization techniques used in the literature to find decision trees are integer linear programming (shortly ILP), dynamic programming (Payne and Meisel 1977), and stochastic gradient descent based methods (Norouzi et al. 2015).”
Optimization Models for Machine Learning: A Survey (2019, methodology): “Since building optimal binary decision trees is known to be NP-hard [122], heuristic approaches based on mathematical programming paradigms, such as linear optimization [21], continuous optimization [22], dynamic programming [8, 10, 74, 175], have been proposed.”
Optimal trees for prediction and prescription (2018, background): “Nevertheless, there have been many efforts previously to develop effective ways of constructing optimal univariate decision trees using a variety of heuristic methods for growing the tree in one step, including linear optimization [7], continuous optimization [8], dynamic programming [37, 99], genet”
Mining optimal decision trees from itemset lattices (2007, background): “The search for optimal decision trees dates back to the 70s, when several dynamic programming algorithms for building such trees were proposed [9, 16, 26, 30, 15].”
Column generation based heuristic for learning classification trees (2020, methodology): “Other optimization techniques used in the literature to find decision trees are integer linear programming (shortly ILP), dynamic programming [30], and stochastic gradient descent based methods [29].”
Fifty Years of Classification and Regression Trees (2014, background): “…idea of recursive partitioning was gaining steam in the computer science and engineering communities as more efficient algorithms for carrying out the search for splits began to appear (Chou 1969; Henrichon & Fu, 1973; Meisel & Michalopoulos, 1977; Payne & Meisel, 1977; Sethi & Chatterjee, 1991).”
Optimal classification trees (2017, methodology): “Nevertheless, there have been many efforts previously to develop effective ways of constructing optimal univariate decision trees using a variety of heuristic methods for growing the tree in one step, including linear optimization (Bennett 1992), continuous optimization (Bennett and Blue 1996), dyna”