Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-076 | 13th November 1998 00:00

#### Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

TR98-076
Authors: Nader Bshouty, Jeffrey J. Jackson, Christino Tamon
Publication: 18th December 1998 14:59
Keywords:

Abstract:

We study attribute efficient learning in the PAC learning model with
membership queries. First, we give an {\it attribute efficient}
PAC-learning algorithm for DNF with membership queries under the
uniform distribution. Previous algorithms for DNF have sample size
polynomial in the number of attributes $n$. Our algorithm is the
first attribute efficient learning for DNF, i.e., that runs in polynomial
time and uses sample of size polynomial in $\log n$.
We also develop lower bound techniques for
PAC learning with membership queries under a fixed distribution
and
show that the sample size of our algorithm
for learning DNF under the uniform distribution
is almost optimal in terms of $n$.
Finally, we present a learning algorithm for DNF that is attribute
efficient in its use of random bits.

ISSN 1433-8092 | Imprint