2. Métodos de ensamble

Motivación Los algoritmos de aprendizaje supervisado comunmente se entienden algoritmos que realizan una búsqueda en un espacio de hipótesis que hace buenas predicciones en un problema particular. Incluso si el espacio de hipótesis contiene hipótesis que son apropiadas para un problema en particular puede ser muy difícil encontrar una buena solución. Los métodos de ensamble combinan múltiples hipótesis para formar una hipótesis mejor. En otras palabras, los métodos de ensamble son técnicas para combinar varios algoritmos de aprendizaje débiles en un intento por construir un algoritmo de aprendizaje más poderoso.

Motivación Metodología: Entrene varios predictores con diversas metodologías (clasificadores, regresores) y use un sistema de agregación para definir una solución con poca polarización (bias) y poca varianza. Usar diferentes modelos para obtener mejor desempeño en predicción, que el que se pudiera obtener con los métodos invididuales. Evaluar la predicción de un ensamble, requiere mayor computación que un modelo simple. Los ensambles pueden ser vistos como una forma de compensar el bajo desempeño de algoritmos simples con computación adicional.

Ejemplos Algoritmos rápidos como árboles de decisiones son usados generalmente con en ensambles decision trees are commonly used with ensambles y son llamados Bosques Aleatorios (Random Forest). Viola-Jones para detección facial. Predicción de tormentas.

Clasificador óptimo de Bayes como ensamble Es un encamble de todas hipótesis en el espacio de hipótesis. En promedio a cada hipótesis se le da un voto proporcional a la likelihood de que los datos de entrenamiento pertenezcan a cierta hipótesis en caso de que esta sea verdadera. El voto de cada hipótesis es también ponderado por la probabilidad a priori de la hipótesis.

Donde C es el conjunto de todas las clases, H es el espacio de hipótesis, T son los datos de entrenamiento.

Clasificador óptimo de Bayes Desafortunadamente el clasificador óptimo de Bayes solo puede ser implementado en casos sencillos. Existen varias razones por las que no se puede realizar una implementación práctica:

●

La mayoría de los espacios de hipótesis son muy grandes para iterarlos todos.

●

Computar estimados de la probabilidad de los datos dadas la hipótesis es un problema no trivial.

●

Estimar la probabilidad a priori es raramente posible.

Tipos de Ensambles Bagging (bootstrap aggregation) Combina diferentes clasificadores y votan con igual peso. Cada clasificador es entrenado con submuestras aleatorias (con reemplazo). Boosting Combina diferentes clasificadores de forma incremental, dándole mayor peso a las muestras que fueron mal clasificadas en pasos anteriores. Mejores resultados que Bagging pero tiende a sobre-ajustar (overfit)

Algoritmos débiles de aprendizaje ● Stumps: Particiones de un plano en 2. ● Árboles de decisión: Particiones jerarquizadas de un espacio. ● Perceptrones multicapa: Acercamientos para funciones no lineales. ● Funciones radiales y otros kernels: Expansiones no lineales

Combinación de clasificadores Entrada: Un juego de posibles clasificadores c1, c2,..., cn Objetivo: Encontrar una función de agregación:

Tips:

● Diversificación de clasificadores. ● Usar diferentes subconjuntos de datos de entrenamiento para cada ci.

● Usar diferentes verctores de características. ● Decorrelacionar clasificadores en el entrenamiento.

Bagging Generar diversidad muestreando (con reemplazo) de diferentes subconjuntos de muestras. Entrada: Diferentes clasificadores c1,..., cb Entrenar cada clasificador con un subconjunto de datos. Salida: Clasificar cada muestra según voto de mayoría 1,...,b.

Boosting Combinación adaptativa de clasificadores simples. Salida:

Entrene en secuencia y forme un promedio ponderado por el error de cada clasificador. alpha es una función del error de cada clasificador.

Adaboost - boosting adaptativo en cascada Entrada: datos con su tag de clasificación. Salida: Clasificador agregado Inicialice los pesos de cada clasificador con los mismos valors wi = 1/n 1. For i=1..b 2. Ajuste el clasificador ci a la muestra de boostrap bi con los pesos iniciales 3. Calcule el error e para el clasificador ci 4. Calcule alpha como función del error e.g. log(1/e-1) 5. Reajuste los pesos wi 6. end for 7. Salida:

AdaBoost en acción tutorial singer y lewis

AdaBoost en acción tutorial singer y lewis

AdaBoost en acción tutorial singer y lewis

Árboles de decisión Los datos son partidos consecutivamente en dicotomías

Ejemplo: detección de spam Curvas de error: roja: test data verde: crosvalidación

Comparación Bagging y Boosting Bagging

Boosting

Los clasificadores son simples particiones de los ejes

Ejemplo: Detección Facial en Tiempo Real Primeras y segundas características seleccionadas por el AdaBoost. El primero detecta cambios de intensidad de los ojos a los pómulos, el segundo el brillo de la nariz.

Ejemplo: Detección Facial en Tiempo Real

Notas Adicionales: Curvas de aprendizaje teóricas

Notas Adicionales: Boostrap Muestrear con reemplazo los datos que tenemos hasta completar un número de muestras predifinidas (o el total de las muestras) Se usa para determinar errores estándar e intervalos de confianza. Práctico cuando no conocemos las distribuciones de probabilidad subyacentes o son muy complejas. Práctico cuando tenemos pocos datos.

Notas Adicionales: Crosvalidación Tenemos un conjunto de datos T. Separamos los datos en K diferentes conjuntos del mismo tamaño. Aprender K clasificadores usando como datos de entrenamiento T-K1 datos. Calcular el error de predicción como el promedio del error de los K clasificadores.

Notas Adicionales: Crosvalidación Qué pasa cuando K = N datos? Se llama Leave One Out Crossvalidation ● Es cercano al verdadero error de predicción ● Costoso computacionalmente K pequeño? Tiende a subajustar los datos (underfit) Usar K = 5 o 10

Selección de modelos ● ● ● ●

AIC (akaike information criteria) BIC (bayesian information criteria) MDL (minimum description length) Crosvalidación

Objetivo: seleccionar el modelo que mejor se ajuste a mis datos y que sea lo más sencillo posible. Maximizar la likelihood dado el modelo, más un término de penalización por la complejidad del