Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles     Next Articles

On Several Problems of Statistical Learning Theory

DUAN Zhisheng, HUANG Lin   

  1. Center for Systems and Control Department of Mechanics and Engineering Science, Peking University, Beijing, 100871
  • Received:1999-04-07 Online:2000-05-20 Published:2000-05-20


段志生, 黄琳   

  1. 北京大学系统与控制中心,力学与工程科学系,北京,100871

Abstract: It is proved that the UCEM property of a family of measurable functions F implies that F is totally bounded; the UCEMUP property and PAC learnability still preserve when the family of probabilities is replaced by its closure. And a concept class C is constructed to show that every PAC algorithm of C would require a super-polynomial number of samples. Finally, the learnability of a concept class C with respect to the probability measures P and its convex hull C(P) is discussed and a mistake of [1] is corrected.

Key words: UCEM property, PAC learnability, PUAC learnability, totally bounded

摘要: 证明了如果函数族F具有UCEM性质,那么F是完全有界的。此外如果F关于概率族P是PAC可学习的或具有UCEM性质,则F关于P的闭包也具有同样的性质。构造了一个非多项式可学习的例子,说明了PAC可学习的概念族可以有任意的复杂性。最后讨论了概念族C关于概率族P及其凸包C(P)的可学习性,并纠正了文[1]的一点错误。

关键词: UCEM性质, PAC可学习, PUAC可学习, 完全有界

CLC Number: