VC-Dimensão do vizinho mais próximo k

Qual é a dimensão VC do algoritmo k-vizinho mais próximo se k for igual ao número de pontos de treinamento usados?

Contexto: Essa pergunta foi feita em um curso que eu faço e a resposta dada foi 0. Eu, no entanto, não entendo por que esse é o caso. Minha intuição é que a VC-Dimension seja 1, porque deve ser possível escolher dois modelos (isto é, conjuntos de pontos de treinamento) para que cada ponto seja rotulado como pertencendo a uma classe de acordo com o primeiro modelo e como pertencendo a outra classe de acordo com o segundo modelo, portanto, deve ser possível quebrar um único ponto. Onde está o erro no meu raciocínio?

Você diz que o algoritmo é: k - algoritmo vizinho mais próximo com k = número de pontos de treinamento usados. Eu defino isso como jms-k-vizinho mais próximo .

Como a dimensão VC é o maior número de pontos de treinamento que podem ser destruídos pelo algoritmo com erro de trem 0, a dimensão VC de jms-k-vizinho mais próximo pode ser apenas k ou 0.

1 instância de treinamento => k = 1: Durante o treinamento, o jms-1-vizinho mais próximo armazena exatamente esta instância. Durante a aplicação exatamente no mesmo conjunto de treinamento, a instância é a mais próxima da instância de treinamento armazenada (porque são iguais), portanto, o erro de treinamento é 0.

Então, eu concordo, a dimensão VC é pelo menos 1.

2 instâncias de treinamento => k = 2: Só pode haver um problema se os rótulos forem diferentes. Nesse caso, a questão é: como é tomada a decisão para um rótulo de classe. O voto majoritário não leva a um resultado (VC = 0?). Se usarmos voto majoritário ponderado inversamente pela distância, a dimensão do VC é 2 (supondo que não seja permitido ter a mesma instância de treinamento duas vezes com rótulos diferentes, pois caso a dimensão VC de todos os algoritmos seja 0 (eu acho)).

Não existe um algoritmo vizinho k-mais próximo, é mais uma família com a mesma idéia básica, mas com sabores diferentes quando se trata de detalhes da implementação.

Recursos utilizados: slides da dimensão VC de Andrew Moore