证明了有限概念类的无冲突教学维数不超过VC维。
The No-Clash Teaching Dimension is Bounded by VC Dimension
- 用大小等于VC维的片段构造有序压缩方案
- 这些片段可作教学集且满足无冲突条件
- 解决了一个长期未解的理论难题，适合理论研究者
在机器学习理论中，为避免教师与学习者之间不自然的编码协作，引入了无冲突教学维数作为无勾结教学的最优复杂度度量。然而，无冲突教学维数是否受Vapnik-Chervonenkis（VC）维上界限制仍未知。本文针对任意有限概念类，构造出大小等于其VC维的片段，通过有序压缩方案识别概念。这些片段自然可作为教学集，显然满足无冲突条件，从而解决了该开放问题。
原文摘要 · Abstract (English)
In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching. However, whether No-Clash Teaching Dimension is upper-bounded by Vapnik-Chervonenkis dimension remains unknown. In this paper, for any finite concept class, we construct fragments of size equals to its Vapnik-Chervonenkis dimension which identify concepts through an ordered compression scheme. Naturally, these fragments are used as teaching sets, one can easily see that they satisfy the non-clashing condition, i.e., this open question is resolved for finite concept classes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。