Wymiar VC to liczba bitów informacji (próbek) potrzebnych do znalezienia określonego obiektu (funkcji) wśród zestawu obiektów (funkcji)N .
VCWymiar 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źnieNNlog2(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 danegoNxND={(x1,y1),(x2,y2),...,(xl,yl)}xiz 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 jestxiNxiϵϵ -close z prawdopodobieństwem ( - środowisko PAC ), potrzebna liczba bitów informacji (liczba próbek) będzie .1−δ(ϵ,δ)log2N/δϵ
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ϵ1−δlog2N/δϵ2
Zauważ, że wyniki w obu przypadkach są proporcjonalne do - podobnie jak w przypadku wyszukiwania binarnego.log2N
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).ϵ1−δϵ
___________________ 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 iVClog2NVCVC−log(δ)ϵVC−log(δ)ϵ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ϵ1−δ