Lehrstuhl Mathematik & InformatikLearning Decision Lists and Trees with Equivalence-Queries
Abstract. This paper is concerned with the model of learning with equivalence-queries which was introduced by Angluin in [2]. We show that decision lists and decision trees of bounded rank are polynomially learnable in this model. If there are N base functions, then N2 queries are sufficient for learning lists. For learning trees of rank r, (1+o(1))N2r queries are sufficient. we also investigate the problem of learning a shortest representation of a target decision list. Let k-DL denote the class of decision lists with boolean terms of maximal length k as base functions. We show that shortest representations for lists from 1-DL can be learned efficiently. The corresponding questions for k >= 2 are open, although we are able to show som related (but weaker) results. For instance, we present an algorithm which efficiently learns shortest representations of boolean 2-CNF or 2-DNF formulas.
References:
[2] Dana Angluin, Queries and concept learning, Machine
Learning, 2(4):319-342, 1988