PDF de programación - Aprendizaje Automático sobre Grandes Volúmenes de Datos - Clase 15

Décima Quinta Clase: Paralelizando Árboles de Decisión

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 15

Pablo Ariel Duboue, PhD

Universidad Nacional de Córdoba,

Facultad de Matemática, Astronomía y Física

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Material de lectura

Clase pasada:

Tackling the Poor Assumptions of Naive Bayes Text Classiers

Rennie et al., ICML 2003
http://people.csail.mit.edu/jrennie/papers/icml03-nb.pdf

http://www.cs.columbia.edu/~smaskey/CS6998-
0412/slides/week7_statnlp_web.pdf
http://spectrallyclustered.wordpress.com/2013/02/20/naive-bayes-on-
hadoop/
http://machinomics.blogspot.com.ar/2013/11/naive-bayes-with-map-
reduce.html

Ésta clase:

Random Forests

Breiman, Machine Learning (2001)

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Preguntas

Ejemplo en python de la clase pasada, ¾cuál es la plataforma
subyacente?

Una plataforma de ejemplo del autor
Implementar MapReduce sin localidad de datos ni redundancia
a fallas es muy sencillo

¾El método de aprendizaje que yo elija va a depender del
problema o con todos puedo lograr resultados en cualquier
escenario?

No Free Lunch Theorem!

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Recordatorio

El sitio Web de la materia es http://aprendizajengrande.net

Allí está el material del curso (lminas, audio)

Leer la cuenta de Twitter https://twitter.com/aprendengrande
es obligatorio antes de venir a clase

Allí encontrarán anuncios como cambios de aula, etc
No necesitan tener cuenta de Twitter para ver los anuncios,
simplemente visiten la página
Suscribirse a la lista de mail en
[email protected] es optativo

Si están suscriptos a la lista no necesitan ver Twitter

Feedback para alumnos de posgrado es obligatorio y rmado,
incluyan si son alumnos de grado, posgrado u oyentes

El "resúmen" de la clase puede ser tan sencillo como un
listado del título de los temas tratados

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Naive Bayes en MapReduce

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

map(clave={features con nombres y valores}, valor: función
objetivo)

devuelve clave=función objetivo:nombre del features,
valor=valor del feature

reduce(clave=función objetivo y0:nombre del feature Fi ,
valor=valor del feature vi,0):

calcular P(Fi = vi,0|y = y0):

Calcular la suma sobre todos los valores posibles para el
feature dado y usarla para normalizar

devuelve clave=función objetivo:nombre del feature,
valor=valor del feature:probabilidad

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Algoritmos Actualizables

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Naive Bayes pertenece a una familia de algoritmos que pueden
ser actualizados

Es posible agregar más datos una vez el algoritmo ya ha sido
entrenado

En muchos casos los algoritmos actualizables pueden ser
paralelizados calculando las actualizaciones en paralelo y
aplicandolas nalmente en el nodo central
Entrenamiento de redes neuronales en modo batch

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Búsqueda Distribuída

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

En el método de Hill Climbing con restarts se explora un
espacio de búsqueda en la dirección de mayor mejora hasta
que se estabiliza el valor

En ese momento se vuelve a retomar la búsqueda desde un
punto al azar
Salirse de máximos locales
El algoritmo devuelve el mejor valor encontrado en todos los
restarts

Se puede considerar cada restart como corriendo en paralelo

Paralelización trivial

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Corrigiendo los errores de Naive Bayes

Tackling the Poor Assumptions of Naive Bayes Text Classiers

Rennie et al., ICML 2003

Naive Bayes tiene problemas con:

Clases desbalanceadas
Mayoría de datos dependientes en una clase vs. en otra
Distribuciones especícas a datos textuales

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Naive Bayes Multinomial

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

m clases c, n cantidad de features (palabras) fi , necesitamos
estimar los parámetros (cid:126)θc = {θc1, . . . ,θcn} tales que ∑i θci = 1

Estimador MAP:

mapNB (d ) = argmaxc

(cid:34)
log p((cid:126)θc ) +∑

i

p(d|(cid:126)θc ) =

(∑i fi )!
∏i fi ! ∏(θci )fi
(cid:35)

fi logθci

= argmaxc

(cid:34)
bc +∑

i

(cid:35)

fi wci

Con smoothing de Dirichlet (Nci , cantidad de veces la palabra
i aparece en documentos con la categoría c; Nc, total de
palabras en la clase c; αi , valores de smoothing; α = ∑αi ):

ˆθci =

Nci + αi
Nc + α

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Mejoras

Cuando hay muchas más instancias para un valor de la función
objetivo que para otras, el valor con menos instancias sufre
En vez de estimar la probabilidad de que las features
observadas correspondan con un cierto valor de la función
objetivo, estimar que no correspondan

Naive Bayes Complementario

ˆθ¯c i =

mapCNB (d ) = argmaxc

N¯c i + αi
(cid:34)
Nc + α
log p((cid:126)θc )−∑

(cid:35)

fi log ˆθ¯c i

i

Normalizar vectores para contrarrestar features dependientes

log ˆθci

(cid:12)(cid:12)(cid:12)log ˆθck

(cid:12)(cid:12)(cid:12)

∑k

ˆwci =

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Meta-learning y métodos ensemble

Una técnica para obtener mejores resultados es combinar
clasicadores

Votación
Entrenar un segundo clasicador

Otras técnicas de meta-learning involucran cambiar el peso de
cada instancia

De ciertos ejemplos se puede aprender más que otros
Parecido al concepto de support vector

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Random Forests

Generar un gran conjunto de árboles de decisión repitiendo el
siguiente algoritmo:

Tomar un subconjunto de los datos de entrenamiento al azar,
con reemplazo
Para la construcción de los nodos de cada árbol, tomar un
subconjunto de features al azar y realizar la división en el nodo
usando sólo esas features

Para predecir, usar todos los árboles a la vez y quedarse con el
valor predicho más frequente
Por la Ley de los Grandes Números, a partir de cierto punto
agregar más árboles no cambia el resultado del clasicador
Muy tolerantes a ruido y a features nocivas

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Midiendo el Error de Generalización

Los Random Forests permiten medir el error de generalización
utilizando árboles out-of-bag:

Medimos el error de generalización sobre el mismo conjunto de
datos sobre el cual se entrenó el random forest
Para cada instancia de entrenamiento, calculamos la clase
predicha por el random forest completo, y la comparamos con
la clase predicha por los árboles que no utilizaron esa instancia
para entrenarse
Es similar a cros-validación pero Breiman (2001) explica que es
un estimador sin sesgo mientras que cros-validación comparte
el sesgo del algoritmo original

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Paralelizando Random Forests

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Paralelizar Random Forests es trivial en la medida que
podamos obtener un muestreo con reemplazo en cada nodo de
manera eciente

A priori ésto no parece posible en Hadoop a causa de la
localidad de datos
Un mapper que asigna varios valores al azar para cada dato
leido y reducers que computan los árboles en sí

Apache Mahout (según su documentación Web) no utiliza
muestreo con reemplazo si no que divide el conjunto de
entrenamiento de manera completa

El número de árboles es el número de mappers

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Resúmen

MapReduce
Teorema CAP
Operaciones matriciales distribuídas

Descomposición LU

Descenso por el gradiente distribuido
MPI y AMQ
Paralelización de Naive Bayes y Árboles de Decisión

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

MapReduce

Modelo de cómputo que simplica el uso de clusters
Computa una función f ({(kin, vin)}) → {(kout, list(vout)}

map(kin, vin) → list(kout, vint)
reduce(kout, list(vint)) → list(vout)

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase15-8/10

Décima Quinta Clase: Paralelizando Árboles de Decisión

Clase anterior
Clase Anterior
Random Forests
Cierre Cómputo Distribuido

Teorema CAP