Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-059 | 21st November 1995 00:00

The Monotone Theory for the PAC-Model

RSS-Feed




TR95-059
Authors: Nader H. Bshouty
Publication: 4th December 1995 18:40
Downloads: 994
Keywords: 


Abstract:

We show that a DNF formula that has a CNF representation that contains
at least one ``$1/poly$-heavy''
clause with respect to a distribution $D$ is weakly learnable
under this distribution. So DNF that are not weakly
learnable under the distribution $D$ do not have
any ``$1/poly$-heavy'' clauses in any of their CNF representations.
We then show that $\tau$-CDNF, a DNF $f$ that has a CNF representation that
contains $poly(n)$ clauses that $\tau$-approximates
$f$
according to a distribution $D$,
is weakly ${\tau}+\epsilon$-PAC-learnable
with membership queries under the distribution $D$.

We then show how to change our algorithm to a parallel
algorithm that runs in polylogarithmic time
with a polynomial number of processors.
In particular, decision trees are (strongly) PAC-learnable with
membership queries under any distribution in parallel
in polylogarithmic time with a polynomial number of processors.
Finally we show that no efficient parallel exact learning
algorithm exists for decision trees.



ISSN 1433-8092 | Imprint