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

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