Wymiar Vapnika-Chervonenkisa (VC) jest miarą zdolności postawionej hipotezy do dopasowania do różnych zbiorów danych. Została wprowadzona przez Władimira Vapnika i Aleksieja Chervonenkisa w latach 70. XX wieku i stała się podstawowym pojęciem w statystycznej teorii uczenia się. Wymiar VC jest miarą złożoności modelu, która może pomóc nam zrozumieć, jak dobrze może on pasować do różnych zbiorów danych.
Wymiar VC zbioru hipotez H to największa liczba punktów, które mogą zostać rozbite przez H. Zbiór hipotez H rozbija zbiór punktów S, jeśli dla każdego możliwego etykietowania punktów w S istnieje hipoteza w H, która poprawnie klasyfikuje punkty. Innymi słowy, zestaw hipotez rozbija zbiór punktów, jeśli pasuje do dowolnego możliwego oznakowania tych punktów.
dołączanie ciągu w Javie
Granice VC – wymiar
Wymiar VC zapewnia zarówno górną, jak i dolną granicę liczby przykładów szkoleniowych wymaganych do osiągnięcia danego poziomu dokładności. Górna granica liczby przykładów szkoleniowych jest logarytmiczna w wymiarze VC, podczas gdy dolna granica jest liniowa.
Zastosowania VC – wymiar
Wymiar VC ma szeroki zakres zastosowań w nauczanie maszynowe i statystyki. Na przykład służy do analizy złożoności sieci neuronowych, maszyn wektorów nośnych i drzew decyzyjnych. Wymiar VC można również wykorzystać do projektowania nowych algorytmów uczenia się, które są odporne na szumy i potrafią dobrze generalizować na niewidoczne dane.
Wymiar VC można rozszerzyć na bardziej złożone scenariusze uczenia się, takie jak klasyfikacja wieloklasowa i regresja. Koncepcję wymiaru VC można również zastosować w innych obszarach informatyki, takich jak geometria obliczeniowa i teoria grafów.
Implementacja kodu dla VC – Dimension
Wymiar VC to koncepcja teoretyczna, której nie można bezpośrednio obliczyć na podstawie danych. Możemy jednak oszacować wymiar VC dla danego zestawu hipotez, zliczając liczbę punktów, które zestaw może rozbić. W Pythonie możemy zaimplementować funkcję, która oblicza wymiar VC danego zestawu hipotez, stosując to podejście.
Funkcja przyjmuje postawioną hipotezę jako dane wejściowe i oblicza wymiar VC, stosując metodę brutalnej siły polegającą na sprawdzaniu wszystkich możliwych kombinacji punktów i etykiet. Wykorzystuje moduł itertools do generowania wszystkich możliwych kombinacji punktów i etykiet, a następnie sprawdza, czy zestaw hipotez może zniszczyć każdą kombinację. Funkcja zwraca szacunkowy wymiar VC zestawu hipotez.
Zilustrujmy użycie tej funkcji na kilku przykładach:
Przykład 1:
Załóżmy, że mamy zestaw hipotez składający się ze wszystkich funkcji liniowych w postaci f(x) = ax + b, gdzie a i b są liczbami rzeczywistymi. Możemy zdefiniować tę hipotezę ustawioną w Pythonie w następujący sposób:
Pyton
import> itertools> > > def> vc_dimension(hypothesis_set):> >'''> >Estimates the VC dimension of a hypothesis set using the brute-force approach.> >'''> >n>=> 4> >while> True>:> >points>=> [(i, j)>for> i>in> range>(n)>for> j>in> range>(>2>)]> >shattered_sets>=> 0> >for> combination>in> itertools.combinations(points, n):> >is_shattered>=> True> >for> labeling>in> itertools.product([>0>,>1>], repeat>=>n):> >hypotheses>=> [hypothesis_set(point)>for> point>in> combination]> >if> set>(hypotheses) !>=> set>(labeling):> >is_shattered>=> False> >break> >if> is_shattered:> >shattered_sets>+>=> 1> >else>:> >break> >if> not> is_shattered:> >break> >n>+>=> 1> >return> n>->1> if> shattered_sets>=>=> 2>*>*>n>else> n>->2> > > # Example 1: linear function hypothesis set> def> linear_function(point):> >x, y>=> point> >return> int>(y>>=> x)> > > print>(vc_dimension(linear_function))> |
>
>
Wyjście:
2>
W przykładzie 1 funkcja linear_function implementuje prosty zestaw hipotez funkcji liniowej, który zwraca 1, jeśli współrzędna y punktu wejściowego jest większa lub równa współrzędnej x, i 0 w przeciwnym razie. Następnie używa się funkcji vc_dimension do oszacowania wymiaru VC tego zbioru hipotez, który wynosi 2.
Przykład 2:
Załóżmy, że mamy zestaw hipotez składający się ze wszystkich funkcji kwadratowych w postaci f(x) = ax2+ bx + c, gdzie a, b i c są liczbami rzeczywistymi. Możemy to zdefiniować hipoteza ustawić w Pythonie w następujący sposób:
Pyton
klucz ins
import> itertools> > > def> vc_dimension(hypothesis_set):> >'''> >Estimates the VC dimension of a hypothesis set using the brute-force approach.> >'''> >n>=> 5> >while> True>:> >points>=> [(i, j)>for> i>in> range>(n)>for> j>in> range>(>2>)]> >shattered_sets>=> 0> >for> combination>in> itertools.combinations(points, n):> >is_shattered>=> True> >for> labeling>in> itertools.product([>0>,>1>], repeat>=>n):> >hypotheses>=> [hypothesis_set(point)>for> point>in> combination]> >if> set>(hypotheses) !>=> set>(labeling):> >is_shattered>=> False> >break> >if> is_shattered:> >shattered_sets>+>=> 1> >else>:> >break> >if> not> is_shattered:> >break> >n>+>=> 1> >return> n>->1> if> shattered_sets>=>=> 2>*>*>n>else> n>->2> > > # Example 2: quadratic function hypothesis set> def> quadratic_function(point):> >x, y>=> point> >return> int>(y>>=> x>*>*>2>)> > > print>(vc_dimension(quadratic_function))> |
>
>
Wyjście:
3>
W przykładzie 2 funkcja quadratic_function implementuje bardziej złożony zestaw hipotez funkcji kwadratowej, który zwraca 1, jeśli współrzędna y punktu wejściowego jest większa lub równa kwadratowi współrzędnej x, i 0 w przeciwnym razie. Następnie używa się funkcji vc_dimension do oszacowania wymiaru VC tego zbioru hipotez, który wynosi 3.
Wniosek
Wymiar VC to podstawowe pojęcie statystycznej teorii uczenia się, które mierzy złożoność zestawu hipotez. Zapewnia zarówno górną, jak i dolną granicę liczby przykładów szkoleniowych wymaganych do osiągnięcia danego poziomu dokładności. W Pythonie możemy oszacować wymiar VC danego zestawu hipotez, stosując podejście brute-force, które sprawdza wszystkie możliwe kombinacje punktów i etykiet. Wymiar VC ma szeroki zakres zastosowań w uczeniu maszynowym i statystyce i można go rozszerzyć na bardziej złożone scenariusze uczenia się.