Ajuste de pesos de la muestra en AdaBoost

Question

Estoy tratando de leer acerca de AdaBoost de Tibshirani (página 337 en adelante), y agradecería un poco de ayuda en la comprensión de lo mejor.

El libro dice que "Para cada una de las sucesivas iteración m = 2, 3, . . . , M la observación de pesos son individualmente modificado y el algoritmo de clasificación que se vuelve a aplicar a la ponderación de las observaciones. En el paso m, de esas observaciones que fueron clasificados erróneamente por el clasificador Gm−1 (x) inducida en el paso anterior tiene sus pesos de aumento, mientras que los pesos son la disminución de aquellos que fueron clasificados correctamente. Así como las iteraciones proceda, las observaciones que son difíciles de clasificar correctamente a recibir la influencia cada vez mayor. Cada una de las sucesivas clasificador es lo obligó a concentrarse en las formación de las observaciones que se pierden por las anteriores en la secuencia."

Yo no soy capaz de entender lo que significa "volver a aplicar el algoritmo para la ponderación de las observaciones". Digamos, por ejemplo, si yo estoy haciendo 2-clase de clasificación de textos, ¿qué estoy haciendo para mis observaciones (documento de vectores)? ¿Cómo funciona esta "fuerza" del clasificador a concentrarse en algunas muestras vs otros?

Answer 1

mpq ya ha explicado aumento en la llanura inglés.

Una imagen puede sustituir más que mil palabras ... (robado de R. Meir y G. Rätsch. Una introducción a impulsar y aprovechar)

Imagen de la observación: En la 1ª Iteración el clasificador basado en todos los puntos de datos clasifica todos los puntos correctamente, excepto aquellos en x<0.2/y>0,8 y el punto de alrededor de 0.4/0.55 (ver los círculos en la segunda foto). En la segunda iteración exactamente los puntos de obtener un mayor peso, por lo que el clasificador basado en que la muestra ponderada clasifica correctamente (2ª Iteración, agregó línea discontinua). La combinación de clasificadores (es decir, "la combinación de las líneas de puntos") resultado en el clasificador representa por la línea verde. Ahora el segundo clasificador produce otro missclassifications (x) en [0.5,0.6] / y en [0.3,0.4]), que adquieren un mayor enfoque en la tercera iteración y así sucesivamente y así sucesivamente. En cada paso, la combinación de la clasificadora se acerca más y más cerca de la mejor forma (aunque no de forma continua). El final clasificador (es decir, la combinación de todos solo clasificadores) en el 100 Iteración clasifica todos los puntos correctamente.

Ahora debería ser más claro cómo impulsar obras. Quedan dos preguntas acerca de los detalles algorítmicos.

1. Cómo estimar missclassifications ?

En cada iteración, sólo una muestra de los datos de entrenamiento disponibles en esta iteración se utiliza para el entrenamiento del clasificador, el resto se utiliza para estimar el error / la missclassifications.

2. Cómo aplicar los pesos ?

Puede hacerlo de las siguientes maneras:

• Se muestra los datos utilizando una muestra adecuada algoritmo que puede manejar pesos (por ejemplo, ponderado muestreo aleatorio o rechazo de muestreo) y construir el modelo de clasificación en la muestra. La muestra resultante contiene missclassified ejemplos con mayor probabilidad que los clasificados correctamente, por lo tanto el modelo aprendido en esa muestra se ve obligado a concentrarse en la missclassified parte del espacio de datos.
• Utiliza un modelo de clasificación que es capaz de manejar estos pesos, implícitamente, como por ejemplo, los Árboles de Decisión. DT simplemente contar. Así que en lugar de utilizar 1 como contador/incremento de si un ejemplo con un cierto predictor y los valores de la clase, se utiliza el peso determinado w. Si w = 0, el ejemplo es prácticamente ignorada. Como resultado, el missclassified ejemplos tienen más influencia en la clase de probabilidad estimada por el modelo.

Con respecto a su documento de ejemplo:

Imagina una palabra que separa a las clases perfectamente, pero solo aparece en una determinada parte del espacio de datos (es decir, cerca de la decisión de la frontera). A continuación, la palabra no tiene el poder para separar todos los documentos (de ahí su expresividad para todo el conjunto de datos es baja), pero sólo los que están cerca del límite (donde la expresividad es alto). Por lo tanto los documentos que contengan esta palabra, serán clasificados erróneamente en la primera iteración(s), y por lo tanto obtener un mayor enfoque en las solicitudes posteriores. La restricción de la dataspace a la frontera (por documento de ponderación), el clasificador se puede/debe detectar la expresividad de la palabra y clasificar los ejemplos en que el subespacio correctamente.

(Dios me ayude, no puedo pensar de una forma más precisa ejemplo. Si la musa más tarde decide pasar algún tiempo conmigo, voy a editar mi respuesta).

Tenga en cuenta que aumentar asume débil de los clasificadores. E. g. Impulsar aplica junto con la NaiveBayes tendrá ningún efecto significativo (al menos en cuanto a mi experiencia).

edit: Añadido algunos detalles sobre el algoritmo y la explicación de la imagen.