Funkcja wzrostu

Funkcja wzrostu , zwana także współczynnikiem rozbicia lub liczbą rozbicia , mierzy bogactwo zbioru rodziny . Jest szczególnie używany w kontekście statystycznej teorii uczenia się , gdzie mierzy złożoność klasy hipotez. Termin „funkcja wzrostu” został ukuty przez Vapnika i Chervonenkisa w ich pracy z 1968 r., w której udowodnili również wiele jej właściwości. Jest to podstawowa koncepcja uczenia maszynowego .

Definicje

Definicja rodziny zestawów

Niech $będzie$ rodziną $zestawem$ zestawów) i . Ich przecięcie jest zdefiniowane jako następująca rodzina zestawów:

${\ Displaystyle H \ nasadka C: = \ {h \ nasadka C \ środkowa h \ w H \}}$

Rozmiar skrzyżowania (zwany także indeksem ) $}$ odniesieniu do ${\ displaystyle H$ to ${\ Displaystyle | H \ nasadka C |}$ . Jeśli zestaw $zawiera$$elementy,$ to indeks wynosi co najwyżej 2 ${m}}$ . Jeśli indeks wynosi dokładnie 2 ^m , to zbiór mówi się, że jest rozbity przez H. $\ Displaystyle$$H \ cap C}$ wszystkie podzbiory, tj.: $do {\ displaystyle$$}$

$\ Displaystyle | H \ czapka C | = 2 ^ {| C |},}$

Funkcja wzrostu mierzy rozmiar ${\ displaystyle H \ cap C}$ jako funkcja ${\ Displaystyle | C |}$ . Formalnie:

${\ Displaystyle \ nazwa operatora {wzrost} (H, m): = \ max _ {C: | C | = m} | H \ nasadka C |}$

Definicja klasy hipotezy

Równoważnie, niech $klasą$$hipotezy$ (zbiorem funkcji binarnych) $zbiorem$ elementami . Ograniczeniem do jest $które$ funkcji binarnych na $}$ można wyprowadzić z $:$$H$ \ displaystyle

${\ Displaystyle H_ {C}: = \ {(h (x_ {1}), \ldots ,h(x_{m}))\mid h\in H,x_{i}\in C\}}$

$mierzy$ rozmiar funkcję ${\ Displaystyle | C|}$ :

${\ Displaystyle \ nazwa operatora {wzrost} (H, m): = \ max _ {C:|C|=m}|H_ {C}|}$

Przykłady

1. Dziedziną jest linia rzeczywista ${\ displaystyle \ mathbb {R}}$ . Rodzina zestawów $∈$ wszystkie półproste (promienie) od ${\ Displaystyle \ {x> x_ {0} \ mid x \ in \ mathbb {R} \}}$ liczby do dodatniej nieskończoności, tj. wszystkie zbiory postaci dla pewnego ${\ Displaystyle x_ {0} \ in \ mathbb {R}}$ . Dla dowolnego zestawu do ${\ displaystyle C$ m {\ $C}$$m}$$liczb$$rzeczywistych$ , przecięcie zawiera zbiory: zbiór , zbiór zawierający największy element $}$$i$ , zestaw zawierający dwa największe elementy tak dalej. Zatem: ${\ Displaystyle \ nazwa operatora {wzrost} (H, m) = m + 1}$ . To samo dotyczy tego, czy $półproste$ , zamknięte półproste, czy oba

2. Domena to segment ${\ Displaystyle [0,1]}$ . Rodzina zestawów $zawiera$ wszystkie otwarte zbiory $Dla$ dowolnego skończonego zbioru rzeczywistych przecięcie zawiera wszystkie $m$ podzbiory do $displaystyle$$}$ Istnieją $,$ więc ${\ Displaystyle \ operatorname {wzrost} (H, m) = 2 ^ {m}}$ .

3. Dziedziną jest przestrzeń euklidesowa ${\ displaystyle \ mathbb {R} ^ {n}}$ . Rodzina zestawów $jest$ wszystkie półprzestrzenie postaci: $\ Displaystyle \ phi}$ φ $ustalonym$ wektorem . Wtedy ${\ displaystyle \ operatorname {wzrost} (H, m) = \ operatorname {Comp} (n, m)}$ , gdzie Comp to liczba składników w podziale n-wymiarowej przestrzeni przez m hiperpłaszczyzn .

4. Dziedziną jest linia rzeczywista ${\ displaystyle \ mathbb {R}}$ . Rodzina zestawów $wszystkie$ zbiory postaci ${\ Displaystyle \ {x \ w [x_ {0}, x_ {1}] | x \ w \ mathbb {R} \}}$ dla pewnego ${\ Displaystyle x_ {0} ,x_{1}\w \mathbb {R}}$ . Dla dowolnego zestawu ${\ Displaystyle C}$$liczb$ rzeczywistych , przecięcie zawiera wszystkie przebiegi między 0 a $m}$$displaystyle$ kolejne elementy do $m}$ . Liczba takich przebiegów to ${\ Displaystyle {m + 1 \ wybierz 2} + 1}$ , więc ${\ Displaystyle \ nazwa operatora {wzrost} (H, m) = {m + 1 \ wybierz 2} + 1}$ .

Wielomian lub wykładniczy

Główną właściwością, która sprawia, że ​​funkcja wzrostu jest interesująca, jest to, że może być wielomianowa lub wykładnicza - nic pośredniego.

Poniżej znajduje się właściwość rozmiaru skrzyżowania:

• Jeśli dla pewnego zestawu $równoważnik m}$$|$ dla pewnej liczby ${\ Displaystyle | H \ cap C_ {m} | \ geq \ operatorname {Comp} (n, m)}$$Displaystyle n$ \ , -
• wtedy istnieje podzbiór o rozmiarze takim, że $}$${\ Displaystyle C_ {n} \ subseteq C_ {$${\ Displaystyle | H \ czapka C_ {n} | = 2 ^ {n}}$ .

Implikuje to następującą właściwość funkcji Growth. Dla każdej rodziny istnieją dwa przypadki: ${\ displaystyle H}$

• Przypadek wykładniczy : ${\ Displaystyle \ operatorname {wzrost} (H, m) = 2 ^ {m}}$ identycznie.
• Przypadek wielomianu : $jest$$\ Displaystyle \ operatorname {$ przez $równoważnik$ , gdzie jest najmniejszą liczbą całkowitą, dla której ${\ Displaystyle \ operatorname {wzrost} (H, n) <2 ^ {n}}$ .

Inne właściwości

Trywialna górna granica

Dla każdego skończonego ${\ displaystyle H}$ :

${\ Displaystyle \ nazwa operatora {wzrost} (H, m) \ równoważnik | H |}$

ponieważ dla każdego liczba elementów w $wynosi$$\ Displaystyle H \ cap C}$${\ Displaystyle | H|}$ najwyżej . Dlatego funkcja wzrostu jest interesująca głównie wtedy, gdy $jest$ .

Wykładnicza górna granica

Dla każdego niepustego ${\ displaystyle H}$ :

${\ Displaystyle \ operatorname {wzrost} (H, m) \ równoważnik 2 ^ {m}}$

Tj. funkcja wzrostu ma wykładniczą górną granicę.

$,$ że rodzina zestawów rozbija zbiór $C=2^{C}}$ jeśli ich przecięcie zawiera wszystkie możliwe podzbiory , tj. $H.$$=$$H$ . Jeśli $H}$$displaystyle$ rozbija się o rozmiar to $wzrost$${\ Displaystyle \ operatorname {wzrost} (H, C) = 2 ^ {m}}$ , co jest górną granicą.

Przecięcie kartezjańskie

Zdefiniuj kartezjańskie przecięcie dwóch rodzin zbiorów jako:

${\ Displaystyle H_ {1} \ bigotimes H_ {2}: = \ {h_ {1} \ czapka h_ {2}\mid h_{1}\in H_{1},h_{2}\in H_{2}\}}$ .

Następnie:

${\ Displaystyle \ operatorname {wzrost} (H_ {1} \ bigotimes H_ {2}, m )\leq \operatorname {Wzrost} (H_{1},m)\cdot \operatorname {Wzrost} (H_{2},m)}$

Unia

Dla każdych dwóch rodzin zestawów:

${\ Displaystyle \ operatorname {wzrost} (H_ {1} \ kubek H_ {2}, m )\leq \nazwa_operatora {Wzrost} (H_{1},m)+\nazwa_operatora {Wzrost} (H_{2},m)}$

wymiar VC

Wymiar VC jest definiowany zgodnie z tymi dwoma przypadkami: ${\ displaystyle H}$

• W przypadku wielomianu VCDim $\ Displaystyle \ operatorname {VCDim} (H) = n-1}$ = największa liczba całkowita ${\ Displaystyle d}$ dla której ${\ Displaystyle \ operatorname {wzrost} (H, d) = 2 ^ {d}}$ .
• W przypadku wykładniczym ${\ Displaystyle \ operatorname {VCDim} (H) = \ infty}$ .

Więc ${\ Displaystyle \ nazwa operatora {VCDim} (H) \ geq d}$ jeśli i tylko jeśli ${\ Displaystyle \ nazwa operatora {wzrost} (H. ,d)=2^{d}}$ .

Funkcję wzrostu można uznać za udoskonalenie koncepcji wymiaru VC. Wymiar VC mówi nam tylko, czy $)}$${\ Displaystyle \ operatorname {wzrost} (H,$ równy lub mniejszy niż , podczas gdy funkcja wzrostu mówi nam dokładnie, jak $zmienia się$${\ Displaystyle \ operatorname {wzrost} (H, m)}$ w funkcji .

Inny związek między funkcją wzrostu a wymiarem VC daje lemat Sauera – Szelacha :

Jeśli ${\ Displaystyle \ operatorname {VCDim} (H) = d}$ to:

dla $m$ : ${\ Displaystyle \ nazwa operatora {wzrost} (H, m) \ równoważnik \ suma _ {i = 0} ^ {d} {m \ wybierz i}}$

W szczególności,

m ${\ Displaystyle m> d + 1}$ : ${\ Displaystyle \ operatorname {wzrost} (H,$

więc gdy wymiar VC jest skończony, funkcja wzrostu rośnie wielomianowo z ${\ displaystyle m}$ .

$>$ ciasna, tj. dla wszystkich istnieje taki wymiar VC, że: $displaystyle m$ > $d }$

${\ Displaystyle \ operatorname {wzrost} (H, m) = \ suma _ {i = 0} ^ {d} {m \ wybierz i}}$

Entropia

Podczas gdy funkcja wzrostu jest związana z maksymalnym rozmiarem skrzyżowania, entropia jest związana ze średnim rozmiarem skrzyżowania:

${\ Displaystyle \ operatorname {Entropia} (H, m) = E_ {| C_ {m} | = m} {\ duży [} \ log _ {2 }(|H\cap C_{m}|){\duży ]}}$

Rozmiar skrzyżowania ma następującą właściwość. Dla każdej rodziny zestawów ${\ displaystyle H}$ :

${\ Displaystyle | H \ czapka (C_ {1} \ kubek C_ {2}) | \ równoważnik | H \ czapka C_ {1} | \ cdot | H \ czapka C_ {2} |}$

Stąd:

${\ Displaystyle \ operatorname {Entropia} (H, m_ {1} + m_ {2}) \leq \operatorname {Entropia} (H,m_{1})+\operatorname {Entropia} (H,m_{2})}$

Co więcej, sekwencja ${\ Displaystyle \ operatorname {Entropia} (H, m) / m}$ zbiega się do stałej do $\ Displaystyle c \ w [0,1] }$ kiedy ${\ Displaystyle m \ do \ infty}$ .

${\ Displaystyle \ log _ {2} {| H \ cap C_ {m} |/ m}}$ zmiennej losowej koncentruje się w pobliżu do $\ displaystyle c}$ .

Zastosowania w teorii prawdopodobieństwa

Niech będzie $zbiorem,$ którym $zdefiniowana jest$ prawdopodobieństwa . Niech będzie rodziną podzbiorów $}$$Omega$ (= rodzina zdarzeń).

$,$$losowo$ wybieramy zestaw $,$ zawiera gdzie każdy element jest wybierany zgodnie z $.$ , niezależnie od innych (tj. z zamianami). Dla każdego zdarzenia porównujemy następujące dwie wielkości: ${\ displaystyle h \ in H}$

• $tj$ częstotliwość w . ${\ Displaystyle | h \ czapka C_ {m} |/m}$ ;
• Jego prawdopodobieństwo ${\ Displaystyle \ Pr [h]}$ .

Interesuje nas różnica ${\ Displaystyle D (h, C_ {m}): = {\ duży |} | h \ cap C_ {m} |/ m- \ Pr [h] {\ duży |}}$ . Ta różnica spełnia następującą górną granicę:

${\ Displaystyle \ Pr \ lewo [\ forall h \ w H: D (h, C_ {m}) \ leq {\ sqrt {8 (\ ln \ operatorname {wzrost} (H, 2m) + \ ln (4/ \delta )) \over m}}\right]~~~~>~~~~1-\delta }$

co jest równoważne z:

${\ Displaystyle \ Pr {\ duży [} \ forall h \ w H: D (h, C_ {m}) \ równoważnik \ varepsilon {\ duży ]} ~~~~> ~~~~ 1-4 \ cdot \ nazwa operatora {Wzrost} (H,2m)\cdot \exp(-\varepsilon ^{2}\cdot m/8)}$

Słownie: prawdopodobieństwo, że dla wszystkich zdarzeń w $prawdopodobieństwu$ , jest ograniczone dolnym wyrażeniem zależnym od funkcji wzrostu ${\ displaystyle H}$ .

Następstwem tego jest to, że jeśli funkcja wzrostu jest wielomianem w $($ . istnieje coś $)$ , że ${\ Displaystyle$ ), to powyższe prawdopodobieństwo zbliża się do 1 jako ${\ Displaystyle m \ do \ infty}$ . To znaczy rodzina $cieszy$ jednostajna zbieżność prawdopodobieństwa .