Deep Learning desde cero. Capítulo 04 – Grafo Computacional.

[As Pablo Picasso said of computers]: But they are useless. They can only give you answers.”

In search of Genius. William Fifield, 1982

Hoy vamos a retroceder un poco en el tiempo. Hasta hace unos 2500 años, entre el siglo 5 o 6 AC, la época donde vivía un lingüista llamado “पाणिनि” ( algo así como “Pāṇini” ) en el área de Gandhara de la antigua India, lo que ahora es el sudeste de Afganistán.

Pues resulta que esta persona escribió el “Aṣṭādhyāyī”, un tratado sobre la lingüística y gramática del Sánscrito. y por ello está considerada como “El padre de la lingüística”.

Transcripción tratado de Pāṇini – 1663 – Source: Wellcome Collection

En este tratado, Pāṇini desarrolló un sistema para describir un lenguaje mediante una serie de reglas básicas y bien definidas, que combinándolas puedes definir la estructura de un lenguaje.

Estos métodos (o muy similares) se han usado en matemáticas con la teoría de autómatas y lenguajes formales, desde Axel Thue, pasando por Alan Turing, llegando incluso a Noam Chomsky.

En los tiempos actuales usamos la forma de Backus-Naur (BNF) y variaciones, para definir lenguajes formales y gramáticas libres de contexto.

¿Y esto que tiene que ver?

Bueno, pues habría que hablar de bastantes temas para ver una relación directa, empezando de Lenguajes formales, autómatas, FDA, etc. Pero al fin y al cabo nosotros queremos interpretar una función matemática, escrita en un lenguaje que no entiende nuestro ordenador a algo que lo entienda. Y básicamente eso es una gramática.

Pero resumiendo, tenemos que pasar de:

\( f(x)=2*\sin(x) \)

A una serie de pasos que correspondan a unas operaciones simples que tengan entradas y produzcan salidas.

Se podría usar infinidad de distintos lenguajes formales y técnicas para “interpretar” estos lenguajes, pero nosotros vamos a usar una forma específica llamada Grafo Computacional.

¿Que son los Grafos Computacionales?

Un Grafo Computacional se define como una 6-tupla tal que:

\(\langle n, l,E, u^{1}…u^{n},d^{1}…d^{n}, f^{l+1}…f^{n}\rangle\)

donde…

  • \(n\): es un entero que especifica el número de vertices del Grafo.
  • \(l\): es un entero entre 1 ≤ l < n tal que especifica el número de hojas en el Grafo.
  • \(E\): es el conjunto de vértices del Grafo Computacional para cada (i,j) ∈ \(E\) tenemos que i…

No

No vamos a ver la definición matemática de un Grafo Computacional. Ya sabemos lo que es.

Un Grafo Computacional es simplemente un Grafo, en concreto un DAG. Por que ya sabemos lo que es un DAG, ¿no? 😉

Y con este Grafo vamos a ser capaces de definir cualquier función matemática.

Términos que vamos a usar.

Para poder entendernos, vamos a definir unos cuantos conceptos. Vamos a usar una terminología similar a la de Tensorflow, simplemente por comodidad.

Un Grafo Computacional es un DAG donde los Nodos pueden ser de tres tipos:

  • Variables: Una Variable será un Nodo que contendrá datos (un Tensor) que podrán ser modificados o no en los cálculos y solo contendrá Nodos hijos.
  • Placeholders: Un Placeholder será un tipo especial de Variable donde recibirá datos de entrada (un Tensor) y solo contendrá Nodos hijos. O sea, solo tendrá vértices de salida. Datos que no se van a modificar cuando calculemos algo. Serán las variables de entrada.
  • Operaciones: Una Operación será un Nodo que contendrá una Operación, y SIEMPRE tendrá uno o dos vértices de entrada y, al menos, una salida.

¿Y como define una función matemática?

Bueno, pues como no queremos liarnos mucho con las explicaciones, vamos a verlo directamente:

Supongamos que queremos representar la función matemática de antes.

\( f(x)=2*\sin(x) \)

está función puede ser representada por:

Donde podemos ver que el Placeholder “x” está representada por un circulo simple, la Variable “2″ está representado por un circulo doble y las operaciones la representamos como un cuadrado.

Sí, es un ejemplo muy simple, pero con nuestro Grafo Computacional podremos expresar funciones tremendamente complejas con elementos sencillos.

¿Que tipos de Grafos Computacionales hay?

En las librerías de Deep Learning se usan mayoritariamente dos tipos de Grafos Computacionales, los estáticos y dinámicos.

La diferencia fundamental es que en los estáticos, se define primero la estructura del Grafo que vas a usar y una vez se tiene el Grafo definido, se ejecutará una y otra vez sin posibilidad de modificarlo.

La mayor ventaja de esta aproximación es que permite optimizar la ejecución, ya que al no modificarse se puede ejecutar todas las veces que se quiera lo más rápido posible, además se puede optimizar el Grafo o paralelizar la ejecución. De hecho la librería CUDA de Nvidia tiene una serie de funciones para subir a la GPU directamente el Grafo Computacional.

El problema de los Grafos Computacionales estáticos, es que no puedes trabajar con distintos tamaños o estructuras de datos una vez definidas.

Si se define que una variable de entrada tiene un tamaño de 256×256, No podrás ejecutarlo con una variable de 128×128.

En cambio los Grafos Computacionales dinámicos, la definición y la ejecución se hacen de una manera más explicita. Ya que cada vez que lo ejecutamos recorremos el Grafo para saber qué tenemos que ejecutar.

Si no os ha quedado muy claro no os preocupéis mucho. Al final del post, se entenderá mejor 🙂

Después de esta pequeña introducción histórica y teórica, toca ir al lío.

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

Recopilando código.

Lo primero que tenemos que hacer es ver si tenemos todo el código que necesitamos.

Empezamos por nuestro Grafo. Sí, el del capítulo 1. Por que lo tenéis hecho, ¿no?

Bueno, pues este Grafo va a ser la base de nuestro Grafo Computacional.

Una vez que hayamos recuperado nuestro grafo, podemos empezar la estructura del Grafo Computacional.

Solo vamos a necesitar las operaciones que veis, poder agregar Variables, Placeholders y Operaciones, y ejecutarlo. Ya, si queremos ampliarlo para desactivar operaciones u otras cosas que se nos ocurran, bueno pues no hay problema en hacerlo :).

¿Qué son las variables?

Como ya hemos comentado, las variables son nodos donde almacenamos valores (Tensores) que pueden, o no, variar el valor (ya veréis a que me refiero en el siguiente post) pero que no dependen de un valor de entrada.

¿Cómo se implementan?

Pues son bastante sencillas.

Simplemente tiene que tener un valor inicial, y una operación forward que simplemente pondrán en el output el valor almacenado.

Y esto es todo lo que tiene nuestra clase “Variable”. Por ahora.

¿Qué son los Placeholders?

No son nada más que variables de entrada. Será el nodo donde insertaremos los valores de entrada.

Para ello deberemos tener una clase de Placeholder que sea a su vez un Nodo del Grafo.

Los Placeholders, al ser valores dependientes de un parámetro de entrada, tendrán una función para asignarle el valor que queramos cada vez que queramos ejecutar el Grafo Computacional.

¿Cómo se implementan?

Prácticamente igual que las Variables 😉

La única diferencia es que tiene una función para poder darle un valor antes de empezar a ejecutar el Grafo Computacional.

¿Qué son las operaciones?

Deberíais saberlo del capítulo 2 y 3 de esta serie ;), pero aquí vamos a ampliarlo un poquito.

Por comodidad (y velocidad) vamos a usar numpy, aunque teóricamente habréis implementado un montón de operaciones en los capítulos anteriores 😉

Las operaciones son similares a las que vimos en los anteriores capítulos pero debemos guardar cierta información extra. Por ejemplo deberemos tener controlados los nodos de entrada de la operación, para poder extraer los valores de ellos cuando nos hagan falta. Ademas, así podremos tener un control sobre quién está llamando a quién.

Y como en todos los demás nodos, al ejecutar el forward, guardaremos el resultado en el output.

¿Y ya está?

Claro que no.

Ahora que ya tenemos nuestros tres tipos de nodos, debemos empezar a trabajar con ellos en nuestro Grafo Computacional.

¿Como lo haremos?, pues vamos a ir implementando poco a poco todo el Grafo Computacional.

Implementando nuestro Grafo Computacional.

Para implementar nuestro propio Grafo Computacional debemos tener claro cómo vamos a montar nuestro Grafo.

Agregando Variables y Placeholders

Como ya sabemos las Variables y los Placeholders no pueden tener nodos padres, así que no habrá ningún vértice que llegue a ellos. Esto nos facilita mucho el trabajo, ya que solo deberemos insertar los nodos en el Grafo sin preocuparnos, por ahora, de los vértices 😉

Así de fácil es agregar un Placeholder o Variable. Hay que tener en cuenta que esta implementación es tan sencilla porque la mayor parte de la dificultad la hemos ido abstrayendo en los anteriores posts.

Como hemos comentado, los Placeholder y las Variables solo tienen nodos hijo, por lo que no tendremos que gestionar ningún vértice en esta parte. Ya lo liaremos con las operaciones.

Agregando operaciones.

Cada operación tiene 1 o 2 inputs, así que podremos saber desde donde llegan esos inputs, o lo que es lo mismo, podremos crear un vértice desde el input a la propia operación.

Como hemos visto cuando hemos implementando las operaciones, nos hemos guardado los nodos de entrada que recibe la operación por lo que simplemente tendremos que asignar un vértice de cada input a la operación.

Y con esto ya tenemos todo nuestro Grafo Computacional creado.

Pero así se queda un poco soso, ¿no?.

Tal vez deberíamos darle un poco de alegría siendo capaces de ejecutar la función que hemos definido, ¿verdad?

Pues vamos a darle caña.

Run.

Una vez hemos definido la función que queremos ejecutar en nuestro DAG, deberemos ser capaces de recorrerlo de alguna manera que nos permita pasar una sola vez y en orden definido por cada nodo.

¿Os suena esto?

¿No?

¿Seguro?

BFS. source Primer capítulo de estos posts

Bueno, pues al recorrer nuestro Grafo usando el BFS sacaremos la lista que necesitamos pero el problema es que nos da el orden desde el nodo final, hasta las hojas. Y nosotros queremos recorrerlo justo en el sentido contrario.

¿Recordais el primer ejercicio de los deberes, el “Reverse_BFS”?

¿A que ahora os gustaría haberlo hecho? 😉

Simplemente con esta función ya somos capaces de ejecutar y calcular nuestra función.

Así como nosotros lo hemos implementado, el Grafo Computacional saca el orden de ejecución cada vez que queremos calcular algo, esto nos da la capacidad de modificar, agregar o quitar nodos entre ejecuciones. Por ejemplo, no ejecutando algo o cambiando el flujo de datos entre ejecuciones. Esto es un Grafo Computacional dinámico.

Si, en cambio, a la hora de ejecutarlo tenemos una función previa que saca el orden, y puede hacer otras cosas como optimizarlo, comprobar si es un DAG, sacar caminos independientes o paralelizarlo, o subir todas las operaciones y datos de golpe a la GPU. Pero de esta manera no podremos modificar nada del Grafo entre ejecuciones, pero ese Grafo podrá ser optimizado de una manera más eficiente y se ejecutará más rápido.

Poniéndolo todo junto

Bueno, pues ya hemos programado nuestro Grafo Computacional. Ahora deberemos probar que funciona.

Tomando la función que hemos comentado antes:

\(f(x)=2*sin(x)\)

podemos definirla así:

Leñe, sí, sí que funciona :D.

Pero no solo eso, con la función to_dot que hicimos en el capítulo 1, podemos visualizar nuestra función como un DAG:

¿Y si ahora quisiéramos ejecutarlo con otros valores en el Placeholder?

Y ya está.

Ya hemos implementado la parte inicial de nuestro Grafo Computacional.

Recordad que todo el código lo podeis encontrar en el repositorio de Github.

Unas palabras finales.

Los Grafos Computacionales son una estupenda manera de definir funciones matemáticas,por su simplicidad y potencial. Pero no tienen solo esta bondad.

La mayor bondad que tienen es que nos abren el camino a calcular derivadas y derivadas parciales de las funciones que definimos de manera automática.

Sí, como lo lees. En el siguiente capitulo vamos a hacer que nuestro Grafo Computacional nos calcule automáticamente las derivadas, y derivadas parciales, de todas las funciones que queramos ;).

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.

Deja una respuesta

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

− seven = 3