Learning Monotone DNF with an Incomplete Membership Oracle
Abstract
We introduce a new fault-tolerant model of algorithmic learning using an equivalence oracle and an incomplete membership oracle , in which the answers to a random subset of the learner's membership queries may be missing. We demonstrate that, with high probability, it is still possible to learn monotone DNF formulas in polynomial time, provided that the fraction of missing answers is bounded by some constant. Even when half the membership queries are expected to yield no additional information, our algorithm will exactly identify m -term, n -variable monotone DNF formulas with an expected O ( mn 2 ) queries. The same task has been shown to require exponential time using equivalence queries alone. Thus, this model may lead to a better understanding of the power of membership queries.
Cite
Text
Angluin and Slonim. "Learning Monotone DNF with an Incomplete Membership Oracle." Annual Conference on Computational Learning Theory, 1991. doi:10.5555/114836.114849Markdown
[Angluin and Slonim. "Learning Monotone DNF with an Incomplete Membership Oracle." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/angluin1991colt-learning/) doi:10.5555/114836.114849BibTeX
@inproceedings{angluin1991colt-learning,
title = {{Learning Monotone DNF with an Incomplete Membership Oracle}},
author = {Angluin, Dana and Slonim, Donna K.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1991},
pages = {139-146},
doi = {10.5555/114836.114849},
url = {https://mlanthology.org/colt/1991/angluin1991colt-learning/}
}