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

12

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

Например:

h(x)={1if axb0else  , с параметрами(a,b)R2 .

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

铭 声 孙
источник

Ответы:

10

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

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

  1. , х 2 : 1x1:1x2:1
  2. , х 2 : 0x1:0x2:0
  3. , х 2 : 0x1:1x2:0
  4. , х 2 : 1x1:0x2:1

Все маркировки могут быть достигнуты с помощью классификатора путем установки параметров a < b R таким образом, чтобыha<bR

  1. a<x1<x2<b
  2. x1<x2<a<b
  3. a<x1<b<x2
  4. x1<a<x2<b

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

Теперь рассмотрим три произвольных (!) Точки , 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 3x1x2x3x1<x2<x3x1x2a<x1<b<x2x3x3 должно быть 0. Таким образом, классификатор не может разбить любой набор из трех точек, и, следовательно, размерность VC равна 2.

-

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

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

введите описание изображения здесь

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

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

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

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

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

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

oW_
источник
1
> Но функция может достигать x1 = 0, x2 = 0, x3 = 0. Это нужно для достижения всех ярлыков?
孙 声 孙
Я задал похожий вопрос здесь: datascience.stackexchange.com/questions/39064/…, который относится к функции линейной гипотезы. Не могли бы вы помочь ответить на это?
Сухаил Гупта
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 баллам, независимо от того, как вы расставили баллы

Ваш пример

р

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

  1. Очки: 0 и 42
  2. Распределения:
    • aзнак равно1337,бзнак равно3141
    • aзнак равно40,бзнак равно1337
    • aзнак равно-1,бзнак равно1
    • aзнак равно-1,бзнак равно1337

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

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

Икс1,Икс2,Икс3рИкс1<Икс2<Икс3

Икс1Икс2Икс3

Икс1

aИкс1б
Икс2 требуется. В виде х 1 и х 1 < х 2 , она должна быть Ь
Икс2<a or b<x2
aИкс1Икс1<Икс2б<Икс2
aИкс1б<Икс2<Икс3
Икс3
aИкс3б
б<Икс3, Следовательно, с помощью этого классификатора невозможно правильно классифицировать все распределения классов любых трех точек. Следовательно, он не имеет размерности VC 3.
Мартин Тома
источник
1
постоянный классификатор имеет VC-измерение 0 (хотя можно утверждать, что его не следует считать классификатором в первую очередь)
oW_
1
О верно. Но да, я бы не назвал систему, которая вообще не может адаптироваться к данным, классификатором в контексте машинного обучения.
Мартин Тома