Abstract:
This paper studies the learnability of branching programs and small depth circuits with modular and threshold gates in both the exact and PAC learning models with and without membership queries. Some of the results extend earlier works in [GG95,ERR95,BTW95]. The main results are as follows. For branching programs we show the following. 1) Any monotone width two branching program (defined by Borodin {\em et al.} [BDFP86] is PAC learnable with membership queries under the uniform distribution. This extends Jackson's result \cite{j94} for learning DNF formulae. 2) Any width two branching program with a bounded number of sinks is exactly learnable using equivalence queries only. This extends the result of PAC learning width two branching programs with two sinks [BTW95]. This cannot be extended to an unbounded number of sinks unless $k$-term DNF is learnable from equivalence queries, for non-constant $k$. 3) Any width three and width four even permutation branching program (defined by Barrington [B89]) are exactly learnable with equivalence and membership queries. These results cannot be extended to width five unless $NC^1$ is learnable with membership queries [B89,AK95]. 4) Any $mod_p$ of polynomially many Obdds (ordered binary decision diagrams) and any constant Boolean combination of $mod_p$ of Obdds are exactly learnable using equivalence and membership queries, assuming that $p$ is a fixed prime. This extends a result of Gavalda and Guijarro [GG95]. For small depth circuits with modular and threshold gates we prove the following. 5) Any depth two circuit with a $mod_p$ gate at the top, for a fixed prime $p$, and arbitrary modular gates at the bottom level is exactly learnable using equivalence and membership queries. 6) Any depth two circuit with a $mod_p$ gates at the top, for a fixed prime $p$, and arbitrary threshold gates at the bottom level is exactly learnable using equivalence and membership queries. We note that by a result of Krause and Pudlak [KP94] learning a threshold of modular gates will imply the learnability of DNF formulae. 7) Any $f(g_1,g_2,\ldots,g_k)$, where $k$ is constant, $f$ is any Boolean function and $g_1,g_2,\ldots,g_k$ are one of the above two classes, is exactly learnable using equivalence and membership queries.