VC Dimensão da classe de classificadores polinomiais de grau $ n $

Question

Eu me deparei com esta declaração na página 85 do livro "Entendendo a aprendizagem de máquina: da teoria dos algoritmos" < / a>

A ideia geral é a seguinte:

Considere um problema de classificação binária com o domínio da instância sendo $ x=mathbb R $ .

Para cada $ n \ in \ mathbb n $ Deixe $ h_n $ ser a classe de polinômio classificados de grau $ n $ ; nomeadamente, $ h_n $ é o conjunto de todos os classificados da forma $ h (x)=operatorName {sinal} ( p (x)) $ , onde $ P \ Colon \ mathbb r \ to \ mathbb r $ é um polinomial de grau $ n $ .

Prove que a dimensão VC da $ h_n $ é $ N + 1 $ .

Answer 1

A ideia é que um polinômio de grau $ n $ tem no máximo $ n $ raízes, E assim pode mudar sinais no máximo $ n $ vezes. Portanto, nenhum polinômio de grau $ n $ pode formar um padrão alternado + - + -... ou - + - + ... de comprimento $ N + 2 $ . Isso mostra que a dimensão VC está no máximo $ n + 1 $ .

Por outro lado, para qualquer conjunto de $ N + 1 $ pares $ (x_1, y_1), \ ldots (x_ {n + 1}, y_ {n + 1}) $ , há um polinomial de grau $ n $ que os interppra, dada pela fórmula de interpolação de Lagrange. Usando $ y_i=pm 1 $ , você pode facilmente mostrar que qualquer conjunto de $ n +1 $ pontos está despedaçado. Portanto, a dimensão VC é exatamente $ n + 1 $ .