期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 logn.
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.
关键词：Attribute Efficient Learning, PAC Learning DNF under Uniform with Membership Queries
