Hace unos días ocurrió un evento que sorprendió a la comunidad de inteligencia artificial en todo el mundo. Investigadores en DeepMind (una compañía de Inteligencia Artificial que le pertenece a Google) desarrollaron software que tras ser entrenado, logró vencer a el campeón del juego de mesa Go, llamado Sedol Lee. El duelo fue de 5 juegos, donde la puntuación final fue de 4 a 1, a favor de la máquina.

El nombre de esta AI es AlphaGo, y si nunca has jugado Go, o no estás enterado de los grandes retos de la inteligencia artificial, podría parecerte cosa simple (recordemos que en 1997 Garry Kasparov fue derrotado por DeepBlue); pero que un sistema computacional logre vencer a un campeón humano en Go es cosa muy seria. El juego de Go es computacionalmente mucho más complejo que el Ajedrez. Esto es así porque cada turno en un juego de Go tiene unas 200 posibilidades distintas, mientras que en un juego de Ajedrez sólo son unas 20 posibilidades cada turno - esto significa que el juego de Go tiene muchísimos juegos posibles - muchos más que el ajedrez - checa la Figura 1.

</img> </img>
Figura 1. Figuras mostrando el factor de ramificación, o branching factor del Ajedrez (arriba) y el Go (abajo). Aquí es posible apreciar que el espacio de búsqueda de Go es enorme.

De hecho, ningún sistema computacional anterior a AlphaGo había logrado jugar al nivel de un jugador profesional de Go. Más aún, a diferencia de DeepBlue, que es un sistema con reglas y puntuaciones diseñadas por humanos; AlphaGo es un sistema que ‘aprendió’ a jugar tras ser expuesto a muchos juegos de Go. Este aprendizaje fue a través de redes neuronales profundas, una tecnología que sigue rompiendo las barreras de la inteligencia artificial. Por eso es que la noticia es tan importante.

Pero antes de meternos a hablar de AlphaGo y de Deep Learning, demos un paso atrás. De hecho, DeepMind y Google no son los primeros en utilizar redes neuronales para resolver problemas complejos como éste. Aproximadamente desde 2012, las redes neuronales profundas han sido utilizadas para resolver problemas que hasta antes parecían ser demasiado complejos y requerir demasiada inteligencia.

Sin duda, el término red neuronal suena interesante, pero en realidad ¿qué es una red neuronal?

¿Qué son las redes neuronales y quién las inventó?

En realidad, el nombre completo es ‘red neuronal artificial’. Es una estrategia para procesar información que fue inspirada por la manera en que funciona el sistema nervioso de organismos vivos. Normalmente son utilizadas para estimar funciones que pueden depender de varios parámetros, y en general son desconocidas y no-lineales. Tal vez recuerden cómo en un post anterior codificamos un perceptron: Una neurona básica, utilizada en esquemas de clasificación.

Los primeros intentos para diseñar y utilizar redes neuronales artificiales fueron en los 40s. Warren McCulloch, y Walter Pitts desarrollaron el primer modelo en 1943, y de ahí nació la investigación en redes neuronales. El campó siguió creciendo en los 50s y 60s.

En 1969, el profesor Marvin Minsky, de MIT publicó el libro ‘Perceptrons’, donde estudia a detalle, y estrictamente las redes neuronales artificiales con Perceptrones. Entre otras cosas, Minsky concluyó que el modelo de redes neuronales no se beneficiaría mucho de volverse más complejas. Al día de hoy, se le da crédito a este libro por provocar que se perdiera interés por las redes neuronales a lo largo de la década de los 70s. De hecho, en este periodo, y hasta finales de los 80s hubo muy pocos investigadores realizando investigación, pero estos pocos investigadores fueron poco a poco avanzando el campo de las redes neuronales.

Todo cambió en 2012 en el concurso de ImageNet, que es un concurso donde investigadores proponen algoritmos inteligentes para buscar objectos dentro de imágenes. Alex Krizhevsky de la Universidad de Toronto utilizó una red neuronal profunda, y logró arrasar con todos los records establecidos hasta ese momento.

Exactamente ¿Cómo funciona una red neuronal?

Una red neuronal artificial es un sistema de varias ‘neuronas’ interconectadas. Una neurona artificial es un elemento con varias entradas y una salida. Una neurona puede operar en dos modos: Modo de entrenamiento, y modo de ‘uso’, o de predicción.

</img>
Figura 2. Una neurona simple con 3 entradas ponderadas (observa los parámetros w) y una salida.

Cuando la neurona de la Figura 2 está en modo de predicción, la salida está dada por el promedio ponderado de las entradas, y el término independiente, como se puede ver en la Figura 3.

</img>
Figura 3. Ecuación de la salida del perceptrón.

Sin embargo, la parte más interesante de una red neuronal es su entrenamiento. Ya vimos en el post del Perceptron cómo se entrena un Perceptron básico. Para entrenar redes neuronales con más de una capa se utiliza un algoritmo llamado Retropropagación de errores, o en inglés “Backpropagation”.

</img>
Figura 4. Una red neuronal con una capa oculta.

Retropropagación

El algoritmo de retropropagación de errores tiene dos fases básicas:

1. Fase de Propagación

Propagación de un patrón de entrenamiento a través de la red. Es decir que dado el estado de la red, un ejemplo de datos X (por ejemplo la estatura y el peso de una persona), y una salida esperada (por ejemplo, si la persona es hombre o mujer), introducimos X a la red, y observamos la salida calculada por la red.

Si la salida de la red es diferente de la salida Y, entonces realizamos retropropagación de los errores encontrados en cada capa de la red, para obtener las deltas: la diferencia entre la salida observada y la salida correcta.

2. Fase de Actualización de las Ponderaciones

Multiplicar la delta de salida y la activación de entrada para obtener el vector gradiente de las ponderaciones, y substraer una fracción del vector gradiente de las ponderaciones. Eso básicamente significa que vamos a obtener el error, y empujar las ponderaciones un poquito para reducir el error.

Para imaginar este proceso un poco mejor puedes checar esta visualización del algoritmo de retropropagación, donde puedes ver cómo los pesos de una red neuronal son ajustados poco a poco hasta converger. Como ven, los pesos en la capa más lejana a la salida son ajustados muy lentamente. Ahora imagina 20 capas más!

En un post posterior vamos a ver un ejemplo del algoritmo de retropropagación aplicado a un problema de clasificación.

¿Y qué es deep learning?

En 1989, Yann LeCun demostró el primer sistema de redes neuronales profundas que utilizaba el algoritmo de retropropagación, y constaba de 5 capas. La red de LeCun (quien ahora trabaja para Facebook) fue utilizada para reconocer códigos postales escritos a mano en sobres postales. La red tomó tres días para ser entrenada, y resultó ser muy efectiva.

Como lo mencionamos en la sección de retropropagación, uno de los principale problemas al entrenar redes neuronales profundas es el tiempo que tardan en converger hacia soluciones. Sepp Hochreiter fue el primer investigador en estudiar este problema de manera analítica. Así encontró el Vanishing Gradient Problem, o ‘problema del gradiente que se desvanece’ (perdonen la mala traducción). Este problema ocurre porque, como vimos en el algoritmo de retropropagación, entre más profunda sea la red, más lento es lograr que las ponderaciones de las entradas en la red lleguen a la solución. De hecho, AlphaGo utilizó 50 GPUs para su fase de entrenamiento.

AlphaGo

El programa AlphaGo no es puramente una red neuronal profunda. De hecho, AphaGo funciona con un algoritmo de búsqueda Monte Carlo, que es la técnica clásica para Inteligencias Artificiales en juegos por turnos. La diferencia es que a la hora de seleccionar los mejores movimientos, en vez de utilizar reglas y heurísticas preprogramadas (que es lo que se había utilizado hasta ahora), AlphaGo utilizó un conjunto de dos redes neuronales profundas que fueron entrenadas incialmente con millones de juegos de expertos y amateurs de Go; y posteriormente, AlphaGo entrenó jugando contra sí mismo.

La red neuronal más importante en AlphaGo es conocida como policy network, o una red de “reglas”. Lo interesante es que este tipo de red es muy utilizada en análisis de imágenes - y el tablero de Go también es analizado omo si fuera una imagen de 19x19 pixeles!

El resultado fue una inteligencia que es bastante buena para localizar los mejores movimientos en un juego… Pero que además requiere de mucho procesamiento paralelo para realizar el algoritmo de búsqueda Monte Carlo: 1,202 CPUs y 176 GPUs. Si quieres saber más al respecto, checa el artículo de DeepMind en la revista Nature.

Las redes neuronales hoy en día

Y esa es la historia de las redes neuronales. En la actualidad, casi cada semana hay una noticia emocionante que tiene que ver con ellas. Por ejemplo, cuando Google abrió el código de su herramienta interna TensorFlow, o que algunos rockstars de la inteligencia artificial iniciaron la fundación OpenAI, o cuando DeepMind consiguió que su algoritmo aprendiera a jugar videojuegos mejor que jugadores humanos. Hay montones de aplicaciones donde las redes neuronales han resultado ser muy útiles, como reconocimiento de imágenes, procesamiento de lenguaje natural y sistemas de recomendación; sin embargo, aún existen muchos desafíos para el avance de esta tecnología.

Uno de los desafíos más interesantes viene del costo computacional que es construir redes neuronales profundas, que requieren muchos datos. De hecho, conforme las redes se vuelven más amplias y más profundas, el tiempo que toma crearlas y entrenarlas con datos aumenta mucho. Esto ha llevado a que el software sea optimizado muchísimo, al grado que existen muchas librerías que permiten utilizar tarjetas gráficas (GPUs) para entrenar las redes neuronales (e.g. TensorFlow, Caffe); sin embargo, poco a poco se vuelve evidente que existirán aplicaciones que requieran hardware especializado. Por esto es que IBM creó TrueNorth, un procesador diseñado como una red neuronal, para ejecutar y entrenar redes personalizadas. Sin embargo, el problema de hardware de las redes neuronales aún no está resuelto. Queda mucho espacio para explorar.

Otro desafío importante es el de toma de decisiones de largo plazo. Las redes neuronales actuales aún no han alcanzado inteligencia que les permita planear y tomar decisiones con resultados de largo plazo. Hay mucha investigación en este aspecto.

Finalmente, me gustaría señalar que la historia es excelente, pero no olvidemos que AlphaGo no es sólo una red neuronal: es un sistema muy complejot de 1,200 CPUs y casi 180 GPUs - Enfrentando a un chico de 30 años de edad, que incluso consiguió vencer a AlphaGo una vez.

En fin, espero que el post fuera informativo - y gracias por la paciencia ; ). Comentarios bienvenidos.

El día de hoy toca hablar de redes neuronales. Las redes neuronales han estado empujando el horizonte de lo que se creía posible en la inteligencia artificial, y casi cada semana hay noticias nuevas de un sistema inteligente basado en redes neuronales. Hoy vamos a programar una red neuronal muuuy sencilla.

El Perceptrón

Uno de los primeros modelos artificiales de una neurona fue inventado en 1957 por Frank Rosenblatt, un profesor de psicología en la Universidad de Cornell. Rosenblatt diseñó un algoritmo de clasificación con aprendizaje supervisado, es decir, un algoritmo que aprende a clasificar nuevos datos basado en datos conocidos.

Un perceptrón es un modelo con varias entradas, que su vez son ponderadas, tiene un término independiente y una salida binaria que depende de si la suma ponderada de las entradas es mayor o menor a cero. En la figura 1 podemos ver cómo se calcula la salida de un perceptrón simple.

</img>
Figura 1. Ecuación de la salida del perceptrón.

El producto punto entre el vector w y las entradas x es el promedio ponderado de las entradas. Una visualización de nuestro perceptrón sería la siguiente:

</img>
Figura 2. Un perceptrón simple con 3 entradas ponderadas, un término independiente (observa los parámetros w) y una salida.

En la figura 2, nuestro término independiente es el parámetro w0. De esta manera, podemos reducir la salida a un producto punto entre dos vectores.

Datos

Las entradas del perceptrón pueden ser números que cuantifiquen cualquier cosa. Por ejemplo, podemos hacer un modelo para clasificar hombres y mujeres según su peso y su estatura*. Los siguientes datos obtuve de amigos míos:

Implementando el perceptron

Para la implementación, vamos a crear una clase Perceptron, que va a encapsular toda la funcionalidad. Vamos a hacerlo en python para que cualquiera pueda probarlo en sus propias máquinas. Primero ponemos el constructor:

import random

class Perceptron:
    def __init__(self,input_number,step_size=0.1):
    self._ins = input_number # Número de parámetros de entrada
    
    # Seleccionamos pesos aleatorios
    self._w = [random.random() for _ in range(input_number)]
    self._eta = step_size # La tasa de convergencia
    ...

La variable self._w son los pesos w, la variable self._ins es el número de variables de entrada, etc.

Ahora necesitamos también la función para calcular la salida del perceptron. Como sabemos, sólo es necesario calcular un producto punto entre la entrada y los pesos, y verificar si es mayor a cero o no:

class Perceptron:
    ...
    def predict(self,inputs):
        # Producto punto de entrada y pesos
        weighted_average = sum(w*elm for w,elm in zip(self._w,inputs))
        if weighted_average > 0:
            return 1
        return 0
    ...

No se confundan con la línea del producto punto. No es más que un truco de Python llamado comprensión de lista. Vale la pena que lo aprendan ; )

El último elemento que necesitamos es la función de entrenamiento del perceptron. Antes de agregarla, volvamos a la figura 1, con la ecuación de la salida. Y pensemos en qué ocurre cuando hay errores.

Si tenemos una mujer (la salida correcta sería 1), y el modelo incorrectamente da una salida de 0, entonces tendríamos que reducir los pesos, para que no se vuelva a equivocar. En el caso contrario, deberíamos incrementar los pesos para evitar el error. Pues de hecho, así es como funciona el algoritmo de aprendizaje del perceptron (y tiene sustento matemático, del que hablaremos posteriormente, pero por lo pronto, conformémonos).

class Perceptron:
    ...
    def train(self,inputs,ex_output):
        output = self.predict(inputs)
        error = ex_output - output
        # El error es la diferencia entre la salida correcta y la esperada
        if error != 0:
            self._w = [w+self._eta*error*x for w,x in
            zip(self._w,inputs)]
        return error

La variable self._eta se llama así por la letra griega, y es una tasa de convergencia. Un parámetro comunmente utilizado en análisis numérico para suavizar la convergencia de un algoritmo.

Y con eso tenemos el código de nuestra clase perceptron listo. Con esto podemos agregar código para probarlo y verlo funcionando. El código para probarlo es el siguiente:

#!/usr/bin/env python
from perceptron import Perceptron

## Datos de hombres y mujeres
input_data = [[1.7,56,1], # Mujer de 1.70m y 56kg
              [1.72,63,0],# Hombre de 1.72m y 63kg
              [1.6,50,1], # Mujer de 1.60m y 50kg
              [1.7,63,0], # Hombre de 1.70m y 63kg
              [1.74,66,0],# Hombre de 1.74m y 66kg
              [1.58,55,1],# Mujer de 1.58m y 55kg
              [1.83,80,0],# Hombre de 1.83m y 80kg
              [1.82,70,0],# Hombre de 1.82m y 70kg
              [1.65,54,1]]# Mujer de 1.65m y 54kg

## Creamos el perceptron
pr = Perceptron(3) # Perceptron con 3 entradas

## Fase de entrenamiento
for _ in range(100):
    # Vamos a entrenarlo varias veces sobre los mismos datos
    # para que los 'pesos' converjan
    for person in input_data:
        output = person[-1]
        inp = [1] + person[0:-1] # Agregamos un uno por default
        err = pr.train(inp,output)

h = float(raw_input("Introduce tu estatura en centimetros.- "))
w = float(raw_input("Introduce tu peso en kilogramos.- "))

if pr.predict([1,h,2]) == 1: print "Mujer"
else: print "Hombre"

Como ven, tenemos que iterar varias veces para lograr que el algoritmo converja. En la Figura 3 se puede ver cómo ocurrieron errores en el resultado:

</img>
Figura 3. Variabilidad del error en entrenamiento de perceptron.

Y para concluir, en la figura 4 pueden ver cómo la frontera entre hombres y mujeres quedó tras el entrenamiento. Como ven, nuestro perceptrón logró clasificar nuestros datos, pero tal vez no le vaya tan bien con otros.

</img>
Figura 4. Datos conocidos y frontera obtenida tras el entrenamiento..

• Vale la pena mencionar también que clasificar perfectamente a hombres y mujeres por peso y estatura no es posible, pero con este algoritmo podemos obtener una predicción razonable.

Para concluir

Hemos implementado un pequeño Perceptrón. Uno de los algorítmos de aprendizaje más sencillos que existen, y un ejemplo básico de red neuronal. Pueden descargar el código en zip, o con git y correrlo en sus propias máquinas - se los recomiendo ; ).

Posteriormente escribiré un post nuevo donde vamos a estudiar (de manera sencilla) las matemáticas del perceptrón, y los avances de las redes neuronales, y en particular de las redes neuronales profundas.

Comentarios bienvenidos y gracias por compartir! ;)

JavaScript es uno de los lenguajes de programación más utilizados en el mundo; y la función Math.random() es la función estándar de JavaScript para obtener números pseudoaleatorios. ¿Me creerían si les dijera que hasta hace unos días, la función Math.random() en uno de los motores de JavaScript más usados en el mundo era medio mala?

Pues sí: hace unos días, el algoritmo para generar números pseudoaleatorios que se utiliza en el motor de JavaScript V8 fue modificado. Esto después de que usuarios encontraran problemas en sus servidores que dependían de un generador de números aleatorios confiable.

En este post vamos a estudiar los Generadores de Números Pseudoaleatorios (también conocidos como PRNGs por sus siglas en inglés), de cómo los desarrolladores de V8 utilizaron uno bastante malo - y de cómo los cacharon con las manos en la masa.

Pero entonces, ¿porqué era tan malo el generador de Javascript? y en general, ¿qué determina que un Generador de Números Pseudoaleatorios sea bueno?

¿Qué es aleatorio y cómo lo generamos?

<p align="right">Cualquiera que piense en métodos aritméticos para generar números aleatorios está, por supuesto, en pecado. — JOHN VON NEUMANN (1951)</p>

En la ciencia de la computación y las matemáticas es común que se necesite una ‘fuente de aleatoriedad’. Por ejemplo, para criptografía, juegos y apuestas, simulaciones de Montecarlo, o incluso para cosas sencillas como el algoritmo QuickSort se necesita generar múchos números que sean aleatorios, y que sean generables rápidamente. Desafortunadamente, generar números veraderamente aleatorios no es sencillo. Existen aplicaciones donde es muy importante que los números sean verdaderamente aleatorios, como la criptografía o las apuestas. Para estas aplicaciones existen generadores basados en eventos cuánticos o en sistemas caóticos (e.g. ruido atmosférico, dispositivos mecánicos, etc.). Estos generadores generan números verdaderamente aleatorios. Posteriormente escribiré un post sobre ellos.

Para otras aplicaciones, no es tan importante que los números generados sean totalmente aleatorios. Basta con que sean bastante aleatorios. Para eso fueron crados los Generadores de Números Pseudoaleatorios, que utilizan un ‘estado interno’ al que se le aplica una operación determinística para generar una secuencia de números. Es decir que estos generadores funcionan algo así:

var estado = VALOR_INICIAL;
function random(){
    estado = operacion_deterministica(estado);
    return estado; // estado es el número 'aleatorio' producido
}

¿Qué? ¿Operación determinística? Entonces no son aleatorios! (véase la cita de John Von Neumann al principio de esta sección)- Así es. Los generadores de números pseudoaleatorios generan una secuencia de números que no es aleatoria, pero parece ser aleatoria. Observen que dado el mismo valor inicial, la secuencia de números producida sería la misma.

Resulta que existen varias funciones aritméticas que pueden utilizarse para generar secuencias que parecen ser bastante aleatorias. Estas funciones han sido estudiadas extensivamente, y se ha escrito bastante sobre el tema. Por ejemplo, el renombrado profesor Donald Knuth de la Universidad de Stanford le dedica un capítulo de su serie de libros The Art of Computer Programming a la generación de números aleatorios y pseudoaleatorios. Entre otras cosas, Knuth concluye que un generador de números aleatorio no puede ser una funcion cualquiera, sino que tiene que ser una función diseñada y seleccionada muy cuidadosamente.

¿Qué es un PRNG?

Con lo que hemos hablado, vamos a observar un ejemplo de PRNG que funciona con un método conocido como congruencial lineal. Se llama de esta manera porque es una función ‘lineal por partes’. Esta función se construye con dos números primos ‘grandes’. En este caso, vamos a restringir nuestro número a generar a que esté entre 0 y 15, así que nuestros primos pueden ser 5 y 3. Bastante grandes para nuestro rango. Nuestra función congruencial lineal para generar números pseudoaleatorios es la siguiente:

var estado = VALOR_INICIAL % 16;
function random(){
    estado = (estado * 5 + 3) % 16
    return estado;
}

La secuencia de números que puede ser generada con este PRNG es la siguiente:

Como pueden observar, la secuencia se repite cada 16 números generados. Tómense un minuto para ver cómo se genera cada uno de los números. También, como pueden ver, la secuencia parece ser bastante aleatoria (aunque en realidad no lo es).

Vamos a ver entonces, qué características son importantes al diseñar un PRNG.

Diseñando PRNGs

Una de las características más importantes de un PRNG es su periodicidad. Ya hemos mencionado que un PRNG tiene un estado interno, con base en el cual genera una secuencia de números. Dado un estado inicial en particular, un mismo algoritmo generará la misma secuencia. Y como estamos trabajando con una computadora, todas éstas son variables limitadas: Es decir que hay un número finito de estados internos que puede generarse.

Entonces, sabemos lo siguiente:

• Dado el mismo valor inicial, la secuencia generada por un PRNG es siempre la misma
• La cantidad de números distintos que pueden ser generados es finita

Esto significa que la secuencia generada por un PRNG es de una longitud finita, y eventualmente empieza a repetirse a sí misma. Pueden observar esto en la secuencia de números en la Figura 1.

La longitud de la máxima secuencia de números distintos que puede ser generada por un PRNG es conocida como el periodo de este PRNG. Como es deseable generar secuencias que sean distintas, las funciones utilizadas en el PRNG deben tener periodos tan largos como sea posible.

Si el estado interno de un PRNG tiene una representación de k bits, entonces el periodo del PRNG es como máximo 2ᵏ. Los buenos PRNGs deben tratar de alcanzar esta periodicidad. Si no, solamente están desperdiciando memoria.

El otro criterio importante para un PRNG es que el algoritmo produzca secuencias que tenga una distribución uniforme, y que muestren poca correlación entre valores sucesivos.

¿Cómo fue encontrado el problema?

El problema fue descubierto por Betable, una compañía que ofrece una plataforma de apuestas en línea. El director general de Betable, Mike Malone detalló lo ocurrido en un post en el blog de ingeniería de Betable. Básicamente, en uno de sus servicios, que estaba programado en Javascript, utilizaron una función para generar identificadores aleatorios para sus transacciones. Su función para generar estos identificadores es simple:

var ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';

function random_base64(length) {
    var str = "";
    for (var i=0; i < length; ++i) {
        var rand = Math.floor(Math.random() * ALPHABET.length);
        str += ALPHABET.substring(rand, rand+1);
    }
    return str;
}

En Betable utilizaron identificadores de 22 caracteres de longitud, que vienen de un alfabeto con 64 caracteres. Esto significa que el espacio de identificadores es de tamaño 64²², es decir, de más o menos 2¹³². Bastante grandecito!

En Betable hicieron cuentas. Según sus números, si seleccionaramos uniformemente de este espacio a una taza de 1 millón de elementos por segundo por 300 años, la probabilidad de una colisión sería de 1 en 6 mil millones. ¿Cómo lo calcularon? Modelándolo como una Paradoja del Cumpleaños (un tema muy interesante, denle un vistazo!).

Sin embargo, tras un mes empezaron a observar problemas donde varias transacciones recibían los mismos identificadores. Dado que el modelado del expacio de identificadores es correcto, no les quedó más que verificar cómo funciona el PRNG de Javascript.

El Math.random de antes y de ahora

El tipo numérico en Javascript es IEEE 754 binary64, así que cuenta con 53 bits para generar números entre 0 y 1. Esto significa que en vez de poder generar 2¹³² diferentes identificadores, serían cuando mucho 2⁵² identificadores por cada variable que se utilice para guardar estado. Vale, no es tan bueno - pero funciona… sin embargo, al investigar más, en Betable descubrieron más problemas en el generador de V8.

Por cierto, Math.random es parte de la especificación oficial de Javascript; donde se indica que devuelve un número mayor o igual a 0 y menor a 1, con una distribución más o menos uniforme. La especificación no dice nada sobre el algoritmo, la periodicidad y la calidad de la distribución.

El algoritmo que utilizaban en V8 para Math.random es el siguiente:

var MAX_RAND = Math.pow(2, 32);
var state = [seed(), seed()];

var mwc1616 = function mwc1616() {
    var r0 = (18030 * (state[0] & 0xFFFF)) + (state[0] >>> 16) | 0;
    var r1 = (36969 * (state[1] & 0xFFFF)) + (state[1] >>> 16) | 0;
    state = [r0, r1];

    var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
    if (x < 0) {
        x = x + MAX_RAND;
    }
    return x / MAX_RAND;
}

Este algoritmo, según los comentarios en el código de V8 es el “Multiply-with-carry de George Marsaglia”. Por cierto, George Marsaglia era un matemático Estadounidense que pasó su carrera estudiando PRNGs - osea que no parece mala idea utilizar esta función como PRNG… pero entonces?

Pues si se fijan en este generador, genera 32 bits con base en dos variables. Lo hace con xors tras realizar corrimientos de 16 bits en cada dirección. Si se fijan, los 16 bits ‘altos’ del número generado vienen de r0, mientras que los 16 bits ‘bajos’ vienen de r1. Esto causa que la periodicidad de un generador como el de Betable donde se utiliza un redondeo de tipo Math.floor(Math.random() * arr.length); (donde sólo se utilizan los bits más altos del número generado) dependan de una sola semilla de 16 bits. Es decir que su periodo es muy corto.

Pero ¿Porqué sólo se utilizan los bits altos del número? Imaginen que Math.random genera el número binario 0.1010001100101. Ahora, en el código de Betable, nuestra variable ALPHABET tiene una longitud de 64 caracteres. 64 es 2⁵. Es decir que nuestro número generado, lo multiplicamos por 2⁵, que en binario es 100000. Es decir result = 100000*0.1010001100101 = 10100.01100101. Luego, hacemos Math.floor a ese resultado, que no es más que un truncamiento. El número que devolvemos es 10100, que no es más que los 5 bits más altos del número generado por Math.random.

Dado que esos números dependen de una sola semilla de 16 bits, como ya dije, el periodo es mucho más corto.

Y por eso es que en Betable empezaron a encontrar problemas a tan solo un mes.

Para darle una forma visual a la calidad de los PRNGs de en Javascript, observen cómo en la figura 2 se pueden ver ‘imágenes de ruido’ generadas con los PRNGs de (1) Safari y de (2) V8. Es bastante notorio que el PRNG de Safari genera una imagen que se ve más aleatoria.

El nuevo Math.random

El post de Malone en Betable fue muy popular (¿y cómo no? Es un análisis profundo y muy bueno de V8 y su PRNG); y eventualmente los desarrolladores de V8 se enteraron - y claro, lo tenían que arreglar : )

El algoritmo que seleccionaron fue xorshift128+, un algoritmo rápido, con periodicidad de 2¹²⁸-1, y que pasa la mayor parte de los tests básicos de aleatoriedad. El nuevo código se ve así:

uint64_t state0 = 1;
uint64_t state1 = 2;
uint64_t xorshift128plus() {
  uint64_t s1 = state0;
  uint64_t s0 = state1;
  state0 = s0;
  s1 ^= s1 << 23;
  s1 ^= s1 >> 17;
  s1 ^= s0;
  s1 ^= s0 >> 26;
  state1 = s1;
  return state0 + state1;
}

Específicamente, el código está disponible en el repositorio de V8 en Github. (viva el open source!)

Claro, no hay que olvidar que este tipo de generadores no son aptos para aplicaciones criptográficas (de seguridad), o de apuestas oficiales; pero simulación y cómputo distribuído son aplicaciones válidas para un PRNG de este tipo.

Y con esto, el drama del mal PRNG en V8 se termina. Tengan en cuenta que el Chrome que tienen instalado en sus computadoras tardará algunos días, semanas o meses en tener este nuevo algoritmo incorporado, así que no vayan a basar apuestas en él todavía! ; )

Por cierto, para cualquier curioso, chequen el análisis de Mike Malone, que es mucho más completo que el mío, y mucho más informado. De nuevo, espero que les haya agradado el post y hayan aprendido algo.

Recuerden la moraleja: Antes de usar un PRNG, asegúrense de que sean aptos para la aplicación que necesitan, y de que pasan suficientes pruebas de aleatoreidad.

Y claro, como la gente en Betable, no tengan miedo de darse un clavado al código de las librerías que utilizan!

Hasta la próxima, y felices fiestas ; ).

Hace unas semanas encontré un mapa en TopoJSON de México, y decidí utilizar información que obtuve del sitio web del INEGI para hacer una pequeña visualización de Producción bruta total, y población en el territorio Mexicano. Aquí la pueden ver:

(Nota: Las barras de abajo representan población y producción bruta por municipio. Están coloreadas por quintiles sobre la producción. Es decir que la zona morada corresponde a los municipios que producen 20% de la riqueza, y donde vive 2.36% de la población. Es posible interactura con la visualización haciendo click en las barras del fondo.)

La visualización me gustó bastante, porque es posible ver varios patrones interesantes. Primero que nada, el hecho de que la economía Mexicana se ha diversificado, y ahora es muy variada. El petróleo aún es muy importante, y la región cerca del Complejo Cantarell contiene a algunos de los municipios más productivos del país (e.g. Carmen, Paraíso); sin embargo, los 10 municipios más productivos del país están bastante repartidos geográficamente (en Cd. de México, Monterrey, Guadalajara, Toluca y la región de Cantarell). Conforme seleccionamos más municipios, más y más áreas del país se colorean, desde centros turísticos, ciudades fronterizas, centros industriales y grandes zonas metropolitanas.

Desafortunadamente, hay un par de cuestiones menos agradables que es posible observar. Por un lado está la desigualdad económica: 90% de la producción es realizada en 140 municipios, donde solamente vive 50% de la población. Esto significa que el otro 50% vive lejos de las principales zonas productivas (aunque en lugares como la ciudad de México, esto no significa que el resto de la población no pueda recibir los beneficios de la riqueza producida en municipios aledaños).

El otro hecho que es posible observar, es la pobreza al sur del país, partícularmente en el estado de Oaxaca, donde la mayoría de los municipios permanecen obscuros hasta cerca del final. Claro, esto es en parte debido a que Oaxaca tiene muchísimos municipios (60 de los cuales se llaman San Juan!:)), y la producción económica está dividida en más piezas - pero el hecho de la pobreza en el sur del país persiste.

En fin, espero que les haya agradado. Todos los comentarios son bienvenidos, y el repositorio en Github también está disponible. Hasta pronto! ; )

Hace un poco más de dos meses, el mundo de los algoritmos fue sacudido con un nuevo resultado en Isomorfismo de Grafos. El profesor Lázló Babai de la Universidad de Chicago es un brillante académico de ciencia de la computación y matemáticas. De origen Húngaro, el profesor Lázló realiza investigación en la Teoría de la Complejidad, matemáticas discretas y algoritmos. Hace un par de meses, el profesor Lázló (conocido entre sus amigos como Laci) anunció que había descubierto un algoritmo cuasi-polinomial que permite resolver el el problema de Isomorfismo de Grafos. Vamos a ver qué significa todo esto…

Nota: Antes de continuar, es importante que tengan una idea de qué es la Notación Big O, dado que vamos a hablar mucho sobre complejidad de algoritmos.

##¿El iso- qué de Grafos? Isomorfismo de Grafos es un concepto de la Teoría de Grafos. Dados dos grafos, queremos saber si esos dos grafos son isomórficos - o sea, si en realidad representan la misma “estructura”. Por ejemplo, en la Figura 1 podemos ver dos grafos ordenados de distinta forma, pero si observamos de cerca, podemos ver que su estructura es la misma.

¿Se nota? Observen que el nodo Azul está conectado con los nodos Naranja, Rojo y Verde en ambos grafos; luego, el nodo Morado está conectado con los nodos Amarillo, Rosa y Azul claro - también en ambos grafos. Observen que con todos los nodos, el resultado es siempre el mismo. Tómense un minuto para ver que es cierto. Entonces, buscamos un algoritmo eficiente que recibe dos grafos, y puede determinar si son isomórficos o no.

Isomorfismo de Grafos es un problema interesante, entre otras razones, porque es uno de pocos problemas que no se sabe bien si son del gripo de problemas P, o si es NP-Completo (más sobre esto adelante). Esto significa que -hasta no verificar que el Profesor Lázsló esté en lo correctio- no se sabe muy bien si el Isomorfismo de Grafos es un problema ‘fácil’ de resolver, o si es bastante ‘difícil’ de resolver. De hecho, la cuestión de si el Isomorfismo de Grafos puede ser resuelto en tiempo polinomial ha sido un problema abierto por más de cuarenta años!

P y NP

Esta sección es un poquito pesada. Si no quieres leer sobre la Teoría de la Complejidad, puedes saltártela - pero es interesante y muy importante. ;)

El problema de P vs NP es uno de los problemas más importantes de la ciencia de la computación, y de las matemáticas modernas. De hecho, es uno de los 10 Problemas del Milenio; y es un área con muchísimos esfuerzos de investigación en todo el mundo. Es casi como un esfuerzo cartográfico, para construir un mapa de la complejidad de los distintos problemas algorítmicos.

P y NP son dos clases de problemas algorítmicos. Por un lado, P es la clase de problemas que pueden ser resueltos en tiempo polinomial en función del tamaño de la entrada en una Máquina Determinística de Turing; mientras que NP es la clase de problemas que pueden ser verificados por una máquina determinística de Turing. Esto suena muy técnico, pero no se asusten. Una máquina de Turing no es más que un modelo matemático de una computadora.

En términos más simples, P es la clase de problemas que pueden ser resueltos ‘rápidamente’. Por ejemplo, ordenar una lista de N números puede hacerse en O(n log(n)). Es decir que puede hacerse en tiempo polinomial.

Por otro lado, NP es la clase de problemas que puede ser difícil de resolver, pero es fácil de verificar. Esto significa que los problemas en P, también son problemas en NP, pero no todos los problemas en NP son problemas en P.

Por ejemplo, el problema de colorear un mapa con K colores de manera que no haya dos estados contiguos con el mismo color es un problema NP. Dados N estados y K colores, existen K^N maneras de colorearlo. Es decir que conforme el número de estados crece, el tiempo que tomaría encontrar una combinación válida aumenta exponencialmente. Sin embargo, si recibimos el mapa ya coloreado, sería bastante rápido verificar que no hay dos estados con los mismos colores. Tiene sentido, ¿no? Otro ejemplo de un problema en NP es el verificar si una expresión de lógica proposicional es una contradicción o no.

La clase NP tiene varias características interesantes. Dentro de esta clase hay una serie de problemas llamados NP-Completos. Las características principales de los problemas NP-Completos, son (1) se ha demostrado matemáticamente que cualquier problema NP-Completo no puede ser resuelto más rápido que ningún otro problema en P o NP (aunque podría ser resuelto en tiempo equivalente). La otra característica (en lenguaje sencillo) es que todos ellos son prácticamente equivalentes* entre sí. Es decir que la solución de un problema NP puede ser utilizada para resolver cualquier otro problema NP. De esta manera, por ejemplo, es posible expresar los colores de un mapa como una expresión de lógica proposicional(link en inglés), y resolver ambos problemas “al mismo tiempo”.

Vale la pena mencionar que la primera característica fue demostrada por el Teorema de Cook-Levin, uno de los resultados más importantes de la ciencia de la computación!

Una cuestión importante de NP es que hasta ahora, nadie ha demostrado que los problemas NP-Completos sean imposibles de resolver en tiempo polinomial. De hecho, es factible que exista un algoritmo que pueda resolver el problema de satisfabilidad booleana en tiempo polinomial; es sólo que nadie lo ha inventado/encontrado.

¿Se dan cuenta de lo que esto significa? Es decir que si alguien logra resolver uno solo de los problemas NP en tiempo polinomial, entonces todos los problemas NP en realidad son problemas P, y NP sería igual a P (NP = P). Y viceversa, si alguien demostrara que los problemas NP son imposibles de resolver en tiempo polinomial, entonces el mundo podría descansar y aceptar que los problemas NP-Completos en realidad no son fáciles de resolver. En la Figura 2 se ven los diagramas de Venn para cada uno de estos casos.

Por esto es que el problema de P vs NP es tan importante. Y por eso el resultado del profesor László Babai es tan interesante. Ahora vamos a hablar de Isomorfismo de Grafos.

Nota: El lenguaje que usé en esta sección es sencillo e impreciso a propósito; pero si quieren saber con más precisión de la Teoría de la Complejidad, y del problema de NP vs P, pueden estudiarlo en Wikipedia en español y en inglés, que es mucho más completo.

¿Qué descubrió Laci?

Ya que estudiamos la significancia de todo esto; entonces podemos ir al grano: la pregunta es si el problema de isomorfismo de grafos le pertenece a la clase P, o solamente a la clase de NP - y si no es P, sería NP-Completo? También podría no ser ninguno de los dos. Un problema que no es NP-Completo pero tampoco es P.

Aunque el profesor Lázsló aún no ha logrado mostrar que Isomorfismo de Grafos es un problema P, ha logrado mostrar que es muy cercano a P; contradiciendo lo que muchos suponían antes: que era cercano a NP-Completo. Esto lo hizo mostrando que el problema de Isomorfismo de Grafos es equivalente al problema de Isomorfismo de Cadenas, que es más general; y luego utilizando la técnica de Divide and Conquer para dividir el grafo en secciones más pequeñas que pueden ser resueltas recursivamente. El resultado es entonces:

Dados dos grafos, cada uno con N nodos, un algoritmo que determina si son isomórficos o no tiene un tiempo de ejcución de . Esta función no es exactamente polinomial, así que se le llama cuasi-polinomial.

Este resultado es mejor que el mejor algoritmo que se conocía, cuyo tiempo de ejecución era . Como ven, este viejo algoritmo tiene un factor polinomial dentro del exponente, así que es un algoritmo cuasi-exponencial. Es decir que la diferencia es muy grande.

La prueba del resultado de Babai es larga, y difícil - y yo tampoco la entiendo bien. El borrador del artículo está disponible en ArXiV, y es prácticamente un libro: son 74 páginas de pruebas matemáticas y análisis. Laci también dio un seminario de tres sesiones donde explica su argumento, y está disponible en su sitio personal. Si les interesa este tema, pero el trabajo de Babai es muy avanzado, pueden empezar por Wikipedia, y luego este borrador del libro Computational Complexity: A modern approach escrito por dos profesores en la Universidad de Princeton son buenos recursos.

¿Y todo esto sirve para algo?

La cuestión de si dos grafos son isomórficos sí tiene aplicación fuera de la ciencia de la computación o las matemáticas. El estudio de grafos, o redes, ha crecido mucho en esta era en que la cantidad de información disponible ha crecido exponencialmente.

Una de las disciplinas que usan grafos continuamente es la Bioinformática, donde los nodos en un grafo pueden representar genes o proteínas y los vínculos entre ellos representan su nivel de coexpresión. De hecho, la teoría de grafos aplicada a la bioinformática ha sido utilizada para mejorar nuestra comprensión del cáncer en humanos, y en cómo diseñar curas.

Otro campo donde el isomorfismo de grafos podría ser útil sería en el análisis de redes sociales, y el estudio del internet.

Sin embargo, la mayor parte de las personas que estudian la teoría de la complejidad lo hacen por pura curiosidad matemática, no porque busquen implementar algoritmos más eficientes en las ciencias genómicas o de estudio de redes sociales ;). De hecho, los algoritmos sugeridos en todos estos artículos son puramente teóricos, y muchos no han sido implementados (aunque otros muchos sí lo han sido).

De cualquier forma espero que el post les pareciera interesante - ya sea que les gusten los algoritmos, o que les interese su aplicación. Hasta la próxima, y todos los comentarios son bienvenidos! ;)

Recientemente, investigadores de la Universidad de Fribourg en Suiza han estado trabajando en un nuevo artículo donde estudian el profundamente el algoritmo de PageRank. Particularmente, este estudio se centra en el comportamiento de PageRank caundo es utilizado para analizar redes (también conocidas como grafos) que crecen con el tiempo. El artículo fue mencionado en la lista [‘Emerging Technology from the ArXiv’] (http://www.technologyreview.com/view/541416/other-interesting-arxiv-papers-week-ending-september-19-2015/), de MIT Technology Review: Una lista semanal donde se seleccionan artículos novedosos e interesantes. Acabo de leer el artículo (en parte porque tengo que presentarlo en la escuela:P) y decidí escribir un pequeño post al respecto, dado que PageRank es un algoritmo famoso e importante.

¿Qué es PageRank?

Pues primero lo primero. Algunos tal vez nunca hayan escuchado el nombre, y algunos otros tal vez lo habrán escuchado pero no aprendieron los detalles de qué es y cómo funciona el algoritmo de PageRank. Para esas personas, vamos a revisarlo - y si tú ya conoces el algoritmo, puedes saltarte esta sección y leer ¿Qué dice el tal artículo?

El algoritmo PageRank fue desarrollado en 1996 en la Universidad de Stanford por Larry Page y Sergey Brin. ¿Les suenan? Éstos son los fundadores de Google, y PageRank fue el algoritmo que utilizaron para ordenar resultados web en las búsquedas de Google. Por cierto, [el artículo original donde Larry y Sergey presentan la anatomía de Google] (http://infolab.stanford.edu/pub/papers/google.pdf) está disponible en línea, y vale la pena checarlo.

De vuelta a PageRank. El algoritmo se basa en la idea de que sitios web importantes tienen muchas ligas que apuntan hacia ellos. Es decir, que si mi sitio web es importante, otros sitios web van a agregar ligas hacia él. Estas ideas sobre la importancia de los sitios web sugieren que la Web puede ser entendida como una red (valga la redundancia) de sitios que son conectados con ligas. La siguiente figura muestra una red con cuatro nodos, que podría representar cuatro sitios web que tienen ligas entre ellos.

Figura 1. Una red o grafo simple con cuatro nodos.

¿Porqué fue importante?

PageRank no fue el primer algoritmo en explorar la categorización de nodos en redes con base en su importancia. Sin embargo, Google fue de los primeros buscadores en utilizar un algoritmo de este tipo en su sistema de búsqueda. Hasta antes de eso, los buscadores utilizaban conteo de palabras clave para decidir qué sitios web son los más relevantes para una busqueda; es decir que si una persona busca “Pokemón”, los resultados serían sitios web con la palabra “Pokemón” escrita muchas veces. Esta métrica para ordenar los sitios web es bastante mala, dado que un sitio de baja calidad puede estar lleno de la palabra “Pokemón”, y parecer relevante; pero no tener ninguna información relevante o interesante más allá de la palabra “Pokemón”. Este sitio sería un resultado inútil.

Entonces, PageRank (junto con decisiones de negocio inteligentes) fue la chispa que convirtió a Google en una de las empresas más importantes del mundo. Es, de hecho, un algoritmo muy inteligente, que incluye muchos conceptos de probabilidad y ciencia de la computación. Vamos a echarnos el clavado a PageRank.

Detalles técnicos

Ahora vamos a explorar exactamente cómo funciona PageRank. PageRank es un algoritmo que recibe como entrada [un grafo] (https://es.wikipedia.org/wiki/Grafo), que es una entidad matemática representada por un conjunto de nodos y un conjunto de ligas entre esos nodos. En el ejemplo en la Figura 1, el conjunto de nodos es [1,2,3,4], y la lista de ligas puede ser una lista de pares de nodos que están conectados, por ejemplo: [(1,2),(1,3),(3,2),(3,4),(4,3)]. Para leer más sobre grafos, puedes checar el artículo de Wikipedia al respecto.

Entonces, PageRank recibe un grafo y calcula una distribución de probabilidad. Esta distribución representa la probabilidad de que si uno navega los links del grafo aleatoriamente, vaya a dar a un sitio web específico. En probabilidad existen varios problemas donde podemos imaginar a un ‘navegante’ que se mueve aleatoriamente en un espacio. Estos problemas son conocidos como caminos aleatorios. PageRank es un problema de este tipo, ya que supone que uno navega la web aleatoriamente a través de ligas. PageRank supone un camino aleatorio a través de la web.

Podemos considerar nuestro grafo de la Figura 1 como ejemplo. Imaginemos que cada uno de los nodos representa un sitio web, y las conexiones entre ellos representan ligas. Si empezamos nuestro camino aleatorio en el nodo 1, tenemos la misma probabilidad de que nuestro primer paso sea al nodo 2 o al nodo 3 - esta probabilidad es de 0.5, o de 50%. Luego, para nuestro segundo paso, del nodo 3 podemos movernos a los nodos 2, o 4, cada uno con probabilidad 0.5; mientras que el nodo 2 no tiene ninguna liga hacia otros nodos, así que ahí permanecemos en él con probabilidad igual a 1.

Vamos a sacar números para nuestros primeros dos pasos en la caminata aleatoria que parte del nodo número 1:

• Del nodo 1 podemos ir al nodo 2 con probabilidad 0.5. Luego:
  • En el nodo 2 permanecemos con probabilidad 1.
• Del nodo 1 también podemos ir al nodo 3 con probabilidad 0.5. Luego, del nodo 3:
  • Podemos ir al nodo 2 con probabilidad 0.5
  • Podemos ir al nodo 4 con probabilidad 0.5

Estas decisiones pueden expresarse como un árbol de decisión con probabilidades que empieza en el nodo número 1, y camina aleatoriamente por el grafo. Se puede ver que tras dos pasos, la probabilidad de estar en el nodo número 2 es de 0.75, mientras que la probabilidad de estar en el nodo número 4 es de 0.25 (o 75% y 25% respectivamente). Noten que en este caso, la probabilidad de estar en cualqueir otro nodo es de cero.

</img> Figura 2. Árbol de probabilidades en una caminata aleatoria.

Pero esto sólo es el principio. PageRank considera una caminata aleatoria infinita. Si observamos la Figura 1, podemos ver que conforme la caminata aleatoria se vuelve más larga, la probabilidad de estar en el nodo número 2 tiende a 1 y la probabilidad de estar en cualquier otro nodo tiende a 0 (tómense un minuto para ir a la Figura 1 y verificar que es verdad). Esto no es ideal, así que PageRank tiene una condición extra: Un parámetro α, conocido como el ‘factor de amortiguamiento’. Cada turno, con probabilidad α volvemos a empezar la caminata, seleccionando cualquiera de los nodos aleatoriamente; y con probabilidad α-1 continuamos la caminata normalmente. Típicamente α tiene un valor de 0.15. De esta manera, la probabilidad de volver al nodo 1 se vuelve de 0.15 dividido entre los cuatro nodos.

Con la adición del parámetro α, PageRank tiene una distribución más uniforme, y no beneficia a algunos nodos desproporcionadamente. Ahora sí tenemos todos los ingredientes necesarios para un modelo completo. Agárrense, porque vamos a ir un poco rápido.

Existe un proceso estocástico (o proceso probabilístico) que permite modelar perfectamente esta clase de camino aleatorio. Es bastante famoso: La cadena de Márkov. Márkov era un matemático Ruso, que hizo varias contribuciones a la teoría de probabilidad. Platicaremos de él después. La cadena de Márkov es un proceso estocástico con un sinnúmero de aplicaciones prácticas; y que puede ser representado en forma de una matriz, donde se definen las probailidades de moverse de un nodo al otro en un camino aleatorio. Bajo esta idea, la matriz definida por el grafo de la Figura 1 (sin factor de amortiguamento) se ve así:

</img> Figura 3. Matriz del Proceso de Markov para la caminata aleatoria en el grafo de la Figura 1.

Como ven, en la matriz A están las probabilidades de moverse de un nodo a otro. La probabilidad de moverse del nodo 1 al nodo 2 es 0.5, así que A[1,2] es 0.5. Lo mismo para el resto de la matriz.

Con cadenas de Markov existe un concepto conocido como la ‘distribución estacionaria’, donde dado un vector p, que representa posiciones iniciales en el grafo, representa la probabilidad de estar en cada nodo al largo plazo (¿les suena? Justo como PageRank); es decir:

</img> Figura 4. Ecuación de la distribución estacionaria.

Como ya habíamos mencionado, cuando no hay factor de amortiguamiento, todas las caminatas aleatorias terminan en el nodo 2. Les dejo de tarea verificar que el vector p que resuelve la ecuación para la matriz de la figura 3 es el vector [0,1,0,0]. (Nota: Para eso pueden usar www.wolframalpha.com!).

Y entonces, si agregamos el factor de amortiguamiento, la matriz que resulta es la siguiente:

</img> Figura 5. Matriz completa de pagerank para el grafo de la Figura 1.

¿De dónde salieron tantos decimales? Estos decimales resultan de agregar el factor de amortiguamiento de 0.15. Recordemos que 0.15/4 es 0.0375. Entonces, si estoy en el nodo 2, en vez de parmanecer ahí con probabilidad 1, voy a reiniciar el camino en un nodo aleatorio con probabilidad 0.15. Es decir que tengo probabilidad de 0.0375 de saltar a los nodos 1,3 o 4 y tengo probabilidad de 0.85 de permanacer en el nodo 2, más 0.0375 de ‘saltar’ al nodo 2 de nuevo: O sea 0.8875. El resto de las probabilidades puede calcularse de igual manera.

Ya no es tan fácil, pero tampoco es difícil resolver la ecuación de la Figura 4 utilizando la matriz de la Figura 5

• si utilizamos una herramienta como Matlab, Maple, o WolframAlpha ;). El resultado, tras algunas iteraciones, es el vector [0.0375,0.734,0.134,0.09]. Este vector es una distribución de probabilidad conocida como la distribución estacionaria de nuestro Modelo de Markov. Representa también la calificación de PageRank de cada uno de los nodos en nuestro grafo (Nodo 1: 0.0375; Nodo 2: 0.734; Nodo 3: 0.134; Nodo 4: 0.09). Esto nos permite rankear sitios web según su importancia! Es decir que el nodo 2 es el más importante, y después son el nodo 3, 4 y 1 respectivamente.

¿Qué tal?

Ahora que ya hemos hecho un ejemplo de PageRank, y tenemos una idea de qué es; podemos hablar del artículo donde fue PageRank fue analizado. Por cierto, para aquellos que quieren saber más de PageRank, hay una infinidad de recursos en línea, empezando por el artículo de Wikipedia en Español, el artículo de Wikipedia en inglés, que es mucho más completo y este sitio web de la Universidad de Cornell con muchos ejemplos.

¿Qué dice el tal artículo?

Suficientes bases de PageRank. Ahora toca hablar de lo que dice el famoso artículo hecho en Suiza. ¿Qué dice? Pues Mariani, Medo y Zhang observan que PageRank es un algoritmo muy popular. Es utilizado ampliamente en un sinnúmero de aplicaciones; por ejemplo el algoritmo de Google para rankear sitios web, ranking de [Artículos de investigación] (http://www.sciencedirect.com/science/article/pii/S0306457307001203) (siento esto está muy meta), e incluso estudiar las redes de interacciones entre proteínas en nuestras células. Los autores observan que PageRank es como un martillo que utilizamos para resolver todos nuestros problemas; pero que no todos los problemas son clavos. Es decir, que somos demasiado aventados a la hora de utilizar PageRank. Por eso este artículo es para estudiar en qué casos PageRank es una buena idea, y en qué casos no lo es tanto. Particularmente, se enfocan en los casos donde la red está en crecimiento constante, ya que sienten que estos casos no han sido bien estudiados. Un ejemplo son las redes sociales como Facebook y Twitter que crecen rápidamente: nuevos nodos y nuevas amistades aparecen todo el tiempo; otro ejemplo de red que crece con el tiempo son las redes de artículos científicos, donde artículos nuevos aparecen continuamente, pero no agregan nuevas referencias a otros artículos una vez que han sido publicados.

¿Cómo le hicieron?

Los autores estudian el comportamiento de PageRank de dos maneras: Con una [simulación Monte Carlo] (https://es.wikipedia.org/wiki/M%C3%A9todo_de_Montecarlo), y con dos bases de datos con información real. Las bases de información real fueron una red social (la de Digg.com) y una red de artículos científicos (de American Physical Society). Los resultados de sus experimentos contribuyeron a la hipótesis de que existen casos donde PageRank no es una elección ideal en ciertos casos.

Simulaciones de Montecarlo

Una simulación de Montecarlo no es más que la simulación de un proceso utilizando datos generados por computadora. Es un campo de estudio fascinante, y es un método muy común en el estudio de grafos. Para este artículo, los datos consistieron en grafos generados aleatoriamente, pero con ciertas reglas. Para ser concisos, basta con decir que los investigadores utilizaron una estrategia llamada Modelo Barabási-Albert, que permite generar grafos aleatorios que se parecen mucho a los grafos que se obtienen en el mundo real, tal como las redes sociales.

La idea del Modelo Barabási-Albert es que unos pocos nodos son muy populares, mientras que el resto son “promedio”. Éste es un fenómeno fácil de ver en Facebook: El usuario promedio tiene menos de 300 amigos, pero existen algunos usuarios que tienen varios cientos, y varios miles de amigos. Este tipo de redes tienen la característica que los nodos más populares se vuelven aún más populares, y los demás permanecen en el promedio. Algo así como el fenómeno de dinero llama dinero.

De vuelta al artículo, los autores encontraron en sus simulaciones que PageRank depende de dos parámetros muy importantes para ser preciso: La actividad de un nodo, y la relevancia de un nodo. ¿Qué son éstos?

• La actividad de un nodo mide qué tan activo es el nodo para agregar nuevas conexiones. Si un nodo se conecta a nuevos nodos cada turno, es un nodo activo; mientras que si un nodo no está haciendo conexiones nuevas, es un nodo inactivo.
• La relevancia de un nodo es una medida de su habilidad para atraer conexiones. Si soy muy divertido, aunque tenga pocos amigos, tengo la habildiad de atraer muchos amigos nuevos. Los autores asumen que PageRank debe poder descubrir esta clase de nodos.

Los autores modelan la actividad y la relevancia como cantidades que decrecen con el tiempo. Un artículo científico se vuelve menos relevante con el tiempo; y una persona en Facebook agrega a la mayoría de sus amigos al principio, y después agrega menos conforme el tiempo pasa. Parece razonable.

Los resultados en las simulaciones fueron que PageRank funciona bien en redes donde la actividad y la relevancia decaen a velocidades similares. Las redes sociales son un buen ejemplo: Un usuario en Twitter que pasa mucho tiempo en Twitter puede publicar contenido interesante, y buscar nuevos usuarios que seguir: mientras que un usuario que no usa Twitter mucho es poco relevante y poco activo. PageRank es un buen algoritmo para rankear elementos de una red social por importancia.

Por otro lado, los autores mencionan que en redes donde la actividad y la relevancia decrecen a velocidades muy diferentes, PageRank es bastante malo para reconocer los nodos más relevantes. Las redes de Artículos Científicos son un buen ejemplo. Un artículo puede ser relevante por mucho tiempo, pero una vez que es publicado, no vuelve a citar a ningún otro artículo. Es decir que la relevancia decae lentamente, mientras que la actividad decae inmediatamente; y esto provoca que PageRank sea sesgado hacia nodos viejos.

En el caso contrario, en pruebas donde la actividad decae lentamente, y la relevancia decae inmediatamente, los autores encontraron que PageRank tiene un serio sesgo que favorece nodos nuevos. Puntos extra para la persona que tenga una idea sobre una red que muestre actividad de largo plazo y relevancia de corto plazo : ).

Resultados en datos reales

Las simulaciones dieron el resultado esperado, pero es importante verificar esta clase de hipótesis con datos reales. Cuando los autores del artículo decidieron aplicar su metodología a datos reales se encontraron con un problema en particular: Estimar la relevancia de un artículo científico, o de un usuario en una red social. ¿Cómo hacerle? Ése es el problema que PageRank trata de resolver, así que ellos tenían que encontrar una manera alternativa de calcular la relevancia de un nodo (y por cierto, en mi opinión ésta es una debilidad importante de este artículo).

Bajo el esquema que los autores diseñaron, encontraron lo esperado: La red de la American Physical Society, una red de artículos científicos mostró que PageRank tiende a favorecer nodos antiguos; y que el número de citas es una medida mucho más precisa de la importancia de un artículo.

Para los datos de Digg.com, donde los nodos representan usuarios y las conexiones representan ‘follows’, o seguidores, dado que la red social tiene un comportamiento de relevancia y actividad similar, PageRank resultó ser una buena medida de la importancia de un nodo; pero la cuenta de seguidores de un usuario de nuevo fue un indicador más útil.

Discusión y conclusiones

Pues bueno, así es esto. El artículo es bastante completo, y de hecho los autores realizaron muchos experimentos detallados. Sin duda, el artículo tiene una debilidad: Los autores están tratando de medir el desempeño de PageRank. PageRank es una herramienta que trata de estimar la importancia de un nodo en un grafo; sin embargo, la importancia de un nodo en un grafo de datos reales es muy difícil de estimar. ¿Cómo saber si un Twittero es el más importante? ¿O un artículo científico? Pues en este artículo, diseñaron una medida que pretende ser mejor que PageRank, pero ¿quién sabe?

De cualquier forma, el artículo es inteligente, y presenta un buen punto: Hay que tener cuidado con las herramientas que utilizamos para resolver nuestros problemas. No todos los problemas son clavos, y el martillo no es la única herramienta. PageRank es un algoritmo brillante, interesante y útil; pero hay que detenernos a pensar antes de aplicarlo a nuestros datos o realizar una aplicación que depanda de PageRank.

Hace poco descargué una base de datos con información de negocios de “manufactura” del sitio web del INEGI. La información está disponible para todos, y hay muchas cosas interesantes. Me puse a jugar con esos datos, y decidí hacer mi primera visualización de mapa con la información de los negocios y algunos datos extra.

Al estar observando los datos, me di cuenta de que el tipo de negocio más común en la base de datos es el de tortillerias. Así es: tenemos más tortillerías en México, que cualquier otro tipo de negocio que fabrique algo. Se me hizo muy chistoso. Decidí estudiarlo en un pequeño mapa del Distrito Federal; y para no mostrar solamente tortillerías, busqué información sobre la población y el producto interno bruto de cada delegación. Todos estos datos los pueden visualizar en el mapa que ven a continuación:

Hay muchos patrones interesantes. Por ejemplo, el número de tortillerías y la población tienen casi los mismos colores en el mapa! esto significa que no importa que seamos ricos o pobres: Todos los Defeños comemos bastantes tortillas. Sin importar el PIB, ni el PIB per cápita; la concentración de tortillerías en el Distrito Federal es más o menos uniforme, de entre 3 y 10 por cada 1000 personas.

Por otro lado, se pueden ver unos datos que no son tan alentadores: Las disparidades en el Producto Interno Bruto; y especialmente las del PIB per cápita. Podemos ver que la delegación más poblada (Iztapalapa) es también una de las delegaciones con el menor PIB del DF; mientras que la Miguel Hidalgo tiene un PIB casi 7 veces más grande. Esto habla de muchísima desigualdad. Claro, el PIB no representa exactamente el nivel de ingresos de los habitantes de cada zona; sino que representa la riqueza generada en esas zonas cada año - y claro, zonas con negocios como las delegaciones Cuauhtémoc y Miguel Hidalgo tienen un PIB alto, aunque muchos de los trabajadores vengan desde otras zonas.

Sin embargo, las disparidades no dejan de ser nada menos que escandalosas. De hecho, el PIB per cápita de la delegación Miguel Hidalgo es comparable con el de los países más ricos del mundo (hagan la conversión: son unos 80,000 USD. Equivalente al de Suiza!); mientras que el PIB per cápita de la delegación Iztapalapa es de unos 2,400 USD: Comparable al de Gana; y apenas 3% del de la Miguel Hidalgo.

De nuevo, no es posible atribuir estas diferencias solamente a la desigualdad económica - y tampoco es posible decir que es todo debido a la distribución desigual de empresas y medios para generar riqueza. También hay que considerar que una ciudad está muy interconectada, y que para comprenderla, un pequeño mapa con estadísticas no es suficiente.

De cualquier manera, podemos recordar que aunque la ciudad está llena de contrastes, hay algo donde todos estamos en la misma página: amamos nuestra comida, y cómo no? Nuestra comida es la mejor del mundo. Y no importa si vives en Milpa Alta, Iztapalapa, la Cuauhtémoc o la Miguel Hidalgo: las tortillas nos unen.

Saludos!

Pues así es. También planeo llevar una versión del blog en español - aunque aquí habrá actualizaciones menos frecuentes, si hago posts que conciernan a México, o que simplemente me parezca que vale la pena tener también en español, los voy a poner acá. Así que por aquí nos vemos, a la misma hora en el mismo canal.

-P.