×

A syntactic characterization of bounded-rank decision trees in terms of decision lists. (English) Zbl 0876.68092

Summary: We define syntactically a subclass of decision lists (tree-like decision lists) and we show its equivalence with the class of bounded rank decision trees. As a by-product, the main theorem provides an alternate and easier proof of the Blum’s containement Theorem. Furthermore, we give an inversion procedure for Blum’s derivation of a decision list from a bounded rank decision tree.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. A. BLUM, Rank-\Upsilon decision trees are a subclass of \Upsilon -decision lists, Information Processing Letters, 1992, 42, pp. 183-185. Zbl0773.68059 MR1170878 · Zbl 0773.68059
[2] 2. A. EHRENFEUCHT and D. HAUSSLER, Learning decision trees from random examples, Information and Computation, 1989, 82, pp. 231-246. Zbl0679.68157 MR1016682 · Zbl 0679.68157
[3] 3. R. L. RIVEST, Learning decision lists, Machine Learning, 1987, 2, pp. 223-246.
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.