ML Anthology

Teaching Classes with High Teaching Dimension Using Few Examples

Frank J. Balbach
COLT 2005 pp. 668-683
doi:10.1007/11503415_45 /colt/2005/balbach2005colt-teaching/

Abstract

We consider the Boolean concept classes of 2-term DNF and 1-decision lists which both have a teaching dimension exponential in the number n of variables. It is shown that both classes have an average teaching dimension linear in n . We also consider learners that always choose a simplest consistent hypothesis instead of an arbitrary consistent one. Both classes can be taught to these learners by efficient teaching algorithms using only a linear number of examples.

PDF COLT Semantic Scholar

Cite

Text

Balbach. "Teaching Classes with High Teaching Dimension Using Few Examples." Annual Conference on Computational Learning Theory, 2005. doi:10.1007/11503415_45

Markdown

[Balbach. "Teaching Classes with High Teaching Dimension Using Few Examples." Annual Conference on Computational Learning Theory, 2005.](https://mlanthology.org/colt/2005/balbach2005colt-teaching/) doi:10.1007/11503415_45

BibTeX

@inproceedings{balbach2005colt-teaching,
  title     = {{Teaching Classes with High Teaching Dimension Using Few Examples}},
  author    = {Balbach, Frank J.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2005},
  pages     = {668-683},
  doi       = {10.1007/11503415_45},
  url       = {https://mlanthology.org/colt/2005/balbach2005colt-teaching/}
}