Sauer's Bound for a Notion of Teaching Complexity
Abstract
This paper establishes an upper bound on the size of a concept class with given recursive teaching dimension (RTD, a teaching complexity parameter.) The upper bound coincides with Sauer’s well-known bound on classes with a fixed VC-dimension. Our result thus supports the recently emerging conjecture that the combinatorics of VC-dimension and those of teaching complexity are intrinsically interlinked. We further introduce and study RTD-maximum classes (whose size meets the upper bound) and RTD-maximal classes (whose RTD increases if a concept is added to them), showing similarities but also differences to the corresponding notions for VC-dimension. Another contribution is a set of new results on maximal classes of a given VC-dimension. Methodologically, our contribution is the successful application of algebraic techniques, which we use to obtain a purely algebraic characterization of teaching sets (sample sets that uniquely identify a concept in a given concept class) and to prove our analog of Sauer’s bound for RTD.
Cite
Text
Samei et al. "Sauer's Bound for a Notion of Teaching Complexity." International Conference on Algorithmic Learning Theory, 2012. doi:10.1007/978-3-642-34106-9_11Markdown
[Samei et al. "Sauer's Bound for a Notion of Teaching Complexity." International Conference on Algorithmic Learning Theory, 2012.](https://mlanthology.org/alt/2012/samei2012alt-sauer/) doi:10.1007/978-3-642-34106-9_11BibTeX
@inproceedings{samei2012alt-sauer,
title = {{Sauer's Bound for a Notion of Teaching Complexity}},
author = {Samei, Rahim and Semukhin, Pavel and Yang, Boting and Zilles, Sandra},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2012},
pages = {96-110},
doi = {10.1007/978-3-642-34106-9_11},
url = {https://mlanthology.org/alt/2012/samei2012alt-sauer/}
}