28
Parallel Ensemble Pablo Orme˜ no A. Universidad T´ ecnica Federico Santa Mar´ ıa [email protected] Junio 2015 Pablo Orme˜ no A. (UTFSM) Parallel Ensemble Junio 2015 1 / 28

Parallel Ensemble

Embed Size (px)

DESCRIPTION

Presentation

Citation preview

  • Parallel Ensemble

    Pablo Ormeno A.

    Universidad Tecnica Federico Santa Mara

    [email protected]

    Junio 2015

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 1 / 28

  • Propuesta

    Figura : Ensamblado de Topc Models

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 2 / 28

  • Propuesta

    Objetivo 1: Paralelizar un Ensamblado de Topic Models.

    Objetivo 2: Disminuir los tiempos de ejecucion del algoritmosecuencial.

    Objetivo 3: Probar Bagging y Adaboost Paralelo aplicado a TopicModels con gran volumen de datos.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 3 / 28

  • 1 Introduccion

    2 Ensamblados

    3 Ensamblados Paralelos

    4 Evaluacion y Resultados

    5 Conclusiones

    6 Propuesta

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 4 / 28

  • Introduccion

    Data Mining es una poderosa tecnica para extraer informacionoculta de un gran dataset.

    Clasificacion es una aplicacion muy popular en Data Mining.

    Dado un conjunto de entrenamiento, el objetivo de clasificacion esel de entrenar un modelo para predecir las etiquetas de las clases.

    Luego de que el modelo es entrenado, se utiliza para analizar nuevosdatos y hacer predicciones.

    La calidad de la clasificacion se mide en accuracy : se refiere al gradode ajuste entre el modelo y los datos

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 5 / 28

  • Introduccion

    Por lo general, los datasets son muy grandes, usan pequenasproporciones o subconjuntos que permitan acelerar las tareas.

    Es posible generar una familia de predictores usando diferentessubconjuntos del dataset de entrenamiento y combinar esospredictores y obtener accuracy mas alto.

    Al usar tecnicas de ensamblado, se obtienen altos accuracy a unmenor costo. Existen muchas variantes de tecnicas de ensamblado,como por ejemplo Bagging [REFERENCIA] y Boosting[REFERENCIAS]

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 6 / 28

  • 1 Introduccion

    2 Ensamblados

    3 Ensamblados Paralelos

    4 Evaluacion y Resultados

    5 Conclusiones

    6 Propuesta

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 7 / 28

  • Bagging

    Bagging (Boostrap Aggregating): metodo para generar multiplesversiones de un predictor.

    Esta agregacion promedia sobre las versiones y usa esta pluralidadcuando se quiere predecir una clase.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 8 / 28

  • Algoritmo Bagging

    Figura : Algoritmo Bagging

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 9 / 28

  • Adaboost

    Adaboost utiliza perturbacion y combinacion. Adopta la forma deremuestreo adaptativo y combina los pesos en la etapa de remuestreo,donde los datos mal clasificados obtienen mayor ponderacion. Lacombinacion tambien se hace por votacion.

    Para Adaboost, el conjunto de pesos se mantiene sobre el conjuntode entrenamiento. Una forma de implementarlo en la practica esremuestrear el dataset basado en los pesos de las instancias. El pesode cada instancia se ajusta en cada ronda de acuerdo a las instanciasclasificadas correctamente o no.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 10 / 28

  • Algoritmo Adaboost

    Figura : Algoritmo Adaboost

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 11 / 28

  • 1 Introduccion

    2 Ensamblados

    3 Ensamblados Paralelos

    4 Evaluacion y Resultados

    5 Conclusiones

    6 Propuesta

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 12 / 28

  • Parallel Bagging

    Se divide el conjunto de entrenamiento en P subconjuntos (oProcesadores) y se asignan cada subconjunto a un procesador. Estesubconjunto sera el datasert local de entrenamiento en cadaprocesador.

    Cada uno de los procesadores crea su conjunto replica boostrap(remuestreo con reemplazo), del conjunto de entrenamiento.

    Cada procesador ejecuta el mismo algoritmo de data mining en estamuestra local y genera un predictor de este. El proceso se repite Rveces hasta que R x P predictores se obtienen. Donde el valor de Rdepende de las propiedades del dataset, del tamano de la muestra y elnumero de predictores que se utilizan actualmente.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 13 / 28

  • Parallel Bagging

    La tecnica de Bagging funciona ya que genera una familia depredictores agregandolos por votacion o promedio.

    Parallel Bagging reduce el acceso a los datos al particionar elconjunto de datos completo. Al usar muestras de tamao pequeo seayuda a disminuir el tiempo de entrenamiento.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 14 / 28

  • Algoritmo Parallel Bagging

    Figura : Algoritmo Bagging Parallel

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 15 / 28

  • Parallel Adaboost

    Suponer P procesadores. El conjunto completo de datos se divide enP subconjuntos y cada subconjunto se asigna a un procesador comoconjunto de entrenamiento local a cada procesador. Una distribucionde este conjunto de entrenamiento local se mantiene en cadaprocesador.

    Esta distribucion representa la seleccion de probabilidad de cadainstancia desde el conjunto de entrenamiento local. La probabilidadde cada ejemplo se inicializa en 1

    n, donde n es el numero de ejemplos

    del conjunto de datos de entrenamiento.

    El subconjunto selecciona basado en la probabilidad de que cadainstancia en cada procesador para formar la muestra.

    El mismo algoritmo de data mining se aplica a cada una de lasmuestras locales y se genera un predictor.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 16 / 28

  • Parallel Adaboost

    Entonces un intercambio total entre todos los procesadores seejecuta, cada procesadorpasa su predictor local a todos los otrosprocesadores, por lo que ahora cada procesador tiene P predictores.

    En las siguiente ronda, en cada procesador, una nueva muestra seforma basada en la distribucion actualizada y un predictor se generanuevamente de esta nueva muestra, seguido por el intercambio totalde los predictores generados en esta etapa y en la actualizacion de ladistribucion.

    Mismo procedimiento se repite R veces hasta que finalmente R x Ppredictores se obtienen, donde R es el numero de iteracionesdefinidas por el usuario.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 17 / 28

  • Parallel Adaboost

    Este entrenamiento termina con R x P predictores. Luego todos estospredictores se utilizan con los nuevos datos de test.

    Para calcular el accuracy, todos los predictores votan en el conjuntode test con un peso log( 1

    para obtener la salida final del predictor

    combinado.

    En [REFERENCIA] se puede observar que Adaboost obtiene mejoresresultados que Bagging.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 18 / 28

  • Algoritmo Parallel Adaboost

    Figura : Algoritmo Adaboost Parallel

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 19 / 28

  • 1 Introduccion

    2 Ensamblados

    3 Ensamblados Paralelos

    4 Evaluacion y Resultados

    5 Conclusiones

    6 Propuesta

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 20 / 28

  • Medidas de evaluacion y performance

    Accuracy de Clasificacion: habilidad de predecir correctamente lasetiquetas nuevas.

    Tiempo de Ejecucion: tiempo comprendido entre el comienzo y elfinal en la ejecucion de un programa.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 21 / 28

  • Bagging Secuencial y Bagging Paralelo

    Figura : Comparacion Accuracy y Tiempo de Ejecucion

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 22 / 28

  • Adaboost Secuencial y Adaboost Paralelo

    Figura : Comparacion Accuracy y Tiempo de Ejecucion

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 23 / 28

  • 1 Introduccion

    2 Ensamblados

    3 Ensamblados Paralelos

    4 Evaluacion y Resultados

    5 Conclusiones

    6 Propuesta

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 24 / 28

  • Conclusiones

    Ambos algoritmos se pueden paralelizar.

    EL accuracy esta limitado por el tamao de la muestra.

    Parallel Adaboost supera a Parallel Bagging en precision, lo que sefundamenta principalmente en el poder adapativo del remuestro.

    Parallel Adaboost es mas barato que Parallel Bagging, debido a lasfrecuentes repeticiones en las muestras generadas en este ultimo, enlas rondas subsiguientes. Se necesita menos tiempo.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 25 / 28

  • 1 Introduccion

    2 Ensamblados

    3 Ensamblados Paralelos

    4 Evaluacion y Resultados

    5 Conclusiones

    6 Propuesta

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 26 / 28

  • Propuesta

    Figura : Ejemplo Simplex

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 27 / 28

  • Propuesta

    Objetivo 1: Paralelizar un Ensamblado de Topic Models.

    Objetivo 2: Disminuir los tiempos de ejecucion del algoritmosecuencial.

    Objetivo 3: Probar Bagging y Adaboost Paralelo aplicado a TopicModels con gran volumen de datos.

    Pablo Ormeno A. (UTFSM) Parallel Ensemble Junio 2015 28 / 28

    IntroduccinEnsambladosEnsamblados ParalelosEvaluacin y ResultadosConclusionesPropuesta