Rozbity zestaw

Pojęcie rozbitych zbiorów odgrywa ważną rolę w teorii Vapnika-Chervonenkisa , znanej również jako teoria VC. Teoria wstrząsów i teoria VC są wykorzystywane w badaniu procesów empirycznych , a także w statystycznej teorii obliczeniowego uczenia się .

Definicja

Załóżmy, że A jest zbiorem , a C klasą zbiorów. Klasa C rozbija zbiór A , jeśli dla każdego podzbioru a zbioru A istnieje element c zbioru C taki, że

{\ displaystyle a = c \ czapka A.}

Równoważnie, C rozbija A , gdy ich przecięcie jest równe zbiorowi mocy A : P ( A ) = { c ∩ A | do ∈ do }.

Używamy litery C , aby odnieść się do „klasy” lub „zbioru” zestawów, jak w klasie Vapnik-Chervonenkis (klasa VC). Często zakłada się, że zbiór A jest skończony , ponieważ w procesach empirycznych interesuje nas rozbijanie skończonych zbiorów punktów danych.

Przykład

Pokażemy, że klasa wszystkich dysków na płaszczyźnie (przestrzeń dwuwymiarowa) nie rozbija każdego zbioru czterech punktów na okręgu jednostkowym , ale klasa wszystkich zbiorów wypukłych na płaszczyźnie rozbija każdy skończony zbiór punktów na koło jednostkowe .

Niech A będzie zbiorem czterech punktów na okręgu jednostkowym, a C klasą wszystkich krążków.

Zbiór A czterech określonych punktów na okręgu jednostkowym (okrąg jednostkowy jest zaznaczony na fioletowo).

Aby sprawdzić, gdzie C rozbija A , próbujemy narysować dysk wokół każdego podzbioru punktów w A . Najpierw rysujemy dysk wokół podzbiorów każdego izolowanego punktu. Następnie próbujemy narysować krążek wokół każdego podzbioru par punktów. Okazuje się, że jest to wykonalne dla sąsiednich punktów, ale niemożliwe dla punktów po przeciwnych stronach okręgu. Jak zwizualizowano poniżej:

Każdy pojedynczy punkt można wyizolować za pomocą dysku (pokazującego wszystkie cztery).
Każdy podzbiór sąsiednich punktów można wydzielić za pomocą dysku (pokazującego jeden z czterech).
Podzbiór punktów po przeciwnych stronach koła jednostkowego nie może być izolowany za pomocą dysku.

C istnieje pewien podzbiór, którego nie może wydzielić żaden krążek , wnioskujemy, że A nie jest rozbite przez C. Przy odrobinie zastanowienia możemy udowodnić, że żaden zbiór czterech punktów nie jest rozbity przez to C .

Jeśli jednak ponownie zdefiniujemy C jako klasę wszystkich dysków eliptycznych , okaże się, że nadal możemy wyizolować wszystkie podzbiory z góry, a także punkty, które wcześniej były problematyczne. Tak więc ten specyficzny zestaw 4 punktów jest rozbity przez klasę dysków eliptycznych. Zwizualizowane poniżej:

Przeciwne punkty A są teraz rozdzielone jakąś elipsą (pokazującą jeden z dwóch)
Każdy podzbiór trzech punktów w A jest również rozdzielny jakąś elipsą (pokazującą jeden z czterech)

Przy odrobinie zastanowienia moglibyśmy uogólnić, że każdy zbiór skończonych punktów na okręgu jednostkowym może zostać rozbity przez klasę wszystkich zbiorów wypukłych (zobacz łączenie kropek).

Współczynnik rozbicia

Aby określić ilościowo bogactwo zbioru C zbiorów, używamy koncepcji współczynników niszczących (znanych również jako funkcja wzrostu ). Dla zbioru C zbiorów będącego dowolną $przestrzenią$ ^, często przestrzenią $,$ definiujemy ty wstrząsu C jako

{\ Displaystyle S_ {C} (n) = \ max _ {\ forall x_ {1}, x_ {2}, \ kropki, x_ {n} \ w \ Omega} \ operatorname {karta} \ {\, \ { \,x_{1},x_{2},\kropki ,x_{n}\}\cap s,s\w C\}}

gdzie $}$ oznacza liczność zbioru i $\in \Omega }$ ${\ Displaystyle x_ {1}, x_ {2}, \ kropki, x_ {n$ to dowolny zbiór n punktów.

${\ Displaystyle S_ {C} (n)}$ to największa liczba podzbiorów dowolnego zbioru A z n punktów, które można utworzyć przez przecięcie A ze zbiorami w zbiorze C .

Oto kilka faktów na temat ${\ Displaystyle S_ {C} (n)}$ :

${\ Displaystyle S_ {C} (n) \ równoważnik 2 ^ {n}}$ dla wszystkich n , ponieważ ${\ Displaystyle \ {s \ cap A | s \ w C \} \ subseteq P (A)}$ dla dowolnego ${\ Displaystyle A \ subseteq \ Omega}$ .
Jeśli ${\ displaystyle S_ {C} (n) = 2 ^ {n}}$ , oznacza to, że istnieje zbiór liczności n , który może zostać rozbity przez do .
Jeśli ${\ Displaystyle S_ {C} (N) <2 ^ {N}}$ $jakiegoś$ , do $Displaystyle S_ {C} (n) <2 ^ {n}}$ dla wszystkich ${\ Displaystyle n \ geq N}$ .

Trzecia właściwość oznacza, że jeśli C nie może rozbić żadnego zbioru liczności N , to nie może rozbić zbiorów większych liczności.

Klasa Vapnik-Chervonenkis

Wymiar VC klasy C jest zdefiniowany jako

{\ Displaystyle VC (C) = {\ underset {n} {\ min}} \ {n: S_ {C} (n) <2^{n}\}\,}

lub alternatywnie jako

{\ Displaystyle VC_ {0} (C) = {\ underset {n} {\ max}} \ {n: S_ {C} (n) = 2 ^ {n} \}. \,}

Zauważ, że ${\ Displaystyle VC (C) = VC_ {0} (C) + 1.}$

Jeśli dla dowolnego $dla$ istnieje liczności , może zostać C , to wszystkich i wymiar tej klasy C jest nieskończony.

Klasa o skończonym wymiarze VC nazywana jest klasą Vapnika-Chervonenkisa lub klasą VC . Klasa C jest jednolicie Glivenko – Cantelli wtedy i tylko wtedy, gdy jest klasą VC.

Zobacz też

Lemat Sauera – Szelacha , odnoszący liczność rodziny zbiorów do wielkości jej największego rozbitego zbioru

Wencour, RS; Dudley, RM (1981), „Niektóre specjalne klasy Vapnika – Chervonenkisa”, Discrete Mathematics , 33 (3): 313–318, doi : 10.1016/0012-365X (81) 90274-0 .
Steele, JM (1975), Entropia kombinatoryczna i jednolite prawa graniczne , Ph.D. praca magisterska, Uniwersytet Stanforda, Wydział Matematyki
Steele, JM (1978), „Rozbieżności empiryczne i procesy subaddytywne”, Annals of Probability , 6 (1): 118–227, doi : 10.1214/aop/1176995615 , JSTOR 2242865 .

Linki zewnętrzne

Pochodzenie terminologii „Zbiory rozbite” autorstwa J. Steele