On Exact Learning Monotone DNF from Membership Queries

Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi

ALT 2014 pp. 111-124

doi:10.1007/978-3-319-11662-4_9 /alt/2014/abasi2014alt-exact/

Abstract

In this paper, we study the problem of learning a monotone DNF with at most s terms of size (number of variables in each term) at most r (s term r-MDNF) from membership queries. This problem is equivalent to the problem of learning a general hypergraph using hyperedge-detecting queries, a problem motivated by applications arising in chemical reactions and genome sequencing.

PDF ALT Semantic Scholar

Cite

Text

Abasi et al. "On Exact Learning Monotone DNF from Membership Queries." International Conference on Algorithmic Learning Theory, 2014. doi:10.1007/978-3-319-11662-4_9

Markdown

[Abasi et al. "On Exact Learning Monotone DNF from Membership Queries." International Conference on Algorithmic Learning Theory, 2014.](https://mlanthology.org/alt/2014/abasi2014alt-exact/) doi:10.1007/978-3-319-11662-4_9

BibTeX

@inproceedings{abasi2014alt-exact,
  title     = {{On Exact Learning Monotone DNF from Membership Queries}},
  author    = {Abasi, Hasan and Bshouty, Nader H. and Mazzawi, Hanna},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2014},
  pages     = {111-124},
  doi       = {10.1007/978-3-319-11662-4_9},
  url       = {https://mlanthology.org/alt/2014/abasi2014alt-exact/}
}