TR96-009 Authors: Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

Publication: 7th February 1996 17:20

Downloads: 1300

Keywords:

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.