Learning restricted-read branching programs with queries
Dawn E. Wilkins · 1995
There are two predominant models of computational learning theory--the probably approximately correct (PAC) model and the exact model. The goal of computational learning theory is to develop algorithms for efficiently learning concept classes and to show that classes cannot be efficiently learned. Boolean classes are among the most natural classes to study and are the focus of this dissertation. There is cryptographic evidence to support the belief that the class of general branching programs is not predictable. Thus, our emphasis is on restricted subclasses of of branching programs. We present both positive and negative results. Specifically, a general framework for learning projection-closed, augmentable concept classes in the exact model (with membership queries) is developed. We then present a characterization of the class of $\mu$-branching programs (where each variable may appear in the branching program at most once). The characterization is used to show that $\mu$-branching programs are augmentable, and therefore learnable by the general framework. Using a result by Angluin, it is easy to show that $\mu$-branching programs are also learnable in the PAC model (with membership queries). The negative results show that (i) $\mu$-branching programs cannot be learned with membership queries alone, or equivalence queries alone, (ii) ${k\mu}$-branching programs (where each variable may appear at most k times in the representation), for $k \ge 3$, are not predictable modulo cryptographic assumptions, and (iii) the class of read-k-times branching programs (where each variable may appear at most k times on any root-to-terminal path), for $k \ge 2$, is not predictable modulo cryptographic assumptions. Also included in the dissertation is a chapter on equivalence testing of branching programs. Using the characterization of $\mu$-branching programs, we show that a pair of $\mu$-branching programs can be tested for equivalence in O(${n\alpha(n}$)) time where n is the number of nodes in the larger of the $\mu$-branching programs. Equivalence testing for the classes of ${k\mu}$-branching programs, for $k \ge 3$ and read-k-times branching programs, for $k \ge 2$ are show to be co-NP-complete.