Learning Decision Lists

Abstract

This paper introduces a new representation for Boolean functions, called decision lists , and shows that they are efficiently learnable from examples. More precisely, this result is established for k -DL the set of decision lists with conjunctive clauses of size k at each decision. Since k -DL properly includes other well-known techniques for representing Boolean functions such as k -CNF (formulae in conjunctive normal form with at most k literals per clause), k -DNF (formulae in disjunctive normal form with at most k literals per term), and decision trees of depth k , our result strictly increases the set of functions that are known to be polynomially learnable, in the sense of Valiant (1984). Our proof is constructive: we present an algorithm that can efficiently construct an element of k -DL consistent with a given set of examples, if one exists.