viernes, 14 de octubre de 2011

Computación evolutiva: Ejemplo VI

Abstract

Para el ejemplo VI de la serie práctica de algoritmos evolutivos, he implementado un OCR básico, a partir del ejemplo anterior donde realizamos un algoritmo capaz de reconocer los patrones de las vocales mediante aprendizaje evolutivo.

El OCR es bastante básico, pero permite comprobar la potencia de la computación evolutiva en relación al mundo del reconocimiento de patrones.

Ejemplo práctico VI: OCR básico

El programa que os presento a continuación; programado en un applet de Java para que podáis probarlo de primera mano, consigue precisamente eso: aprender a reconocer los patrones de las vocales, en formato Times New Roma, y un tamaño de 8 (8 x 5 = 40 píxeles). Se utiliza una red neuronal cuyos pesos se ajustan mediante una estrategia evolutiva.

El programa actua como un OCR, consiguiendo capturar la información textual dentro de una imagen (en formato GIF), y transcribiendo dicha información en una caja de texto.

Para agilizar la programación necesaria, el OCR sólo reconoce vocales en formato Times New Roman, y un tamaño de letra de 8.

En cualquier momento del entrenamiento, podemos pulsar en el botón Cancelar, y comprobar cómo va mejorando el reconocimiento del patrón.

Una vez entrenada la red neuronal, debemos introducir la ruta url de la imagen a procesar (en formato GIF), y pulsar sobre el botón Pasar OCR.

Las instrucción de uso se pueden esquematizar así:

1) Pulsa sobre el botón Entrenar para que la red neuronal aprenda a reconocer las vocales (espera hasta obtener una media de 120 en la función de evaluación).
2) Abre el Paint de Windows.
3) Crea un nuevo documento, y escribe con la herramienta de texto (con formato Times New Roman, y tamaño 8) todas las vocales que quieras, en cualquier lugar del documento (que pueden no ser consecutivos ni estar alineadas).
4) Guarda la imagen en formato GIF.
5) Sube la imagen a un hosting gratuito de imágenes. Por ejemplo: www.imgur.com.
6) Copia la ruta de la imagen subida (comprueba que la url termina en extensión ".gif").
7) Pega la url en el applet, donde dice URL de la imagen a procesar.
8) Pulsar sobre el botón Pasar OCR.

¡Y listo! Si todo va bien, el applet reconocerá todas las vocales del texto, y las introducirá en orden (y manteniedo los espacios en blanco entre ellas).


Debajo del siguiente applet encontrarás un enlace con el código fuente del ejemplo:

No puede ejecutar applets de Java. Instale la JVM, y vuelva a recargar la página, por favor.

Podéis descargar el código fuente del ejemplo VI desde este enlace.


martes, 11 de octubre de 2011

Computación evolutiva: Ejemplo V

Abstract

El siguiente ejemplo práctico, consiste en una revisión del ejemplo anterior donde realizamos un algoritmo capaz de reconocer las vocales mediante aprendizaje evolutivo.

En esta versión, hemos introducido algo de ruido durante el entrenamiento y prueba del reconocimiento conseguido. El ruido consiste en la introducción o borrado de píxeles en la imagen de la vocal a reconocer.

Ejemplo práctico V: Proyecto evolutivo de reconocimiento de patrones con ruido

El programa que os presento a continuación; programado en un applet de Java para que podáis probarlo de primera mano, consigue precisamente eso: aprender a reconocer los patrones de las vocales, en formato Times New Roma, y un tamaño de 8 (8 x 5 = 40 píxeles). No se usa ninguna técnica estratégica mediante heurística, sólo una red neuronal cuyos pesos se ajustan mediante una estrategia evolutiva.

El programa, al ejecutarse inicialmente el applet, sólo no tiene "conocimiento" alguno, y se limita a dar una respuesta aleatoria, cuando se le presenta los píxles de la imagen de una vocal en Times New Roman.

Para conseguir, de manera on-line; que el programa aprenda a reconocer el patrón de las vocales, debemos pulsar sobre el botón Entrenar. En ese momento, el programa comenzará a seleccionar evolutivamente, los individuos que mejor aproximen sus respuestas cuando se le interroga por las vocales.

En cualquier momento del entrenamiento, podemos pulsar en el botón Cancelar, y comprobar cómo va mejorando el reconocimiento del patrón.

Debajo del siguiente applet con el ejemplo V, explicaré más en profundidad la teoría que sigue el proyecto de aprendizaje automático, y encontrarás un enlace con el código fuente del ejemplo:

No puede ejecutar applets de Java. Instale la JVM, y vuelva a recargar la página, por favor.

Podéis descargar el código fuente del ejemplo V desde este enlace.


Explicación técnica del ejemplo


El proyecto de ejemplo V, tiene las siguientes características técnicas:

Todo el aprendizaje corre a cuenta de una red neuronal; con conexión hacia delante y una capa oculta (hidden layer).

La capa de entrada contiene 40 nodos; uno por cada posible contenido dentro del array que forma el conjunto de píxles de la imagen de la vocal. Hay 5 nodos de salida, los cuales indican la probabilidad de que la vocal pasada sea la que representa sicho nodo de salida.

Inicialmente, los pesos wij de la red neuronal son marcados aleatoriamente, por lo que la respuesta de la red neuronal ante el problema será aleatorio.

Hay pues que entrenar al programa para que aprenda, lo que vamos a conseguir ajustando evolutivamente los pesos de la red neuronal utilizada. Dicho entrenamiento evolutivo se realizará mediante una estrategia evolutiva.

La estrategia evolutiva será representada por un vector de 210 elementos de tipo real. Esos elementos o individuos de selección se van a corresponder con los pesos de los nodos que contiene la red neuronal, de manera que serán esos pesos los que irán evolucionando.

Así pues, la población en evolución, consistirá en n individuos (con n = 15), que tendrán n hijos, con variación exclusiva por mutación -sin recombinación- y cuya función de desempeño (fitness fuction) será calculada mediante competición -selección por torneo-.
Para el proceso de mutación, hay que tener en cuenta que cada individuo; además de un vector de pesos, contiene un vector de variables de ajuste, que también irá evolucionando junto con los pesos.

La mutación es de la forma:



Con alpha igual 0.2f, y donde xi indica el peso en la posición i del vector de pesos, y N(0,1) indica un valor tomado aleatoriamente de una distribución normal de desviación típica igual a 1, y media igual a 0. La otra variable que interviene en el proceso se corresponde con la variable de ajuste del elemento i, que; como se puede ver, muta antes de que lo haga el peso xi.

La evaluación de un individuo se realiza mediante el recuento de los aciertos conseguidos cuando se le pasa las 5 vocales. Se sumará uno cuando se acierta, y se restará uno si falla en el reconocimiento.

Finalmente, el proceso de selección consistirá en tomar los 15 mejores individuos de entre los 30 (15 padres + 15 hijos) individuos de la generación en curso. En caso de empate en la función de desempeño, se favorecerá a los individuos más longevos.

El paso de generaciones tendrá como resultado un ajuste en los pesos de la red neuronal, lo que dará lugar a un entrenamiento de la misma, que será lo que permitirá; a su vez, al programa a reconocer los patrones de las vocales dadas en una imagen GIF.


lunes, 10 de octubre de 2011

Computación evolutiva: Ejemplo IV

Abstract

Siguiendo con la serie de ejemplos prácticos -pulsa aquí para ver el ejemplo III: Aprendizaje automático en el juego 4 en raya- y disponibles con licencia GPL, de algoritmos evolutivos, voy a mostrar ahora otro ejemplo práctico. En esta ocasión se trata de diseñar un algoritmo capaz de aprender a reconocer las letras de las vocales dadas en un archivo GIF.

El esquema principal seguido es el mismo del ejemplo II y III de la serie de ejemplos evolutivos prácticos que estoy desarrollando. Es decir; haciendo uso de estrategias evolutivas y una red neuronal se consigue un apndizaje automático por parte de un programa.

Ejemplo práctico IV: Proyecto evolutivo de reconocimiento de patrones

El programa que os presento a continuación; programado en un applet de Java para que podáis probarlo de primera mano, consigue precisamente eso: aprender a reconocer los patrones de las vocales, en formato Times New Roma, y un tamaño de 8 (8 x 5 = 40 píxeles). No se usa ninguna técnica estratégica mediante heurística, sólo una red neuronal cuyos pesos se ajustan mediante una estrategia evolutiva.

El programa, al ejecutarse inicialmente el applet, sólo no tiene "conocimiento" alguno, y se limita a dar una respuesta aleatoria, cuando se le presenta los píxles de la imagen de una vocal en Times New Roman.

Para conseguir, de manera on-line; que el programa aprenda a reconocer el patrón de las vocales, debemos pulsar sobre el botón Entrenar. En ese momento, el programa comenzará a seleccionar evolutivamente, los individuos que mejor aproximen sus respuestas cuando se le interroga por las vocales.

En cualquier momento del entrenamiento, podemos pulsar en el botón Cancelar, y comprobar cómo va mejorando el reconocimiento del patrón.

Debajo del siguiente applet con el ejemplo IV, explicaré más en profundidad la teoría que sigue el proyecto de aprendizaje automático, y encontrarás un enlace con el código fuente del ejemplo:

No puede ejecutar applets de Java. Instale la JVM, y vuelva a recargar la página, por favor.

Podéis descargar el código fuente del ejemplo IV desde este enlace.


Explicación técnica del ejemplo


El proyecto de ejemplo IV, tiene las siguientes características técnicas:

Todo el aprendizaje corre a cuenta de una red neuronal; con conexión hacia delante y una capa oculta (hidden layer).

La capa de entrada contiene 40 nodos; uno por cada posible contenido dentro del array que forma el conjunto de píxles de la imagen de la vocal. Hay 5 nodos de salida, los cuales indican la probabilidad de que la vocal pasada sea la que representa sicho nodo de salida.

Inicialmente, los pesos wij de la red neuronal son marcados aleatoriamente, por lo que la respuesta de la red neuronal ante el problema será aleatorio.

Hay pues que entrenar al programa para que aprenda, lo que vamos a conseguir ajustando evolutivamente los pesos de la red neuronal utilizada. Dicho entrenamiento evolutivo se realizará mediante una estrategia evolutiva.

La estrategia evolutiva será representada por un vector de 210 elementos de tipo real. Esos elementos o individuos de selección se van a corresponder con los pesos de los nodos que contiene la red neuronal, de manera que serán esos pesos los que irán evolucionando.

Así pues, la población en evolución, consistirá en n individuos (con n = 15), que tendrán n hijos, con variación exclusiva por mutación -sin recombinación- y cuya función de desempeño (fitness fuction) será calculada mediante competición -selección por torneo-.
Para el proceso de mutación, hay que tener en cuenta que cada individuo; además de un vector de pesos, contiene un vector de variables de ajuste, que también irá evolucionando junto con los pesos.

La mutación es de la forma:



Con alpha igual 0.2f, y donde xi indica el peso en la posición i del vector de pesos, y N(0,1) indica un valor tomado aleatoriamente de una distribución normal de desviación típica igual a 1, y media igual a 0. La otra variable que interviene en el proceso se corresponde con la variable de ajuste del elemento i, que; como se puede ver, muta antes de que lo haga el peso xi.

La evaluación de un individuo se realiza mediante el recuento de los aciertos conseguidos cuando se le pasa las 5 vocales. Se sumará uno cuando se acierta, y se restará uno si falla en el reconocimiento.

Finalmente, el proceso de selección consistirá en tomar los 15 mejores individuos de entre los 30 (15 padres + 15 hijos) individuos de la generación en curso. En caso de empate en la función de desempeño, se favorecerá a los individuos más longevos.

El paso de generaciones tendrá como resultado un ajuste en los pesos de la red neuronal, lo que dará lugar a un entrenamiento de la misma, que será lo que permitirá; a su vez, al programa a reconocer los patrones de las vocales dadas en una imagen GIF.


lunes, 3 de octubre de 2011

Cómo desaparecer completamente


Tristeza. Es lo único que desde hace años veo en sus ojos.

Esa que está ahí no es ella (That there, that's not she), porque ella siempre va donde quiere (She goes, where she pleases). Ella ya no está aquí (She’s not here), aunque parezca mentira (This isn't happening). Y en poco tiempo se irá (In a little while she'll be gone). Su tiempo ya ha pasado (The moment's already passed). Ya no está aquí (She’s not here), y no me lo puedo creer (This isn't happening).

La vida es dura, y cruel. Eso lo sabemos todos. Y sin embargo, tenemos motivaciones para luchar. Pero llega un momento; y, por supuesto, con suerte, en el que éstas desaparecen. Lo que nos hacía levantarnos cada mañana, aquello que nos hacía soportar la vida tal y como es.

Debe ser tan sencillo como levantarse un día, y darse cuenta de que ya no eres el que solías ser. Que ese que está ahí, no eres tú (That there, that’s not me). Dejas de ser útil a la sociedad, y te conviertes en una carga, en un ser inválido (The moment's already passed Yeah, it's gone).

Casi sin darte cuenta, ya no puedes hacer nada por ti mismo, no puedes cruzar la puerta
(I go where I please. I walk through walls).

Tormento. No creo que exista otra palabra que describa mejor vivir una vida sin motivaciones. Tormento que podemos ver en los ojos de cualquier anciano, en los ojos de cualquier persona no válida. Desesperación. Tristeza. Se puede casi palpar su constante lucha por querer vivir. Y no hay posible consuelo. Sólo podemos besarles, abrazarles, y; por supuesto, en cuanto podamos mirar hacia otro lado.

No es sólo una muestra más, sino la muestra más clara de la insoportable levedad del ser.

Nota:

La canción que has podido escuchar de fondo, es “How to disappear completely” del grupo Radiohead. A continuación tenéis la letra completa:

That there, that's not me
I go where I please
I walk through walls
I float down the Liffey

I'm not here
This isn't happening
I'm not here, I'm not here

In a little while
I'll be gone
The moment's already passed
Yeah, it's gone

I'm not here
This isn't happening
I'm not here, I'm not here

Strobe lights and blown speakers
Fireworks and hurricanes

I'm not here
This isn't happening
I'm not here, I'm not here....



sábado, 1 de octubre de 2011

Computación evolutiva: Ejemplo III

Abstract

Siguiendo con la serie de ejemplos prácticos -pulsa aquí para ver el ejemplo II: Aprendizaje de estrategias no-loss en el juego 3 en raya o Tic-tac-toe- y disponibles con licencia GPL, de algoritmos evolutivos, voy a mostrar ahora otro ejemplo práctico. En esta ocasión se trata de diseñar un algoritmo capaz de aprender por si solo a jugar bien al famoso juego Conecta 4 -o cuatro en línea-.

El esquema principal seguido es el mismo del ejemplo II de la serie de ejemplos evolutivos prácticos que estoy desarrollando. Es decir; se sigue la idea detrás de Blondie24; un juego de damas, implementado por David B. Fogel, que; haciendo uso de Estrategias Evolutivas y una red neuronal, consiguió que el programa aprendiera, tras 8 meses de entrenamiento, a jugar bien a las damas. Y tan bien aprendió, que consiguió un rating de 2048 –un 99,6% mejor que cualquier jugador humano-.

Ejemplo práctico III: Proyecto Evolutivo para el juego Cuatro en Línea -o Conecta 4-

El programa que os presento a continuación; programado en un applet de Java para que podáis probarlo de primera mano, consigue precisamente eso: aprender a jugar al Cuatro en Línea, sin enseñarle a priori ninguna técnica estratégica mediante heurística, sólo usando una red neuronal cuyos pesos se ajustarán mediante una estrategia evolutiva.

El programa, al ejecutarse inicialmente el applet, sólo "conoce" las reglas básicas del juego, cuándo termina la partida y el resultado de la misma, y sólo sabe prever si tu próximo movimiento la hará perder. Pero no entiende de estrategias, ni es capaz de jugar demasiado bien.

Si pulsamos en el botón Estadísticas, podremos ver cuántas partidas empata o pierde en este momento el programa tras jugar 150 veces contra un jugador que puede ver 6 jugadas hacia delante (ply =6).

Si pulsamos sobre el botón Jugar, veremos que, en cuanto pensamos un poco y aplicamos una estrategia correcta, comenzamos a ganar partidas.

Para conseguir, de manera on-line; que el programa aprenda a jugar, debemos pulsar sobre el botón Entrenar. En ese momento, el programa comenzará a competir consigo mismo una y otra vez, mejorando con el paso de tiempo –de las generaciones- de manera automática su juego. Irá aprendiendo buenas estrategias de juego.

En cualquier momento del entrenamiento, podemos pulsar en el botón Cancelar, y comprobar cómo va mejorando el juego del programa. Si jugamos contra él, veremos que estrategias con las que antes le ganábamos, ahora ya no son efectivas, o que, si pulsamos sobre el botón Estadísticas, el porcentaje de partidas perdidas va disminuyendo.

Debajo del siguiente applet con el ejemplo III, explicaré más en profundidad la teoría que sigue el proyecto de aprendizaje automático, y encontrarás un enlace con el código fuente del ejemplo:

No puede ejecutar applets de Java. Instale la JVM, y vuelva a recargar la página, por favor.

Podéis descargar el código fuente del ejemplo III desde este enlace.


Explicación técnica del ejemplo


El proyecto de ejemplo III, tiene las siguientes características técnicas:

Toda la estrategia de juego, corre a cuenta de una red neuronal; con conexión hacia delante y una capaa oculta (hidden layer).

La capa de entrada contiene 42 nodos; uno por cada posible contenido dentro del array que forma el tablero de juego –con un 1 si la ficha de una casilla es propia, un -1 si la ficha es del adversario, y un 0 si la casilla está vacía-, y un nodo de salida, responsable de devolver el resultado del proceso neuronal: expresando lo bueno o malo que un movimiento concreto es.

Inicialmente, los pesos wij de la red neuronal son marcados aleatoriamente, por lo que la respuesta de la red neuronal ante el problema sobre qué buena o mala es una jugada será también aleatoria.

Hay pues que entrenar al programa para que aprenda a evaluar las jugadas, lo que vamos a conseguir ajustando evolutivamente los pesos de la red neuronal utilizada. Dicho entrenamiento evolutivo se realizará mediante una estrategia evolutiva.

La estrategia evolutiva será representada por un vector de 1848 elementos de tipo real. Esos elementos o individuos de selección se van a corresponder con los pesos de los nodos que contiene la red neuronal, de manera que serán esos pesos los que irán evolucionando.

Así pues, la población en evolución, consistirá en n individuos (con n = 15), que tendrán n hijos, con variación exclusiva por mutación -sin recombinación- y cuya función de desempeño (fitness fuction) será calculada mediante competición -selección por torneo-.
Para el proceso de mutación, hay que tener en cuenta que cada individuo; además de un vector de pesos, contiene un vector de variables de ajuste, que también irá evolucionando junto con los pesos.

La mutación es de la forma:



Con alpha igual 0.2f, y donde xi indica el peso en la posición i del vector de pesos, y N(0,1) indica un valor tomado aleatoriamente de una distribución normal de desviación típica igual a 1, y media igual a 0. La otra variable que interviene en el proceso se corresponde con la variable de ajuste del elemento i, que; como se puede ver, muta antes de que lo haga el peso xi.

La evaluación de un individuo se realiza mediante q partidas (con q = 15), jugadas entre el individuo a evaluar, y otro individuo de la población, tomado aleatoriamente sin reemplazamiento. Cada partida ganada le sumará 1 punto, las perdidas le restará 2, y los empates no suman nada. El valor final será su función de desempeño.

Finalmente, el proceso de selección consistirá en tomar los 15 mejores individuos de entre los 30 (15 padres + 15 hijos) individuos de la generación en curso. En caso de empate en la función de desempeño, se favorecerá a los individuos más longevos.

El paso de generaciones tendrá como resultado un ajuste en los pesos de la red neuronal, lo que dará lugar a un entrenamiento de la misma, que será lo que permitirá; a su vez, al programa a jugar bien, sin intervención heurística alguna.

Detalles adicionales


1º) Para que el aprendizaje automático tenga lugar, es necesario; al menos, prever un movimiento del contrario por adelantado -qué hará él si yo muevo aquí-. Esto se consigue mediante el uso de un árbol min-max de profundidad 2 (ply=2 ), lo que es insuficiente para que la máquina comprenda estrategias, pero que sí permite una base para el ajuste de pesos de la red neuronal. Pero siempre evaluar lo bueno o malo de una jugada será objeto de la red neuronal. Es decir; aunque hay un árbol min-max de ply igual a dos, la evaluación de la tabla de tu movimiento y el mejor movimiento del contrario, la desempeña la red neuronal y no ninguna regla a priori.

2º) La red neuronal utilizada va a devolver siempre un valor real en el rango [-1,1]. Un -1 sólo cuando el movimiento a evaluar termina siendo una victoria del adversario, un 1 si la victoria es suya, y un valor entre (-1, 1) indicando lo bueno que es una jugada para el programa (valores cercanos a 1) o para el contrario (valores cercanos a 1).

3º) El campo llamado Info, en el lateral superior derecho del applet, contiene información sobre el estado del entrenamiento. Conforme pasan las generaciones, la pantalla se actualiza, y muestra datos sobre el mejor individuo de la última generación: su función de desempeño, su edad -cuanto tiempo lleva en el pool evolutivo-, y la media de su juego -resultados/edad-. Cuando juegues contra la máquina, te mostrará la misma información, pero sobre jugador contra el que estás jugando -el mejor que se encontró-.