¿Es AdaBoost menos o más propenso al sobreajuste?

Question

He leído varias afirmaciones (aparentemente) contradictorias sobre si AdaBoost (u otras técnicas de boosting) son menos o más propensas al sobreajuste en comparación con otros métodos de aprendizaje.

¿Hay buenas razones para creer en una u otra? Si depende, ¿de qué depende? ¿Cuáles son las razones por las que AdaBoost es menos/más propenso al sobreajuste?

Answer 1

Como dices se ha discutido mucho sobre este asunto, y hay una teoría bastante pesada que lo acompaña que tengo que admitir que nunca entendí del todo. En mi experiencia práctica, AdaBoost es bastante robusto al sobreajuste, y LPBoost (Linear Programming Boosting) aún más (porque la función objetivo requiere una combinación dispersa de aprendices débiles, que es una forma de control de la capacidad). Los principales factores que influyen son:

• La "fuerza" de los aprendices "débiles": Si se utilizan aprendices débiles muy sencillos, como los tocones de decisión (árboles de decisión de 1 nivel), los algoritmos son mucho menos propensos al sobreajuste. Siempre que he intentado utilizar aprendices débiles más complicados (como árboles de decisión o incluso hiperplanos) he descubierto que el sobreajuste se produce mucho más rápidamente

• El nivel de ruido en los datos: AdaBoost es especialmente propenso a sobreajustarse en conjuntos de datos ruidosos. En este caso, son preferibles las formas regularizadas (RegBoost, AdaBoostReg, LPBoost, QPBoost).

• La dimensionalidad de los datos: Sabemos que, en general, experimentamos más el sobreajuste en espacios de alta dimensionalidad ("la maldición de la dimensionalidad"), y AdaBoost también puede sufrir en ese sentido, ya que es simplemente una combinación lineal de clasificadores que a su vez sufren el problema. Es difícil determinar si es tan propenso como otros clasificadores.

Por supuesto, puede utilizar métodos heurísticos como los conjuntos de validación o $k$ -fold cross-validation para establecer el parámetro de parada (u otros parámetros en las diferentes variantes) como lo haría para cualquier otro clasificador.

Answer 2

Estoy de acuerdo con la mayoría de los puntos mencionados en el comentario de tdc. sin embargo, tengo que añadir y corregir algunas cosas.

• Como se muestra en L2Boost de Peter Bühlmann, a medida que aumenta el número de aprendices débiles (rondas de boosting), el sesgo converge exponencialmente rápido mientras que la varianza aumenta en magnitudes geométricamente decrecientes, lo que significa: Que sobreadapta mucho más lentamente que la mayoría de los otros métodos.
• En el comentario de Zach se mencionó erróneamente que es mejor que el bosque aleatorio en términos de sobreajuste. Esto es completamente erróneo. De hecho, según la teoría (véase el artículo original de Breiman sobre el bosque aleatorio), el bosque aleatorio es absolutamente inmune al sobreajuste siempre que sus clasificadores débiles no se ajusten en exceso a los datos.
• A diferencia de lo mencionado en el comentario de tdc, la mayoría de los métodos de refuerzo son muy sensibles al ruido de etiquetado y pueden sobreajustarse fácilmente en presencia de ruido de etiquetado.
• En los conjuntos de datos en los que las tasas de error de Bayes están lejos de 0 (es decir, las características no son lo suficientemente discriminativas) los métodos de refuerzo pueden fácilmente sobreajustarse, también. Porque intentan reducir el error de entrenamiento a cero, mientras que en realidad incluso el clasificador óptimo, es decir, el clasificador de Bayes, puede alcanzar, digamos, una tasa de error del 40%.
• Por último, y esto no se ha publicado en ningún sitio (que yo sepa) existe un tipo de sobreajuste en el que el error de generalización no aumenta a medida que aumentan las rondas de boosting pero tampoco disminuye. Esto significa que el algoritmo se ha atascado en un óptimo local. En esta situación, el error de entrenamiento disminuye constantemente mientras que el error de prueba permanece casi constante. Hasta ahora, nunca habíamos considerado este fenómeno como una indicación de sobreajuste, pero creo que es una señal de sobreajuste y, al utilizar aprendices débiles más complejos, (¡extraño!) podemos, de hecho, ir en contra de ello (Este último punto debe considerarse con precaución :D)