Rank-\(r\) decision trees are a subclass of \(r\)-decision lists. (English) Zbl 0773.68059

Summary: We prove that the concept class of rank-\(r\) decision trees is contained within the class of \(r\)-decision lists. Each class if known to be learnable in polynomial time in the PAC model for constant \(r\). One result of this note, however, is that the algorithm of R. L. Rivest [Learning decision lists, Machine Learning 2, 229-246 (1987)] can be used for both.


68T05 Learning and adaptive systems in artificial intelligence
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Ehrenfeucht, A.; Haussler, D., Learning decision trees from random examples, Inform. and comput., 82, 231-246, (1989) · Zbl 0679.68157
[2] Helmbold, D.; Sloan, R.; Warmuth, M.K., Learning nested differences of intersection-closed concept classes, Proc. second ann. workshop on computational learning theory, 41-56, (1989) · Zbl 0746.68072
[3] Kearns, M.; Li, M.; Pitt, L.; Valiant, L., On the learnibility of Boolean formulae, Proc. nineteenth ann. ACM symp. on theory of computing, 285-295, (1987)
[4] Littlestone, N., Personal communication (a mistake-bound version of Rivest’s decision-List algorithm), (1989)
[5] Rivest, R.L., Learning decision lists, Machine learning, 2, 229-246, (1987)
[6] Sakakibara, Y., Algorithmic learning of formal languages and decision trees, ()
[7] Simon, H.U., On the number of examples and stages needed for learning decision trees, (), 303-313
[8] Valiant, L.G., A theory of the learnable, Comm. ACM, 27, 1134-1142, (1984) · Zbl 0587.68077
[9] Wenocur, R.S.; Dudley, R.M., Some special vapnik-chervonenkis classes, Discrete math., 33, 313-318, (1981) · Zbl 0459.60008
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.