Glivenko-Cantelli集合相關探討

Abstract

在統計學習中對於特定演算法產生的風險函數估計一直是重要課題，分析相關問題時Vapnik-Chervonenkis維度扮演了相當重要的角色。VC維度是一個測量集合複雜度的指標，大數法則在一VC維度有限之集合上可以有與機率分佈無關的均勻收斂速度估計。VC維度無窮大時，對於特定的機率分佈大數法則依然可能均勻成立。此論文中我們將探討一個VC維度無窮大但對特定機率分佈大數法則均勻成立的特殊情形來展示集合複雜度與機率分佈之間的關係，亦即：當集合越複雜，機率分佈的限制就越多。我們也將VC維度有限的相關討論適當地整理、濃縮後，附在本論文主要結果之後，以便讀者參照。而後半部的內容大部分是由Vapnik, V.N.和Chervonenkis, A.Y.完成，從van Handel, R.編寫之'Probability in High Dimension'中擷取 。

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.