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.