Jak obliczyć wymiar VC?

Studiuję uczenie maszynowe i chciałbym wiedzieć, jak obliczyć wymiar VC.

Na przykład:

$h(x)=\begin{cases} 1 &\mbox{if } a\leq x \leq b \\ 0 & \mbox{else } \end{cases}$ , z parametrami.$(a,b) ∈ R^2$

Jaki jest jego wymiar VC?

Wymiar VC jest oszacowaniem zdolności klasyfikatora binarnego. Jeśli możesz znaleźć zestaw punktów, aby mógł zostać rozbity przez klasyfikator (tj. Poprawnie sklasyfikuj wszystkie możliwe 2 n oznakowania) i nie możesz znaleźć żadnego zestawu n + 1 punktów, który można rozbić (tj. Dla dowolnego zestawu n + 1 punktów istnieje co najmniej jedna kolejność etykietowania, aby klasyfikator nie mógł poprawnie rozdzielić wszystkich punktów), wówczas wymiar VC wynosi n .$n$$2^n$$n+1$$n+1$$n$

W twoim przypadku najpierw rozważ dwa punkty i x 2 , tak aby x 1 < x 2 . Następnie są 2 2 = 4 możliwe oznaczenia$x_1$$x_2$$x_1 < x_2$$2^2=4$

1. , x 2 : $x_1:1$$x_2:1$
2. , x 2 : $x_1:0$$x_2:0$
3. , x 2 : $x_1:1$$x_2:0$
4. , x 2 : $x_1:0$$x_2:1$

Wszystkie oznaczenia można uzyskać za pomocą klasyfikatora , ustawiając parametry a < b ∈ R takie, że$h$$a<b \in R$

1. $a<x_1<x_2<b$
2. $x_1<x_2<a<b$
3. $a<x_1<b<x_2$
4. $x_1<a<x_2<b$

odpowiednio. (W rzeczywistości można założyć wlog, ale wystarczy znaleźć jeden zestaw, który można rozbić.)$x_1 < x_2$

Rozważmy teraz trzy arbitralne (!) Punkty , x 2 , x 3, a wlog zakłada x 1 < x 2 < x 3 , wtedy nie można osiągnąć oznaczenia (1,0,1). Podobnie jak w przypadku 3 powyżej, etykiety x 1 : 1 i x 2 : 0 oznaczają a < x 1 < b < x 2 . Co implikuje x 3 > b, a zatem etykietę x $x_1$$x_2$$x_3$$x_1<x_2<x_3$$x_1$$x_2$$a<x_1<b<x_2$$x_3$$x_3$ musi wynosić 0. Zatem klasyfikator nie może rozbić żadnego zestawu trzech punktów, a zatem wymiar VC wynosi 2.

-

Może staje się bardziej zrozumiały dzięki bardziej przydatnemu klasyfikatorowi. Rozważmy hiperpłaszczyzny (tj. Linie w 2D).

Łatwo jest znaleźć zestaw trzech punktów, które można poprawnie sklasyfikować bez względu na sposób ich oznaczenia:

Dla wszystkich możliwych etykiet możemy znaleźć hiperpłaszczyznę, która je doskonale oddziela.$2^3=8$

Nie możemy jednak znaleźć żadnego zestawu 4 punktów, abyśmy mogli poprawnie sklasyfikować wszystkie możliwych etykiet. Zamiast formalnego dowodu staram się przedstawić argument wizualny:$2^4=16$

Załóżmy na razie, że 4 punkty tworzą figurę z 4 bokami. Wówczas niemożliwe jest znalezienie hiperpłaszczyzny, która może poprawnie oddzielić punkty, jeśli oznaczymy przeciwległe rogi tą samą etykietą:

Jeśli nie tworzą figury z 4 bokami, istnieją dwa „przypadki graniczne”: „Zewnętrzne” punkty muszą albo tworzyć trójkąt, albo wszystkie tworzyć linię prostą. W przypadku trójkąta łatwo zauważyć, że nie można osiągnąć etykietowania, w którym punkt „wewnętrzny” (lub punkt między dwoma rogami) jest inny niż pozostałe:

W przypadku segmentu linii obowiązuje ten sam pomysł. Jeśli punkty końcowe są oznaczone inaczej niż jeden z innych punktów, nie można ich rozdzielić hiperpłaszczyzną.

Ponieważ omówiliśmy wszystkie możliwe formacje 4 punktów w 2D, możemy stwierdzić, że nie ma 4 punktów, które można by rozbić. Dlatego wymiar VC musi wynosić 3.

Wymiar VC klasyfikatora określa się w następujący sposób:

VC = 1
found = False
while True:
    for point_distribution in all possible point distributions of VC+1 points:
        allcorrect = True
        for classdist in every way the classes could be assigned to the classes:
            adjust classifier
            if classifier can't classify everything correct:
                allcorrect = False
                break
        if allcorrect:
            VC += 1
            continue
    break

Tak więc musi być tylko jeden sposób na umieszczenie trzech punktów, tak aby wszystkie możliwe rozkłady klas między tym rozmieszczeniem punktów mogły zostać sklasyfikowane we właściwy sposób.

Jeśli nie umieścisz trzech punktów na linii, percepcja zrobi to dobrze. Ale nie ma sposobu, aby uzyskać postrzeganie sklasyfikować wszystkie możliwe rozkłady klas 4 punktów, bez względu na to, jak umieścisz punkty

Twój przykład

$\mathbb{R}$

VC-Dimension 2: Może poprawnie sklasyfikować wszystkie cztery sytuacje.

1. Punkty: 0 i 42
2. Dystrybucje:
   • $a = 1337, b=3141$
   • $a = 40, b = 1337$
   • $a = -1, b = 1$
   • $a = -1, b = 1337$

Wymiar VC 3: Nie, to nie działa. Wyobraź sobie klasy truei falseporządek True False True. Twój klasyfikator nie może sobie z tym poradzić. Dlatego ma VC-Wymiar 2.

Dowód

$x_1, x_2, x_3 \in \mathbb{R}$$x_1 < x_2 < x_3$

$x_1$$x_2$$x_3$

$x_1$

$$a \leq x_1 \leq b$$ $x_2$ $$x_2 < a \qquad\text{ or }\qquad b < x_2$$ $a \leq x_1$$x_1 < x_2$$b < x_2$ $$a \leq x_1 \leq b < x_2 < x_3$$ $x_3$ $$a \leq x_3 \leq b$$ jest wymagane. Ale inne ograniczenia są już wymagane$b < x_3$. Dlatego nie jest możliwe prawidłowe sklasyfikowanie wszystkich rozkładów klas 3 dowolnych punktów za pomocą tego klasyfikatora. Dlatego nie ma wymiaru VC 3.