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

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 13

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-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Clase anterior

Material de lectura

Clase pasada:

Scalable Scientic Computing Algorithms Using MapReduce
por Xiang Jingen, Master of Mathematics UWaterloo '13

https://uwspace.uwaterloo.ca/bitstream/handle/10012/7830/Xiang_Jingen.pdf

Parallelized stochastic gradient descent por Zinkevich, Weimer,
Li, Smola (NIPS 2010)

Ésta clase:

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/

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Clase anterior

Preguntas

½Sin preguntas!

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

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-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Temas Claves

Identicación de la máxima tarea que puede hacerse por nodo
Descomposición de la tarea normal en tareas por nodo
Tareas globales, realizadas en un nodo (central) y tareas
paralelas
Comunicación entre tareas mediante HDFS y archivos bandera
Tareas que sólo hacen Map
Cálculos intermedios

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Descomposición LU

(adaptado de Xiang Jingen, 2013)

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Descomposición LU en MR

(adaptado de Xiang Jingen, 2013)

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Descomposición LU en MR

(adaptado de Xiang Jingen, 2013)

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

El algoritmo a vuelo de pájaro

Dividir la matriz original recursivamente hasta que
L1U1 = P1A1 sea soluble en una máquina
Descomponer A1
Calcular U2
(cid:48)
Calcular la permutación de L2, L
2
Calcular B = A4 − L
Descomponer B
Armar la salida total a partir las partes

2U2

(cid:48)

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Implementación en MapReduce

1 Nodo master crea archivos de control que son usados como

entrada a las tareas map subsecuentes

Falsas entradas

2 Una tarea MapReduce subdivide A de manera recursiva
3 Se envian tareas MapReduce para L

(cid:48)
2, U2 y B

L1 y U1 son ejecutadas en el master node si A1es lo
suficientemente pequeña

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Número de Tareas

m0 es la cantidad de máquinas en el cluster
nb es el máximo tamaño de una matriz para computar en un
solo nodo

Número de tareas será 2

log2

n
nb

(cid:108)

(cid:109)

:

(adaptado de Xiang Jingen, 2013)

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Ejecución

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

(adaptado de Xiang Jingen, 2013)

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

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-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Algoritmo en nodo worker

(adaptado de Zinkevich et al, 2010)

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Algoritmo en nodo central

(adaptado de Zinkevich et al, 2010)

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

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-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Más allá de MapReduce:

MPi: Message Passing Interface

AMQP: Advanced Message Queuing Protocol

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

MPI

Estándar de facto

Desde 1994
Tres revisiones
Especicaciones independientes del lenguaje para llamadas de
función

CORBA o RPC
Mucha menor latencia entre llamadas

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

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

MPI

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-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Decisiones de diseño

Todo el paralelismo es explícito
Distintas implementaciones (en distinto hardware) sólo
requieren recompilación del código

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

BDML-clase13-1/10

Décima Tercera Clase: Métodos Alternativos
Clase Anterior
Descenso por el gradiente distribuido
Método de Dirección Alternada de Multiplicadores
Métodos Alternativos
UIMA

Implementación de ejemplo: MPICH

Programas mpicc y mpiexec
ssh con certicados (sin password)
mpiexec -f lista-de-hostnames -n <número>
programa-ejecutable

La lista de hostnames puede tener de manera opcional el
número de cores después de un :

mpiexec -f lista-de-hostnames -n 1 ./master : -n 15 ./slave
Diferentes métodos de comunicación entre procesos

Más recient "némesis" usa memoria compartida para procesos
en la misma máquina y sockets (o Myrinet-MX) para
comunicación