Divertimentos Informáticos

¿Cuántas palabras caben en una imagen?

2012-02-28T12:30:00.000-08:00

Sofía no suele ser una persona muy expresiva, y difícilmente uno penetra su coraza para poder siquiera atisbar qué es lo que está pensando en cada momento. Ya sé que llegar al trabajo por la mañana temprano no infunde la mayor de las alegrías, pero Sofía parecía tener su propio rito de autoresignación consistente en sentarse tratando de no llamar demasiado la atención, colocarse sus cascos, abrir sus herramientas de trabajo que organizaba siempre de la misma manera en la pantalla de la derecha (era de las pocas programadoras que tenía dos monitores) y en la de la izquierda comenzaba a leer algún artículo o alguna web de noticias hasta que, cuando lo consideraba oportuno, volvía la cabeza al otro monitor y comenzaba a escribir código. El rito debe ser poderoso porque, probablemente es la programadora más brillante de la empresa.
El caso es que aquella precisa mañana, su rito cambió. En vez de colocarse los cascos y abrir una web, abrió un ejemplar del "Código de Da Vinci" de Dan Brown y se puso a leer. A mí, la verdad, es que ese libro no me entusiasmaba especialmente y puestos a elegir prefiero al Holmes de Conan Doyle o al Hércules Poirot de Agatha Christie. El caso es que no es el tipo de libro que esperaba ver leyendo a Sofía, así que me atreví a preguntar.

¿Qué tal el libro? ¿Te gusta? -pregunté.
No mucho, pero habla de criptografía y tenía curiosidad. Me ha llamado la atención la parte en la que el protagonista interpreta supuestos mensajes secretos de Da Vinci en su obra de La Última Cena. ¿No es curioso pensar que el pintor podría estar comunicándose con alguien que vive cientos de años después de su muerte?
Visto así sí que impresiona -dije- pero supongo que es lo que buscan todos los pintores al pintar un cuadro ¿no?
Si, pero imagina poder esconder información oculta en la obra y que pase desapercibida para el público general, pero no para el receptor del mensaje.
Pues sería muy interesante, pero sería más fácil enviarle una carta con algún código cifrado.
Si, pero si alguien la intercepta tiene ya una información valiosa: El emisor quiere enviar un mensaje secreto al receptor. Eso de por sí es ya una información útil para el enemigo. Se trata, pues, de enviar el mensaje sin levantar sospechas. Hoy en día lo tenemos bastante fácil con las imágenes digitales, ya no hay que pintar un cuadro. Hay una técnica detrás de este tipo de ocultación de la información llamada Esteganografía.

Te refieres a que se pueden almacenar datos en las cabeceras de los archivos de imágenes ¿no? en fin, eso no parece muy seguro -traté de parecer inteligente haciendo mis propias deducciones.
Para nada Alberto, te equivocas. Hablo de guardar información en la propia información de la imagen, en los píxeles que la componen.
Sofía me observó unos segundo como esperando a que cayera en la cuenta de cómo podía hacerse tal cosa, como si fuera evidente, pero por enésima vez vio defraudadas sus expectativas sobre mis capacidades.
Verás -prosiguió- una imagen digital de ordenador está compuesta por una cabecera, como tú bien dices, en la que se almacena información específica del formato en la que se almacena. La cabecera de una imagen JPG es diferente a la cabecera de una imagen PNG o GIF, por ejemplo. Tras la cabecera están los datos de la imagen propiamente dichos. Una imagen está compuesta por muchos píxeles, y cada pixel tiene un color. Pues bien, la clave está en cómo se almacena el color de cada pixel. El formato más común (aunque no el único) es codificar el color usando tres bytes (24 bits) en el que cada byte representa el nivel de cada componente de color (a saber: rojo, verde y azul).
Por ejemplo, un componente alto de rojo y verde, y un componente bajo de azul daría lugar al color amarillo. Podríamos codificarlo como Rojo:255, Verde:255, Azul:0. Recordemos que un byte (8 bits) pueden representar un rango de valores que va del 0 al 255 (sin signo).
En un archivo gráfico, generalmente los pixeles se almacenan como secuencias de tres bytes en formato RRVVAA (o RRGGBB de red, Green y Blue).

Vale, esto más o menos lo entiendo, pero no llego a comprender cómo puedo almacenar algo en un pixel. Para el color se usan los 24 bits y no queda ninguno sin usar donde almacenar nada sin que se vea modificado el color en sí.

Touché querido Watson, de eso precisamente se trata: de cambiar el color del pixel, pero tan ligeramente que el ojo humano sea incapaz de notar la diferencia. De hecho Alberto, ¿eres capaz de notar alguna diferencia de color entre los dos siguientes rectángulos de color rojo? (Sofía me mostró los cuadros en su pantalla).

Por más que me esforcé no fui capaz de ver diferencia alguna, así que me aventuré a decir: Son iguales.

Para nada -rió sofía. El primero tienen una componente roja de 255 (en binario 11111111) y la segunda de 254 (en binario 11111110). Fíjate que sólo hay una diferencia de un bit entre uno y otro color.
Entonces, si cambio un sólo bit en una componente de color, ¿no notaré la diferencia? -de nuevo traté de parecerme más a Holmes que a Watson.
No, si cambio el primer bit (01111111), por ejemplo, mira lo que pasa:

Ahora, la componente roja pasa a ser 127, que dista bastante del 255 original. Por lo tanto, si queremos que el color se mantenga visualmente igual, sólo podemos tocar el bit de más a la derecha, también llamado bit menos significativo.

Ya entiendo -dije. Se trata entonces de codificar la información que queremos ocultar alterando los últimos bits de cada componente de color ¿es así?
Elemental querido Alberto. Así es. Te pongo un ejemplo. Imagina que quieres esconder un mensaje que empieza por la letra A en una imagen. La letra A tiene el código ASCII 65 (10000001 en binario). Pues bien, necesitamos modificar el último bit de la componente roja del primer bit para que acabe en 1, el de la componente verde para que acabe en 0, y así sucesivamente. Como tenemos 8 bits, cada carácter necesitará tres píxeles (3 pixeles * 3 componentes de color = 9 componentes de color) Es decir, nos sobra un bit que, por mantener las cosas simples, no vamos a modificar.
El proceso sería pues el siguiente (Sofía garabateó sobre un papel):

Sofía rodeó de color rojo los bits que era necesario cambiar y me hizo notar como la componente azul del último pixel no la estábamos usando en el ejemplo, pero que podía usarse sin problema aunque complicaba un poco la programación. También me explicó que debían usarse formatos de archivos con compresión sin pérdidas, ya que formatos como el JPG pueden alterar las componentes de color originales.

Por cierto -continuó Sofía- puede almacenarse información "secreta" en otros tipos de archivos digitales, como vídeo o sonido. De hecho, en el caso del sonido el proceso es muy similar.

Lo cierto es que todo lo que me estaba contando Sofía empezaba a sonarme a buen argumento para una novela, pero como se me da mejor la programación que la literatura, decidí escribir un programa para poner todo en práctica en vez de tratar de hacerle sombra a Dan Brown. Tecleé dos programas, una llamado Encode.java que almacena un texto en una imagen y otro llamado Decode.java que realiza el proceso contrario. Reproduzco aquí los dos programas.

Encode.java

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import javax.imageio.ImageIO;
 
public class Encode {
    public static void main(String[] args) {
        if (args.length<2) {
            System.out.println("Formato: Encode imagen \"texto\"");
            System.exit(0);
        }
        String img_in=args[0];
        String message=args[1];
        
        message=message+"#";
        // cargar imagen
        BufferedImage img = null;
        try {
            img = ImageIO.read(new File(img_in));
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        if (message.length()>((img.getWidth()*img.getHeight())/3)) {
            System.out.println("El mensaje es demasiado grande para la imagen.");
            System.exit(0);
        }
        // almacenar mensaje
        // cada tres pixels un caracter
        int pix_index=0;
        byte[] chars=null;
        try {
            chars=message.getBytes("ASCII");
        } catch (Exception e) {
            e.printStackTrace();
        }
        for (int i=0; i<chars.length; i++) {
            for (int j=0; j<3; j++) {
                int ycoord=(int)(pix_index/img.getWidth());
                int xcoord=pix_index-(ycoord*img.getWidth());
                int c = img.getRGB(xcoord,ycoord);
                int red = (int)((c & 0x00ff0000) >> 16);
                int green = (int)((c & 0x0000ff00) >> 8);
                int blue = (int)(c & 0x000000ff);
                if (isBitSet(chars[i], (j*3)+0)) {
                    red |= 1 << 0;
                } else {
                    red &= ~(1 << 0);
                }
                if (isBitSet(chars[i], (j*3)+1)) {
                    green |= 1 << 0;
                } else {
                    green &= ~(1 << 0);
                }
                if (j<2) {  // el ultimo byte no lo usamos
                    if (isBitSet(chars[i], (j*3)+2)) {
                        blue |= 1 << 0;
                    } else {
                        blue &= ~(1 << 0);
                    }           
                }
                Color color=new Color(red, green, blue);
                img.setRGB(xcoord, ycoord, color.getRGB());
                pix_index++;
            }
        }
        // guardar imagen
        try {
            File outputfile = new File("encodedimage.png");
            ImageIO.write(img, "png", outputfile);
        } catch(Exception e) {
            e.printStackTrace();
        }
    }
    
    private static Boolean isBitSet(byte b, int bit) {
        return (b & (1 << bit)) != 0;
    }
}

Decode.java

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import javax.imageio.ImageIO;
 
public class Decode {
    public static void main(String[] args) {
        if (args.length<1) {
            System.out.println("Formato: Decode imagen");
            System.exit(0);
        }
        String img_in=args[0];
 
        // cargar imagen
        BufferedImage img = null;
        try {
            img = ImageIO.read(new File(img_in));
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        // obtener mensaje
        for (int i=0; i<(img.getWidth()*img.getHeight())-3; i=i+3){
            char car=' ';
            // primer pixel
            int ycoord=(int)(i/img.getWidth());
            int xcoord=i-(ycoord*img.getWidth());
            int c = img.getRGB(xcoord,ycoord);
            int red = (int)((c & 0x00ff0000) >> 16);
            int green = (int)((c & 0x0000ff00) >> 8);
            int blue = (int)(c & 0x000000ff);
            if (isBitSet((byte)red,0)) {
                car |= 1 << 0;
            } else {
                car &= ~(1 << 0);
            }
            if (isBitSet((byte)green,0)) {
                car |= 1 << 1;
            } else {
                car &= ~(1 << 1);
            }
            if (isBitSet((byte)blue,0)) {
                car |= 1 << 2;
            } else {
                car &= ~(1 << 2);
            }
            // segundo pixel
            ycoord=(int)((i+1)/img.getWidth());
            xcoord=i+1-(ycoord*img.getWidth());
            c = img.getRGB(xcoord,ycoord);
            red = (int)((c & 0x00ff0000) >> 16);
            green = (int)((c & 0x0000ff00) >> 8);
            blue = (int)(c & 0x000000ff);
            if (isBitSet((byte)red,0)) {
                car |= 1 << 3;
            } else {
                car &= ~(1 << 3);
            }
            if (isBitSet((byte)green,0)) {
                car |= 1 << 4;
            } else {
                car &= ~(1 << 4);
            }
            if (isBitSet((byte)blue,0)) {
                car |= 1 << 5;
            } else {
                car &= ~(1 << 5);
            }
    
            // tercer pixel
            ycoord=(int)((i+2)/img.getWidth());
            xcoord=i+2-(ycoord*img.getWidth());
            c = img.getRGB(xcoord,ycoord);
            red = (int)((c & 0x00ff0000) >> 16);
            green = (int)((c & 0x0000ff00) >> 8);
            blue = (int)(c & 0x000000ff);
            if (isBitSet((byte)red,0)) {
                car |= 1 << 6;
            } else {
                car &= ~(1 << 6);
            }
            if (isBitSet((byte)green,0)) {
                car |= 1 << 7;
            } else {
                car &= ~(1 << 7);
            }
    
            if (car=='#') {
                break;
            }
            System.out.print(car);
        }
    }
    
    private static Boolean isBitSet(byte b, int bit) {
        return (b & (1 << bit)) != 0;
    }
}
 

Bueno, el código no es especialmente elegante, pero parece que funcionará -dijo Sofía machacando de nuevo mi autoestima.
Para probar el programa usamos la siguiente imagen de una fotografía de un viaje a Dinamarca que había realizado Sofía.

Tras compilar los programas ejecutamos el comando: java Encode dinamarca.jpg "mensaje oculto"
Obtuvimos la siguiente imagen:

Como ves -dijo Sofía- son indistinguibles la una de la otra.
Tras ejecutar: java Decode encodedimage.png obtuvimos de nuevo el texto "mensaje oculto".

Bien, se me ocurren algunas utilidades para este programa -dije.
Si estas pensando en pasar mensajes ocultos dentro de imágenes a otra empresa para ganarte un sobresueldo, tendrás que refinar un poco el método, ya que, aunque codificada en la imagen, el texto no está encriptado y si alguien sospecha que hay un mensaje oculto será fácil obtenerlo. Aunque si lo que quieres es que Gaznápiro no los intercepte, creo que ni en mil años sería capaz.

De la cola del cine a la danza estelar

2012-01-22T12:04:00.000-08:00

Llevabamos ya casi media hora en la cola y aquello parecía no avanzar, lo que para ser un jueves por la tarde era bastante poco corriente. Mi amigo Descollante y yo solemos ir al cine este día porque suele haber poca afluencia, sin embargo, hoy la cosa estaba imposible.

Para la próxima sacamos la entrada por Internet -dije- aunque haya que pagar algo más. No entiendo como puede haber tanta gente hoy y el Jueves pasado estuvimos solos.

Pues no hay ningún misterio -dijo Descollante sin ni siquiera volver su mirada- los grupos de personas se comportan como sistemas dinámicos. No hay más.

Como era habitual, Descollante, que no distingue una pregunta retórica de otra real, se disponía a buscarle una explicación racional a un hecho que nadie más que él se atrevería a analizar seriamente, así que tenía dos opciones: callarme y seguir disfrutando de la cola, o hacer como si me interesara su comentario y enfrentarme a una disertación que no estaba seguro de querer escuchar. Por desgracia mi maldita manía de empatizar hasta con las piedras me hizo pronunciar dos fatídicas palabras: ¿sistemas dinámicos?

Así que Descollante se animó: Sí, la dinámica de sistemas trata de explicar el comportamiento de sistemas complejos que evolucionan a través del tiempo. El comportamiento de las masas se asemeja a un sistema dinámico, ya que la forma de actuar de un grupo grande de personas a menudo no puede entenderse a partir del comportamiento de cada individuo por separado.

¿No irás a decirme que esta cola podríamos haberla predecido? Porque si es así nos forramos prediciendo el comportamiento de las masas.

Tú siempre pensando en el dinero -rió mi amigo. De hecho no creo, ya que hablamos de lo que los matemáticos llaman sistemas no lineales: sistemas cuyo comportamiento global no puede expresarse como la suma de los comportamientos individuales.

Descollante, estoy seguro de que lo que me estás contando sería muy interesante si fuera capaz de comprender algo, pero no termino de entender a dónde quieres llegar.

Está bien, Alberto, te pondré un ejemplo más simple. ¿Recuerdas del instituto cómo se calcula la fuerza gravitatoria ejercida entre dos cuerpos?
Si -respondí- era algo así como que la fuerza es directamente proporcional al producto de sus masas e inversamente proporcional al cuadrado de su distancia.
Exacto -dijo Descollante mientras dábamos el par de pasos que había avanzado la cola- y esa formulita te permite calcular fácilmente cosas como la órbita que describirá un cuerpo alrededor del otro. Sin embargo, si añadimos un tercer cuerpo, tenemos un problema ya que lo convertimos en un sistema no lineal y describir analíticamente sus órbitas es una tarea tremendamente compleja con las matemáticas de las que disponemos. De hecho, se transforma en un sistema caótico donde empiezan a mandar las leyes de la teoría del caos.

Ahora sí que estaba desconcertado ya que aquello no tenía demasiado sentido para mí, así que no pude callarme: pero si no podemos calcular la trayectoria de sólo tres cuerpos, ¿cómo calculan los astrónomos la evolución de un cúmulo estelar o incluso de toda una galaxia?

Descollante me miró casi perdonandome la vida: he dicho que no podemos calcularlo analíticamente, pero disponemos de una herramienta maravillosa, la simulación por ordenador.

Aquello ya empezaba a gustarme más, habiendo un ordenador de por medio siempre me siento más cómodo. Así, entre teoría del caos por aquí y problemas no lineales por allá logramos entrar en el cine y ver la peli. Ya de regreso a casa de Descollante nos sentamos ante el ordenador porque quería mostrarme cómo hacer la simulación de un sistema complejo como un cúmulo estelar.

Verás Alberto, para representar cada estrella en el ordenador almacenaremos su posición en el espacio como una coordenada tridimensional X,Y,Z. Necesitamos también almacenar su velocidad y su aceleración como vector tridimensional. La idea es que todas las estrellas ejercen una fuerza entre sí. Como hay muchas estrellas, la fuerza resultante ejercida sobre una estrella es la suma de todas las fuerzas que actúan sobre ella. Como sabes F=G(m1*m2)/d, siendo la distancia d=sqrt(x1-x2*y1-y2*z1-z2). En realidad, como bien me dijiste antes hay que utilizar el cuadrado de la distancia, pero para la simulación vamos a utilizar directamente la distancia ya que buscamos también un efecto estético en la animación del movimiento de las estrellas. Tampoco vamos a meter de por medio a la constante G, la dejaremos descansar hoy. Desde luego, si fuéramos astrofísicos tratando de hacer cálculos exactos sí que tendríamos que tener todo esto en cuenta.
Conocida la fuerza, podemos calcular la aceleración que sufre la estrella en cada eje de coordenadas:

aceleración_x=F*(posición_x2-posición_x1)/d

Es decir, la aceleración en el eje X es igual al producto de la fuerza por la diferencia entre la posición en el eje X de la otra estrella y la posición X de la estrella sobre la que estamos realizando el cálculo. Todo ello dividido por la distancia. La aceleración total que sufre la estrella es la suma de todas las aceleraciones (una por cada estrella que la rodea). El cálculo en el eje Y y Z es idéntico.
Ahora que tenemos calculado el resultado de todas las interacciones entre estrellas, sólo nos resta calcular su velocidad sumándole la aceleración calculada en el paso anterior.

velocidad_x = velocidad_x + aceleración_x

Y lo mismo para las otras dos componentes Y y Z.
Ya sólo tenemos que sumar la velocidad a la posición de la estrella y habremos calculado su movimiento.

posición_x = posición_x + velocidad_x

Y de nuevo repetimos el cálculo para los ejes Y y Z.
Repitiendo estos cálculos en un bucle y representando cada estrella gráficamente tendremos una simulación animada de un cúmulo estelar.

Mientras me lo explicaba, Descollante iba tecleando un pequeño programa en Java. Una vez terminó de teclear lo ejecutó y esto es lo que se vio en la pantalla:

He creado un campo aleatorio de 25 estrellas -dijo Descollante- pero si quieres más sólo tienes que cambiar el valor de la variable NUM_STARS. Tampoco he simulado la colisión entre estrellas ni nada parecido, ya que simplemente queremos ver visualmente como evoluciona un sistema dinámico.
Hoy en día, los gobiernos y grandes corporaciones utilizan herramientas de análisis de sistemas dinámicos para predecir comportamientos económicos o incluso sociales.
Pues no sabes cómo me tranquiliza eso -dije.
¿Te tranquiliza? dijo sorprendido Descollante.
Reí pero no dije nada más. Aunque se lo explicara, dudo que Descollante fuera capaz de entender lo que es una frase irónica.

Aquí se reproduce el código que tecleó Descollante:

import java.util.Random;
import java.awt.*;
import javax.swing.*;
 
class SpaceDance extends JFrame {
 
  int RES_X = 640;
  int RES_Y = 480;
 
  public SpaceDance() {
    super("SpaceDance");
    setBounds(0, 0, RES_X, RES_Y);
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    Container con = this.getContentPane();
    con.setBackground(Color.black);
    GCanvas canvas = new GCanvas();
    con.add(canvas);
    setVisible(true);
  }
 
  public static void main(String[] args) {
    new SpaceDance();
  }
}
 
class Star {
 
  int posx, posy, posz; // posición
  double spdx, spdy, spdz; // velocidad
  double accx, accy, accz; // aceleración
  double mass; // masa
}
 
class GCanvas extends Canvas implements Runnable {
 
  int RES_X = 640;
  int RES_Y = 480;
  int NUM_STARS = 25;
  int tiempo_pausa = 100;
  Star[] stars = new Star[NUM_STARS];
  Thread t;
 
  public GCanvas() {
    t = new Thread(this);
    t.start();
  }
 
  @Override
  public void paint(Graphics g) {
    // dibujar las estrellas
    g.setColor(Color.black);
    g.fillRect(0, 0, RES_X, RES_Y);
    for (int i = 0; i < NUM_STARS; i++) {
      if (stars[i] != null) {
        int tam = (int) stars[i].mass;
        if (tam < 2) {
          g.setColor(Color.white);
        } else if (tam < 4) {
          g.setColor(Color.yellow);
        } else if (tam < 6) {
          g.setColor(Color.blue);
        } else {
          g.setColor(Color.red);
        }
        g.fillOval(stars[i].posx, stars[i].posy, tam, tam);
      }
    }
  }
 
  public void initStars() {
    // inicializar estrellas aleatoriamente
    Random rnd = new Random();
    for (int i = 0; i < NUM_STARS; i++) {
      stars[i] = new Star();
      stars[i].posx = rnd.nextInt(RES_X);
      stars[i].posy = rnd.nextInt(RES_Y);
      stars[i].posz = rnd.nextInt(RES_Y);
      stars[i].accx = 0;
      stars[i].accy = 0;
      stars[i].accz = 0;
      stars[i].mass = (rnd.nextFloat() + 0.1) * 10;
    }
  }
 
  @Override
  public void run() {
    initStars();
    do {
 
      for (int i = 0; i < NUM_STARS; i++) {
        // cálculo de las aceleraciones
        stars[i].accx = 0;
        stars[i].accy = 0;
        stars[i].accz = 0;
        for (int j = 0; j < NUM_STARS; j++) {
          if (i != j) {
            int dx = stars[i].posx - stars[j].posx;
            int dy = stars[i].posy - stars[j].posy;
            int dz = stars[i].posz - stars[j].posz;
            // distancia
            double d = Math.sqrt(dx * dx + dy * dy + dz * dz);
            if (d != 0) {
              // fuerza
              double f = (stars[i].mass*stars[j].mass) / d;
              // aceleraciÛn
              stars[i].accx += f * (stars[j].posx - stars[i].posx) / d;
              stars[i].accy += f * (stars[j].posy - stars[i].posy) / d;
              stars[i].accz += f * (stars[j].posz - stars[i].posz) / d;
            }
          }
        }
      }
 
      // cálculo de las velocidades
      for (int i = 0; i < NUM_STARS; i++) {
        stars[i].spdx += stars[i].accx;
        stars[i].spdy += stars[i].accy;
        stars[i].spdz += stars[i].accz;
      }
 
      // cálculo de las coordenadas
      for (int i = 0; i < NUM_STARS; i++) {
        stars[i].posx += (int) stars[i].spdx;
        stars[i].posy += (int) stars[i].spdy;
        stars[i].posz += (int) stars[i].spdz;
      }
 
      repaint();
      try {
        Thread.sleep(tiempo_pausa);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    } while (true);
  }
}
 

La máquina predictora de estados de ánimo

2011-11-04T16:35:00.000-07:00

No es ningún secreto que un tonto "leal" tiene más posibilidades de ascender en una empresa que un listo librepensador, pero si el tonto, además, disfruta gritando a los demás, sus posibilidades de ascender rozan el 100%. En eso andaba Gaznápiro, entrenando sus mejores gritos con el Sr. Lego dentro de su despacho (su faceta de tonto no necesitaba entrenarla más porque, probablemente, había llegado ya a lo más alto que nadie pueda llegar). Los gritos podían oírse en toda la oficina, entre nasales y con un tono agudo que daban más risa que miedo, y que agudizaban, aún más si cabía, la condición de tonto "leal" que le hace el trabajo sucio al gran jefe.
El Sr. Lego salió del despacho con la cabeza baja y maldiciendo hasta en arameo antiguo. Sofía, que se sentaba en la mesa contigua a la mía no paraba de anotar cosas en una libreta pequeña de color rojo, de esas de anillas en la parte de arriba.
¿Qué anotas con tanto interés? -pregunté a Sofía intentando esconder mi curiosidad.
Anoto el estado de ánimo que tiene Gaznápiro. Lo hago desde hace nueve días. -respondió.
Me quedé mirandola un rato esperando que me dijera que estaba de broma, pero no lo hizo. En vez de eso, prosiguió contándome detalles.
Intento encontrar un patrón de comportamento para ver si descubro qué es lo que hace que tenga un día de perros o un día de buen humor. Así sabré cuando pedir un ascenso o un día de vacaciones. Anoto lo que ha desayunado, el color de la corbata, si toma o no café… en fin todo lo que pueda observar lo anoto.
Lo peor de todo es que, conociendo a Sofía, lo estaba diciéndolo totalmente en serio.
El Sr. Lego, que andaba pegando el oído preguntó a Sofía si podía decirle qué tal día iba a tener mañana, ya que tocaba reunión de proyecto y andaba algo retrasado con la programación.
Bueno, -respondió Sofía- desgraciadamente aún no he encontrado ningún patrón.
Ambos me miraron como esperando que me sacara un as de la manga.
Venga Alberto, seguro que conoces algún truco para convertir todos estos datos en algo utilizable -dijo el Sr. Lego dándome palmaditas en la espalda y sonriendo como si me hubiera pillado en un renuncio.
Claro, si la información que ha anotado Sofía es la mitad de precisa de lo que esperaría de ella podemos utilizar un clasificador bayesiano para modelar el comportamiento de Gaznápiro e intentar predecir con qué estado de ánimo llegará mañana a la oficina.
Ahora eran Sofía y el Sr. Lego los que me miraban a mí como si fuera un bicho raro, lo que me hizo anotar mentalmente: "No volver a mirar a mis compañeros como si se hubieran escapado de un manicomio".

Usando los datos que había tomado Sofía obtuvimos la siguiente tabla en la que anotamos el color de la corbata, lo que había comido en el desayuno y lo que había bebido. En la última columna anotamos si ese día había estado o no de buen humor.

día	Corbata	Desayuno	Bebida	Humor
1	Roja	Pan	Café	Malo
2	Roja	Pan	Zumo	Malo
3	Roja	Fruta	Café	Bueno
4	Amarilla	Pan	Café	Malo
5	Amarilla	Fruta	Café	Bueno
6	Azul	Pan	Zumo	Bueno
7	Azul	Fruta	Café	Malo
8	Azul	Fruta	Zumo	Bueno
9	Azul	Pan	Café	Malo

Un clasificador bayesiano -comencé a explicar- selecciona la mejor clasificación según los atributos de los que disponemos. En nuestro caso, las clasificaciones posibles son Bueno o Malo, que describen el estado de humor de Gaznápiro. Nuestros atributos son: Corbata, Desayuno y Bebida, que pueden tomar los siguientes valores:

Corbata={Roja | Amarilla | Azul}
Desayuno={Pan | Fruta}
Bebida={Café | Zumo}

Espero que recordéis bien el teorema de Bayes, porque lo que sigue se basa en él. No es por casualidad que se llame clasificador bayesiano.

Nuestro clasificador va a basarse en la siguiente expresión:

Como sabéis P(c) es la probabilidad de que ocurra la clasificación c, siendo c={Bueno | Malo}. Por otro lado, P(a_i|c) es lo que llamamos probabilidad condicionada de a sabiendo que ocurre c. Por ejemplo, P(Azul|Bueno) es la probabilidad de que Gaznápiro lleve corbata azul sabiendo que hoy tiene buen humor.

Para calcular P(a_i|c) vamos a usar la siguiente fórmula:

Donde:
n es el número total de ocurrencias de la clasificación c.
n_c es el número de ocurrencias de la clasificación c para el atributo a_i.
p es el valor a priori estimado para P(a_i|c).
m es el tamaño de muestra equivalente.

Sofía no quitaba la vista del folio donde andaba garabateando las fórmulas, y el Sr. Lego no dejaba de mirarme tratando de seguir todo aquel maremagnum de formulitas y conceptos de Probabilidad.

Está bien, veámoslo con un ejemplo concreto -concedí. Imaginad que mañana Gaznápiro llega a la oficina con una corbata amarilla, y desayuna pan y zumo. Fijaos en que ese caso concreto no está en nuestra tabla, sin embargo, vamos a tratar de inferir con los datos que tenemos cuál será su estado de ánimo. Necesitamos calcular las siguientes probabilidades:
P(Amarilla|Bueno); P(Pan|Bueno); P(Zumo|Bueno)
P(Amarilla|Malo); P(Pan|Malo); P(Zumo|Malo)

Y también las probabilidades de:
P(Bueno) y P(Malo)

Para luego poder aplicar la primera fórmula y obtener un valor que nos permita clasificar los atributos. Según la primera formula, el cálculo se realiza así:

clasificar_dia_bueno = P(Bueno)*P(Amarilla|Bueno)*P(Pan|Bueno)*P(Zumo|Bueno)

Y para el caso de que tenga un mal día será:

clasificar_dia_malo = P(Malo)*P(Amarilla|Malo)*P(Pan|Malo)*P(Zumo|Malo)

Vamos a ir calculando cada una de las probabilidades condicionadas usando la segunda fórmula. Empecemos con P(Amarilla|Bueno). Tenemos que n=4, ya que hay un total de 4 casos en la tabla en el que humor=Bueno. Para n_c tenemos que n_c=1, ya que sólo hay un caso en el que el día haya sido bueno cuando llevaba corbata amarilla. Para p tenemos que p=1/3, ya que tenemos 3 posibles valores del atributo Corbata (Rojo, Amarillo y Azul). Finalmente, m es un valor arbitrario, pero ha de ser consistente para todos los casos. Vamos a tomar un valor m=3.
Es decir:
n=4
n_c=1
p=1/3=0.333
m=3

P(Amarilla|Bueno)=(1+(3*0.333))/(4+3)=0.285

No vamos a desarrollar aquí el cálculo de todas las probabilidades, ya que se calcula siempre igual. Simplemente, calcularemos otra más correspondiente al caso humor=malo y después pondremos todos los resultados ya calculados.
Como ejemplo calcularemos la probabilidad P(Pan|Malo):
Ahora tenemos:
n=5 (hay 5 casos en la tabla en el que Humor=Malo)
n_c=4 (hay 4 casos en el que comió pan teniendo un día malo)
p=1/2=0.5 (hay dos posibilidades: Pan o Fruta, por lo que la probabilidad es del 50% para cada una).
m=3

P(Pan|Malo)=(4+(3*0.5))/(5+3)=0.687

Resumiendo, estos son los valores que hemos obtenido después de calcular todas las probabilidades condicionadas:

P(Amarilla|Bueno)=0.285
P(Pan|Bueno)=0.357
P(Zumo|Bueno)=0.5

P(Amarilla|Malo)=0.249
P(Pan|Malo)=0.687
P(Zumo|Malo)=0.312

Nos resta calcular la probabilidad de P(Bueno) y P(Malo) que son:
P(Bueno)=4/9=0.444 (4 ocurrencias de Bueno sobre 9)
P(Malo)=5/9=0.555 (5 ocurrencias de Malo sobre 9)
Aunque aquí nos hemos limitado a dos, evidentemente podemos hacer una clasificación en más de dos categorías.

Usando la primera fórmula obtenemos el siguiente resultado para el caso Humor=Bueno:
clasificar_dia_bueno = 0.444*0.285*0.357*0.5 = 0.0225

y para el caso Humor=Malo:
clasificar_dia_malo = 0.555*0.249*0.687*0.312 = 0.0296

Por lo que, en principio, podemos prever que, dados los condicionantes observados (corbata amarilla y desayuno de pan y zumo), lo más probable es que tenga un mal día.

Sofía y el Sr. Lego levantaron la vista del papel donde estaba haciendo los cálculos y se me quedaron mirando sin saber qué decir, así que me adelanté a la pregunta que suponía que estaban a punto de hacerme:
Evidentemente, esto no es más que un modelo estadístico y no el oráculo de Delfos, esto no quiere decir que siempre que Gaznápiro pida pan y zumo para desayunar y traiga una corbata amarilla venga de mal humor. Además, el número de muestras (días) que hemos usado es bajo. En todo caso, este método, pese a su sencillez, es una poderosa herramienta para clasificar casi cualquier cosa. Los clasificadores bayesianos son muy utilizados, por ejemplo, en la clasificación de documentos. Un buen ejemplo de ello son los programas anti-spam que utilizan los servidores de correo electrónico. Si os interesa, quizá otro día os explique como se utilizan para filtrar el spam. También se utiliza en minería de datos, traducción automática, correctores ortográficos, predicción (meteorológica, bursátil, etc…). Y en general tiene multitud de aplicaciones dentro del campo de la Inteligencia Artificial.

Al día siguiente el Sr. Lego llegó con el siguiente programa en Python que había preparado para predecir el humor de Gaznápiro:

def classify(attr, classif, data, ask):
  # entrenar el clasificador
  m=3
  classes={}
  attribs={}
  attribs_count={}
  attribs_count_per_class={}
 
  # obtener atributos
  for i in range(len(attr)):
    attribs[attr[i]]=[]
 
  for k,v in data.iteritems():
    # obtener clases
    if not v in classes:
      classes[v]=1
    else:
      classes[v]=classes[v]+1
 
    # contabilizar atributos
    for at in k:
      if not at in attribs[attr[k.index(at)]]:
        attribs[attr[k.index(at)]].append(at)
      # cuenta total
      if not at in attribs_count:
        attribs_count[at]=1
      else:
        attribs_count[at]=attribs_count[at]+1
      # cuenta por clase
      if not (at,v) in attribs_count_per_class:
        attribs_count_per_class[(at,v)]=1
      else:
        attribs_count_per_class[(at,v)]=attribs_count_per_class[(at,v)]+1
 
  # calculo valor por cada clase
  calc={}
  for i in classes:
    calc[i]=float(classes[i])/float(len(data))
    for j in ask:
      n=classes[i]
      nc=attribs_count_per_class[(j,i)]
      p=1.0/len(attribs[attr[ask.index(j)]])
      calc[i]=calc[i]*((nc+m*p)/(n+m))
 
  return max(calc)
 
 
if __name__ == "__main__":
  attr=['corbata','desayuno','bebida']
  classif=['humor']
 
  data={('roja','pan','cafe'):'malo',
    ('roja','pan','zumo'):'malo',
    ('roja','fruta','cafe'):'bueno',
    ('amarilla','pan','cafe'):'malo',
    ('amarilla','fruta','cafe'):'bueno',
    ('azul','pan','zumo'):'bueno',
    ('azul','fruta','cafe'):'malo',
    ('azul','fruta','zumo'):'bueno',
    ('azul','pan','cafe'):'malo'}
 
  ask=['amarilla','pan','zumo']
 
  theclass = classify(attr, classif, data, ask)
  print "Clasificado como: " + theclass

De todas formas hoy no necesito ejecutarlo para saber cómo vendrá Gaznápiro a la oficina -dijo el Sr. Lego sonriendo- He visto su coche en el parking y alguien acaba de hacerle un buen bollo en la puerta. ¿Crees que deberíamos añadir un atributo al programa para eso?

PD. Para los que tengan curiosidad, la ejecución del programa predijo que Gaznápiro tendría un mal día… y acertó.

La leyenda de los "predictores" perfectos

2011-09-25T13:36:00.000-07:00

En una mañana cualquiera, aún no habría podido ponerme a trabajar en serio, pero aquél día sólo llevaba media hora sentado en mi mesa y había podido leer todos los emails pendientes, contestarlos, planificarme la jornada e incluso había empezado a trabajar en el código del programa que tenía entre manos. Un día normal mi compañera Sofía me habría entretenido contándome alguna batallita nocturna tras haber derribado alguna web "enemiga" (defacement lo llama ella), pero esa mañana estaba especialmente silenciosa y, pese a ir de alternativa por la vida, ahí estaba con su ipod enchufado a sus orejas. Gaznápiro, mi jefe, había pasado por delante de nuestras mesas como una exhalación, con la cabeza gacha y con un montón de papeles bajo el brazo. Mal presagio sin duda. Es la calma que precede a la tempestad. Cuando Gaznápiro llega tan temprano al trabajo acompañado de tantos papeles (ya podría comprarse una carpeta el hombre) es señal de que tiene que preparar una reunión con la plana mayor, de la que suele salir bastante cabreado. Evidentemente, tiene que desfogar con alguien y parece que, además de informáticos, somos buenos esparrings, porque nada más salir de esas reuniones la emprende, metafóricamente hablando, con nosotros.
Pero lo más extraño de todo era que el Sr. Lego aún no había aparecido por allí, y eso que suele ser el primero en llegar cada mañana. Puntual como un reloj suizo. Fue pensar en ello y aparecer por la puerta de la oficina. Traía el hombre mala cara esa mañana y unas ojeras bastante pronunciadas.
Buenos días Sr. Lego ¿mala noche? -dije.
Pues sí -respondió- he dormido regular. El crío, que anda con dolores de estómago y se pasa la noche llora que te llora, el pobre. Y encima escuchando la radio en el coche me entero de que han bajado las acciones de Microsol, justo ahora que acababa de comprar algunas por probar esto de la bolsa. Afortunadamente no invertí mucho, pero mira que tengo mala pata. Ojalá hubiera algún programa que te dijera en qué empresa hay que invertir para ganar dinero.
¡Ojalá! -dije. Pero me temo que todavía no lo han inventado. Aun así hay bastante gente investigando en ese campo, y por lo que sé, algunos programas no lo hacen mucho peor que brokers profesionales.
Evidentemente, acababa de captar la atención del Sr. Lego porque había dejado de mirar los valóres de bolsa para mirarme a mí.
Bueno -continué- el otro día leí algo sobre que habían desarrollado un programa que usando algoritmos genéticos era capaz de hacer mejor papel que la mayoría de los inversores humanos en el mercado de futuros.
¿Algoritmos genéticos? -preguntó el Sr. Lego.
Sí, es una de las ramas de la Inteligencia Artificial que se está explorando con más interés en la actualidad, y además tiene un campo de aplicación bastante amplio.
Pues no tenía ni idea -reconoció el Sr. Lego. ¿Cómo funcionan los algoritmos genéticos?
Verá usted Sr. Lego, no es fácil explicar cómo funcionan en pocas palabras, pero le voy a contar la leyenda de los "predictores" perfectos y verá como lo entiende rápidamente.

Cuenta la leyenda que en un mundo paralelo al nuestro vivían unos seres llamados predictores. En ese mundo todo era digital y estaba formado por ceros y unos. Todo se comportaba de forma binaria. Encendido/apagado, activo/inactivo, abierto/cerrado, etc… Los predictores no eran una excepción, y se alimentaban de cifras binarias. La comida de los predictores llegaba en forma de impulsos desde no se sabe dónde, el caso es que cada segundo llegaba un impulso que los predictores debían asimilar y digerir. Esos impulsos podían corresponder a un cero o un uno y siempre llegaban formando el mismo patrón que se repetía una y otra vez: 1101001011.
El Sr. Lego me estaba mirando con cara de incredulidad como pensando "No puede estar contándome semejante tontería", así que me apresuré a continuar antes de que me cortara en seco.
El problema es que los predictores necesitaban emitir una señal idéntica a la que recibían para poder digerirla. Los predictores emitían cada segundo, de forma sincronizada con la llegada de comida, una señal. La señal que emitían los predictores estaba codificada en su ADN en forma de secuencia fija de 10 bits. Cada predictor tenía una secuencia diferente, por lo que algunos, dependiendo del grado de similitud entre la secuencia de su ADN y la del patrón de llegada de comida se alimentaban mejor que otros.
Es decir, si un predictor tenía la secuencia 1001011001 en su ADN (recordemos que el patrón de llegada de alimentos es 1101001011), este comerá 7 de cada 10 veces que recibe comida, ya que hay 3 cifras que son diferentes entre los dos patrones.
O sea, que habrá predictores que estén mejor alimentados que otros ¿no? -dijo el Sr. Lego.
Efectivamente, son predictores mejor adaptados al mundo y, por lo tanto, con mayor probabilidad de sobrevivir y procrear.
El Sr. Lego sonrió: Así que los predictores también tienen hijos.
Realmente, Sr. Lego, son seres hermafroditas y muy promiscuos. Cada pocos segundos sienten la necesidad de unirse a otro predictor. Cada vez que dos predictores tienen relaciones tienen exactamente dos hijos (uno cada uno). Afortunadamente, cada vez que nace un predictor otro se desintegra y de esta forma la población se mantiene estable.
Qué bonita historia de Amor… -se mofó el Sr. Lego.

Verá Sr. Lego, lo más impresionante de esta historia es que tras algunas generaciones de predictores, el ADN de la mayoría de la población era capaz de predecir al 100% el patrón de llegada de alimento. Un hecho increíble. La población entera había evolucionado en su conjunto para adaptarse al medio. Es por ello que llamamos a esta historia la leyenda de los predictores perfectos.
Vaya, esto se parece bastante a la selección natural de la que hablaba Darwin -dijo el Sr. Lego. Sobreviven los más adaptados y con el tiempo los peor adaptados desaparecen.
Efectivamente, pero ¿sabe cuál es el mecanismo que consiguió que toda la población convergiera hacia un ADN perfecto? El secreto estaba en que los mejores adaptados también tenían más posibilidades de reproducirse y, por ende, de transmitir su ADN de mejor calidad.
Como la vida misma -bromeó el Sr. Lego. Lo que no entiendo es qué tiene que ver todo esto con un algoritmo capaz de predecir el comportamiento de la bolsa.

Bueno Sr. Lego, una vez establecida la analogía con el mundo de los predictores vamos a entrar en materia y a ver como funciona un algoritmo genético o evolutivo, como prefiero llamarlo.
En una población completa, llamaremos individuo a cada uno de sus componentes. Al ADN de cada predictor lo llamaremos gen y a cada bit que lo compone lo llamaremos cromosoma.
La población inicial tiene que ser lo suficientemente grande como para tener cierta riqueza genética, así que lo primero que hay que hacer es generar una población grande y con ADNs aleatorios.
Todo algoritmo genético consta de cuatro fases: Selección, cruce, mutación y extinción.

La selección consiste en escoger los mejores individuos para que procreen. Sin embargo, en pro de la diversidad genética no conviene quedarse estrictamente con los mejores. Es preferible asignar una probabilidad de ser seleccionado a cada individuo según su nivel de adaptación. Por ejemplo, un predictor que acierta 8 veces con su secuencia de ADN tiene que tener un 50% más de probabilidad de ser seleccionado para procrear que un predictor con 4 aciertos.
En cualquier caso, un predictor con mal ADN tiene que tener alguna probabilidad de procrear, aunque sea baja, ya que uno de sus hijos podría aportar una gran mejora a la población.
El nivel de adaptación al medio de cada predictor nos lo dará la llamada función de adaptación, que es una función que nos indica cómo de bien adaptado está el individuo. En el caso de los predictores, la función de adaptación nos devolvería el número de bits del ADN del predictor que coinciden con el patrón de llegada de comida.

En la fase de cruce es donde procrean los individuos seleccionados dando lugar a dos hijos. Se llama fase de cruce porque se seleccionan dos individuos y se entrecruzan sus ADNs. El proceso consiste en seleccionar de forma aleatoria un punto de corte del ADN y recombinarlos según el siguiente esquema. Supongamos que el punto de corte ha sido el tercer cromosoma.

Es decir, que del cruce de los padres (arriba) obtenemos dos nuevos hijos (abajo).

La tercera fase, llamada mutación, imita las mutaciones genéticas biológicas. Estas mutaciones no deben ser muy frecuentes (sobre un 1% de probabilidad de que se produzca, aunque se puede jugar con este valor). La mutación consiste en cambiar uno de los cromosomas de forma aleatoria en un gen, es decir, seleccionamos un cromosoma aleatoriamente y si es un cero lo cambiamos a un uno y si es un uno lo transformamos en un cero.

Finalmente nos queda la fase de extinción, donde elegiremos a los dos individuos peor adaptados para eliminarlos.
Todo el proceso se repite hasta que, o bien la población converge (aproximadamente un 95% de la población tiene un valor similar en la función de adaptación) o bien se alcanza un número máximo de iteraciones.
Este sería, grosso modo, el pseudocódigo de un algoritmo genético:

generar población inicial de forma aleatoria

  Mientras(no fin)

   Para tamaño(población)/2 hacer

      seleccionar dos individuos

      cruzar los dos individuos

      mutar con cierta probabilidad los nuevos individuos

      añadir los dos nuevos individuos a la población

      eliminar los dos peores individuos de la población

    fin para

  fin mientras

quedarse con la mejor solución

El señor lego estaba entusiasmado. Parecía haberlo entendido y ya estaba pensando en construir su propio modelo del mundo de los predictores. No tardó más de un par de horas en enviarme el siguiente código.

import math
import random
def initial_population(max_population, num_vars):
  # crear población inicial aleatoria
  population=[]
  for i in range(max_population):
    gene=[]
    for j in range(num_vars):
      if random.random()>0.5:
        gene.append(1)
      else:
        gene.append(0)
    population.append(gene[:])
  return population
def adaptation_function(gene, solution):
  # valor de adaptación del gen
  cont=0
  for i in range(len(gene)):
    if (gene[i]==solution[i]):
      cont=cont+1
  return cont
def evaluate_population(population, solution):
  # evalua todos los genes de la poblacion
  adaptation=[]
  for i in range(len(population)):
    adaptation.append(adaptation_function(population[i], solution))
  return adaptation
def selection(population, solution):
  adaptation=evaluate_population(population, solution)
  # suma de todas las puntuaciones
  total=0
  for i in range(len(adaptation)):
    total=total+adaptation[i]
  # escogemos dos elementos
  val1=random.randint(0,total)
  val2=random.randint(0,total)
  sum_sel=0
  for i in range(len(adaptation)):
    sum_sel=sum_sel+adaptation[i]
    if sum_sel>=val1:
      gene1=population[i]
      break
  sum_sel=0
  for i in range(len(adaptation)):
    sum_sel=sum_sel+adaptation[i]
    if sum_sel>=val2:
      gene2=population[i]
      break
  return gene1, gene2
def crossover(gene1, gene2):
  # cruza 2 genes y obtiene 2 descendientes
  new_gene1=[]
  new_gene2=[]
  cutpoint=random.randint(0, len(gene1))
  new_gene1[0:cutpoint]=gene1[0:cutpoint]
  new_gene1[cutpoint:]=gene2[cutpoint:]
  new_gene2[0:cutpoint]=gene2[0:cutpoint]
  new_gene2[cutpoint:]=gene1[cutpoint:]
  return new_gene1, new_gene2
def mutation(prob, gene):
  # muta un gen con una probabilidad prob.
  if random.random<prob:
    chromosome=random.randint(0, len(gene))
    if gene[chromosome]==0:
      gene[chromosome]=1
    else:
      gene[chromosome]=0
  return gene
def drop_worse_genes(population, solution):
  # elimina los dos peores genes
  adaptation=evaluate_population(population, solution)
  i=adaptation.index(min(adaptation))
  del population[i]
  del adaptation[i]
  i=adaptation.index(min(adaptation))
  del population[i]
  del adaptation[i]
def best_gene(population, solution):
  # devuelve el mejor gen de la poblacion
  adaptation=evaluate_population(population, solution)
  return population[adaptation.index(max(adaptation))]
def genetic_algorithm():
  max_iter=10
  max_population=50
  num_vars=10
  done=False
  solution = initial_population(1, num_vars)[0]
  population = initial_population(max_population, num_vars)
  iterations=0
  while not done:
    iterations=iterations+1
    for i in range((len(population))/2):
      gene1, gene2 = selection(population, solution)
      new_gene1, new_gene2 = crossover(gene1, gene2)
      new_gene1 = mutation(0.1, new_gene1)
      new_gene2 = mutation(0.1, new_gene2)
      population.append(new_gene1)
      population.append(new_gene2)
      drop_worse_genes(population, solution)
    if (max_iter<iterations):
      done=True
  print "Solucion: "+str(solution)
  best = best_gene(population, solution)
  return best, adaptation_function(best, solution)
if __name__ == "__main__":
  random.seed()
  best_gene = genetic_algorithm()
  print "Mejor gen encontrado: "+ str(best_gene[0])
  print "Funcion de adaptacion: "+str(best_gene[1])

Excelente Sr. Lego, veo que ha captado perfectamente la idea. De hecho sus predictores se convierten en predictores perfectos tras muy pocas iteraciones. ¡Enhorabuena!
Sí, y me parece que los predictores están muy felices, pero ¿valen para algo más los algoritmos genéticos?
Pues valen para muchas cosas. Son de hecho una metaheurística usada en búsquedas locales.
¿cómo? ¿metaqué? -preguntó el Sr. Lego.
Metaheurística. Es una forma de búsqueda heurística que podemos adaptar a casi cualquier problema que no tenga un algoritmo propio que lo resuelva. Una especie de comodín. Si no sabemos cómo afrontar la solución de un problema podemos usar una metaheurística como pueda ser un algoritmo genético.
Nos vale para problemas de optimización, diseño automático, aprendizaje, predicción, etc…
De hecho, si podemos representar el problema como ristras de números binarios, podemos usar el programa que acaba de hacer para resolverlo. Por ejemplo, si quisiéramos encontrar un valor entero para x que maximice la función f(x)=x^2, sólo tendríamos que crear una población de números binarios, que representarían a sus contrapartidas enteras, y usar como función de adaptación el valor de la propia función X^2 al evaluar el número representado por el ADN. En pocas iteraciones obtendríamos una población que convergería hacia ese valor de X que maximiza la función.
Interesante -dijo el señor Lego. ¿Pero sólo podemos tener genes cuyos cromosomas son ceros y unos?
Para nada -contesté. En el campo de la investigación suelen representarse así ya que con números binarios podemos codificar casi cualquier valor. De hecho, los cromosomas podrían ser cualquier cosa: números, letras, etc…
Eso sí, teniendo en cuenta que hay que elegir una función de adaptación acorde a la representación que usemos para la información.
Bueno, dijo el Sr. Lego. Voy a darle algunas vueltas a todo esto que me has contado para ver como hago un predictor perfecto para los valores de la bolsa.
Desafortunadamente (o afortunadamente) la bolsa no sigue patrones fijos, al menos aparentemente, aunque quizás dé usted con un predictor bursatil que le saque de esta empresa.
Ojalá, contestó el Sr. Lego. Aunque echaría de menos nuestras conversaciones.

¿Sueñan los ordenadores con imitar a Cervantes?

2011-08-24T13:29:00.000-07:00

Cualquier día es bueno, y más si la climatología acompaña, para dar un paseo por el parque. Aquel día coincidía con una feria del libro, y mi amigo Descollante y yo andábamos de caseta en caseta en busca de algún buen libro extranjero de informática (porque de los autóctonos mejor ni hablamos). En una de las casetas estaba Fulano sentado, firmando libros a troche y moche, el último fabricante de bestsellers en serie. A mí no me parece mal siempre que ayude a que algunos lean algo, aunque sea por poder decir que se han leído el último libro de moda, pero mi amigo Descollante suele ser algo más radical e intolerante con la literatura barata y de consumo, y más si mediocres escritores que aprovechan filón literario del último tema de moda, junto con un marketing estudiadísimo, acaban forrándose de la noche a la mañana. Quizás influya que Descollante lleva dentro un escritor frustrado y un montón de negativas de editoriales a sus espaldas. Y no es que sea Borges o Delibes, pero tampoco se le da mal eso de contar historias dándole a la tecla.

Para mí que Fulano tiene un grupo de monos escribiéndole las cosas esas que publica -comenzó a decir Descollante- Seguro que tiene un programa de ordenador que le escribe los libros.
Si fueras capaz de hacer un programa para escribir bestsellers seguro que te forrabas más que Fulano con sus libros -bromeé.
Descollante me miró con media sonrisa y me dijo que quizás no estábamos tan lejos de conseguir que los ordenadores fueran capaces de hacer literatura. No pude esconder mi sonrisa al pensar que ya estaba fanfarroneando de nuevo. Tuvo que captar mi pensamiento porque se paró en seco frente a una terraza-bar y se sentó en una silla sin ni siquiera avisar. Antes de que pudiera reaccionar había pedido dos Cocacolas.
No hace mucho estuve "jugando" con cadenas de Markov para tratar de generar texto con cierto sentido. Y no fue mal el experimento -comenzó a decirme Descollante.
¿Cadenas de Markov? me suena de la facultad -le contesté- pero no recuerdo muy bien en qué consistían.
Descollante sonrió y empezó a explicarme que las cadenas de Markov son una estructura matemática cuya definición formal es algo compleja, aburrida y además requiere sólidos conocimientos de Probabilidad. Así que, saltándose toda la parte aburrida, me explicó que una cadena de Markov es básicamente un grafo dirigido (un digrafo realmente) cuyos nodos están conectados por aristas, y a cada arista se le asocia un valor que es la probabilidad que hay de pasar de un nodo a otro.
La verdad es que me he quedado un poco a cuadros -le dije.
Es muy sencillo, Alberto. Imagina que le mostramos a un ordenador el siguiente texto: "Hola Lola". Y queremos construir una cadena de Markov que nos indique qué probabilidad hay, en esta frase, de pasar de una letra a otra. O mejor dicho de que a una letra le siga otra concreta. Por ejemplo, ¿qué probabilidad hay de que a la letra H le siga una O?
Teniendo en cuenta que las letras posibles son sólo H, O, L, A y espacio (SP), ya que no distinguimos aquí entre mayúsculas y minúsculas. Una cadena de Markov para esta frase tendría el siguiente aspecto.

Según el grafo, la probabilidad de que tras una L aparezca una A es del 50%. Aunque para trabajar con estos porcentajes mejor diremos que la probabilidad es de 0.5, es decir, la probabilidad será un valor real entre 0 y 1. La suma de las probabilidades de las aristas salientes de un nodo siempre tiene que valer 1.
Como ya habrás deducido -me dijo Descollante por sorpresa- el cambio de un estado a otro es una función de probabilidad que depende exclusivamente del estado anterior. Por lo tanto, aquello que haya ocurrido antes del estado anterior no tiene relevancia.
Vale, le dije. Y... ¿cómo se supone que esto va a escribir un libro?
Descollante empezó a reír mientras sacaba su portátil. Mira -me dijo- esto es una prueba que hice el otro día.
Me enseño el siguiente listado.

import random
 
def create_char_map(filepath):
  chars={}
  f = open(filepath, 'r')
  done=False
  lastchar=''
  while not done:
    t=f.readline()
    if len(t)==0:
      done=True
    else:
      for c in t:
        if not c in chars:
          chars[c]={}
        if len(lastchar)>0:
          if c in chars[lastchar]:
            chars[lastchar][c]=chars[lastchar][c]+1.0
          else:
            chars[lastchar][c]=1.0
        lastchar=c
  f.close()
 
  return chars
 
 
 
def markov_net(chars):
  for c in chars:
    tot=0
    for n in chars[c]:
      tot=tot+chars[c][n]
 
    for n in chars[c]:
      chars[c][n]=chars[c][n]/tot
 
  return chars
 
 
def generate_text(chars, initial_char, num_chars):
  text=''
  ch=initial_char
  for c in range(num_chars-1):
    text += ch
    ch=prob_choice(chars[ch])
  return text
 
 
def prob_choice(prob_chars):
  probability = []
  char = []
  cur_prob = 0.0
 
  for c, p in prob_chars.iteritems():
    cur_prob = cur_prob + p
    probability.append(cur_prob)
    char.append(c)
 
  rnd = random.random() * cur_prob
  for i, total in enumerate(probability):
    if rnd < total:
      return char[i]
 
 
if __name__ == "__main__":
  # cambiar alicia.txt por el nombre del
  # archivo que se quiera utilizar.
  chars = create_char_map('alicia.txt')
  chars = markov_net(chars)
  text = generate_text(chars, 'd', 1000)
  print text

Este programita lee un texto (preferiblemente grande) y construye una malla de probabilidades como esta, pero evidentemente mucho más grande para albergar todas las letras del alfabeto y los signos de puntuación.

La idea es que a partir de esta malla de probabilidades podemos hacer que el ordenador genere un texto sin sentido, pero con silabas habituales del idioma. Algo así como un lenguaje inventado.
Tras ejecutarlo usando el texto del libro Alicia en el país de las maravillas obtuvimos el siguiente texto:

de domal ajaterébobasta sesude co taditegabocudes a ni Ala y desuiñose os e itadonco ladezaden mo do paribl dace senanoca ca lie e mel M, diciontando renastuefa seloren coso llomara br Fun sero pre ire do-. atis Resties tun magunande la e sapu sa gils dedonco do acaren dontiga ventrtijo ta e padele aitoja vor dicancora-Nos y qur a puema dicienchadante deca la m!

Pues no creo que esto se venda más que los libros de Fulanito -dije riendo. Aunque la verdad es que parecen palabras inventadas de un idioma de Tolkien. Descollante ejecutó el programa varias veces más obteniendo diferentes resultados.
Bueno, todavía podemos mejorarlo un poco -dijo. En vez de construir una malla de probabilidades con las letras del alfabeto podemos hacerlo directamente con palabras completas.
¿Quieres decir que habría que construir una malla en la que, dada un palabra, contenga la probabilidad con la que aparecerá la siguiente palabra?
Efectivamente -respondió. Por cada palabra del texto analizado incluiremos todas las palabras que en algún momento del texto la sigan y con qué frecuencia, por ejemplo, en la frase "Soy grande porque no soy pequeño" vemos que tras la palabra "soy" aparecen las palabras "grande" y "pequeño", por lo tanto tras la palabra "soy" hay una probabilidad de 0.5 de que aparezca "grande" y 0.5 de que aparezca la palabra "pequeño".
Descollante se puso a teclear y cambió el programa que acabó teniendo el siguiente aspecto:

import random
 
def create_word_map(filepath):
  words={}
  f = open(filepath, 'r')
  done=False
  lastword=''
  while not done:
    t=f.readline()
    if len(t)==0:
      done=True
    else:
      for c in t.split(' '):
        if not c in words:
          words[c]={}
        if len(lastword)>0:
          if c in words[lastword]:
            words[lastword][c]=words[lastword][c]+1.0
          else:
            words[lastword][c]=1.0
        lastword=c
  f.close()
  return words
 
 
 
def markov_net(chars):
  for c in chars:
    tot=0
    for n in chars[c]:
      tot=tot+chars[c][n]
 
    for n in chars[c]:
      chars[c][n]=chars[c][n]/tot
 
  return chars
 
 
def generate_text(chars, initial_char, num_chars):
  text=''
  ch=initial_char
  for c in range(num_chars-1):
    text += ' '+ch
    ch=prob_choice(chars[ch])
  return text
 
 
def prob_choice(prob_chars):
  probability = []
  char = []
  cur_prob = 0.0
 
  for c, p in prob_chars.iteritems():
    cur_prob = cur_prob + p
    probability.append(cur_prob)
    char.append(c)
 
  rnd = random.random() * cur_prob
  for i, total in enumerate(probability):
    if rnd < total:
      return char[i]
 
 
if __name__ == "__main__":
  chars = create_word_map('alicia.txt')
  chars = markov_net(chars)
  text = generate_text(chars, 'La', 1000)
  print text

Descollante ejecutó el programa de nuevo usando el texto de Alicia en el país de las maravillas y este fue el texto obtenido.

 El Lirón se llevó a la boca, mamá! -protestó Alicia quedó muy soliviantadas.
 
 -¡Ratoncito querido! ¡vuelve atrás, que los pájaros se me suene de estas palabras, su libro de las palabras:
 
 Cuando volvió hacia arriba, pero no es muy cómodo, y después una de debajo de extrañar que vio al cuerpo, y a suceder en que comer y seguía achicándose rápidamente. Se está del jardín, y Morcaro, duques de haber muchas ganas de manzanas, con el suelo su alrededor hacia el aire. Incluso la dirección en esto, pero no lo que no se interrumpió, y tan terrible entre los pececillos
 Para esto no hacer esta mañana -dijo Alicia.
 
 -¡Yo no quiere decir! -refunfuñó el Grifo.
 
 Alicia empezaba a oír esto no había largado al principio -dijo Alicia-, qué tipo de que ir a

Curioso -dije- parece un texto escrito por un paranoico, pero algunas frases tienen sentido y todo. Parece interesante esto de las cadenas de Markov.
Pues sí -dijo Descollante. Las cadenas de Markov se aplican en gran cantidad de campos: en problemas de termodinámica y física estadística, para crear modelos meteorológicos, en simulación, juegos de azar, economía y predicción de valores de bolsa, incluso el algoritmo page rank de google hace uso de él.