No confundir con el framework diseñado para simplificar el proceso de creación de diseños web que desarrolla Twitter (mismo nombre). El bootstrapping es un método de remuestreo propuesto por Bradley Efron en 1979. Se utiliza para aproximar la distribución en el muestreo de un estadístico ϴ. La idea es obtener muestras aleatorias con reemplazamiento (es posible incluir el mismo dato varias veces), siendo esas muestras de igual tamaño N que el conjunto de datos original.
- Seleccionar muestras de tamaño N con reemplazamiento de la población original (elevado coste computacional).
- Para cada muestra de bootstrap calcular el estadístico de interés ϴ* (ejemplo: media, varianza).
La probabilidad de que cierta instancia del conjunto de entrenamiento (población) sea seleccionada para formar parte de una muestra bootstrap es del 63% cuando N es grande. Por ejemplo, dada la población [0,1,2,3,4,5,6,7,8,9], ¿cuál es la probabilidad de elegir el dato 2?. Siendo 1-(1/10)=0.9 la probabilidad de no elegir el número y N=10 el tamaño de la muestra. 1-(0.9^10)=0.65 (65% de probabilidad de elegir de manera aleatoria el 2).
Finalmente, con los estadísticos ϴ* queda construir la distribución con la que estimar el estadístico ϴ de manera precisa. Bootstrap es útil frecuentemente para aproximar el sesgo y la varianza de un análisis estadístico, así como para construir intervalos de confianza.
La idea de partida es usar un conjunto de clasificadores para obtener una mayor precisión de la que cada uno de éstos logra de manera individual. Bootstrap Aggregating es el método propuesto por Leo Breiman en 1994 basado en la combinación de clasificadores inestables como las redes de neuronas o los árboles de decisión (donde ligeros cambios en el conjunto de entrenamiento llevan a construir otro clasificador). Bagging carece de sentido con un clasificador estable como el kNN (K vecinos más próximos).
- Entrenamiento de cada clasificador
- Seleccionar una muestra de tamaño N con reemplazamiento de la población original.
- Entrenar un clasificador básico h(t) con esa muestra extraída.
- Clasificación
- La decisión de la combinación de clasificadores H = h(1) ... h(T) es la predicción más votada.
Una técnica mejorada del Bagging es el Random Forest. Además de elegir de manera aleatoria cada dato, el Random Tree selecciona aleatoriamente el vector de características. Cabe hacer uso del conjunto de instancias no seleccionadas para entrenar cada árbol, denominado Out-Of-Bag (obb), para el cálculo del error de generalización.
En contraposición con Bagging (donde cada clasificador es generado de manera individual), en Boosting la construción de estos clasificadores básicos depende del error cometido en el clasificador anterior. A la hora de seleccionar una muestra para el clasificador básico h(t), el objetivo es seleccionar observaciones clasificadas erróneamente antes (tienen mayor peso w(i)).
Existen varias versiones de algoritmos Boosting, pero la más extendida es la propuesta por Yoav Freund y Robert Schapire en 1996, conocida como Adaptive Boosting. Considerando un problema de 2 clases, siendo H = {-1,1} la salida del clasificador, el algoritmo detalla:
- Asignar un peso inicial w(i) = 1/N a cada observación de la muestra de entrenamiento.
- Para cada clasificador débil h(1) ... h(T)
- Construir el mejor clasificador h(t) en relación a los correspondientes pesos w(i).
- Calcular la tasa de error e(t). Esta suma de pesos de observaciones erróneas debe ser menor que 0.5 (clasificador aleatorio).
- Obtener el peso a(t) del clasificador débil: a(t) = Ln([1-e(t)]/e(t))/2.
- Reasignar el peso de las observaciones de entrenamiento w(i). Multiplicar cada peso por la función de error exponencial: w(i) *= exp(-a(t)). Finalmente, normalizar todos los pesos w(i) para que la suma sea 1.
- Clasificador H producto de la combinación de clasificadores débiles: H = a(1)·h(1) ... a(T)·h(T).
Respecto a la demostración matemática, la idea es minimizar la función de pérdida L = exp(-y*H), de manera que cuando el valor de la etiqueta y la salida del clasificador no coincida, la perdida L sea alta.
Otra alternativa, es no insistir en dar excesivo peso a las muestras mal clasificadas. La propuesta es sustituir la función exponencial por la binomial, cuya penalización es menor.
Destacar la extensión al problema multiclase. Algunas variantes modifican el weak-learner por otro clasificador, o bien, tratan de transformar el problema multiclase en un conjunto de problemas binarios.
Para rebajar el problema de sobreajustar al aumentar el número de iteraciones de Boosting y evitar finalmente el efecto rebote, interesa aplicar los pesos de manera gradual (shrinkage). La otra posible solución es la de combinar Bagging y Boosting (subsampling).
Involves training a learning algorithm to combine the predictions of several other learning algorithms. First, all of the other algorithms are trained using the available data, then a combiner algorithm is trained to make a final prediction using all the predictions of the other algorithms as additional inputs. If an arbitrary combiner algorithm is used, then stacking can theoretically represent any of the ensemble techniques described in this article.