En el refuerzo, ¿por qué los alumnos son "débiles"?

Question

Ver también una pregunta similar en stats.SE .

En impulsando algoritmos como AdaBoost y LPBoost se sabe que los aprendices "débiles" que se combinan sólo tienen que rendir más que el azar para ser útiles, desde Wikipedia:

Los clasificadores que utiliza pueden ser débiles (es decir, mostrar una tasa de error considerable), pero siempre que su rendimiento no sea aleatorio (lo que supone una tasa de error de 0,5 para la clasificación binaria), mejorarán el modelo final. Incluso los clasificadores con una tasa de error superior a la que cabría esperar de un clasificador aleatorio serán útiles, ya que tendrán coeficientes negativos en la combinación lineal final de clasificadores y, por tanto, se comportarán como sus inversos.

• ¿Cuáles son las ventajas de utilizar estudiantes débiles en lugar de fuertes? (Por ejemplo, ¿por qué no potenciar con métodos de aprendizaje "fuertes", somos más propensos al sobreajuste?)

• ¿Existe algún tipo de fuerza "óptima" para los aprendices débiles? ¿Y está esto relacionado con el número de alumnos en el conjunto?

¿Hay alguna teoría que respalde las respuestas a estas preguntas?

Answer 1

Así, el boosting es un algoritmo de aprendizaje, que puede generar predicciones de alta precisión utilizando como subrutina otro algoritmo, que a su vez puede generar eficientemente hipótesis sólo ligeramente mejores (por un polinomio inverso) que la adivinación aleatoria.

Su principal ventaja es la velocidad.

Cuando Schapire lo presentó en 1990 fue un gran avance, ya que demostró que un aprendiz de tiempo polinómico que genera hipótesis con errores apenas menores a 1/2 puede transformarse en un aprendiz de tiempo polinómico que genera hipótesis con un error arbitrariamente pequeño.

Por lo tanto, la teoría que respalda su pregunta está en "La fuerza del aprendizaje débil" ( pdf ) donde básicamente demostró que el aprendizaje "fuerte" y el "débil" son equivalentes.

Y tal vez la respuesta a la pregunta original sea: "no tiene sentido construir aprendices fuertes cuando se pueden construir débiles más baratos".

---

De los documentos relativamente recientes, hay "Sobre la equivalencia de la aprendibilidad débil y la separabilidad lineal: nuevas relajaciones y algoritmos de refuerzo eficientes" ( pdf ) que no entiendo pero que parece estar relacionado y puede ser de interés para personas más cultas :)

Answer 2

Abordaré el tema del sobreajuste, que aún no se ha mencionado, con una explicación más intuitiva. Su primera pregunta era:

¿Cuáles son las ventajas de utilizar estudiantes débiles en lugar de fuertes? (Por ejemplo, ¿por qué no potenciar con métodos de aprendizaje "fuertes", somos más propensos al sobreajuste?)

Las principales razones, a mi entender, son:

• Velocidad Como ya se ha dicho en las otras respuestas;
• Mejora de la precisión Si ya tienes un alumno fuerte, los beneficios de la potenciación son menos relevantes;
• Evitar el sobreajuste Como ya has adivinado. Piénsalo de esta manera:

Lo que hace la potenciación es combinar muchos diferentes hipótesis del espacio de hipótesis para que terminemos con una hipótesis final mejor. El gran poder de la potenciación, por tanto, proviene de la diversidad de la hipótesis combinada.

Si utilizamos un aprendiz fuerte, esta diversidad tiende a disminuir: después de cada iteración no habrá muchos errores (ya que el modelo es complejo), lo que hará que el boosting no cambie mucho la nueva hipótesis. Con hipótesis muy parecidas, el conjunto será muy parecido a un único modelo complejo, ¡que a su vez tiende a sobreajustarse!

Answer 3

En el refuerzo utilizamos sobre todo a los alumnos débiles, ya que se les entrena más rápido que a los alumnos fuertes. Piensa en ello. Si utilizo una red neuronal multicapa como aprendiz, necesito entrenar muchas de ellas. Por otro lado, un árbol de decisión puede ser mucho más rápido, entonces puedo entrenar muchos de ellos.

Digamos que utilizo 100 alumnos. Entreno la NN en 100 segundos y el árbol de decisión en 10 segundos. Mi primer refuerzo con NN tardará 100*100 segundos mientras que el segundo refuerzo con el árbol de decisión tardará 100*10 segundos.

Dicho esto, he visto artículos, que utiliza a los estudiantes fuertes en el impulso. Pero en esos problemas que los aprendices fuertes eran rápidos en mi opinión.

Intenté entrenar el MLP en el conjunto de datos de detección de intrusos de la KDD99, (más de 4 millones) usando Weka. Me llevó más de 72 horas en mi máquina. Sin embargo, el entrenamiento (AdaBoostM1 con el árbol de decisión - Decision Stump) sólo tardó 3 horas. En este problema está claro que no puedo utilizar boosting con un aprendiz fuerte, es decir, un aprendiz que tarda demasiado tiempo.