Learning decision trees from random examples. (English) Zbl 0679.68157

Summary: We define the rank of a decision tree and show that for any fixed r, the class of all decision trees of rank at most r on n Boolean variables is learnable from random examples in time polynomial in n and linear in 1/\(\epsilon\) and log(1/\(\delta)\), where \(\epsilon\) is the accuracy parameter and \(\delta\) is the confidence parameter. Using a suitable encoding of variables, Rivest’s polynomial learnability result for decision lists can be interpreted as a special case of this result for rank 1. As another corollary, we show that decision trees on n Boolean variables of size polynomial in n are learnable from random examples in time linear in \(n^{O(\log n)}\), 1/\(\epsilon\), and log(1/\(\delta)\). As a third corollary, we show that Boolean functions that have polynomial size DNF expressions for both their positive and their negtive instances are learnable from random examples in time linear in \(n^{O((\log n)^ 2)}\), 1/\(\epsilon\), and log(1/\(\delta)\).


68T05 Learning and adaptive systems in artificial intelligence
90B50 Management decision making, including multiple objectives
05C05 Trees
06E30 Boolean functions
Full Text: DOI


[1] Breiman, L.; Friedman, J.H.; Olshen, R.A.; Stone, C.J., ()
[2] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M.K., Occam’s razor, Inform. process. lett., 24, 377-380, (1987) · Zbl 0653.68084
[3] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M.K., Learnability and the vapnik-chervonenkis dimension, J. assoc. comput. Mach., 36, No. 4, (1989) · Zbl 0697.68079
[4] Haussler, D., Quantifying inductive bias: AI learning algorithms and Valiant’s learning framework, Artif. intell., 36, 177-221, (1988) · Zbl 0651.68104
[5] Haussler, D.; Kearns, M.; Littlestone, N.; Warmuth, M.K., Equivalence of models of polynomial learnability, (), 42-55
[6] Kearns, M.; Li, M.; Pitt, L.; Valiant, L.G., On the learnability of Boolean formulae, (), 285-295
[7] Littlestone, N., Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Mach. learning, 2, No. 4, 245-318, (1988)
[8] Pitt, L.; Valiant, L.G., Computational limitations on learning from examples, J. assoc. comput. Mach., 33, No. 4, 965-984, (1988) · Zbl 0662.68086
[9] Quinlan, J.R., Induction of decision trees, Mach. learning, 1, No. 1, 81-106, (1986)
[10] Quinlan, J.R.; Rivest, R., Inferring decision trees using the minimum description length principle, Inform. and comput., 80, 227-448, (1989) · Zbl 0664.94015
[11] Rivest, R., Learning decision lists, Mach. learning, 2, No. 3, 229-246, (1987)
[12] Valiant, L.G., A theory of the learnable, Comm. ACM, 27, No. 11, 1134-1142, (1984) · Zbl 0587.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.