Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 12

Pablo Ariel Duboue, PhD

Universidad Nacional de Córdoba,
Facultad de Matemática, Astronomía y Física

None.1 Duodécima Clase: Descomposición LU distribuida

None.1.1 Clase anterior

Material de lectura

Clase pasada:
- Capítulo 6 del Owen et al. (2012)
- http://www.cs.utah.edu/~jeffp/teaching/cs7960/L17-MR-Matrix+DB
- HAMA: An efficient matrix computation with the mapreduce framework por Seo, Yoon, Kim, Jin, Kim, Maeng
  - CloudCom, 2010
Ésta clase:
- Scalable Scientific Computing Algorithms Using MapReduce por Xiang Jingen, Master of Mathematics UWaterloo ’13
  - https://uwspace.uwaterloo.ca/bitstream/handle/10012/7830/Xiang_Jingen.pdf
- Design and Evaluation of Parallel Block Algorithms: LU Factorization on an IBM 3090 VF/600J, por Dackland, Elmroth, Kågström, Van Loan.
  - 5th SIAM Conf. on Parallel Processing for Scientific Computing, 1991
- Parallelized stochastic gradient descent por Zinkevich, Weimer, Li, Smola (NIPS 2010)

Preguntas

Preguntas sobre LU (hoy)
Representaciones estándar
- HIVE
Ejemplo de Map/Reduce
- Próxima clase
Material de lectura previo
- Ahora en Twitter / Lista
Metodología de evaluación

Recordatorio

El sitio Web de la materia es http://aprendizajengrande.net
- Allí está el material del curso (filminas, 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 aprendizajengrande@librelist.com es optativo
- Si están suscriptos a la lista no necesitan ver Twitter
Feedback para alumnos de posgrado es obligatorio y firmado, 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

Distribución de Matrices Dispersas

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

Multiplicación de una matriz por un vector

Ax = ⎡⎢⎢⎢⎢⎢⎣ a₁₁ a₁₂ … a_1n a₂₁ a₂₂ … a_2n ⋮ ⋮ ⋮ ⋮ a_m1 a_m2 … a_mn ⎤⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎣ x₁ x₂ ⋮ x_n ⎤⎥⎥⎥⎥⎥⎦ = ⎡⎢⎢⎢⎢⎢⎣ a₁₁x₁ + a₁₂x₂ + ⋯ + a_1nx_n a₂₁x₁ + a₂₂x₂ + ⋯ + a_2nx_n ⋮ a_m1x₁ + a_m2x₂ + ⋯ + a_mnx_n ⎤⎥⎥⎥⎥⎥⎦

http://mathinsight.org/matrix_vector_multiplication

Matriz por vector en MR

Entrada: Matriz M = n × n, vector V = n × 1
Salida: Vector X = M*V
- x_i = ∑ⁿ_j = 1m_ij*v_j
Map(i, <fila i de M, segmento de V entre b_s y b_e>):
- (i,∑^b_e_{j = b_s}m_ij*v_j)
Reduce(i,∑^b_e_{j = b_s}m_ij*v_j):
- x_i = ∑ⁿ_j = 1m_ijv_j

Multiplicación de Matriz por Matriz

⎡⎢⎢⎢⎢⎢⎣ b₁₁ b₁₂ … b_1p b₂₁ b₂₂ … b_2p ⋮ ⋮ ⋮ ⋮ b_n1 b_n2 … b_np ⎤⎥⎥⎥⎥⎥⎦ = ⎡⎢⎢⎢⎢⎢⎣⎡⎢⎢⎢⎢⎢⎣ b₁₁ b₂₁ ⋮ b_n1 ⎤⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎣ b₁₂ b₂₂ ⋮ b_n2 ⎤⎥⎥⎥⎥⎥⎦⋯⎡⎢⎢⎢⎢⎢⎣ b_1p b_2p ⋮ b_np ⎤⎥⎥⎥⎥⎥⎦⎤⎥⎥⎥⎥⎥⎦

http://mathinsight.org/matrix_vector_multiplication

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 fila y la columna sobre la que se está operando
Map((i, k), <fila i de M, columna k deB >):
- ((i, k),∑ⁿ_j = 1m_ij*n_jk)
- el índice de la columna final es el mismo que el de la columna en al segunda matriz

Solución de Ax = b

Dados una matriz A simétrica y definida positiva y un vector B, buscamos un vector x tal que Ax = b
Método del gradiente conjugado:
- Definimos f(x) = (1)/(2)x^TAx − b^Tx + c
- Entonces f’(x) = (1)/(2)A^Tx + (1)/(2)Ax − b = Ax − b
- La ecuación Ax = b tiene un cero en los puntos críticos de la ecuación de arriba
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

None.2 Descomposición LU distribuida

Temas Claves

Identificació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

Inversión Matricial

La inversa de una matriz A es otra matriz B tal que AB = BA = I_n donde I_n es la matriz identidad.
- La inversa de A se denota por A^− 1

Algoritmos clásicos para encontrar la matriz inversa

Gauss-Jordan
- Realizar operaciones en órden
SVD, calcular U, V y W tales que
- A = UWV^T con
  - UU^T = VV^T = I_n
  - W diagonal
- Requiere intercambios de filas
Decomposición QR
- A = QR con
  - QQ^T = I_n
  - R triangular superior
- Usa Gram-Schmidt para calcular vectores en órden
Descomposición LU

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

Descomposición LU