×

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.

MSC:

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

References:

[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, (Ph.D. Thesis (October 1991), Tokyo Institute of Technology)
[7] Simon, H. U., On the number of examples and stages needed for learning decision trees, (Proc. Third Ann. Workshop Computational Learning Theory (1990), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.