« Aprendizaje Inductivo… « || Inicio || » Minimax: Juegos con a… »

Métodos combinados de aprendizaje

Última modificación: 13 de Diciembre de 2015, y ha tenido 758 vistas

Etiquetas utilizadas: || ||

These icons link to social bookmarking sites where readers can share and discover new web pages.
  • BarraPunto
  • Del.icio.us
  • Digg
  • email
  • Facebook
  • Google
  • LinkedIn
  • PDF
  • Reddit
  • Slashdot
  • Twitter

En el campo del aprendizaje automático, los métodos combinados (métodos de ensemble) utilizan múltiples algoritmos de aprendizaje para obtener un rendimiento predictivo que mejore el que podría obtenerse por medio de cualquiera de los algoritmos de aprendizaje individuales que lo constituyen.

Como ya vimos, los algoritmos de aprendizaje supervisado se describen normalmente como la tarea de buscar a través de un espacio de hipótesis para encontrar la más adecuada que haga buenas predicciones con un problema en particular. En general, esta tarea es muy complicada y, ni siquiera teniendo la certeza de que en el espacio completo existe una buena solución, podemos estar seguros de encontrarla.

La idea de los métodos combinados es considerar múltiples hipótesis simultáneamente para formar una hipótesis que, con suerte, se comporte mejor. El término de métodos de ensemble se suele reservar para aquellas combinaciones que hacen uso de múltiples hipótesis pertenecientes a una misma familia, mientras que se usa el término más general de sistemas de aprendizaje múltiples cuando las hipótesis que se combinan provienen de diversas familias.

Evidentemente, debido a que los métodos combinados hacen uso de varias hipótesis simultáneas, se produce una elevación en los costes computacionales, por lo que suele ser habitual utilizar algoritmos rápidos como espacio de hipótesis base, como son los árboles de decisión.

Una combinación de algoritmos de aprendizaje supervisado es en si mismo un algoritmo de aprendizaje supervisado y puede ser entrenado y usado para hacer predicciones. Sin embargo, se debe tener en cuenta que una combinación de hipótesis (algoritmos) de una determinada familia no es necesariamente una hipótesis (algoritmo) de la misma familia, por lo que podríamos obtener mejores resultados que con los elementos individuales de la familia, aunque también podemos correr el riesgo de obtener un modelo sobreajustado si no se tienen algunas precauciones. En la práctica, la forma en que se seleccionan los modelos individuales que se combinan hacen uso de algunas técnicas que tienden a reducir los problemas relacionados con el exceso de ajuste de los datos de entrenamiento y mejoran la prediccióm conjunta.

Empíricamente, se ha comprobado que cuando existe una diversidad significativa entre los modelos individuales, las combinaciones tienden a obtener mejores resultados, por lo que muchos de los métodos existentes buscan promover la diversidad entre los modelos que se combinan, y ello provoca a veces que se usen como modelos aquellos que hacen un uso fuerte de la aleatoriedad, en vez de modelos más dirigidos y que funcionan mejor individualmente.

Los métodos de combinación más comunes

A continuación mostramos algunos de los métodos de combinación más extendidos y comunes. En las referencias finales de esta entrada podrás encontrar estos mismos métodos analizados con más detalle, así como muchos otros que están siendo utilizados en la actualidad.

Agregación Bootstrap

La agregación Bootstrap, tambien conocida por Bagging, es realmente un meta-algoritmo diseñado para conseguir combinaciones de modelos a partir de una familia inicial, provocando una disminución de la varianza y evitando el sobreajuste. Aunque lo más común es aplicarlo con los métodos basados en árboles de decisión, se puede usar con cualquier familia.

La técnica consiste en lo siguiente:

  1. Dada un conjunto de entrenamiento, \(D\), de tamaño \(n\), el bagging genera \(m\) nuevos conjuntos de entrenamiento, \(D_i\), de tamaño \(n′\), tomando al azar elementos de \(D\) de manera uniforme y con reemplazo, por tanto, algunos elementos del conjunto original pueden aparecer repetidos en los nuevos conjuntos generados.
  2. Si \(n′=n\), entonces para valores de \(n\) suficientemente grandes, se espera que cada \(D_i\) tenga una fracción de (1 - 1/e) (≈63.2%) elementos únicos de \(D\), y el resto son duplicados.
  3. A partir de estos \(m\) nuevos conjuntos de entrenamiento se construyen \(m\) nuevos modelos de aprendizaje, y la respuesta final de la combinación se consigue por medio de votación de las \(m\) respuestas (en caso de buscar una clasificación) o por la media de ellas (en caso de buscar una regresión).

Se ha probado que el bagging tiende a producir mejoras en los casos de modelos individuales inestables (como es el caso de las redes neuronales o los árboles de decisión), pero puede producir resultados mediocres o incluso empeorar los resultados con otros métodos, como el de los K vecinos más cercanos.

Boosting

A diferencia del bagging, en el boosting no se crean versiones del conjunto de entrenamiento, sino que se trabaja siempre con el conjunto completo de entrada, y se manipulan los pesos de los datos para generar modelos distintos. La idea es que en cada iteración se incremente el peso de los objetos mal clasificados por el predictor en esa iteración, por lo que en la construcción del próximo predictor estos objetos serán más importantes y será más probable clasificarlos bien.

El método de boosting más famoso es el que se conoce como AdaBoost que consta de los siguientes pasos:

  1. Inicialmente a todos los datos del conjunto de entrenamiento se les asigna un peso idéntico, \(w_i = \frac{1}{n}\), donde \(n\) es el tamaño del conjunto de datos.
  2. Se entrena el modelo usando el conjunto de entrenamiento.
  3. Se calcula el error del modelo en el conjunto de entrenamiento, se cuentan cuántos objetos han sido mal clasificados y se identifican cuáles son.
  4. Se incrementan los pesos en aquellos casos de entrenamiento en los que el modelo anterior ha dado resultados erróneos.
  5. Se entrena un nuevo modelo usando el conjunto de pesos modificados.
  6. Volver al punto 3 (y se repite el proceso hasta el número de iteraciones fijadas inicialmente)
  7. El modelo final se consigue por votación ponderada usando los pesos de todos los modelos.

Concretamente, para modificar los pesos tras el cálculo del predictor \(M_t\) con los pesos en el tiempo \(t\), \(w_{i,t}\) se utilizan las siguientes ecuaciones:

\[e_t =\frac{\sum_{i=1}^n w_{i,t}y_t M_t(x_i)}{\sum_{i=1}^n w_{i,t}}\]
\[\alpha_t =\frac{1}{2}\ln (\frac{1-e_t}{1+e_t})\]

donde \(x_i\) es el vector de entrada del objeto, \(y_i\) es la clase del objeto \(i\)-ésimo, y \(M_t(x_i)\) es la predicción del modelo para la entrada \(x_i\).

Tras esto, los pesos son actualizados de la siguiente forma:

\[w_{i,t+1} = c \cdot w_{i,t} e^{−\alpha_t y_i M_t(x_i)}\]

donde \(c\) es una constante de normalización elegida de forma que

\[\sum_{i=1}^n w_{i,t+1} = 1\]

La combinación construida clasifica por medio del voto de la mayoría, ponderando cada modelo \(M_t\) por medio de \(\alpha_t\). Es decir:

\[M(x_i) = sign (\sum_{i=1}^{t_{max}}\alpha_t M_t(x_i))\]

Normalmente, se espera una mejora significativa sobre la clasificación producida por cada uno de los modelos individuales, pero la convergencia no está garantizada y el rendimiendo podría degradarse tras un cierto número de pasos.

Subespacios Aleatorios

En este método cada modelo se entrena con todos los ejemplos, pero solo considera un subconjunto de los atributos. El tamaño de estos subconjuntos es el parámetro del método, y de nuevo el resultado es el promedio o votación de los resultados individuales de los modelos.

La combinación se construye siguiendo el siguiente algoritmo:

  1. Sea \(N\) el tamaño del conjunto de entrenamiento, y \(D\) el número de atributos de los datos.
  2. Sea \(L\) el número de clasificadores individuales del conjunto.
  3. Para cada clasificador individual, \(l\), tomamos \(d_l\) con \(d_l < D\), el número de variables de entrada de \(l\). Suele ser común usar el mismo valor de \(d_l\) para todos los clasificadores individuales.
  4. Para cada clasificador individual, \(l\), se crea un conjunto de entrenamiento seleccionado al azar \(d_l\) atributos distintos de los datos de entrada, y se entrena con ellos al clasificador.
  5. Para clasificar un nuevo objeto, se combinan las salidas de los \(L\) clasificadore individuales por medio del voto de la mayoría o por combinación ponderada.

Para saber más...

Ensemble Methods in Machine Learning (T.G: Dietterich)

Boosting (M. Cárdenas Montes)

Bagging (M. Cárdenas Montes)

Wikipedia: Ensemble Methods in Machine Learning

Improve Machine Learning Results with Boosting, Bagging and Blending Ensemble Methods in Weka

« Aprendizaje Inductivo… « || Inicio || » Minimax: Juegos con a… »