Comment calculer la dimension VC?

Im étudie l'apprentissage automatique, et je voudrais savoir comment calculer la dimension VC.

Par exemple:

$h(x)=\begin{cases} 1 &\mbox{if } a\leq x \leq b \\ 0 & \mbox{else } \end{cases}$ , avec les paramètres$(a,b) ∈ R^2$ .

Quelle en est la dimension VC?

La dimension VC est une estimation de la capacité d'un classificateur binaire. Si vous pouvez trouver un ensemble de points, de sorte qu'il puisse être brisé par le classificateur (c.-à-d. Classer correctement tous les 2 n étiquetages possibles ) et vous ne pouvez pas trouver un ensemble de n + 1 points qui peuvent être brisés (c.-à-d. Pour tout ensemble de n + 1 points, il y a au moins un ordre d'étiquetage pour que le classificateur ne puisse pas séparer tous les points correctement), alors la dimension VC est n .$n$$2^n$$n+1$$n+1$$n$

Dans votre cas, considérez d'abord deux points et x 2 , tels que x 1 < x 2 . Ensuite, il y a 2 2 = 4 étiquetages possibles$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$

Tous les étiquetages peuvent être obtenus via le classificateur en définissant les paramètres a < b ∈ R de telle sorte que$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$

respectivement. (En fait, peut être supposé wlog mais il suffit de trouver un ensemble qui peut être brisé.)$x_1 < x_2$

Maintenant, considérez trois points arbitraires (!) , x 2 , x 3 et wlog suppose x 1 < x 2 < x 3 , alors vous ne pouvez pas obtenir l'étiquetage (1,0,1). Comme dans le cas 3 ci-dessus, les étiquettes x 1 : 1 et x 2 : 0 impliquent a < x 1 < b < x 2 . Ce qui implique x 3 > b et donc l'étiquette de 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$ doit être 0. Ainsi, le classificateur ne peut briser aucun ensemble de trois points et donc la dimension VC est 2.

-

Peut-être que cela devient plus clair avec un classificateur plus utile. Prenons les hyperplans (c'est-à-dire les lignes en 2D).

Il est facile de trouver un ensemble de trois points qui peuvent être classés correctement, quelle que soit leur étiquette:

$2^3=8$

$2^4=16$

Supposons pour l'instant que les 4 points forment une figure à 4 côtés. Ensuite, il est impossible de trouver un hyperplan qui puisse séparer correctement les points si nous étiquetons les coins opposés avec la même étiquette:

S'ils ne forment pas une figure à 4 côtés, il y a deux "cas limites": Les points "externes" doivent soit former un triangle, soit former une ligne droite. Dans le cas du triangle, il est facile de voir que l'étiquetage où le point "intérieur" (ou le point entre deux coins) est étiqueté différemment des autres ne peut pas être réalisé:

Dans le cas d'un segment de ligne, la même idée s'applique. Si les points d'extrémité sont étiquetés différemment de l'un des autres points, ils ne peuvent pas être séparés par un hyperplan.

Puisque nous avons couvert toutes les formations possibles de 4 points en 2D, nous pouvons conclure qu'il n'y a pas 4 points qui peuvent être brisés. Par conséquent, la dimension VC doit être 3.

La dimension VC d'un classificateur est déterminée de la manière suivante:

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

Il ne doit donc y avoir qu'une seule façon de placer trois points de telle sorte que toutes les distributions de classes possibles parmi ce placement de points puissent être classées de la bonne façon.

Si vous ne placez pas les trois points sur une ligne, la perception est juste. Mais il n'y a aucun moyen pour que la perception classe toutes les distributions de classes possibles de 4 points, peu importe la façon dont vous placez les points

Votre exemple

$\mathbb{R}$

VC-Dimension 2: Il peut classer correctement les quatre situations.

1. Points: 0 et 42
2. Distributions:
   • $a = 1337, b=3141$
   • $a = 40, b = 1337$
   • $a = -1, b = 1$
   • $a = -1, b = 1337$

VC-Dimension 3: Non, cela ne fonctionne pas. Imaginez les classes trueet falseêtre ordonné comme True False True. Votre classificateur ne peut pas gérer cela. Par conséquent, il a une dimension VC de 2.

Preuve

$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$$ $b < x_3$. Par conséquent, il n'est pas possible de classer correctement toutes les distributions de classes de 3 points avec ce classificateur. Par conséquent, il n'a pas de dimension VC 3.