Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries
Abstract
We present results concerning the learning of Monotone DNF (MDNF) from Incomplete Membership Queries and Equivalence Queries. Our main result is a new algorithm that allows efficient learning of MDNF using Equivalence Queries and Incomplete Membership Queries with probability of $ p = 1 - 1/poly\left( {n, t} \right) $ of failing. Our algorithm is expected to make $ 0\left( {\left( {\frac{{tn}} {{1 - p}}} \right)^2 } \right) $ queries, when learning a MDNF formula with t terms over n variables. Note that this is polynomial for any failure probability p = 1-1/poly( n , t ). The algorithm’s running time is also polynomial in t , n , and 1/(1-tip). In a sense this is the best possible, as learning with p = 1-1/ω(poly( n , t )) would imply learning MDNF, and thus also DNF, from equivalence queries alone.
Cite
Text
Bshouty and Eiron. "Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries." Annual Conference on Computational Learning Theory, 2001. doi:10.1007/3-540-44581-1_36Markdown
[Bshouty and Eiron. "Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries." Annual Conference on Computational Learning Theory, 2001.](https://mlanthology.org/colt/2001/bshouty2001colt-learning/) doi:10.1007/3-540-44581-1_36BibTeX
@inproceedings{bshouty2001colt-learning,
title = {{Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries}},
author = {Bshouty, Nader H. and Eiron, Nadav},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2001},
pages = {546-557},
doi = {10.1007/3-540-44581-1_36},
url = {https://mlanthology.org/colt/2001/bshouty2001colt-learning/}
}