Dlaczego wymiar VC jest ważny?

Wikipedia mówi, że:

Wymiar VC to liczność największego zestawu punktów, które algorytm może rozbić.

Na przykład klasyfikator liniowy ma liczność n + 1. Moje pytanie brzmi: dlaczego nas to obchodzi? Większość zestawów danych, na których dokonuje się klasyfikacji liniowej, ma zwykle bardzo duże rozmiary i zawiera wiele punktów.

Co to jest wymiar VC

Jak wspomniano w @CPerkins, wymiar VC jest miarą złożoności modelu. Można to również zdefiniować w odniesieniu do zdolności do niszczenia punktów danych, takich jak, jak wspomniałeś, wikipedia.

Podstawowy problem

• Chcemy modelu (np. Jakiegoś klasyfikatora), który dobrze uogólnia na niewidzialnych danych.
• Jesteśmy ograniczeni do określonej ilości przykładowych danych.

Poniższy obraz (pobrany stąd ) pokazuje niektóre Modele ( do ) o różnej złożoności (wymiar VC), tutaj pokazane na osi x i nazwane .$\mathcal{S_1}$$\mathcal{S_k}$$h$

Obrazy pokazują, że wyższy wymiar VC pozwala na mniejsze ryzyko empiryczne (błąd, który model popełnia na przykładowych danych), ale wprowadza również wyższy przedział ufności. Ten przedział może być postrzegany jako pewność co do zdolności modelu do uogólnienia.

Niski wymiar VC (duże odchylenie)

Jeśli zastosujemy model o niskiej złożoności, wprowadzimy pewien rodzaj założenia (stronniczości) w odniesieniu do zestawu danych, np. Używając klasyfikatora liniowego zakładamy, że dane można opisać za pomocą modelu liniowego. Jeśli tak nie jest, naszego zadanego problemu nie można rozwiązać za pomocą modelu liniowego, na przykład ponieważ problem ma charakter nieliniowy. Skończy się to modelem o słabej wydajności, który nie będzie w stanie poznać struktury danych. Dlatego powinniśmy starać się unikać wprowadzania silnego uprzedzenia.

Wysoki wymiar VC (większy przedział ufności)

Po drugiej stronie osi X widzimy modele o większej złożoności, które mogą mieć tak dużą pojemność, że raczej zapamiętują dane, a nie uczą się ich ogólnej struktury, tj. Modelu się przerasta. Po zrozumieniu tego problemu wydaje się, że powinniśmy unikać skomplikowanych modeli.

Może się to wydawać kontrowersyjne, ponieważ nie będziemy wprowadzać uprzedzeń, tj. Mają niski wymiar VC, ale nie powinny również mieć wysokiego wymiaru VC. Problem ten ma głębokie korzenie w statystycznej teorii uczenia się i jest znany jako kompromis wariancji-odchylenia . W tej sytuacji powinniśmy być tak złożeni, jak to konieczne i tak uproszczone, jak to możliwe, dlatego porównując dwa modele, które kończą się tym samym błędem empirycznym, powinniśmy użyć mniej złożonego.

Mam nadzieję, że mógłbym wam pokazać, że kryje się za tym pojęcie VC.

Wymiar VC to liczba bitów informacji (próbek) potrzebnych do znalezienia określonego obiektu (funkcji) wśród zestawu obiektów (funkcji)$N$ .

$VC$Wymiar pochodzi z podobnej koncepcji w teorii informacji. Teoria informacji rozpoczęła się od obserwacji Shannona:

Jeśli masz obiektów, a wśród tych obiektów szukasz konkretnego. Ile fragmentów informacji potrzebujesz, aby znaleźć ten obiekt ? Możesz podzielić swój zestaw obiektów na dwie połowy i zapytać „W jakiej połowie znajduje się obiekt, którego szukam?” . Otrzymasz „tak”, jeśli jest w pierwszej połowie lub „nie”, jeśli jest w drugiej połowie. Innymi słowy, otrzymujesz 1 bit informacji . Następnie zadajesz to samo pytanie i dzielisz zestaw raz za razem, aż w końcu znajdziesz pożądany obiekt. Ile informacji potrzebujesz (odpowiedzi tak / nie )? Jest wyraźnie$N$$N$$log_2(N)$ bity informacji - podobnie jak problem wyszukiwania binarnego z posortowaną tablicą.

Vapnik i Chernovenkis zadali podobne pytanie w kwestii rozpoznawania wzorców. Załóżmy, że masz zestaw funkcji dla danego wejścia , każda funkcja generuje tak lub nie (nadzorowany problem z klasyfikacją binarną), a wśród tych funkcji szukasz konkretnej funkcji, która daje prawidłowe wyniki tak / nie dla danego zestawu danych . Możesz zadać pytanie: „Które funkcje zwracają„ nie ”, a które zwracają„ tak ” dla danego$N$$x$$N$$D=\{(x_1,y_1), (x_2, y_2), ..., (x_l, y_l)\}$$x_i$z twojego zestawu danych. Ponieważ wiesz, jaka jest prawdziwa odpowiedź na podstawie posiadanych danych treningowych, możesz odrzucić wszystkie funkcje, które dają błędną odpowiedź dla niektórych . Ile fragmentów informacji potrzebujesz? Innymi słowy: ile przykładów szkoleń potrzebujesz, aby usunąć te wszystkie nieprawidłowe funkcje? . Oto niewielka różnica w stosunku do obserwacji Shannona w teorii informacji. Nie dzielisz zestawu funkcji na dokładnie połowę (może tylko jedna funkcja z daje niepoprawną odpowiedź dla niektórych ), a może twój zestaw funkcji jest bardzo duży i wystarcza, aby znaleźć funkcję, która jest -close do żądanej funkcji i chcesz mieć pewność, że ta funkcja jest$x_i$$N$$x_i$$\epsilon$$\epsilon$ -close z prawdopodobieństwem ( - środowisko PAC ), potrzebna liczba bitów informacji (liczba próbek) będzie .$1-\delta$$(\epsilon, \delta)$$\frac{log_2N/\delta}{\epsilon}$

Załóżmy teraz, że wśród zestawu funkcji nie ma funkcji, która nie popełnia błędów. Tak jak poprzednio, wystarczy znaleźć funkcję -close z prawdopodobieństwem . Potrzebna liczba próbek to .$N$$\epsilon$$1-\delta$$\frac{log_2N/\delta}{\epsilon^2}$

Zauważ, że wyniki w obu przypadkach są proporcjonalne do - podobnie jak w przypadku wyszukiwania binarnego.$log_2N$

Załóżmy teraz, że masz nieskończony zestaw funkcji, a wśród tych funkcji chcesz znaleźć funkcję, która jest -zamknij najlepszą funkcję z prawdopodobieństwem . Załóżmy (dla uproszczenia ilustracji), że funkcje są ciągłe afiniczne (SVM) i znalazłeś funkcję, która jest bliska najlepszej funkcji. Jeśli przesunąłbyś nieco swoją funkcję, nie zmieni to wyników klasyfikacji, miałbyś inną funkcję, która klasyfikuje się z takimi samymi wynikami jak pierwsza. Możesz wziąć wszystkie takie funkcje, które dają te same wyniki klasyfikacji (błąd klasyfikacji) i policzyć je jako pojedynczą funkcję, ponieważ klasyfikują one twoje dane z tą samą stratą (linia na zdjęciu).$\epsilon$$1-\delta$$\epsilon$

^{___________________ Obie linie (funkcja) sklasyfikują punkty z takim samym sukcesem___________________}

Ile próbek potrzebujesz, aby znaleźć określoną funkcję z zestawu zbiorów takich funkcji (pamiętaj, że podzieliliśmy nasze funkcje na zestawy funkcji, w których każda funkcja daje takie same wyniki klasyfikacji dla danego zestawu punktów)? Tak mówi wymiar - jest zastępowany przez ponieważ masz nieskończoną liczbę funkcji ciągłych, które są podzielone na zestawy funkcji z tym samym błędem klasyfikacji dla określonych punktów. Liczba próbek, których potrzebujesz, to jeśli masz funkcję, która doskonale rozpoznaje i$VC$$log_2N$$VC$$\frac{VC -log(\delta)}{\epsilon}$$\frac{VC - log(\delta)}{\epsilon^2}$ jeśli nie masz idealnej funkcji w oryginalnym zestawie funkcji.

Oznacza to, że wymiar daje górną granicę (której nie można poprawić btw) dla wielu próbek potrzebnych do osiągnięcia błędu z prawdopodobieństwem .$VC$$\epsilon$$1-\delta$

Wymiar VC jest miarą złożoności modelu. Na przykład, biorąc pod uwagę wymiar VC Dvc, dobrą zasadą jest, że powinieneś mieć n = 10xDvc punktów danych, biorąc pod uwagę złożoność modelu.

Możesz go również użyć do utworzenia górnej granicy błędu testu.