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

Novena Clase: Map Reduce

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 9

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-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Material de lectura

Clase pasada:

Capítulo 2 y 4 del Owen et al. (2012)

Ésta clase:

MapReduce: Simplied Data Processing on Large Clusters by
Jerey Dean and Sanjay Ghemawat

OSDI'04: Sixth Symposium on Operating System Design and
Implementation, San Francisco, CA, December, 2004

The Google File System by Sanjay Ghemawat, Howard Gobio,
and Shun-Tak Leung

19th ACM Symposium on Operating Systems Principles, Lake
George, NY, October, 2003.

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Preguntas

k-Means y features de tipo enumeración

¾Cómo denir el centroide para features categoriales (e.g.,
"frío, calor, templado")?
En ese caso el centroide no necesita tener la misma
representación que los elementos normales

Distribución de probabilidad sobre cada categoría
Hay dos funciones de distancia: distancia entre instancias y
distancia entre instancia y centroide
Evaluación de sistemas de recomendación

Evaluar sistemas de recomendación es todavía un problema
abierto
Se utilizan técnicas donde se mantiene un porcentaje de
preferencias oculto y después se usa Precision/Recall para
evaluar

Técnica "injusta" y depende de cada partición

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

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-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Cómputo Distribuido

MapReduce
Teorema CAP
Operaciones Matriciales Distribuidas
Descenso por el Gradiente (Búsqueda distribuida)
Algoritmos actualizables, Colas, shared memory
Paralelizando Algoritmos de Aprendizaje Automático

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Modelo de Cluster de Máquinas

Máquinas autónomas con espacio de disco local

Sin memoria compartida

Con una topología de red jerárquica

Máquinas en un mismo switch
Máquinas en un mismo rack

Máquinas de poca conabilidad

Fallas en el sistema son algo no solo probable si no esperable

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

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-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Teorema CAP

Cuando estamos en un ambiente distribuido, de estas tres
características sólo podes escoger dos:

Consistencia
Disponibilidad
Tolerancia a particiones de la red

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Operaciones Matriciales Distribuidas

Distribución de matrices a nodos
Matriz por Vector
(Matriz por Matriz)
(Inversión Matricial)

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Descenso por el Gradiente

Descenso por el Gradiente

Parallelized stochastic gradient descent por M Zinkevich, M
Weimer, L Li, AJ Smola en NIPS 2010

Búsqueda distribuida

(Algoritmos genéticos)

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Otros Modelos

Sistemas por Colas
Memoria Compartida

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Paralelizando Algoritmos

Algoritmos Actualizables

Naive Bayes

Random Forests
(Regresión Logística)

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Objetivo

Simplicar el acceso al cómputo de gran volúmen de datos
para programadores sin experiencia en cómputo distribuido
Simplicar la tolerancia a fallas
Simplicar la alocación de recursos (máquinas, disco y red)

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Modelo de Programación

Computa una función f ({(kin, vin)}) → {(kout, list(vout)}

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

Para cada par (clave, valor) de entrada, produce una lista de
pares de otros claves y valores intermedios

reduce(kout, list(vint)) → list(vout)

Acumular los valores intermedios según su clave de salida
Generar la salida combinada

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

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-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Ejemplos de Uso en Google

distributed grep
distributed sort
web link-graph reversal
term-vector per host
web access log stats
inverted index construction
document clustering
machine learning
statistical machine translation

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Ejecución

(fuente: http://research.google.com/archive/mapreduce-osdi04-slides/index-auto-0007.html)

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

En Paralelo

(fuente: http://research.google.com/archive/mapreduce-osdi04-slides/index-auto-0008.html)

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

Las máquinas pueden ser re-usadas para realizar tareas Map y
Reduce
A medida que las tareas Map terminan, las máquinas pueden
ser utilizadas para hacer tareas Reduce
Load Balancing dinámico
Ejemplo de http://research.google.com/archive/mapreduce-
osdi04-slides/index-auto-0010.html

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Pipelining

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

Tolerancia a Fallas

Si el master muere, el sistema cae
Si un worker muere el sistema se da cuenta via heartbeats

Re-ejecución de tareas fallidas
Re-ejecución de tareas en ejecución

Mejora el peor caso (ejecución redundante)

Semántica en caso de fallas:

No presenta problemas para tareas determinísticas

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

BDML-clase9-10/09

Novena Clase: Map Reduce

Clase anterior
Cómputo Distribuido
Map/Reduce

GFS y Localidad de los Datos

El GFS es un sistema de archivos distribuído

Diseñado para trabajar bien con el modelo de cluster que
hablamos antes

Los archivos son divididos en chunks de tamaño jo y
replicados en los nodos

Usualmente un nivel de réplica de 3 copias por chunk

Una buena implementación de MapReduce asigna