Algebraic methods proving Sauer%26apos;s bound for teaching complexity

作者：Samei Rahim^*; Semukhin Pavel; Yang Boting; Zilles Sandra

来源：Theoretical Computer Science, 2014, 558: 35-50.

DOI：10.1016/j.tcs.2014.09.024

• VC-dimension
• Teaching
• Sauer%26apos
• s bound
• Maximum classes

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%26apos;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. %26lt;br%26gt;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%26apos;s bound for RTD. Such techniques have been used before to prove results relevant to computational learning theory, e.g., by Smolensky [13], but are not standard in the field.

• 出版日期2014-11-13