Stejnoměrný zákon velkých čísel, VC dimenze a strojové učení

Abstract

In this thesis we study the generalized Glivenko-Cantelli theorem and its application in mathematical foundations of machine learning. Firstly, we prove the generalized Glivenko-Cantelli's theorem using covering numbers and lemma of symmetrization. Next we show the uniform law of large numbers. Then, we deal with Vapnik-Chervonenkis classes of functions (VC classes). We show that for VC classes covering numbers are uniformly bounded. Finally, we describe the task of machine learning and give an example of one specific task that can be "learned". The main application will be to prove the fundamental theorem of statistical learning. Usually this theorem is proved for classes of predictors that are Probably Approximately Correct learnable (PAC learnable). In this work we strengthen the property of PAC learnable and for it we prove the basic theorem of statistical learning. 1

V této práci se zabýváme zobecněnou Glivenkovou-Cantelliho větou a její aplikací v matematických základech strojového učení. Nejprve dokážeme zobecněnou Glivenkovu-Cantelliho větu pomocí pokrývacích čísel a lemmatu o symetrizaci. Dále vyslovíme stejnoměrný zákon velkých čísel. Následně budeme se zabývat Vapnikovými-Červonenkisovými třídami funkcí (VC třídami). Ukážeme, že pro VC třídy jsou pokrývací čísla stejnoměrně omezená. Nakonec popíšeme úlohu strojového učení a uvedeme příklad jedné konkretní úlohy, která se dá naučit. Hlavní aplikací bude dokázat základní větu statistického učení. Obvykle je tato věta dokazovaná pro třídy prediktorů, které jsou tzv. Prob- ably Aproximately Correct learnable (PAC learnable). V této práci zesílíme vlastnost PAC learnable a dokážeme pro ni základní větu statistického učení. 1