کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434058 | 689675 | 2014 | 16 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Algebraic methods proving Sauer's bound for teaching complexity Algebraic methods proving Sauer's bound for teaching complexity](/preview/png/434058.png)
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. 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.
Journal: Theoretical Computer Science - Volume 558, 13 November 2014, Pages 35–50