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

Aprendizaje Automático sobre Grandes Volúmenes de Datos - Clase 14gráfica de visualizaciones

Actualizado el 21 de Marzo del 2018 (Publicado el 12 de Diciembre del 2017)
514 visualizaciones desde el 12 de Diciembre del 2017
426,3 KB
24 paginas
Creado hace 9a (06/10/2014)
Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 14

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-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Clase anterior

Material de lectura

Clase pasada:

Alternating Direction Method of Multipliers (Boyd et al. 2011)

web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf
MPI (http://en.wikipedia.org/wiki/Message_Passing_Interface)

http://www.mpich.org/

Colas de pasaje de mensajes
(http://en.wikipedia.org/wiki/Advanced_Message_Queuing_Protocol)

http://activemq.apache.org/

Ésta clase:

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

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Clase anterior

Preguntas

¾Cuándo usar MR vs. MPI vs. AMQ?

MR: programadores sin experiencia en cálculo distribuido,
hardware barato
MPI: hardware dedicado de buena calidad
AMQ: programadores con experiencia en cálculo distribuido,
hardware con acceso restringido a Internet

¾Cómo calcular la tarea máxima?

Depende de la tarea y las máquinas

¾MPI con DFS?

Es posible, pero no dá el caso de uso

Distribución de datos en descenso por el gradiente, ¾se realiza
al comienzo?

Sí, y por eso se puede usar una implementación de descenso
por el gradiente ya conocida

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Clase anterior

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-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Filmínas de la defensa de Jingen Xiang

Filmínas 28-36

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Zinkevich et al., NIPS 2010

Distribuir los datos al azar entre nodos
Realizar descenso por el gradiente en cada nodo, por separado
Unicar los resultados en un nodo central

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Algoritmo en nodo worker

(adaptado de Zinkevich et al, 2010)

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Algoritmo en nodo central

(adaptado de Zinkevich et al, 2010)

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Dirección Alternada de Multiplicadores

Optimizar dos funciones a la vez

Problema similar a regresión logística y SVMs
Alternar la optimización de una función y la otra

Clave: en ciertas condiciones, la primera optimización se puede
hacer en paralelo mientras que la segunda es reducida y puede
hacerse en una sola máquina

minimizar
f (x) + g (z)
dado que Ax + Bz = c

Ver Distributed Optimization and Statistical Learning via the
Alternating Direction Method of Multipliers (201) por Boyd,
Parikh, Chu, Peleato, Eckstein

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

MPI

Estándar de facto

Desde 1994
Mismo programa en todos los nodos, se pasan datos entre ellos

Provee:

Topología virtual, Sincronización, Comunicación

Funciones:

Comunicación punto-a-punto (rendez-vous), send/receive
Topología Cartesiana o de grafo general
Combinar resultados parciales (gather/reduce)
Sincronización de nodos (barreras)
Información general (número de nodos, número de nodo
actual, vecinos, topología)

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

MPI vs. MapReduce

MapReduce es un subconjunto del estándar MPI

Operaciones collectivas y operaciones de usuario

MPI no es tolerante a fallas
MPI provee muchas más primitivas

Requiere que el programador se ocupe de muchos más detalles

En el caso de inversión de matrices, la implementación MPI es
más eciente para matrices pequeñas pero tiene mucho mayor
overhead de comunicación

Escala de manera más pobre

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Message Queues

Message-Oriented Middleware (MOM)

Soporte por software o hardware
Envío y recepción de mensajes
Redes distribuidas heterogéneas
Normalmente asíncrono

Colas
Potencialmente persistentes (tolerancia a fallos)

Ruteo
Potencial transformación

Requiere un message transfer

Talón de Aquiles

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

AMQP vs. MapReduce

El broker es el eslabón más débil
Topología explícita en AMQP

Más versátil
Más trabajo por parte del programador

Tolerancia a fallas de AMQP es potencialmente mejor que
MapReduce

Cómputos intermedios pueden ser mantenidos en colas
persistentes

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Naive Bayes

Teorema de Bayes

P(y|(cid:126)f ) =

P((cid:126)f |y )P(y )

P((cid:126)f )

Naive Bayes asume que las features son probabilisticamente
independientes
yNB = maxy P(f1, ..., fn|y )P(y ) = maxy P(f1|y )...P(fn|y )P(y )

Podemos estimar P(fi|y ) a partir de conteos

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

NB: de conteos a probabilidades

Conteos de instancias (Ni ) vs. conteos de features (Nf )
De la denición de probabilidad conjunta:
P(”.com”|Arts)P(Arts) = P(”.com”, Arts) =
Nf (”.com”, Arts)

Nf (.)

De la denición de probabilidad simple:

P(Arts) =

Ni (Arts)

Ni (.)

Despejando para la probabilidad condicional:
P(”.com”|Arts) =

Nf (”.com”, Arts)

Ni (.)
Nf (.)

Ni (Arts)

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Ejemplo: Contar Palabras

map(input_key: DocName, input_value: DocText):

for each word w in input_value:

EmitIntermediate(w, 1)

reduce(output_key: Word, intermediate_values: List[Int]):

int result = 0
for each v in intermediate_values:

result += v

Emit(result)

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Naive Bayes en MapReduce

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-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

En python

https://github.com/analyticbastard/myml/blob/master/myml/supervised/bayes.py

def map(self , key, value):

for i, k in enumerate (key):

yield (value, i), k

def reduce(self , key, values):

val = set (values)
N = len (values)
for newkey in val:

yield (key[0], key[1], newkey), 1.0*np.sum(values
== newkey)/N

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Implementación Alternativa

Necesitamos calcular:

#(Y=*): número total de instancias (documentos)
#(Y=y): número de instancias por valor de la función
objetivo (etiqueta)
#(Y=y,F=*): número de valores de features (palabras) para
un cierto valor de la función objetivo (etiqueta)
#(Y=y,F=v): numero veces un cierto valor de una cierta
feature (palabra) aparece bajo un cierto valor de la función
objetivo (etiqueta)
dom(X): cuántos valores posibles pueden tomar las features
(vocabulario)
dom(Y): cuántos valores puede tomar la función objetivo
(etiquetas)

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

BDML-clase14-6/10

Décima Cuarta Clase: Paralelizando Naive Bayes
Clase Anterior
Paralelizando Naive Bayes

Calculando valores independientes de las instancias

(Adaptado de http://spectrallyclustered.wordpress.com/2013/02/20/naive-bayes-on-hadoop/)

© 2014 Pablo Dubou
  • Links de descarga
http://lwp-l.com/pdf7852

Comentarios de: Aprendizaje Automático sobre Grandes Volúmenes de Datos - Clase 14 (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad