ML Anthology

A Note on Learning DNF Formulas Using Equivalence and Incomplete Membership Queries

Zhixiang Chen
ALT 1994 pp. 272-281
doi:10.1007/3-540-58520-6_70 /alt/1994/chen1994alt-note/

Abstract

In this note, we prove with derandomization techniques that a subclass of DNF formulas with nonconstant number of terms is polynomial time learnable using equivalence and incomplete membership queries. Although many concept classes are known to be polynomial time learnable using equivalence and membership queries, so far only two concept classes are known to be polynomial time learnable (see, [AS] and [GM]) when incomplete membership queries are used.

PDF ALT Semantic Scholar

Cite

Text

Chen. "A Note on Learning DNF Formulas Using Equivalence and Incomplete Membership Queries." International Conference on Algorithmic Learning Theory, 1994. doi:10.1007/3-540-58520-6_70

Markdown

[Chen. "A Note on Learning DNF Formulas Using Equivalence and Incomplete Membership Queries." International Conference on Algorithmic Learning Theory, 1994.](https://mlanthology.org/alt/1994/chen1994alt-note/) doi:10.1007/3-540-58520-6_70

BibTeX

@inproceedings{chen1994alt-note,
  title     = {{A Note on Learning DNF Formulas Using Equivalence and Incomplete Membership Queries}},
  author    = {Chen, Zhixiang},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {1994},
  pages     = {272-281},
  doi       = {10.1007/3-540-58520-6_70},
  url       = {https://mlanthology.org/alt/1994/chen1994alt-note/}
}