Learning 2µ DNF Formulas and Kµ Decision Trees
Abstract
We consider the learnability of “kμ” DNF formulas and decision trees. These are DNF formulas and decision trees in which every variable appears in at most a constant k different locations. The learning model is Valiant's distribution free model with the addition of membership queries. We present polynomial time learning algorithms for 2μDNF formulas and for kμ decision trees (where k is an arbitrary constant). Learning 3μ DNF formulas in this model is as hard as learning arbitrary DNF formulas.
Cite
Text
Hancock. "Learning 2µ DNF Formulas and Kµ Decision Trees." Annual Conference on Computational Learning Theory, 1991. doi:10.1016/B978-1-55860-213-7.50022-5Markdown
[Hancock. "Learning 2µ DNF Formulas and Kµ Decision Trees." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/hancock1991colt-learning/) doi:10.1016/B978-1-55860-213-7.50022-5BibTeX
@inproceedings{hancock1991colt-learning,
title = {{Learning 2µ DNF Formulas and Kµ Decision Trees}},
author = {Hancock, Thomas R.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1991},
pages = {199-209},
doi = {10.1016/B978-1-55860-213-7.50022-5},
url = {https://mlanthology.org/colt/1991/hancock1991colt-learning/}
}