Deep Learning desde cero. Capítulo 03 – Álgebra lineal (Parte 2).

Disclaimer:
Antes de nada, quiero aclarar que NO soy matemático y sé de matemáticas lo justo para pasar el día.
Hay muchos conceptos que se me escapan y otros que trataré de manera muy superficial.
Matemáticos, perdonadme, por favor.
Y si detectáis alguna metida de pata, ponedlo en los comentarios.

“To give the history of linear algebra is a task that is as important as it is difficult.”

Nicolas Bourbaki, 1984

La operación

Históricamente ha existido una forma de simplificar los cálculos en el álgebra lineal, y sigue siendo indispensable en la física, ingeniería y en la informática. Esta operación es la multiplicación de matrices.

El descubrimiento de esta operación se atribuye a Augustin-Louis Cauchy y a Jacques Philippe Marie Binet allá por el 1812.

Louis Cauchy. Source: Wikipedia
Jacques Philippe Binet. Source: Wikipedia

Dando origen al teorema de Binet-Cauchy donde se define por primera vez la multiplicación de matrices.

Como curiosidad, podemos echar un ojo a los artículos de Binet y de Cauchy.

¿Por qué es tan importante?

Leyendo el artículo de Pete Warden, “Why GEMM is at the heart of deep learning“, podemos encontrar un dato muy esclarecedor.

Entre el 89% y el 95% del tiempo de cálculo entrenando un modelo de Deep Learning se usa en la operación de multiplicación de matrices.

Habréis visto que hemos usado el termino “GEMM”, que significa GEneral Matrix Multiplication. Son una serie de funciones preparadas para trabajar con matrices de la librería BLAS, que es el estándar para el cálculo numérico en cualquier aplicación informática.

La primera aparición de BLAS (Basic Linear Algebra Subprograms for *fortran* usage) fue allí por el 1979.

Bueno, pues después de esta pequeña introducción histórica, toca ir al lío.

Así que prepárate un buen café (o cerveza) y empecemos.

Multiplicación de tensores de rango 2.

La multiplicación de tensores de rango 2 (también llamados matrices 😉 ) está definida como:

\(C_{i,j}=\sum_{k} A_{i,k}*B_{k,j}\)

o, lo que es lo mismo, cada elemento de la matriz C es la multiplicación del vector linea de \(A_{i}\) por el vector columna \(B_{j}\).

Si todavía estás confuso, creo que esta imagen es bastante útil para entenderlo.

Source: Wikipedia

Propiedades de la multiplicación de matrices.

Hay algunas características de la multiplicación de matrices que debemos grabarnos a fuego en la memoria:

  • Las columnas de A deben de ser iguales a las lineas de B (en formato row-column)
  • El tamaño de C es el número de filas de A por el número de columnas de B. \(A^{n,k} * B^{k,m} = C^{n,m}\)
  • NO es conmutativa. \(AB \neq BA\)

Implementando.

La versión más directa de la multiplicación de matrices es recorrer cada una de las filas de \(A\) y cada una de las columnas de \(B\) y multiplicar cada uno de los elementos de esos vectores y acumular ese resultado.

Ahora te toca implementarlo a ti:

Test unitarios

¿Ya lo tienes implementado? Ahora toca probarlo 😉

Velocidades, coste y más.

Bueno, pues no ha sido tan difícil de implementar, ¿no?

Entonces, ¿por qué se pone tan pesado todo el mundo con intentar hacer la multiplicación de matrices más rápida?

Puede que lo mejor sea que lo comprobéis en vuestras carnes…

Para evitarnos tener que pasar un buen rato delante del ordenador esperando a que acabe esta prueba, aquí os dejo la gráfica de los costes temporales.

¿Por qué hay tanta diferencia?

Bueno, pues nuestra implementación de la multiplicación de matrices tiene un coste algorítmico de \(O(n^{3})\) y eso, como habéis podido comprobar, es mucho.

Hay algoritmos mejores, como el de Strassen que consigue un coste asintótico de \(O(n^{2.807355})\) e incluso hay otros como el de Coppersmith–Winograd que consiguen un coste de \(O(n^{2.375477})\). Aunque en la práctica casi nunca se usa este último.

Y, ¿cómo podemos hacer que sea más rápido?

Aquí es donde entra BLAS.

Esta librería, o conjunto de operaciones, tiene unas versiones hiper-optimizadas para cada arquitectura.

Ya sea con BLAS genérica de Netlib u OpenBLAS, de Intel con MKL, de AMD con BLIS o en GPU con cublas. Todas, o casi todas, las aplicaciones de cálculo se basan en esta librería.

Y además, casi todas vienen con capacidades para paralelizar los cálculos.

Por ejemplo, Numpy utiliza la versión que tengáis instalada en vuestro sistema operativo.

A no ser que alguien lo pida en los comentarios, no voy a entrar en la implementación de la multiplicación de matrices con BLAS. Aunque, si tenéis curiosidad, en la versión C++ del repositorio la multiplicación de matrices está implementada con BLAS.

¿Y que pasa con los tensores de rango > 2?

Para explicar las distintas formas de multiplicar tensores de rango mayor de dos, deberíamos escribir un libro.

Pero estamos de enhorabuena, en el Deep Learning no se suele usar la multiplicación tensorial como tal, si no, que se usa una forma de multiplicación llamada Multiplicación de modo N.

Que, simplificando, es una multiplicación de matrices en grupo.

Si tenemos un tensor de tamaño \(T^{2,3,2}\) en el modo 1, podríamos verlo como dos matrices de \(A^{3,2}\) agrupadas.

Sí, sé que es raro, pero nada más esclarecedor que un poco de código:

Cuyo resultado será:

O con TensorFlow

El resultado de lo anterior será:

Lo bueno de esta multiplicación n-mode es que podemos multiplicar tensores de rango mayor de dos con matrices, simplemente haciendo broadcasting de la matriz.

Que dará el siguiente resultado:

Notación de Einstein (einsum)

Realmente las multiplicaciones de tensores se suelen programar con una “forma” de definir las funciones que se llama Notación de Einstein.

No vamos a explicar eso aquí, pero está bien saber que existe y que funciona muy bien.

Como ejemplo vamos a definir la multiplicación de matrices:

El resultado de lo anterior saldrá:

Aquí podéis ver los resultados, y, junto con lo anterior,… sacad vuestras conclusiones.

Info: recordad, si queréis que hable en profundidad sobre la einsum ponedlo en los comentarios.

Ejercicio. Truco del sumatorio

Para terminar hoy vamos a calentarnos el coco un rato.

Hay un pequeño truco para realizar el sumatorio por filas o columnas usando multiplicación de matrices.

¿Sois capaces de sacarlo?

Unas palabras finales.

Hemos estado bastante tiempo con el álgebra lineal y todavía nos quedan bastantes funciones por implementar. Pero para ir avanzando más rápido, dejaremos la implementación de las operaciones que necesitemos para cuando haga falta.

En el próximo post veremos que son, y que tipos hay de Grafos Computacionales y, sobre todo, nos implementaremos nuestro propio Grafo Computacional.

Dudas y preguntas.

Si tienes cualquier duda, pregunta o he metido la pata en algún sitio, puedes contactar conmigo en twitter o mejor, puedes usar los comentarios.

1 pensamiento sobre “Deep Learning desde cero. Capítulo 03 – Álgebra lineal (Parte 2).”

  1. Muchas gracias por estos tutorials : Muy detallados, muy accesibles y explicando lo que no se atreven en otras partes!!

    A mi si mi interesa leer tu opinión sobre la einsum :).

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

65 − fifty five =