Dimensión VC de la clase de clasificadores polinomios de grado $ n $

Question

Me encontré con esta declaración en la página 85 del libro "Entendiendo el aprendizaje de la máquina: de la teoría a los algoritmos" < / a>

La idea general es la siguiente:

Considere un problema de clasificación binario con el dominio de la instancia $ x=mathbb r $ .

para cada $ n \ in \ mathbb n $ Let $ h_n $ ser la clase de polinomio Clasineros de grado $ n $ ; a saber, $ h_n $ es el conjunto de todos los clasificadores del formulario $ h (x)=operatorname {sign} ( p (x)) $ , donde $ P \ colon \ mathbb r \ to \ mathbb r $ es un polinomio de grado $ n $ .

Demuestre que la dimensión VC de $ h_n $ es $ n + 1 $ .

Answer 1

La idea es que un título de polinomio de grado $ n $ tiene en la mayoría $ n $ raíces, Y así, puede cambiar los signos en la mayoría de los $ n $ veces. Por lo tanto, no hay polinomio de grado $ n $ puede formar un patrón alterno + - + -... o - + - + ... de longitud $ n + 2 $ . Esto muestra que la dimensión VC está en la mayoría de $ n + 1 $ .

Por otro lado, para cualquier conjunto de $ n + 1 $ pares $ (x_1, y_1), \ ldots, (x_ {n + 1}, y_ {n + 1}) $ , hay un polinomio de grado $ n $ que los interpolan, Dado por la fórmula de interpolación de Lagrange. Uso de $ y_i=pm 1 $ , puede mostrar fácilmente que any conjunto de $ n +1 $ los puntos se rompen. Por lo tanto, la dimensión VC es exactamente $ n + 1 $ .