# Grafo Computacional.
> " [As Pablo Picasso said of computers]: But they are useless. They can only give you answers."
>
> -- [In search of Genius.]("https://catalogue.nla.gov.au/Record/306231/Copyright" target="_blank") 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](https://es.wikipedia.org/wiki/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]("https://wellcomeimages.org/indexplus/image/L0032691.html") ]("images/sans.jpg")
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)](https://es.wikipedia.org/wiki/Notaci%C3%B3n_de_Backus-Naur target="_blank") 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 especifíca el número de hojas en el Grafo.
- E: es el conjunto de vertices 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 siguiente función matemática
$$ f(x)=2*sin(x) $$
está función puede ser representada por:
![$f(x)$]("images/fx.png")
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]("https://docs.nvidia.com/cuda/cuda-runtime-api/group__CUDART__GRAPH.html#group__CUDART__GRAPH" target="_blank").
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 256x256, No podrás ejecutarlo con una variable de 128x128.
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 que 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]("1.md.html" target="_blank"). 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.
~~~~~~~~~~~~~~~~ python
#importamos la clase graph que implementamos en el capítulo 1.
from graph import Graph
from operations import Operation
from placeholder import Placeholder
from variable import Variable
#esta será la base de nuestro Grafo Computacional.
class CompGraph(object):
name = "unnamed"
graph = None
def __init__(self,name:str="anonymous"):
self.name = name
if not self.graph:
self.graph=Graph()
def add_operation(self,op:Operation):
raise NotImplementedError
def add_Placeholder(self,ph:Placeholder):
raise NotImplementedError
def add_variable(self,v:Variable):
raise NotImplementedError
def run(self,fromNode:Node):
raise NotImplementedError
def to_dot(self):
return self.graph()
~~~~~~~~~~~~~~~~
Solo vamos a necesitar las operaciones que veis, poder agregar Variables, Placeholders y Operaciones, y ejecutarlo. Ya si queremos ampliarlo para desactivar operaciones, o otras cosas que se nos ocurran, bueno pues no hay problema en hacerlo :).
## ¿Que 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.
### ¿Como 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.
~~~~~~~~~~~~~~~~ python
from graph import Node
from tensor import Tensor
class Variable(Node):
value = None
output = None
def __init__(self. initial_value:Tensor, name:str = None):
super().__init__()
if name is not None:
self.name = name
self.value = initial_value
def forward(self):
"""
Exactamente igual que la operación forward de los anteriores capítulos,
pero aquí no ejecutamos nada, solo asignamos el value al output
"""
raise NotImplementedError
~~~~~~~~~~~~~~~~
Y esto es todo lo que tiene nuestra clase "Variable". Por ahora.
## ¿Que 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á una función para asignarle el valor que queramos cada vez que queramos ejecutar el Grafo Computacional.
### ¿Como se implementan?
~~~~~~~~~~~~~~~~ python
from graph import Node
from tensor import Tensor
class Placeholder(Node):
value = None
output = None
def __init__(self. name:str = None):
super().__init__()
if name is not None:
self.name = name
def set_value(self, initial_value:Tensor):
"""
se settea el self.value al valor de entrada initial_value.
"""
raise NotImplementedError
def forward(self):
"""
exactamente igual que la operación forward de los anteriores capítulos,
pero aquí no ejecutamos nada, solo asignamos el value al output
"""
raise NotImplementedError
~~~~~~~~~~~~~~~~
Y nuestra clase no va a tener nada más.
# ¿Que 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 el capitulo 2 y 3 ;)
~~~~~~~~~~~~~~~~ python
class Operation(Node):
base_name:str = None
output:Tensor = None
inputs:list = []
def __init__(self):
super().__init__()
self.inputs=[]
self.output=None
def forward(self):
raise NotImplementedError
def backward(self, gradOutput: Tensor):
raise NotImplementedError
class sin(Operation):
base_name = "Sin"
def __init__(self, A: Node, Name: str = None):
super().__init__()
if Name is not None:
self.name = Name
self.inputs.append(A)
def forward(self):
A = self.inputs[0]
self.output = np.sin(A.output)
class Multiply(Operation):
base_name = "Multiply"
def __init__(self, A: Node,B:Node, Name:str=None):
super().__init__()
if Name is not None:
self.name = Name
self.inputs.append(A)
self.inputs.append(B)
def forward(self):
A = self.inputs[0]
B = self.inputs[1]
self.output = A.output * B.output
~~~~~~~~~~~~~~~~
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 quien está llamando a quien.
Y como en todos los demas nodos, al ejecutar el forward, guardaremos el resultado en el output.
## ¿Y ya está?
Claro que no.
Ahora que ya tenemos nuestro tres tipos de nodos, debemos empezar a trabajar con ellos en nuestro Grafo Computacional.
Y como lo hacemos, pues vamos a ir implementando poco a poco todo el GC.
# Implementando nuestro Grafo Computacional.
Para implementar nuestro propio Grafo Computacional debemos tener claro como 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 ;)
~~~~~~~~~~~~~~~~ python
from graph import Graph, Node
class Compgraph():
name: "Anonymous"
graph:Graph = None
def __init__(self, name:str="Anonymous"):
self.name=name
if not self.graph:
self.graph = Graph()
def add_Placeholder(self, ph:Placeholder) -> Placeholder:
self.graph.add_node(ph)
return ph
def add_variable(self, v:Variable) -> Variable:
self.graph.add_node(v)
return v
~~~~~~~~~~~~~~~~
Así de fácil es agregar un Placeholder o Variable. Hay que tener en cuenta que esta implementación es sencilla por que 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 llega 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.
~~~~~~~~~~~~~~~~ python
def add_operation(self,op:Operacion)->Operation:
self.graph.add_node(op)
for input in op.inputs:
self.graph.add_edge(input,op)
self.nops +=1
~~~~~~~~~~~~~~~~
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, ¿no?.
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]("1.md.html" "target=_blank") ]("images/bfs.webm")
BFS source [Primer capítulo de estos posts]("1.md.html" "target=_blank")
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.
¿Hicisteis el primer ejercicio de los deberes? ¿El Reverse_BFS?, ¿A que ahora os gustaría haberlo hecho? ;)
~~~~~~~~~~~~~~~~ python
class compgraph():
...
def run(self, to_node:Node) -> Tensor:
order = self.graph.reverse_bfs(from_node)
for node in orden:
node.forward()
return to_node.output
~~~~~~~~~~~~~~~~
Y simplemente con esta función ya somo capaces de ejecutar y calcular nuestra función.
Así como nosotros 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.
~~~~~~~~~~~~~~~~ python
class compgraph():
...
def compile(self, to_node:Node):
if not self.graph.is_DAG():
raise RuntimeError("El Grafo no puede contener ciclos")
self.order = self.graph.reverse_bfs(from_node)
def run(self, to_node:Node) -> Tensor:
for node in self.order:
node.forward()
return to_node.output
~~~~~~~~~~~~~~~~
# Poniendolo todo junto
Bueno, pues ya hemos programado nuestro Grafo Computacional. Ahora deberemos probar que funciona.
Tomando lafunción que hemos comentado antes:
la podemos definir así:
~~~~~~~~~~~~~~~~ python
from compgraph import Compgrap
from operations import Operation as op
from variables import Variable
from Placeholders import Placeholder
# f(x) = 2*sen(x)
X = Tensor([x for x in range(0,10)]).reshape((10))
v2 = Tensor()
c = Compgraph()
p_1 = c.add_Placeholder(Placeholder("X"))
x_1 = c.add_variable(Variable(v2,"Dos"))
op_sin = c.add_operation(op.sin(p_1))
op_pv2 = c.add_operaction(op.Multiply(op_sin,x_1))
p_1.set_valor(X)
res = c.run(op_pv2)
print(res)
#[ 0. 1.68294197 1.81859485 0.28224002 -1.51360499 -1.91784855
# -0.558831 1.3139732 1.97871649 0.82423697]
~~~~~~~~~~~~~~~~
Leñe, si funciona :D.
Pero no solo eso, con la función "to_dot" que hicimos en el capítulo 1, podemos visualizar nuestro DAG:
~~~~~~~~~~~~~~~~ python
c.to_dot()
digraph G {
rankdir=LR;
node [shape = none]; "";
node [shape = square]; Sin_0 Multiply_1;
node [shape = doublecircle]; DOS;
node [shape = circle]; X;
DOS->Multiply_1
X->Sin_0
Sin_0->Multiply_1
Multiply_1->"" [ label="result"];
}
~~~~~~~~~~~~~~~~
![$f(x)$]("images/cggraph.png")
¿Y si ahora quisiéramos ejecutarlo con otros valores en el Placeholder?
~~~~~~~~~~~~~~~~ python
X2 = numpy.linspace(0, 10, num=100)
p_1.set_valor(X2)
res = c.run(op_pv2)
#plt.plot(X2,res)
~~~~~~~~~~~~~~~~
![$f(x)$]("images/fxcg.png")
Y ya está. Ya hemos implementado la parte inicial de nuestro Grafo Computacional.
# 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.
-------------------------
