LEARNABILITY AND THE VAPNIK-CHERVONENKIS DIMENSION
LEARNABILITY AND THE VAPNIK-CHERVONENKIS DIMENSION
复制标题
DOI：
10.1145/76359.76371
复制
发表时间：
1989-10-01
影响因子：
2.5
通讯作者：
WARMUTH, MK
中科院分区：
文献类型：
--
作者：
BLUMER, A;EHRENFEUCHT, A;WARMUTH, MK
Valiant的可学习性模型被扩展到学习欧几里得空间中由区域定义的概念类。本文的方法导致了Valiant的一些结果的统一处理，以及先前关于某些模式识别算法的无分布收敛的结果。证明了无分布可学习性的必要条件是待学习概念类的简单组合参数Vapnik-Chervonenkis维数的有限性。利用该参数分析了可学习性类的复杂度和闭包性，给出了可学习性可行的充分必要条件。
Valiant's learnability model is extended to learning classes of concepts defined by regions in Euclidean spaceEn. The methods in this paper lead to a unified treatment of some of Valiant's results, along with previous results on distribution-free convergence of certain pattern recognition algorithms. It is shown that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned. Using this parameter, the complexity and closure properties of learnable classes are analyzed, and the necessary and sufficient conditions are provided for feasible learnability.