Deep Learning desde cero. Capítulo 01 – Grafos

Buenas, soy Angel Lis, programador y friki.

Estoy escribiendo una serie de posts en los cuales intentaré explicar como funciona un framework de Deep Learning. Y para ello lo programaremos.

Aquí teneis la lista de posts, que iré actualizando:

Espero que os guste.

  • Grafos (este capítulo).
  • Algebra.
  • Grafo Computacional.
  • Gradient Descent.
  • Diferenciacion automática.
  • BackProp.
  • Optimizadores.
  • Funciones activación.
  • Neural Networks.
  • Fully Connected.
  • CNN.

También los podéis visitar en mi página web y podéis ver el repositorio.

Grafos

If you wish to make an apple pie from scratch, you must first invent the universe.

Carl Sagan, Cosmos: A Personal Voyage 1980

Vamos a suponer que sabéis algo de Machine Learning y de Deep Learning. ¿Nunca os habéis preguntado cómo funcionan los Frameworks de Deep Learning? o ¿cómo se prueban nuevas funciones? Y si no conocéis nada de este apasionante campo, ¿queréis aprender cómo funciona?

Pues si es que sí, creo que estos posts os gustarán.

Si lo que os interesa es coger un dataset de imágenes y clasificarlas, sin calentaros la cabeza.

Estos no son vuestros posts.

Enfocaremos los posts desde el punto de vista de un coder. Hay miles de tutoriales y cursos que nos explican la teoría y matemáticas del Machine Learning y decenas de miles de tutoriales de como usar keras, tensorflow o pytorch.

Aquí vamos a hacer nuestro propio framework de Deep Learning, desde 0.

Pero para eso, no vamos a hablar (por ahora) de redes neuronales.

Durante los primeros posts vamos a tratar, e implementar, temas tan diversos como álgebra, grafos, optimización de funciones,etc.

¿Qué necesitamos?

Nuestro lenguaje de programación preferido, paciencia, y solo un poco de python 🙂

Pero, aparte de eso, lo haremos sin restricciones.

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

¿Qué es un grafo?

Un poco de historia

Allá por el siglo XVIII, en la ciudad de Königsberg (actual Kaliningrado), se formuló un problema matemático que preguntaba si era posible encontrar un recorrido para cruzar toda la ciudad, pasando por todos los puentes una sola vez y regresando al mismo punto de inicio.

En un alarde de originalidad a este problema se le llamó: Problema de los puentes de Königsberg

Puentes de Königsberg (fuente Wikimedia)

Puedes intentar responder ese problema tu mismo usando la imagen de la ciudad, si quieres :).

Bueno, pues en el año 1736 un matemático conocido como Leonhard Euler expuso una solución general al problema y, de paso, creó una nueva rama de las matemáticas llamada Teoría De Grafos.

Leonhard Euler (source Wikimedia)

Lo que hizo Euler fue simplificar el mapa de la ciudad a unos puntos (barrios) conectados por unas lineas (puentes) eliminando todo lo sobrante.

Abstracción de Euler para los Puentes de Königsberg

Con esta abstracción se deduce que los vértices intermedios deben tener 2 aristas ya que, como solo puedes pasar una vez por cada puente (Arista), si entras a un nodo por una arista debes de salir por otra distinta. Como en este grafo los puntos poseen un número impar de aristas podemos decir que no se puede resolver el problema de puentes de Königsberg.

Si ya tienes experiencia como programador, ya habrás tratado con grafos y conocerás un poco de teoría de grafos.

INFO: De todas maneras, si no conoces nada de teoría de grafos puedes leer bastante aquí

En general, podemos ver un grafo como un conjunto de Vértices (o Nodos) conectados por Aristas, donde las aristas conectan Vértices. Son tremendamente útiles para representar información y aplicar distintos algoritmos.

Nosotros vamos a centrarnos en unos tipos particulares de grafos, Grafos Dirigidos, también se suelen llamar Di-grafos .

Un Grafo Dirigido, o Dígrafo, es un grafo donde las aristas tienen “dirección”, van del nodo A al nodo B, pero no tiene por que ir del nodo B al nodo A.

DG, Digrafo con ciclos

Un Grafo Dirigido Acíclico (DAG) es aquel que no tiene “ciclos”. O lo que es lo mismo: Tomando cualquier nodo del grafo y siguiendo cualquier camino posible, no puedes volver al mismo nodo.

Este es el subtipo de grafos que nosotros vamos a utilizar.

DAG, Digrafo Acíclico.

Podemos resumir que un DAG tiene una serie de características básicas:

  • Aristas dirigidas: “flechas” en una dirección, de un nodo a otro.
  • Nodos: Vértices que almacenan datos o funcionalidad.
  • Nodos sin padres: Nodos a los que no llega ninguna “flecha”
  • Hojas: Nodos que no tienen hijos (que no sale ninguna “flecha”)
  • No tiene Ciclos 😉

Visualizando Grafos

Una forma bastante cómoda y sencilla para visualizar grafos es el formato DOT: graph description language

La gran ventaja de este formato es que es simplemente un archivo de texto, con lo que podremos generarlo fácilmente desde nuestro código y luego visualizarlo.

Un ejemplo

fichero: mygraph.dot

Una vez tenemos ese fichero de texto podemos visualizar el grafo simplemente con usar el comando dot de GraphViz.

y tendremos este resultado:

Nuestro DAG

Si no quieres instalarte este software, puedes usar la versión online webGraphViz.

Programando Grafos

Bueno, vamos a suponer que ya tenemos algo más claro lo que son los grafos y lo útiles que son a la hora de definir sistemas.

Ahora es momento de empezar a hablar de la implementación.

Para trabajar con grafos las operaciones más comunes que debemos tener implementadas son:

Para implementar un DAG se pueden utilizar varias técnicas pero las más comunes son:

Matriz de adyacencia

Una de las formas más comunes de representar el grafo es hacerlo como una matriz. Estas se implementan con una matriz de NxN siendo N el numero de nodos.

Cada posición de i,j de la matriz representa una arista ( flecha ) del nodo i al nodo j.

Se podría expresar así:

\( a_{i,j} \begin{cases} \text{true} & i \rightarrow j \\ \text{false} & i \not \rightarrow j \end{cases} \)

Y podríamos verlo así

\( \begin{matrix}&a &b &c &d &e &f\cr a & 0&0&1&0 &0 &0\cr b & 0&0 &0 &1 &0 &0\cr c & 0&0 &0 &1 &0 &0\cr d & 0& 0 & 0 & 0 & 0 &1\cr e & 0& 0 & 0 & 0 & 0 &1\cr f & 0& 0 & 0 & 0 & 0 &0\cr \end{matrix} \)

Esta implementación tiene la ventaja de que las operaciones de agregar, eliminar y comprobar si dos nodos están conectados tiene coste constante y son triviales

La implementación de las funciones para conocer los “familiares” (Nodos padres e hijos) son bastantes sencillas pero, a la vez, tienen un coste mayor

La gran problemática con este enfoque es que para recorrer el grafo deberemos ejecutar constantemente estas funciones, que tienen un coste lineal, O(n). Además el coste en memoria es n², algo que podría ser un problema para grafos grandes.

Lista de adyacencias

Otro enfoque para trabajar con grafos es el usar una lista con la lista de Nodos hijo de cada nodo.

\( \ a \rightarrow [c] \\ b \rightarrow [d,c] \\ c \rightarrow [d] \\ d \rightarrow [d] \\ e \rightarrow [f] \\ f \rightarrow [] \)

El coste de estas implementaciones depende mucho del contenedor que se use para almacenar las aristas y de como se haya implementado en el lenguaje elegido, pero también ofrece mucha más versatilidad.

Como ejemplo, si usamos una lista se podría implementar así:

La implementación de las funciones para conocer los “familiares” (Nodos padres e hijos) son bastantes sencillas.

También se puede implementar usando multilistas, o lo que es lo mismo una lista que tiene los padres de un nodo y otra lista que contenga los hijos de ese nodo.

Implementando el grafo.

Inciso antes de empezar.

Una vez visto esto por encima, vamos a hacer un pequeño inciso para comentar como vamos a trabajar en estos posts.

En los posts se irá explicando la teoría y dando algunos ejemplos, pero la solución final deberéis programarla vosotros.

Para daros una guía en la que apoyarse haremos un enfoque parecido a TDD (Test Driven Development), así que os plantearé unos test unitarios para que podáis probar vuestro código. Habrá un repositorio en github (con errores para evitar C&P) mostrando una posible implementación en C++ y Python.

Implementando que es gerundio.

En este primer ejercicio vamos a implementar un DAG.

Tenéis libertad absoluta para elegir si queréis usar una matriz de adyacencia, o una lista, o simplemente nodos con referencias a otros nodos.

El pseudo-código estará expuesto como si fuéramos a implementarlo con clases, pero repito,tenéis libertad absoluta para implementarlo como queráis.

Para nuestra primera aproximación vamos a hacer un grafo que sea capaz de ejecutar las operaciones básicas con grafos que ya hemos comentado.

Vamos a tener un Objeto Node que tenga algo de funcionalidad.

Una vez hayas implementado tu grafo vamos a tener que probarlo, así que vamos a definir unos tests que deben pasarse correctamente.

Puedes hacerlos a mano o usar un framework de unittesting.

Si todo está correcto os debería haber generado un grafo como este:

graph

Recordad que podéis probar vuestro resultado en la versión web de GraphViz.

Otras pruebas que deben pasar vuestra implementación.

Bueno, ahora ya has sido capaz de implementar las manipulaciones básicas de un grafo, así que vamos a empezar a trabajar con ellos.

Algoritmos sobre grafos

Una vez tenemos la capacidad de manipular grafos algo que necesitaremos constantemente será recorrerlos y no solo como nodos independientes si no siguiendo el orden definido en el grafo y pasando por cada nodo exactamente una vez.

Y el orden en que se visitan los vértices es importante y depende del problema que quieres resolver.

Los métodos más comunes para recorrer un grafo son el DFS (Depth First Search) y BFS (Breadth First Search).

Haciendo un poco de spoiler, os avanzo que nosotros usaremos BFS constantemente :).

DFS (Depth First Search)

El DFS empieza desde un nodo del grafo y lo visita. Una vez visitado, saltamos a cada uno de los padres de este nodo, y repetimos la operación.

La versión iterativa de este algoritmo usa una Pila (LIFO) a la que agregamos el nodo inicial y empezamos a sacar elementos de la pila. por cada elemento, agregamos sus padres a la Pila, lo visitamos y volvemos al loop.

Visualmente es más sencillo de ver.

El orden en que se agregan los vértices es importante, ya que depende de como los agreges recorrerá los padres de distinto orden.

El resultado es igualmente correcto, pero a nivel de Test Unitarios puede daros más de un dolor de cabeza.

Tests unitarios

Ahora os toca a vosotros implementar este BFS en vuestros grafos, aquí tenéis un test para comprobar que os funciona correctamente.

BFS (Breadth First Search)

Otra forma de recorrer un grafo es la conocida como Breadth First Search (BFS). En esta variación usamos un proceso similar al DFS pero en lugar de usar una pila usaremos una cola (FIFO).

Al usar esta cola, el algoritmo cambia ligeramente. El BFS empieza desde un nodo del grafo, lo visita y agrega sus padres a la cola. Una vez visitado, saltamos a cada uno de los padres de este nodo y repetimos la operación.

La versión iterativa de este algoritmo usa una cola (FIFO) a la que agregamos el nodo inicial y empezamos a sacar elementos de la cola. Por cada elemento, agregamos sus padres a la cola, lo visitamos y volvemos al loop.

Al igual que en el DFS el orden en que se agregan los vértices es importante, ya que depende de como los agreges recorrerá los padres de distinto orden. Pero, aunque el orden sea distinto, es igualmente correcto.

Tests unitarios

Ahora os toca a vosotros implementar este BFS en vuestros grafos, aquí tenéis un test para comprobar que os funciona correctamente.

Enhorabuena!

Ya has implementado una gran parte de la funcionalidad necesaria para trabajar con grafos en cualquier problema.

Pero esto no acaba aquí, ahora os voy a proponer 2 problemillas que deberéis solucionar vosotros solos.

El primero (Reverse BFS) es bastante importante que lo penséis, el segundo es un bonus track.

Deberes 😉

Reverse BFS

Ahora que ya tenemos una forma de recorrer nuestros grafos tenemos que pensar en una funcionalidad que vamos a necesitar para nuestra librería de Deep Learning.

El reverse BFS, y esto no es mas que saber la lista de nodos para recorrer el grafo como se hace en un BFS, pero en dirección contraria.

Si nuestro BFS nos devuelve una lista de [1,2,3,4], nosotros deberemos recorrerla como [4,3,2,1]

Intentad implementarlo :).

Tests unitarios

Para nota.

Detectar ciclos en tu Digrafo

Os comento que con el DFS se pueden detectar ciclos en un DAG, ¿se te ocurre una manera de detectar si un grafo es un DAG o no?

Intentaló y pruébalo.

Tests unitarios

Repositorio

Todo el código y ejemplos los podréis encontrar en el

Repositorio GitHub.

Siguientes pasos

En el próximo posts hablaremos de Álgebra.

Álgebra pura y dura.

Pero no os asustéis demasiado, no será muy doloroso 😉

Dudas y preguntas.

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

Deja una respuesta

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

+ fourteen = eighteen