A learnability model for universal representations and its application to top-down induction of decision trees
Stephen Muggleton, D Page, Masako Satô · 2000
Abstract Automated inductive learning is a vital part of machine intelligence and the design of intelligent agents. A useful formalization of inductive learning is the model of PAC learnability. Nevertheless, the ability to learn every target concept expressible in a given representation, as required in the PAC-learnability model, is highly demanding and leads to many negative results for interesting concept classes. A new model of learnability, called universal learnability or U-learnability, recently has been proposed as a less demanding, average-case variant of PAC-learnability. This paper uses the U-learnability model to analyze a top-down decision tree induction algorithm. Specifically, this paper proves that an idealized variant of the well-known decision tree learning algorithm CART - one of the most successful existing machine learning algorithms - is a U-learner under a natural set of assumptions regarding target hypotheses.