¿Cómo se puede demostrar matemáticamente que el impulso no puede tener cero error en el conjunto de entrenamiento dispuestos en un cuadrado con las esquinas etiqueta más y menos?

Question

Tengo los siguientes datos:

Digamos que queremos perfectamente separados los puntos utilizando sólo un conjunto de horizontal y vertical de la decisión de los tocones. Tal vez el uso de Potenciar o Adaboost, pero el punto principal es cualquier conjunto de coordinar sabio ponderado de los tocones.

Parece intuitivamente "evidente" que este conjunto particular de datos no puede ser separado utilizando sólo los tocones. Sin embargo, no puedo convencer a mi mismo con una matemáticamente rigores prueba de ello. ¿Cómo se podía ir a probar rigurosamente esa afirmación?

Me preguntaba, si no también una generalización de la cantidad de puntos que se requieren para tener hasta el conjunto de los tocones de empezar a fallar para separar los datos perfectamente. Cuando sucede esto y cuál es su prueba?

Answer 1

En este conjunto de datos, hay cuatro cosas triviales que un tocón puede hacer:

• $s_1$ clasifica a la izquierda de los dos puntos como positivo;
• $s_2$ clasifica a la derecha de los dos puntos como positivo;
• $s_3$ clasifica a los dos primeros puntos positivos;
• $s_4$ clasifica la parte inferior dos puntos positivos.

Así que la función terminas aprendiendo podría ser cualquier cosa de la forma $$\hat y(x) = \sum_{i=1}^n f_i(x),$$ where each $f$ is one of the $s_j$.

Ahora, tenga en cuenta que cada copia de $s_1$ de esa suma se anula una copia de $s_2$, porque son opuestos, y de manera similar para$s_3$$s_4$. Por lo $\hat y$ es realmente un entero combinación de $\hat y(x) = a\,s_1(x) + b\,s_3(x)$.

Pero la primera mitad de esa expresión no cambia cuando se mueve de arriba a abajo, y la segunda mitad siempre cambia en la misma cantidad ($b$). Así que sabemos que la salida de $\hat y$ debe aumentar siempre como el punto de datos se mueve de arriba a abajo (si $b < 0$), o que siempre disminuyen (si $b > 0$).

• Si siempre aumenta cuando se mueve desde la parte superior a la parte inferior, a continuación, que no se puede obtener tanto en la parte superior-izquierda e inferior-izquierda de los puntos correcta (porque el de arriba es mayor que 0 y el de abajo es menor que 0).

• Si siempre disminuye, entonces del mismo modo que no se puede obtener tanto en la parte superior derecha e inferior derecha de los puntos correctos.

Por lo tanto, no es posible impulsado la suma de los tocones se puede clasificar el conjunto de datos perfectamente, QED.

(EDIT: hice la prueba más comprensible. El anterior era cierto, pero no proporcionan mucha intuición, y se me ocurrió una manera de hacer la intuitiva cosa sin demasiado análisis de caso.)