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

Undécima Clase: Operaciones Matriciales Distribuidas

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 11

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-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Material de lectura

Clase pasada:

Brewer's conjecture and the feasibility of consistent, available,
partition-tolerant web services por S Gilbert, N Lynch

ACM SIGACT News, 2002

CAP twelve years later: How the" rules" have changed por E
Brewer

Computer, 2012

http://en.wikipedia.org/wiki/Fallacies_of_Distributed_Computing

Ésta clase:

Capítulo 6 del Owen et al. (2012)
http://www.cs.utah.edu/~jep/teaching/cs7960/L17-MR-
Matrix+DB
Scalable Scientic Computing Algorithms Using MapReduce
por Xiang Jingen, Master of Mathematics, CS School,
UWaterloo 2013

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

BDML-clase11-17/09

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

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Preguntas

¾Qué tipo de decisiones CAP hace hadoop?

Pierde Disponibilidad

CAP parece más orientado a datos que a cómputo:

En realidad los datos se reere a un cierto "estado global" o
compartido
Un problema que afecta cualquier tipo de programa con estado
(excepto programación funcional perezosa)

Bases de datos, sistemas de archivos distribuidos, etc
Por eso las bases NoSQL no soportan ACID

¾Hay contextos prácticos donde no import Consistencia o
Disponibilidad?

Falta de consistencia: decoraciones, datos de menor
importancia
Falta de disponibilidad: proceso por lotes

Java para pythoneros (lista)
Preguntas sobre el práctico y su actualización
BDML-clase11-17/09

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

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

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-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Las 8 falacias del cómputo distribuido

Todo programador comete alguno de estos errores cuando
empieza cómputo distribuido (L. Peter Deutsch y otros):

1 La red es conable
2 Hay cero latencia
3 El ancho de banda es innito
4 La red es segura
5 La topología no cambia
6 Hay un sólo administrador
7 El costo de transporte es cero
8 La red es homogénea

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Revisión CAP

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

Consistencia
Disponibilidad (Availability)
Tolerancia a particiones de la red (Partition-tolerance)

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Teorema CAP asíncrono

Dado el modelo de cómputo asíncrono, no es posible garantizar
Consistencia y Disponibilidad
Demostración:

por el absurdo, se construye una cadena de ejecución que
actualiza un valor v en un nodo y se pierden los mensajes de
actualización en el otro

cuando se pide el valor de v en el otro nodo, por
Disponibilidad el otro nodo tiene que responder y responde con
el valor equivocado

Corolario:

Tampoco se puede garantizar Consistencia y Disponibilidad
aún cuando no se pierdan mensajes (pero se puedan demorar
lo suciente como para que se de la construcción por el
absurdo del teorema).

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Teorema CAP revisitado

Formalización clásica ignora el concepto de latencia, pero es
clave.

Durante un time-out, el programa debe decidir:

1 cancelar la operación (afecta Disponibilidad)
2 continuar la operación (afecta Consistencia)

Continuar re-intentando es elegir Consistencia en vez de
Disponiblidad

También está la cuestión práctica... es posible realmente elegir
Consistencia+Disponibilidad? Tarde o temprano la red fallará

Interpretación probabilística de C, A y P

Nuevo énfasis en recuperación después de particiones

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Distribución de Matrices Dispersas

Según el tipo de operación, distribuimos las o columnas
Si una la o columna no entra en un solo nodo, distribuimos
franjas de las o columnas

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Multiplicación de una matriz por un vector

 a11
 a11x1 + a12x2 +··· + a1nxn

. . .
a1n
. . .
a2n
...
...
. . . amn
a21x1 + a22x2 +··· + a2nxn

a12
a22
...
am2

am1x1 + am2x2 +··· + amnxn



 =

 x1


x2
...
xn

Ax =

a21
...
am1

...

http://mathinsight.org/matrix_vector_multiplication

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Matriz por vector en MR

Entrada: Matriz M = n× n, vector V = n× 1
Salida: Vector X = M ∗ V

xi = ∑n

j=1 mij ∗ vj

Map(i, <la i de M, V >):

(j,mij ∗ vj )

Reduce(j,mij ∗ vj ):
j=1 mij vj

xi = ∑n

Si V no entra en un mapper, distribuir franjas de V a cada
mapper

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Multiplicación de Matriz por Matriz

 b11 b12

b21 b22
...
...
bn1 bn2

 =

 b11


b21
...
bn1



 b12

b22
...
bn2

···

 b1p

b2p
...
bnp




. . . b1p
. . . b2p
...
...
. . . bnp

http://mathinsight.org/matrix_vector_multiplication

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Matriz por Matriz dispersa

Una concatenación de los vectores obtenidos de multiplicar las
columnas de la segunda matriz por la primera
La clave recibida en el mapper es una clave compuesta y
recibe la la y la columna sobre la que se está operando
Map((i, k), <la i de M, columna k deB >):

((j, k),mij ∗ njk )
el índice de la columna nal es el mismo que el de la columna
en al segunda matriz

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Multiplicación de Matrices Densas

División por bloques
La multiplicación de un bloque por el otro entra en la memoria
de cada nodo
HAMA

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Álgebra Relacional

Para matrices booleanas es posible implementar unión e
intersección en MR
Muy similar al ejemplo de conteo de palabras

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Solución de Ax = b

Dados una matriz A simétrica y denida positiva y un vector
B, buscamos un vector x tal que Ax = b
Método del gradiente conjugado:

2 x T Ax − bT x + c
2 AT x + 1

Denimos f (x) = 1
Entonces f (cid:48)(x) = 1
La ecuación Ax = b tiene un cero en los puntos críticos de la
ecuación de arriba

2 Ax − b = Ax − b

Usamos el gradiente conjugado para decidir la dirección de
búsqueda y una búsqueda lineal para optimizar el tamaño del
paso en esa dirección
Ver paper de HAMA para los detalles

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Descomposición LU

A = LU

Para mejorar la estabilidad numérica se suele usar una
permutación P de A
L es triangular inferior, U es triangular superior

Las matrices triangulares son fáciles de invertir

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

BDML-clase11-17/09

Undécima Clase: Operaciones Matriciales Distribuidas

Clase anterior
Aplicaciones Matriciales Distribuidas

Descomposición LU en MR

(adaptado de Xiang Jingen, 2013)

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

BDML-clase11-17/09