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.