Author: Victor Dalmau.
Source: Lecture Notes in Artificial Intelligence Vol. 1720, 1999, 301 - 312.
Boolean formulas are known not to be PAC-predictable even with membership queries under some cryptographic assumptions. In this paper, we study the learning complexity of some subclasses of boolean formulas obtained by varying the basis of elementary operations allowed as connectives. This broad family of classes includes, as a particular case, general boolean formulas, by considering the basis given by {AND,OR,NOT}. We completely solve the problem. We prove the following dichotomy theorem: For any set of basic boolean functions, the resulting set of formulas is either polynomially learnable from equivalence queries or membership queries alone or else it is not PAC-predictable even with membership queries under cryptographic assumptions. We identify precisely which sets of basic functions are in which of the two cases. Furthermore, we prove than the learning complexity of formulas over a basis depends only on the absolute expressivity power of the class, ie., the set of functions that can be represented regardless of the size of the representation. In consequence, the same classification holds for the learnability of boolean circuits.
©Copyright 1999 Springer-Verlag