Teoria Wapnika-Czerwonenkisa - Vapnik–Chervonenkis theory

Teoria Vapnika-Chervonenkisa (znana również jako teoria VC ) została opracowana w latach 1960-1990 przez Vladimira Vapnika i Alexey Chervonenkisa . Teoria jest formą obliczeniowej teorii uczenia się , która stara się wyjaśnić proces uczenia się ze statystycznego punktu widzenia.

Teoria VC jest powiązana z teorią uczenia się statystycznego i procesami empirycznymi . Między innymi Richard M. Dudley i Vladimir Vapnik zastosowali teorię VC do procesów empirycznych .

Wstęp

Teoria VC obejmuje co najmniej cztery części (jak wyjaśniono w The Nature of Statistical Learning Theory ):

  • Teoria spójności procesów uczenia się
  • Niesymptotyczna teoria tempa konwergencji procesów uczenia się
    • Jak szybkie jest tempo konwergencji procesu uczenia się?
  • Teoria kontrolowania zdolności generalizacji procesów uczenia się
    • Jak można kontrolować tempo konwergencji ( zdolność generalizacji ) procesu uczenia się?
  • Teoria konstruowania uczących się maszyn
    • Jak konstruować algorytmy, które sterują zdolnością uogólniania?

Teoria VC jest główną gałęzią statystycznej teorii uczenia się . Jednym z jego głównych zastosowań w statystycznej teorii uczenia się jest zapewnienie warunków uogólniania algorytmów uczenia się. Z tego punktu widzenia teoria VC jest powiązana ze stabilnością , która jest alternatywnym podejściem do charakteryzowania uogólnienia.

Ponadto teoria VC i wymiar VC są instrumentalne w teorii procesów empirycznych , w przypadku procesów indeksowanych klasami VC. Zapewne są to najważniejsze zastosowania teorii VC, wykorzystywane do dowodzenia uogólnienia. Wprowadzonych zostanie kilka technik, które są szeroko stosowane w procesie empirycznym i teorii VC. Dyskusja opiera się głównie na książce Weak Convergence and Empirical Processes: With Applications to Statistics .

Przegląd teorii VC w procesach empirycznych

Tło procesów empirycznych

Niech będą elementami losowymi zdefiniowanymi na mierzalnej przestrzeni . Dla każdego środka na i wszelkich funkcji mierzalnych , definiować

Kwestie mierzalności zostaną tutaj zignorowane, więcej szczegółów technicznych znajdziesz w . Niech będzie klasą funkcji mierzalnych i zdefiniuj:

Zdefiniuj miarę empiryczną

gdzie δ tutaj oznacza miarę Diraca . Miara empiryczna indukuje mapę podaną przez:

Załóżmy teraz, że P jest podstawową prawdziwą dystrybucją danych, która jest nieznana. Teoria procesów empirycznych ma na celu zidentyfikowanie klas, dla których obowiązują stwierdzenia takie jak:

  • jednostajne prawo wielkich liczb :

To znaczy, jak ,

jednakowo dla wszystkich .

W pierwszym przypadku klasa nazywana jest Gliveenko-Cantelli , a w drugim (przy założeniu ) klasa nazywana jest Donsker lub P- Donsker. Klasa Donskera to prawdopodobieństwo Glivenka-Cantelli przez zastosowanie twierdzenia Słuckiego .

Stwierdzenia te są prawdziwe dla pojedynczego , standardowo LLN , argumentów CLT w warunkach prawidłowości, a trudność w procesach empirycznych pojawia się, ponieważ wspólne oświadczenia są składane dla wszystkich . Intuicyjnie więc zbiór nie może być zbyt duży, a okazuje się, że geometria odgrywa bardzo ważną rolę.

Jednym ze sposobów mierzenia wielkości zestawu funkcji jest użycie tak zwanych liczb pokrywających . Numer kryjący

to minimalna liczba kulek potrzebnych do pokrycia zestawu (tutaj oczywiście zakłada się, że istnieje norma leżąca u podstaw ). Entropia to logarytm liczby okrywającej.

Poniżej podano dwa wystarczające warunki, przy których można udowodnić, że zestaw to Gliveenko-Cantelli lub Donsker.

Klasa to P -Glivenko-Cantelli, jeśli jest P -mierzalna z obwiednią F taką, że i spełnia:

Następnym warunkiem jest wersja słynnego twierdzenia Dudleya . Jeśli jest klasą funkcji taką, że

to jest P- Donsker dla każdej miary prawdopodobieństwa P takiej, że . W ostatniej całce notacja oznacza

.

Symetryzacja

Większość argumentów dotyczących powiązania procesu empirycznego opiera się na symetryzacji, nierównościach maksymalnych i koncentracji oraz na łańcuchu. Symetryzacja jest zwykle pierwszym etapem dowodu, a ponieważ jest używana w wielu dowodach uczenia maszynowego dotyczących ograniczania empirycznych funkcji straty (w tym dowodu nierówności VC, który jest omówiony w następnej sekcji), jest tutaj prezentowana.

Rozważ proces empiryczny:

Okazuje się, że istnieje związek między procesem empirycznym a następującym symetrycznym procesem:

Proces symetryczny jest procesem Rademachera , uzależnionym od danych . Dlatego jest to proces subgaussowski wynikający z nierówności Hoeffdinga .

Lemat (Symetryzacja). Dla każdego nie malejącego, wypukłego Φ: RR i klasy funkcji mierzalnych ,

Dowód lematu Symetryzacja polega na wprowadzeniu niezależnych kopii oryginalnych zmiennych (czasami określanych jako próbka widmo ) i zastąpieniu wewnętrznego oczekiwania LHS tymi kopiami. Po zastosowaniu nierówności Jensena można było wprowadzić różne znaki (stąd nazwa symetryzacja) bez zmiany oczekiwań. Dowód można znaleźć poniżej ze względu na jego pouczający charakter.

Dowód  —

Wprowadź „próbkę ducha” jako niezależne kopie . Dla stałych wartości jeden ma:

Dlatego nierówność Jensena :

Przyjmowanie oczekiwań w stosunku do daje:

Zauważ, że dodanie znaku minus przed terminem nie zmienia RHS, ponieważ jest to symetryczna funkcja i . Dlatego RHS pozostaje taka sama pod „zaburzeniem znaku”:

dla każdego . W związku z tym:

Na koniec używając najpierw nierówności trójkąta, a następnie wypukłości daje:

Gdzie ostatnie dwa wyrażenia na RHS są takie same, co kończy dowód.

Typowy sposób udowadniania empirycznych CLT, najpierw wykorzystuje symetryzację, aby przekazać proces empiryczny do danych, a następnie warunkowo argumentować na danych, wykorzystując fakt, że procesy Rademachera są prostymi procesami o ładnych właściwościach.

Połączenie VC

Okazuje się, że istnieje fascynujący związek między pewnymi kombinatorycznymi właściwościami zbioru a liczbami entropii. Liczby jednorodnego pokrycia można kontrolować pojęciem klas zbiorów Wapnika-Chervonenkisa - lub w skrócie zbiorów VC .

Rozważmy zbiór podzbiorów przestrzeni próbki . mówi się, że wybiera pewien podzbiór ze zbioru skończonego, jeśli dla niektórych . mówi się, że roztrzaska S, jeśli wybierze każdy z jego 2 n podzbiorów. VC indeks (podobny do wymiaru VC + 1, do odpowiednio wybranego zestawu klasyfikatorów) od jest najmniejsza n , dla których nie ma ustalonego rozmiaru n jest rozerwany .

Lemat Sauera stwierdza następnie, że liczba podzbiorów wybranych przez klasę VC spełnia:

Jest to wielomianowa liczba podzbiorów, a nie liczba wykładnicza. Intuicyjnie oznacza to, że skończony indeks VC implikuje, że ma pozornie uproszczoną strukturę.

Podobną granicę można pokazać (z inną stałą, taką samą szybkością) dla tzw. klas podgrafów VC . Dla funkcji subgraph jest podzbiorem takie, że: . Zbiór wartości nazywa się klasą podgrafu VC, jeśli wszystkie podgrafy tworzą klasę VC.

Rozważmy zestaw funkcji sygnalizacyjnych w na dyskretnych empirycznych rodzaj środka Q (lub równoważnie do każdego środka prawdopodobieństwo Q ). Można więc wykazać, że całkiem godne uwagi, bo :

Rozważmy dalej symetryczną wypukłą powłokę zbioru : będącą zbiorem funkcji formy z . A następnie, jeśli

dla wypukłego kadłuba obowiązują następujące zasady :

Ważną konsekwencją tego faktu jest to, że

co wystarczy, aby całka entropii była zbieżna, a zatem klasą będzie P- Donsker.

Na koniec rozważymy przykład klasy podgrafu VC. Każda skończenie wymiarowa przestrzeń wektorowa funkcji mierzalnych jest podgrafem VC o indeksie mniejszym lub równym .

Dowód: Zbieraj punkty . Wektory:

znajdują się w n − 1 wymiarowej podprzestrzeni R n . Weź ≠ 0 , wektor, który jest prostopadły do tej podprzestrzeni. W związku z tym:

Rozważ zestaw . Ten zestaw nie może być wybrany, ponieważ jeśli jest taki, który sugerowałby, że LHS jest ściśle dodatni, ale RHS jest niedodatni.

Istnieją uogólnienia pojęcia klasy podgrafu VC, np. istnieje pojęcie pseudowymiaru. Zainteresowany czytelnik może zajrzeć.

Nierówność VC

Rozważane jest podobne ustawienie, które jest częstsze w przypadku uczenia maszynowego . Niech jest przestrzenią fabularną i . Funkcja nazywa się klasyfikatorem. Niech będzie zbiorem klasyfikatorów. Podobnie jak w poprzedniej sekcji, zdefiniuj współczynnik rozbicia (znany również jako funkcja wzrostu):

Zauważ tutaj, że istnieje przejście 1:1 między każdą z funkcji w a zbiorem, w którym funkcja ma wartość 1. Możemy zatem zdefiniować jako zbiór podzbiorów uzyskanych z powyższego mapowania dla każdego . Dlatego w odniesieniu do poprzedniej sekcji współczynnik rozbicia jest dokładnie

.

Ta równoważność wraz z Lematem Sauera implikuje, że będzie to wielomian in n , dla wystarczająco dużego n, pod warunkiem, że zbiór ma skończony indeks VC.

Let jest obserwowanym zbiorem danych. Załóżmy, że dane są generowane przez nieznany rozkład prawdopodobieństwa . Zdefiniuj jako oczekiwaną stratę 0/1 . Oczywiście, ponieważ ogólnie nie wiadomo, nie ma dostępu do . Jednak ryzyko empiryczne , podane przez:

z pewnością można ocenić. Wtedy mamy następujące Twierdzenie:

Twierdzenie (nierówność VC)

Dla klasyfikacji binarnej i funkcji straty 0/1 mamy następujące granice uogólnienia:

Mówiąc słowami, nierówność VC mówi, że wraz ze wzrostem próby, pod warunkiem, że ma ona skończony wymiar VC, empiryczne ryzyko 0/1 staje się dobrym przybliżeniem dla oczekiwanego ryzyka 0/1. Zauważ, że obie RHS dwóch nierówności będą zbieżne do 0, pod warunkiem, że rośnie wielomianowo w n .

Związek między tą ramą a ramą procesu empirycznego jest oczywisty. Tutaj mamy do czynienia ze zmodyfikowanym procesem empirycznym

ale nic dziwnego, że pomysły są takie same. Dowód (pierwszej części) nierówności VC polega na symetryzacji, a następnie warunkowo argumentuje na danych z wykorzystaniem nierówności koncentracji (w szczególności nierówności Hoeffdinga ). Zainteresowany czytelnik może zapoznać się z książką Twierdzenia 12.4 i 12.5.

Bibliografia

  • ^ Vapnik, Włodzimierz N (2000). Istota statystycznej teorii uczenia się . Informatyka i statystyka. Springer-Verlag . Numer ISBN 978-0-387-98780-4.
  • Vapnik, Włodzimierz N (1989).Statystyczna teoria uczenia się. Wiley-Interscience . Numer ISBN 978-0-471-03003-4.
  • ^ van der Vaart, Aad W .; Wellner, Jon A. (2000). Słaba konwergencja i procesy empiryczne: z zastosowaniami do statystyki (wyd. 2). Skoczek. Numer ISBN 978-0-387-94640-5.
  • ^ Gyorfi, L.; Devroye, L.; Lugosi, G. (1996). Probabilistyczna teoria rozpoznawania wzorców (wyd. 1). Skoczek. Numer ISBN 978-0387946184.
  • Zobacz odnośniki w artykułach: Richard M. Dudley , Procesy empiryczne , Rozbity zbiór .
  • ^ Pollard, Dawid (1990).Procesy empiryczne: teoria i zastosowania. NSF-CBMS Regionalna seria konferencji na temat prawdopodobieństwa i statystyki, tom 2. ISBN 978-0-940600-16-4.
  • Bukiet, O.; Boucheron, S.; Lugosi, G. (2004). „Wprowadzenie do statystycznej teorii uczenia się”. W O. Bousquet; U. von Luxburg; G. Ratsch (red.). Zaawansowane wykłady z uczenia maszynowego . Notatki z wykładu w sztucznej inteligencji. 3176 . Skoczek. s. 169–207.
  • Vapnik, V.; Czerwonenki, A. (2004). „O jednolitej zbieżności względnych częstotliwości zdarzeń do ich prawdopodobieństw”. Teoria prawdopodobieństwa. Zał . 16 (2): 264–280. doi : 10.1137/1116025 .