Theory and Applications of Agnostic PAC-Learning with Small Decision Trees

By Peter Auer, Robert Craig Holte, Wolfgang Maass. 1995

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

Citations in the corpus

Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead (2018, background): “ve, or because we chose constraints that do not allow enough ﬂexibility in the model to ﬁt the data well?). The question of computing optimal logical models has existed since at least the mid 1990’s [Auer et al., 1995]. We would like models that look like they are created by hand, but they need to b”
Please Stop Explaining Black Box Models for High Stakes Decisions (2018, background): “The question of computing optimal logical models has existed since at least the mid 1990’s [Auer et al., 1995].”
Scalable Bayesian Rule Lists (2016, background): “There are a series of works from the mid-1990’s onwards on finding optimal decision trees using dynamic programming and search techniques (e.g., Bennett & Blue, 1996; Auer et al., 1995; Dobkin et al., 1996; Boros et al., 2000; Garofalakis et al., 2000; Farhangfar et al., 2008), mainly working with f”
Optimal trees for prediction and prescription (2018, methodology): “A different approach is taken by the methods T2 [4], T3 [112] and T3C [117], a family of efficient enumeration approaches which create optimal non-binary decision trees of depths up to 3.”
Mining optimal decision trees from itemset lattices (2007, background): “Still, the idea of exhaustively finding optimal decision trees under certain constraints was also studied [2, 19], but only for much smaller datasets and smaller types of trees than studied in this paper.”
A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms (2000, methodology): “We include some decision tree algorithms that are not included in the StatLog Project, such as S-Plus tree [14], T1 [3, 25], Oc1 [38], Lmdt [9], and Quest [30].”
Elaboration on Two Points Raised in “Classifier Technology and the Illusion of Progress” (2006, methodology): “omplex decision rules be considered. I coined the term “simplicityﬁrst methodology” to describe this systematic approach of proceeding from simple to more complex decision rules. In a follow-up paper [1], Maass and Auer developed an eﬃcient algorithm for constructing a decision tree of ﬁxed depth d,”
A Survey of Methods for Scaling Up Inductive Algorithms (1999, background): “For example, in subsequent work Auer et al. (1995) introduce a theoretically founded al-gorithm, called T2, for learning two-level decision trees.”