摘要
证明了如果函数族F具有UCEM性质 ,那么F是完全有界的。此外如果F关于概率族P是PAC可学习的或具有UCEM性质 ,则F关于P的闭包 P也具有同样的性质。构造了一个非多项式可学习的例子 ,说明了PAC可学习的概念族可以有任意的复杂性。最后讨论了概念族C关于概率族P及其凸包C(P)的可学习性 ,并纠正了文 [1]的一点错误。
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 \ is corrected.
出处
《北京大学学报(自然科学版)》
CAS
CSCD
北大核心
2000年第3期347-357,共11页
Acta Scientiarum Naturalium Universitatis Pekinensis
基金
国家重点基础研究专项经费项目!(G1998020302 )
国家攀登计划资助项目