Como calcular a dimensão VC?

12

Estou estudando aprendizado de máquina e gostaria de saber como calcular a dimensão VC.

Por exemplo:

h(x)={1if axb0else  , com os parâmetros(a,b)R2 .

Qual é a dimensão VC dele?

铭 声 孙
fonte

Respostas:

10

A dimensão VC é uma estimativa da capacidade de um classificador binário. Se você puder encontrar um conjunto de pontos, para que ele possa ser quebrado pelo classificador (ou seja, classifique corretamente todas as 2 n etiquetas possíveis ) e não poderá encontrar nenhum conjunto de n + 1 pontos que possam ser quebrados (ou seja, para qualquer conjunto de n + 1 pontos, há pelo menos uma ordem de rotulagem para que o classificador não possa separar todos os pontos corretamente), então a dimensão VC é n .n2nn+1n+1n

No seu caso, primeiro considere dois pontos e x 2 , de modo que x 1 < x 2 . Depois, existem 2 2 = 4 rotulações possíveisx1x2x1<x222=4

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

Todas as etiquetas podem ser obtidas através do classificador , definindo os parâmetros a < b R de modo queha<bR

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

respectivamente. (Na verdade, pode ser assumido WLOG mas é suficiente para encontrar um conjunto que pode ser quebrado.)x1<x2

Agora, considere três pontos arbitrários (!) , x 2 , x 3 e o wlog assume x 1 < x 2 < x 3 , então você não pode obter o rótulo (1,0,1). Como no caso 3 acima, os rótulos x 1 : 1 ex 2 : 0 implicam a < x 1 < b < x 2 . O que implica x 3 > be, portanto, o rótulo de x 3x1x2x3x1<x2<x3x1x2a<x1<b<x2x3x3 deve ser 0. Portanto, o classificador não pode quebrar nenhum conjunto de três pontos e, portanto, a dimensão VC é 2.

-

Talvez fique mais claro com um classificador mais útil. Vamos considerar hiperplanos (isto é, linhas em 2D).

É fácil encontrar um conjunto de três pontos que podem ser classificados corretamente, independentemente de como eles são rotulados:

insira a descrição da imagem aqui

Para todas as marcações possíveis , podemos encontrar um hiperplano que as separa perfeitamente.23=8

No entanto, não podemos encontrar nenhum conjunto de 4 pontos para que possamos classificar corretamente todas as rotulações possíveis. Em vez de uma prova formal, tento apresentar um argumento visual:24=16

Suponha, por enquanto, que os 4 pontos formem uma figura com 4 lados. É impossível encontrar um hiperplano que possa separar os pontos corretamente se rotularmos os cantos opostos com o mesmo rótulo:

Se eles não formarem uma figura com 4 lados, existem dois "casos de limite": Os pontos "externos" devem formar um triângulo ou todos formar uma linha reta. No caso do triângulo, é fácil ver que a rotulagem onde o ponto "interno" (ou o ponto entre dois cantos) é rotulado diferente dos outros não pode ser alcançada:

No caso de um segmento de linha, a mesma ideia se aplica. Se os pontos finais forem rotulados de maneira diferente de um dos outros pontos, eles não poderão ser separados por um hiperplano.

Como cobrimos todas as formações possíveis de 4 pontos em 2D, podemos concluir que não há 4 pontos que possam ser quebrados. Portanto, a dimensão VC deve ser 3.

oW_
fonte
11
> Mas a função pode atingir x1 = 0, x2 = 0, x3 = 0. Precisa alcançar todos os rótulos?
铭声孙
Fiz uma pergunta semelhante aqui datascience.stackexchange.com/questions/39064/…, que está no contexto de uma função de hipótese linear. Você poderia ajudar a responder isso?
Suhail Gupta
3

A dimensão VC de um classificador é determinada da seguinte maneira:

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

Portanto, deve haver apenas uma maneira de colocar três pontos, de modo que todas as distribuições de classe possíveis entre essa colocação de pontos possam ser classificadas da maneira correta.

Se você não colocar os três pontos em uma linha, a percepção acertará. Mas não há como obter que a percepção classifique todas as distribuições de classes possíveis de 4 pontos, não importa como você os coloque

Seu exemplo

R

VC-Dimension 2: pode classificar todas as quatro situações corretamente.

  1. Pontos: 0 e 42
  2. Distribuições:
    • a=1337,b=3141
    • a=40,b=1337
    • a=1,b=1
    • a=1,b=1337

VC-Dimensão 3: Não, isso não funciona. Imagine as aulas truee falsesendo ordenadas como True False True. Seu classificador não pode lidar com isso. Portanto, ele tem uma dimensão VC de 2.

Prova

x1,x2,x3Rx1<x2<x3

x1x2x3

x1

ax1b
x2
x2<a or b<x2
ax1x1<x2b<x2
ax1b<x2<x3
x3
ax3b
b<x3. Portanto, não é possível classificar todas as distribuições de classe de três pontos corretamente com este classificador. Portanto, ele não possui a dimensão 3 do VC.
Martin Thoma
fonte
11
um classificador constante possui a dimensão 0 do VC (mesmo que alguém possa argumentar que não deve ser considerado um classificador em primeiro lugar)
oW_
11
Oh, certo. Mas sim, eu não chamaria um sistema que não possa se adaptar aos dados em um classificador em um contexto de aprendizado de máquina.
Martin Thoma