ML Anthology

Learning Monotone Log-Term DNF Formulas

Yoshifumi Sakai, Akira Maruoka
COLT 1994 pp. 165-172
doi:10.1145/180139.181095 /colt/1994/sakai1994colt-learning/

Abstract

Based on the uniform distribution PAC learning model, the learnability for monotone disjunctive normal form formulas with at most $O(\log n)$ terms ( $O(\log n)$ -term MDNF) is investigated. Using the technique of restriction, an algorithm that learns $O(\log n)$ -term MDNF in polynomial time is given.

COLT Semantic Scholar

Cite

Text

Sakai and Maruoka. "Learning Monotone Log-Term DNF Formulas." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181095

Markdown

[Sakai and Maruoka. "Learning Monotone Log-Term DNF Formulas." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/sakai1994colt-learning/) doi:10.1145/180139.181095

BibTeX

@inproceedings{sakai1994colt-learning,
  title     = {{Learning Monotone Log-Term DNF Formulas}},
  author    = {Sakai, Yoshifumi and Maruoka, Akira},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1994},
  pages     = {165-172},
  doi       = {10.1145/180139.181095},
  url       = {https://mlanthology.org/colt/1994/sakai1994colt-learning/}
}