[33] A k-decision list over n variables is a list of pairs L =

(m1, b1),...,(ms, bs), where mi is a monomial of at most k variables and bi ∈ {0, 1}, for 1 ≤ i ≤ s, except that always ms = 1. A decision list L represents a Boolean function fL defined as follows: For each example v ∈

{0, 1}n, let fL(v) = bi, where i is the least index such that v satisfies mi.

Since there are at most (2n)k+1 monomials of k literals over n variables, we have s ≤ (2n)k+1.

(a) Using Occam’s razor theorem, Theorem 5.3.1, we show that k-decision lists are polynomially pac-learnable.

(b) Let us define a log-decision list to be a decision list with each term having prefix complexity O(log n). Show that a log-decision list is polynomially learnable under m.

Comments. Source for Item (a): [R. Rivest, Machine Learning, 2:3(1987), 229–246]. Item

(b) was stated as an open problem in the first edition of this book and was solved by J. Castro and J.L. Balc´azar [pp. 239–248 in:

Proc. 6th Int. Workshop on Algorithmic Learning Theory, Lect. Notes Artific. Intell., Vol. 997, Springer-Verlag, 1995]. They also show that simple decision lists, a generalization of the simple DNF of Exercise 5.3.3, are polynomial learnable under m.