ML Anthology

Learning K-Term DNF Formulas with an Incomplete Membership Oracle

Sally A. Goldman, H. David Mathias
COLT 1992 pp. 77-84
doi:10.1145/130385.130394 /colt/1992/goldman1992colt-learning/

Abstract

We consider the problem of learning k-term DNF formulas using equivalence queries and incomplete membership queries as defined by Angluin and Slonim. We demonstrate that this model can be applied to non-monotone classes. Namely, we describe a polynomial-time algorithm that constructs a k-term DNF formula representationally equivalent to the target using incomplete membership queries and equivalence queries from the class of DNF formulas.

PDF COLT Semantic Scholar

Cite

Text

Goldman and Mathias. "Learning K-Term DNF Formulas with an Incomplete Membership Oracle." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130394

Markdown

[Goldman and Mathias. "Learning K-Term DNF Formulas with an Incomplete Membership Oracle." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/goldman1992colt-learning/) doi:10.1145/130385.130394

BibTeX

@inproceedings{goldman1992colt-learning,
  title     = {{Learning K-Term DNF Formulas with an Incomplete Membership Oracle}},
  author    = {Goldman, Sally A. and Mathias, H. David},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1992},
  pages     = {77-84},
  doi       = {10.1145/130385.130394},
  url       = {https://mlanthology.org/colt/1992/goldman1992colt-learning/}
}