AdaBoost

AdaBoost, abreviatura de Adaptive Boosting, es un metaalgoritmo de clasificación estadística formulado por Yoav Freund y Robert Schapire en 1995, quienes ganaron el Premio Gödel en 2003 por su trabajo. . Se puede utilizar junto con muchos otros tipos de algoritmos de aprendizaje para mejorar el rendimiento. El resultado de los otros algoritmos de aprendizaje ('estudiantes débiles') se combina en una suma ponderada que representa el resultado final del clasificador potenciado. Por lo general, AdaBoost se presenta para clasificación binaria, aunque se puede generalizar a múltiples clases o intervalos acotados en la línea real.

AdaBoost es adaptativo en el sentido de que los alumnos débiles posteriores se modifican a favor de aquellas instancias mal clasificadas por clasificadores anteriores. En algunos problemas, puede ser menos susceptible al problema de sobreajuste que otros algoritmos de aprendizaje. Los alumnos individuales pueden ser débiles, pero siempre que el desempeño de cada uno sea ligeramente mejor que las conjeturas aleatorias, se puede demostrar que el modelo final converge hacia un alumno fuerte.

Aunque AdaBoost se utiliza normalmente para combinar alumnos de base débiles (como fragmentos de decisiones), se ha demostrado que también puede combinar de forma eficaz alumnos de base sólidas (como árboles de decisión profundos), lo que produce un modelo aún más preciso.

Cada algoritmo de aprendizaje tiende a adaptarse a algunos tipos de problemas mejor que otros, y por lo general tiene muchos parámetros y configuraciones diferentes para ajustar antes de lograr un rendimiento óptimo en un conjunto de datos. AdaBoost (con los árboles de decisión como los estudiantes débiles) se conoce a menudo como el mejor clasificador fuera de la caja. Cuando se utiliza con el aprendizaje de árboles de decisión, la información reunida en cada etapa del algoritmo de AdaBoost sobre la relativa 'dificultad' de cada muestra de entrenamiento se invierte en el algoritmo de crecimiento de árboles de tal manera que los árboles posteriores tienden a centrarse en ejemplos más difíciles de clasificar.

Entrenamiento

AdaBoost se refiere a un método particular de entrenar un clasificador potenciado. Un clasificador potenciado es un clasificador de la forma

FT()x)=. . t=1Tft()x){displaystyle F_{T}(x)=sum _{t=1}{T}(x),!}

donde cada ft{displaystyle f_{t} es un estudiante débil que toma un objeto x{displaystyle x} como entrada y devuelve un valor indicando la clase del objeto. Por ejemplo, en el problema de dos clases, el signo de la producción del estudiante débil identifica la clase objeto predicho y el valor absoluto da la confianza en esa clasificación. Del mismo modo, el t{displaystyle t}- el clasificador es positivo si la muestra está en una clase positiva y negativa de otro modo.

Cada estudiante débil produce una hipótesis de salida h{displaystyle h} que fija una predicción h()xi){displaystyle h(x_{i})} para cada muestra en el set de entrenamiento. En cada iteración t{displaystyle t}, un estudiante débil es seleccionado y asignado un coeficiente α α t{displaystyle alpha _{t} tal que el error total de entrenamiento Et{displaystyle E_{t} del resultado t{displaystyle t}- Se minimiza el clasificador del escenario.

Et=. . iE[Ft− − 1()xi)+α α th()xi)]{displaystyle E_{t}=sum _{i}E[F_{t-1}(x_{i})+alpha _{t}h(x_{i})}

Aquí. Ft− − 1()x){displaystyle F_{t-1}(x)} es el clasificador impulsado que se ha construido hasta la etapa anterior de entrenamiento y ft()x)=α α th()x){displaystyle f_{t}(x)=alpha _{t}h(x)} es el estudiante débil que se está considerando para añadir al clasificador final.

Ponderación

En cada iteración del proceso de entrenamiento, un peso wi,t{displaystyle w_{i,t} se asigna a cada muestra en el conjunto de entrenamiento igual al error actual E()Ft− − 1()xi)){displaystyle E(F_{t-1}(x_{i})} en esa muestra. Estos pesos se pueden utilizar en el entrenamiento del estudiante débil. Por ejemplo, se pueden cultivar árboles de decisión que favorecen la división de conjuntos de muestras con grandes pesos.

Derivación

Esta derivación sigue a Rojas (2009):

Supongamos que tenemos un conjunto de datos {}()x1,Sí.1),... ... ,()xN,Sí.N)}{displaystyle {(x_{1},y_{1}),ldots(x_{N},y_{N}}} donde cada elemento xi{displaystyle x_{i}} tiene una clase asociada Sí.i▪ ▪ {}− − 1,1}{displaystyle y_{i}in {-1,1}}, y un conjunto de clasificadores débiles {}k1,... ... ,kL}{displaystyle {k_{1},ldotsk_{L}}} cada una de las cuales produce una clasificación kj()xi)▪ ▪ {}− − 1,1}{displaystyle k_{j}(x_{i})in {-1,1} para cada artículo. Después de la ()m− − 1){displaystyle (m-1)}-la iteración nuestro clasificador impulsado es una combinación lineal de los clasificadores débiles de la forma:

C()m− − 1)()xi)=α α 1k1()xi)+⋯ ⋯ +α α m− − 1km− − 1()xi){displaystyle C_{(m-1)}(x_{i})=alpha _{1}k_{1}(x_{i})+cdots +alpha ¿Qué?,

donde la clase será el signo de C()m− − 1)()xi){displaystyle C_{(m-1)}(x_{i}}. En el m{displaystyle m}-la iteración queremos extender esto a un mejor clasificador potenciado añadiendo otro clasificador débil km{displaystyle K_{m}, con otro peso α α m{displaystyle alpha _{m}:

Cm()xi)=C()m− − 1)()xi)+α α mkm()xi){displaystyle C_{m}(x_{i})=C_{(m-1)}(x_{i})+alpha _{m}k_{m}(x_{i}}}

Así que queda por determinar cuál clasificación débil es la mejor opción para km{displaystyle K_{m}, y cuál es su peso α α m{displaystyle alpha _{m} Debería serlo. Definimos el error total E{displaystyle E} de Cm{displaystyle C_{m} como la suma de su pérdida exponencial en cada punto de datos, dado como sigue:

E=. . i=1Ne− − Sí.iCm()xi)=. . i=1Ne− − Sí.iC()m− − 1)()xi)e− − Sí.iα α mkm()xi){displaystyle E=sum ¿Por qué? ¿Por qué? ¿Qué?

Letting wi()1)=1{displaystyle w_{i}{(1)}=1} y wi()m)=e− − Sí.iCm− − 1()xi){displaystyle w_{i}=e^{-y_{i}C_{m-1}(x_{i}}} para 1}" xmlns="http://www.w3.org/1998/Math/MathML">m■1{displaystyle m]1}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7f27527902d05e4c32bcbe28d425d7790f8ae191" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;"/>, tenemos:

E=. . i=1Nwi()m)e− − Sí.iα α mkm()xi){displaystyle E=sum {fnMicrosoft Sans Serif} ¿Qué?

Podemos dividir esta suma entre los puntos de datos que están correctamente clasificados por km{displaystyle K_{m} (so Sí.ikm()xi)=1{displaystyle Y...) y los que son misclasificados (también Sí.ikm()xi)=− − 1{displaystyle Y...):

E=. . Sí.i=km()xi)wi()m)e− − α α m+. . Sí.iل ل km()xi)wi()m)eα α m{displaystyle E=sum ¿Por qué? ¿Qué? ¿Por qué? - Sí.

=. . i=1Nwi()m)e− − α α m+. . Sí.iل ل km()xi)wi()m)()eα α m− − e− − α α m){displaystyle =sum {fnMicrosoft Sans Serif} ¿Qué? ¿Por qué? ¿Por qué? - Sí.

Desde la única parte del lado derecho de esta ecuación que depende de km{displaystyle K_{m} es . . Sí.iل ل km()xi)wi()m){displaystyle sum _{y_{i}neq k_{m}(x_{i}w_{i}{i}{(m)}, vemos que km{displaystyle K_{m} que minimiza E{displaystyle E} es el que minimiza . . Sí.iل ل km()xi)wi()m){displaystyle sum _{y_{i}neq k_{m}(x_{i}w_{i}{i}{(m)} [suponiendo que 0}" xmlns="http://www.w3.org/1998/Math/MathML">α α m■0{displaystyle alpha _{m}0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0c8f2b598dde21a3afc856626f1406298df8f3af" style="vertical-align: -0.671ex; width:7.424ex; height:2.509ex;"/>], es decir, el clasificador débil con el error más bajo ponderado (con pesos wi()m)=e− − Sí.iCm− − 1()xi){displaystyle w_{i}=e^{-y_{i}C_{m-1}(x_{i}}}).

Para determinar el peso deseado α α m{displaystyle alpha _{m} que minimiza E{displaystyle E} con el km{displaystyle K_{m} que acabamos de determinar, diferenciamos:

dEdα α m=d(). . Sí.i=km()xi)wi()m)e− − α α m+. . Sí.iل ل km()xi)wi()m)eα α m)dα α m{displaystyle {frac {}{dalpha ¿Por qué? ¿Qué? ¿Por qué?

Por suerte, el mínimo ocurre cuando se establece esto a cero, luego resolver para α α m{displaystyle alpha _{m} rendimientos:

α α m=12In⁡ ⁡ (). . Sí.i=km()xi)wi()m). . Sí.iل ل km()xi)wi()m)){displaystyle alpha ################################################################################################################################################################################################################################################################ ¿Por qué? ¿Por qué?

Calculamos la tasa de error ponderada del clasificador débil para ser ε ε m=. . Sí.iل ل km()xi)wi()m)/. . i=1Nwi()m){displaystyle epsilon _{m}=sum ¿Por qué? ¿Qué?, por lo que sigue que:

α α m=12In⁡ ⁡ ()1− − ε ε mε ε m){displaystyle alpha ################################################################################################################################################################################################################################################################ ¿Qué? - ¿Sí?

que es la función logit negativa multiplicada por 0,5. Debido a la convexidad de E{displaystyle E} como función de α α m{displaystyle alpha _{m}, esta nueva expresión α α m{displaystyle alpha _{m} da el mínimo global de la función de pérdida.

Nota: Esta derivación sólo se aplica cuando km()xi)▪ ▪ {}− − 1,1}{displaystyle k_{m}(x_{i})in {-1,1}, aunque puede ser una buena adivinanza de inicio en otros casos, como cuando el estudiante débil es sesgado (km()x)▪ ▪ {}a,b},aل ل − − b{displaystyle k_{m}(x)in {a,b},aneq -b}), tiene múltiples hojas (km()x)▪ ▪ {}a,b,... ... ,n}{displaystyle k_{m}(x)in {a,b,dotsn}) o es otra función km()x)▪ ▪ R{displaystyle k_{m}(x)in mathbb {R}.

Así hemos derivado el algoritmo AdaBoost: En cada iteración, elija el clasificador km{displaystyle K_{m}, que minimiza el error total ponderado . . Sí.iل ل km()xi)wi()m){displaystyle sum _{y_{i}neq k_{m}(x_{i}w_{i}{i}{(m)}, utilice esto para calcular la tasa de error ε ε m=. . Sí.iل ل km()xi)wi()m)/. . i=1Nwi()m){displaystyle epsilon _{m}=sum ¿Por qué? ¿Qué?, utilizar esto para calcular el peso α α m=12In⁡ ⁡ ()1− − ε ε mε ε m){displaystyle alpha ################################################################################################################################################################################################################################################################ ¿Qué? - ¿Sí?, y finalmente utilizar esto para mejorar el clasificador impulsado Cm− − 1{displaystyle C_{m-1} a Cm=C()m− − 1)+α α mkm{displaystyle C_{m}=C_{(m-1)}+alpha ¿Qué?.

Comprensión estadística del impulso

Boosting es una forma de regresión lineal en la que las características de cada muestra xi{displaystyle x_{i}} son los resultados de algunos estudiantes débiles h{displaystyle h} aplicadas a xi{displaystyle x_{i}}.

Mientras la regresión intenta encajar F()x){displaystyle F(x)} a Sí.()x){displaystyle y(x)} lo más precisamente posible sin pérdida de generalización, por lo general utilizando menos error cuadrado E()f)=()Sí.()x)− − f()x))2{displaystyle E(f)=(y(x)-f(x)}{2}, mientras que la función de error AdaBoost E()f)=e− − Sí.()x)f()x){displaystyle E(f)=e^{-y(x)f(x)}} toma en cuenta el hecho de que sólo se utiliza la señal del resultado final, por lo tanto SilencioF()x)Silencio{displaystyle SilencioF(x) puede ser mucho más grande que 1 sin aumentar el error. Sin embargo, el aumento exponencial del error de la muestra xi{displaystyle x_{i}} como − − Sí.()xi)f()xi){displaystyle -y(x_{i})f(x_{i}} aumenta. resultando en pesos excesivos que se asignan a los atípicos.

Una característica de la elección de función de error exponencial es que el error del modelo aditivo final es el producto del error de cada etapa, es decir, e. . i− − Sí.if()xi)=∏ ∏ ie− − Sí.if()xi){displaystyle e^{sup - Sí. ¿Qué?. Así se puede ver que la actualización de peso en el algoritmo AdaBoost es equivalente a recalcular el error en Ft()x){displaystyle F_{t}(x)} después de cada etapa.

Se permite mucha flexibilidad en la elección de la función de pérdida. Mientras la función de pérdida sea monótona y continuamente diferenciable, el clasificador siempre se orientará hacia soluciones más puras. Zhang (2004) proporciona una función de pérdida basada en mínimos cuadrados, una función de pérdida de Huber modificada:

<math alttext="{displaystyle phi (y,f(x))={begin{cases}-4yf(x)&{mbox{if }}yf(x)1end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">φ φ ()Sí.,f()x))={}− − 4Sí.f()x)si Sí.f()x)c)− − 1,()Sí.f()x)− − 1)2si − − 1≤ ≤ Sí.f()x)≤ ≤ 1.0si Sí.f()x)■1{displaystyle phi (y,f(x)={begin{cases}-4yf(x) limitada{mbox{if }}yf(x) made-1,(yf(x)-1)^{2} {mbox{if }-1leq yf(x)} {mbox{if}1}<img alt="{displaystyle phi (y,f(x))={begin{cases}-4yf(x)&{mbox{if }}yf(x)1end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/576550a6a2d23f9a188073741ecb7ee3d12acfce" style="vertical-align: -3.838ex; width:50.001ex; height:8.843ex;"/>

Esta función es más bien desarrollada que LogitBoost para f()x){displaystyle f(x)} cerca de 1 o -1, no penaliza las predicciones “sobreconfiden” (1}" xmlns="http://www.w3.org/1998/Math/MathML">Sí.f()x)■1{displaystyle yf(x)}1}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b635df4368e75c2e738cc998b3307a05639e6fb" style="vertical-align: -0.838ex; width:9.834ex; height:2.843ex;"/>), a diferencia de mínimos cuadrados no modificados, y sólo penaliza muestras mal clasificadas con confianza superior a 1 linealmente, en lugar de cuadrática o exponencialmente, y por lo tanto es menos susceptible a los efectos de los outliers.

Impulso como descenso de gradiente

El impulso puede verse como la minimización de una función de pérdida convexa sobre un conjunto convexo de funciones. Específicamente, la pérdida que AdaBoost minimiza es la pérdida exponencial

. . iφ φ ()i,Sí.,f)=. . ie− − Sí.if()xi){displaystyle sum _{i}phi (i,y,f)=sum ¿Qué?,

mientras que LogitBoost realiza una regresión logística, minimizando

. . iφ φ ()i,Sí.,f)=. . iIn⁡ ⁡ ()1+e− − Sí.if()xi)){displaystyle sum _{i}phi (i,y,f)=sum _{i}ln left(1+e^{-y_{i}f(x_{i}}right)}.

En la analogía de descenso gradiente, la salida del clasificador para cada punto de entrenamiento se considera un punto ()Ft()x1),... ... ,Ft()xn)){displaystyle left(F_{t}(x_{1}),dotsF_{t}(x_{n})right)} en el espacio n-dimensional, donde cada eje corresponde a una muestra de entrenamiento, cada estudiante débil h()x){displaystyle h(x)} corresponde a un vector de orientación fija y longitud, y el objetivo es alcanzar el punto objetivo ()Sí.1,... ... ,Sí.n){displaystyle (y_{1},dotsy_{n}} (o cualquier región donde el valor de la función de pérdida ET()x1,... ... ,xn){displaystyle E_{T}(x_{1},dotsx_{n}) } es menos que el valor en ese punto), en los pocos pasos. Así los algoritmos AdaBoost realizan Cauchy (encontrados h()x){displaystyle h(x)} con el más empinado gradiente, elegir α α {displaystyle alpha } para minimizar el error de prueba) o Newton (elegir un punto de destino, encontrar α α h()x){displaystyle alpha h(x)} que trae Ft{displaystyle F_{t} más cercano a ese punto) optimización del error de entrenamiento.

algoritmo de ejemplo (Discrete AdaBoost)

Con:

• Muestras x1... ... xn{displaystyle x_{1}dots x_{n}
• Productos deseados Sí.1... ... Sí.n,Sí.▪ ▪ {}− − 1,1}{displaystyle y_{1}dots y_{n},yin {-1,1}
• Pesos iniciales w1,1... ... wn,1{displaystyle w_{1,1}dots ¿Qué? establecido 1n{fnMicroc} {1}{n}}
• Función de error E()f()x),Sí.,i)=e− − Sí.if()xi){displaystyle E(f(x),y,i)=e^{-y_{i}f(x_{i}}}
• Estudiantes débiles h:: x→ → {}− − 1,1}{displaystyle hcolon xrightarrow{-1,1}

Para t{displaystyle t} dentro 1... ... T{displaystyle 1dots T}:

• Elija ht()x){displaystyle h_{t}(x)}:
  • Encontrar estudiante débil ht()x){displaystyle h_{t}(x)} que minimiza ε ε t{displaystyle epsilon _{t}, el error de suma ponderada para puntos mal clasificados ε ε t=. . ht()xi)ل ل Sí.ii=1nwi,t{displaystyle epsilon ¿Por qué? Y...
  • Elija α α t=12In⁡ ⁡ ()1− − ε ε tε ε t){displaystyle alpha ################################################################################################################################################################################################################################################################ - ¿Sí?
• Añadir a conjunto:
  • Ft()x)=Ft− − 1()x)+α α tht()x){displaystyle F_{t}(x)=F_{t-1}(x)+alpha _{t}h_{t}(x)}
• Pesos de actualización:
  • wi,t+1=wi,te− − Sí.iα α tht()xi){displaystyle w_{i,t+1}=w_{i,t}e^{-y_{i}alpha - Sí. para i{displaystyle i} dentro 1... ... n{displaystyle 1dots n}
  • Renormalizar wi,t+1{displaystyle w_{i,t+1} tales que . . iwi,t+1=1{displaystyle sum _{i}w_{i,t+1}=1}
  • (Nota: Se puede demostrar que . . ht+1()xi)=Sí.iwi,t+1. . ht+1()xi)ل ل Sí.iwi,t+1=. . ht()xi)=Sí.iwi,t. . ht()xi)ل ل Sí.iwi,t{displaystyle {frac {fnMicroc}sum ¿Por qué? _{h_{t+1}(x_{i})neq Y... {cHFF} ¿Qué? ¿Por qué? Sí. en cada paso, que puede simplificar el cálculo de los nuevos pesos.)

Variantes

AdaBoost real

La producción de árboles de decisión es una estimación de probabilidad de clase p()x)=P()Sí.=1Silenciox){displaystyle p(x)=P(y=1 habitx)}, la probabilidad de que x{displaystyle x} está en la clase positiva. Friedman, Hastie y Tibshirani obtienen un minimizador analítico para e− − Sí.()Ft− − 1()x)+ft()p()x))){displaystyle e^{-yleft(F_{t-1}(x)+f_{t}(p(x)right)}} para algunos fijos p()x){displaystyle p(x)} (típicamente elegido usando el error de mínimos cuadrados ponderados):

ft()x)=12In⁡ ⁡ ()x1− − x){displaystyle f_{t}(x)={frac {1}{2}ln left({frac {x}{1-x}right)}.

Así, en lugar de multiplicar la salida de todo el árbol por algún valor fijo, cada nodo de hoja se cambia para producir la mitad de la transformación de logit de su valor anterior.

LogitBoost

LogitBoost representa una aplicación de técnicas de regresión logística establecidas al método AdaBoost. En lugar de minimizar el error con respecto a y, los estudiantes débiles se eligen para minimizar el error (pesado menos cuadrado) ft()x){displaystyle f_{t}(x)} con respecto a

zt=Sí.Alternativa Alternativa − − pt()x)2pt()x)()1− − pt()x)),{displaystyle z_{t}={frac {y^{*}-p_{t}(x)}{2p_{t}(x)(1-p_{t}(x)}}}}}

Donde

pt()x)=eFt− − 1()x)eFt− − 1()x)+e− − Ft− − 1()x),{displaystyle p_{t}(x)={frac {e^{F_{t-1}(x)}{e^{F_{t-1}(x)}+e^{-F_{t-1}(x)}}}}}}}}}} {f} {f} {f}

wt=pt()x)()1− − pt()x)){displaystyle w_{t}=p_{t}(x)(1-p_{t}(x)}

Sí.Alternativa Alternativa =Sí.+12.{displaystyle y^{*}={frac} {y+1}{2}}

Eso es zt{displaystyle z_{t} es la aproximación de Newton-Raphson del minimizador del error de probabilidad de registro en el escenario t{displaystyle t}, y el estudiante débil ft{displaystyle f_{t} es elegido como el estudiante que mejor aproxima zt{displaystyle z_{t} por lo menos cuadrados ponderados.

Como p se acerca 1 o 0, el valor pt()xi)()1− − pt()xi)){displaystyle p_{t}(x_{i})(1-p_{t}(x_{i})} se vuelve muy pequeño y z término, que es grande para muestras desclasificadas, puede convertirse numéricamente inestable, debido a errores de redondeo de precisión de la máquina. Esto se puede superar mediante la aplicación de algún límite sobre el valor absoluto z y el valor mínimo w

AdaBoost suave

Mientras que los algoritmos de impulso anteriores eligen ft{displaystyle f_{t} codicioso, minimizando el error total de prueba tanto como sea posible en cada paso, GentleBoost cuenta con un tamaño de paso consolidado. ft{displaystyle f_{t} es elegido para minimizar . . iwt,i()Sí.i− − ft()xi))2{displaystyle sum _{i}w_{t,i}(y_{i}-f_{t}(x_{i})^{2}, y no se aplica ningún coeficiente adicional. Así, en el caso en que un estudiante débil exhibe un rendimiento de clasificación perfecto, GentleBoost elige ft()x)=α α tht()x){displaystyle f_{t}(x)=alpha ¿Qué? exactamente igual a Sí.{displaystyle y}, mientras los algoritmos de descenso más empinados intentan establecer α α t=JUEGO JUEGO {displaystyle alpha ¿Qué?. Observaciones empíricas sobre el buen desempeño de GentleBoost parecen respaldar la observación de Schapire y Singer que permite valores excesivamente grandes de α α {displaystyle alpha } puede conducir a un mal desempeño de generalización.

Terminación temprana

Una técnica para acelerar el procesamiento de clasificadores mejorados, la terminación temprana se refiere a probar solo cada objeto potencial con tantas capas del clasificador final necesarias para alcanzar algún umbral de confianza, acelerando el cálculo en los casos en los que la clase del objeto puede fácilmente ser determinado. Uno de esos esquemas es el marco de detección de objetos introducido por Viola y Jones: en una aplicación con significativamente más muestras negativas que positivas, se entrena una cascada de clasificadores de refuerzo separados, la salida de cada etapa está sesgada de tal manera que una fracción aceptablemente pequeña de muestras positivas es se etiquetan erróneamente como negativas y todas las muestras marcadas como negativas después de cada etapa se descartan. Si cada etapa filtra el 50% de las muestras negativas, solo una cantidad muy pequeña de objetos pasaría por todo el clasificador, lo que reduciría el esfuerzo de cálculo. Desde entonces, este método se ha generalizado, con una fórmula proporcionada para elegir umbrales óptimos en cada etapa para lograr una tasa deseada de falsos positivos y falsos negativos.

En el campo de las estadísticas, donde AdaBoost se aplica más comúnmente a problemas de dimensionalidad moderada, la detención temprana se utiliza como estrategia para reducir el sobreajuste. Un conjunto de muestras de validación se separa del conjunto de entrenamiento, el rendimiento del clasificador en las muestras utilizadas para el entrenamiento se compara con el rendimiento de las muestras de validación, y el entrenamiento finaliza si se observa que el rendimiento en la muestra de validación disminuye incluso cuando el rendimiento en la muestra de validación disminuye. El conjunto de entrenamiento continúa mejorando.

Algoritmos totalmente correctivos

Para versiones de descenso más pronunciadas de AdaBoost, donde α α t{displaystyle alpha _{t} es elegido en cada capa t para minimizar el error de prueba, se dice que la siguiente capa máximamente independiente de capa t: es poco probable que elija un estudiante débil t+1 que es similar al estudiante t. Sin embargo, sigue existiendo la posibilidad de que t+1 produce información similar a otra capa anterior. Los algoritmos totalmente correctivos, como LPBoost, optimizan el valor de cada coeficiente después de cada paso, de manera que las nuevas capas agregadas son siempre máximamente independientes de cada capa anterior. Esto se puede lograr mediante el ajuste, la programación lineal o algún otro método.

Poda

La poda es el proceso de eliminar clasificadores débiles con un rendimiento deficiente para mejorar la memoria y el costo del tiempo de ejecución del clasificador mejorado. Los métodos más simples, que pueden ser particularmente efectivos junto con un entrenamiento totalmente correctivo, son el recorte de peso o margen: cuando el coeficiente, o la contribución al error total de la prueba, de algún clasificador débil cae por debajo de un cierto umbral, ese clasificador es abandonó. Margineantu & Dietterich sugirió un criterio alternativo para el recorte: los clasificadores débiles deben seleccionarse de manera que se maximice la diversidad del conjunto. Si dos alumnos débiles producen resultados muy similares, la eficiencia se puede mejorar eliminando a uno de ellos y aumentando el coeficiente del alumno débil restante.