Как рассчитать VC-размерность?

Я изучаю машинное обучение, и я хотел бы знать, как рассчитать VC-измерение.

Например:

$h(x)=\begin{cases} 1 &\mbox{if } a\leq x \leq b \\ 0 & \mbox{else } \end{cases}$ , с параметрами$(a,b) ∈ R^2$ .

Каково его VC-измерение?

Измерение VC является оценкой возможностей двоичного классификатора. Если вы можете найти набор из точек, чтобы он мог быть разбит классификатором (т.е. правильно классифицировать все возможные 2 n маркировок), и вы не можете найти ни одного набора из n + 1 точек, которые можно разбить (т.е. для любого набора из n + 1 балл, есть хотя бы один порядок маркировки, чтобы классификатор не мог правильно разделить все точки), тогда размерность VC равна n .$n$$2^n$$n+1$$n+1$$n$

В вашем случае сначала рассмотрим две точки и x 2 , такие что x 1 < x 2 . Тогда есть 2 2 = 4 возможных маркировки$x_1$$x_2$$x_1 < x_2$$2^2=4$

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

Все маркировки могут быть достигнуты с помощью классификатора путем установки параметров a < b ∈ R таким образом, чтобы$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$

соответственно. (На самом деле, можно считать wlog, но этого достаточно, чтобы найти один набор, который можно разбить.)$x_1 < x_2$

Теперь рассмотрим три произвольных (!) Точки , x 2 , x 3 и предположим, что x 1 < x 2 < x 3 , тогда вы не сможете добиться маркировки (1,0,1). Как и в случае 3 выше, метки x 1 : 1 и x 2 : 0 означают a < x 1 < b < x 2 . Что подразумевает x 3 > b и, следовательно, метку 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$ должно быть 0. Таким образом, классификатор не может разбить любой набор из трех точек, и, следовательно, размерность VC равна 2.

-

Может быть, это станет понятнее с помощью более полезного классификатора. Давайте рассмотрим гиперплоскости (т.е. линии в 2D).

Легко найти набор из трех точек, которые можно классифицировать правильно, независимо от того, как они помечены:

Для всех возможных маркировок мы можем найти гиперплоскость, которая идеально их разделяет.$2^3=8$

Однако мы не можем найти какой-либо набор из 4 точек, чтобы мы могли правильно классифицировать все возможных обозначений. Вместо формального доказательства я пытаюсь представить визуальный аргумент:$2^4=16$

Предположим пока, что 4 точки образуют фигуру с 4 сторонами. Тогда невозможно найти гиперплоскость, которая может правильно разделить точки, если мы пометим противоположные углы одинаковыми метками:

Если они не образуют фигуру с четырьмя сторонами, существует два «граничных случая»: «внешние» точки должны либо образовывать треугольник, либо все они должны образовывать прямую линию. В случае треугольника легко увидеть, что маркировка, в которой «внутренняя» точка (или точка между двумя углами) помечена как отличная от других, не может быть достигнута:

В случае отрезка применяется та же идея. Если конечные точки помечены не так, как другие, они не могут быть разделены гиперплоскостью.

Поскольку мы рассмотрели все возможные формации из 4 точек в 2D, мы можем заключить, что нет 4 точек, которые можно разбить. Следовательно, размер VC должен быть 3.

Измерение VC классификатора определяется следующим образом:

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

Таким образом, должен быть только один способ размещения трех точек так, чтобы все возможные распределения классов среди этого размещения точек были классифицированы правильным образом.

Если вы не разместите три точки на линии, восприятие будет правильным. Но нет способа заставить восприятие классифицировать все возможные распределения классов по 4 баллам, независимо от того, как вы расставили баллы

Ваш пример

$\mathbb{R}$

VC-Dimension 2: он может правильно классифицировать все четыре ситуации.

1. Очки: 0 и 42
2. Распределения:
   • $a = 1337, b=3141$
   • $a = 40, b = 1337$
   • $a = -1, b = 1$
   • $a = -1, b = 1337$

VC-Dimension 3: Нет, это не работает. Представьте себе классы trueи falseпорядок как True False True. Ваш классификатор не может справиться с этим. Следовательно, он имеет VC-размерность 2.

доказательство

$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$ требуется. В виде ≤ х 1 и х 1 < х 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$, Следовательно, с помощью этого классификатора невозможно правильно классифицировать все распределения классов любых трех точек. Следовательно, он не имеет размерности VC 3.