ML Anthology

Learning Random Log-Depth Decision Trees Under the Uniform Distribution

Jeffrey C. Jackson, Rocco A. Servedio
COLT 2003 pp. 610-624
doi:10.1007/978-3-540-45167-9_44 /colt/2003/jackson2003colt-learning/

Abstract

We consider three natural models of random log-depth decision trees. We give an efficient algorithm that for each of these models learns—as a decision tree—all but an inverse polynomial fraction of such trees using only uniformly distributed random examples.

PDF COLT Semantic Scholar

Cite

Text

Jackson and Servedio. "Learning Random Log-Depth Decision Trees Under the Uniform Distribution." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_44

Markdown

[Jackson and Servedio. "Learning Random Log-Depth Decision Trees Under the Uniform Distribution." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/jackson2003colt-learning/) doi:10.1007/978-3-540-45167-9_44

BibTeX

@inproceedings{jackson2003colt-learning,
  title     = {{Learning Random Log-Depth Decision Trees Under the Uniform Distribution}},
  author    = {Jackson, Jeffrey C. and Servedio, Rocco A.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2003},
  pages     = {610-624},
  doi       = {10.1007/978-3-540-45167-9_44},
  url       = {https://mlanthology.org/colt/2003/jackson2003colt-learning/}
}