A study on Glivenko-Cantelli classes
Date Issued
2016
Date
2016
Author(s)
Kao, Yu-Chun
Abstract
In statistical learning, an estimation of the risk function over a certain algorithm is of prime importance and the notion of Vapnik-Chervonenkis dimension plays an important role in analyzing and understanding such problems. It''s known that the law of large number holds uniformly over classes with less complexity, and VC-dimension is an important number giving quantitative description of their complexity. Having finite VC-dimension is a necessary and sufficient condition for a class of characteristic functions to be a uniform Glivenko-Cantelli class. However there are cases that VC-dimension is infinite but LLN still holds. We elaborate on a specific circumstance that VC-dimension is infinite but the Glivenko-Cantelli property still holds(but not uniformly) over any distribution which is absolutely continuous with respect to Lebesgue measure. This example demonstrates the trade off between the complexity of the class and of the probabilistic measures. Discussions of finite VC-dimension cases are also attached at the end for reference. Most of the work in the second half of this thesis is first established by Vapnik, V.N. and Chervonenkis, A.Y. and cited from ""Probability in High Dimension"" by van Handel, R. This thesis only serves as a terse introduction for those who want to get a quick grasp of Glivenko-Cantelli property and VC-dimension.
Subjects
Vapnik-Chervonenkis dimension
Glivenko-Cantelli class
Type
thesis