Neptalium

Existen tres notaciones básicas para representar expresiones matemáticas; infija, prefija y postfija.
La infija es la más conocida porque es la que más se utiliza, por ejemplo: (1+2)*(3-4).
En forma prefija se representaría como *+12-34, y en forma postfija sería 12+34-*.

La forma infija resulta muy sencilla para los humanos, estamos acostumbrados a ella y es muy simple. Sin embargo requiere del uso de paréntesis para establecer el orden correcto de las operaciones a realizar, y esto supone un engorro a la hora de programar un evaluador de expresiones.  El “truco” consiste en convertir la expresión de infja a postfija o prefija, de esta forma nos deshacemos de los paréntesis ya que las notaciones prefija y postfija no los necesitan.

Una vez convertida la expresión a notación postfija o prefija es muy fácil crear un árbol binario para calcular el resultado de la expresión.

Los más observadores ya se habrán dado cuenta de que la notación postfija es también conocida como RPN (“Reverse Polish Notation”, notación polaca inversa). Fué inventada por el filósofo y matemático polaco Lukasiewicz precisamente como una notación alternativa para evitar los paréntesis en la expresiones. Más de uno habrá usado esta notación en las calculadoras RPN, especialmente de HP, ¿verdad?

Vamos a ver con un ejemplo muy simple como, usando simplemente un stack,  se puede convertir cualquier expresión infija (por compleja que sea) a notación postfija. Explicaré solamente la conversión de infija a postfija. La conversión a prefija es igual de sencilla pero lo dejo como ejercicio de pasatiempo para el que le apetezca.

Se va cogiendo cada elemento de la expresión (de izquierda a derecha) y se siguen estos pasos:

1. Si el elemento es un número o variable se copia directamente a la salida.
2. Si es un paréntesis izquierdo se mete en el stack.
3. Si es un paréntesis derecho, se van sacando uno a uno todos los elementos del tope del stack (y copiándolos en la salida) hasta encontrar un paréntesis izquierdo en el stack. Finalmente ambos paréntesis se descartan.
4. Si es un operador y en el tope del stack no hay un operador o hay un operador de menor precedencia entonces se añade el nuevo operador al stack.
5. Si es un operador y en el tope del stack hay un operador de mayor o igual precedencia entonces se saca el operador del stack y se copia en la salida, y se repite la comparación del operador con el nuevo tope del stack.
6. Cuando ya no quedan más elementos en la expresión se van sacando uno a uno todos los elementos del stack y se copian en la salida.

Usaré el ejemplo inicial en notación infija: (1+2)*(3-4).

• ( Se mete en el stack.  
  STACK[ ( ]  SALIDA[ ]
• 1 Se copia en la salida.
  STACK[ ( ]  SALIDA[ 1 ]
• + Operador, en el tope del stack no hay otro operador, se mete en el stack.
  STACK[ +( ]  SALIDA[ 1 ]
• 2 Se copia en la salida.
  STACK[ +( ]  SALIDA[ 12 ]
• ) Se sacan del stack y se copian en la salida todos los elementos hasta encontrar un paréntesis izquierdo.  
  STACK[ ]  SALIDA[ 12+ ]
• * Operador, en el tope del stack no hay otro operador, se mete en el stack.  
  STACK[ * ]  SALIDA[ 12+ ]
• ( Se mete en el stack.  
  STACK[ (* ]  SALIDA[ 12+ ]
• 3 Se copia en la salida.
  STACK[ (* ]  SALIDA[ 12+3 ]
• - Operador, en el tope del stack no hay otro operador, se mete en el stack.  
  STACK[ -(* ]  SALIDA[ 12+3 ]
• 4 Se copia en la salida.  
  STACK[ -(* ]  SALIDA[ 12+34 ]
• ) Se sacan del stack y se copian en la salida todos los elementos hasta encontrar un paréntesis izquierdo.  
  STACK[ * ]  SALIDA[ 12+34- ]
• Ya no quedan más elementos en la expresión, se sacan todos del stack y se copian en la salida.  
  STACK[ ]  SALIDA[ 12+34-* ]

El resultado final en notación postfija es 12+34-*

Ahora resulta muy sencillo evaluar la expresión utilizando de nuevo un simple stack.
Vamos cogiendo cada elemento de la expresión en notación postfija (de izquierda a derecha);

• Si el elemento es un operando (número, variable o constante) se mete en el stack.
• Si el elemento es un operador (+, -, *, /, sin, sqrt…) se saca del stack tantos elementos como parámetros necesite el operador, se realiza la operación y el resultado se mete en el stack.
• El proceso se repite hasta que no queden más elementos en la expresión. Al final del proceso habrá en el stack un sólo elemento que corresponde con el resultado final de la evaluación de la expresión.

Veamos como evaluar la expresión 12+34-*

• 1 Es un operando, se mete en el stack.
  STACK[ 1 ]
• 2 Es un operando, se mete en el stack.
  STACK[ 21 ]
• + Es un operador, como + es un operador binario (necesita dos elementos) se sacan del stack y se realiza la operación (1 + 2) y el resultado se mete en el stack.
  STACK[ 3 ]
• 3 Es un operando, se mete en el stack.
  STACK[ 33 ]
• 4 Es un operando, se mete en el stack.
  STACK[ 433 ]
• - Es un operador binario, se sacan dos elementos del stack y se realiza la operación (3 – 4) y el resultado se mete en el stack.
  STACK[ (-1)3 ]
• * Es un operador binario, se sacan dos elementos del stack y se realiza la operación (3 * (-1)) y el resultado se mete en el stack.
  STACK[ (-3) ]
• Resultado final: -3

También se puede utilizar un árbol binario para evaluar las expresiones. Para crearlos usamos un stack y vamos cogiendo cada elemento de la expresión en notación postfija (de izquierda a derecha);

• Si el elemento es un número o variable se crea un nodo con él y se mete en el stack.
• Si el elemento es un operador binario se crea un nodo con dicho operador, se extraen del stack dos nodos y se le añaden como hijos, finalmente el nuevo nodo se añade al stack.
• Si el elemento es un operador unuario se crea un nodo con dicho operador, se extrae del stack un nodo y se le añade como hijo, finalmente el nuevo nodo se añade al stack.
• El proceso se repite hasta que no queden más elementos en la expresión.

Para terminar, simplemente recorriendo recursivamente el árbol en inorden podemos calcular el resultado final de la expresión o incluso reconstruirla en su notación infija:

1. Imprimimos paréntesis izquierdo.
2. Visitamos subárbol izquierdo (*).
3. Imprimimos la raíz.
4. Visitamos subárbol derecho (*).
5. Imprimimos paréntesis derecho.

(*): El proceso se repite recursivamente en los pasos 2 y 4.

Crear y entrenar correctamente RNAs (Redes Neuronales Artificiales) tiene más de arte que de ciencia.

En primer lugar debes decidir el tipo de red más apropiada para el trabajo que debe realizar (Backpropagation, Hopfield, Adaline, Kohonen, Perceptrón Multicapa, máquina de Boltzman, etc. Incluyendo también la elección de sus funciones de propagación, activación/transferencia) y luego decidir su topología (monocapa, multicapa o recurrente), después viene su entrenamiento (con aprendizaje supervisado o no supervisado) para lo cual debes escoger una buena selección de ejemplos del problema que deba resolver y entrenarla lo justo y necesario para que entienda el problema correctamente en lugar de simplemente memorizar los ejemplos que ha visto durante su entrenamiento. O lo que puede ser aún peor; que entienda el problema de una forma completamente distinta a la que tu esperas…  …bueno, lo cierto es que siempre lo entienden como les da la gana, y como casi todo en IA una pequeña dosis de caos es esencial.

Para cada problema es necesario encontrar la mejor elección de su tipología (tipo de red), topología (número de capas y número de neuronas por capa -en el caso de redes multicapa-), cuál es la estructura y codificación de la información de entrada y salida que sea más adecuada; muestras y método de entrenamiento, tipo de función de transferencia…
Si diseñas una red demasiado grande para el problema a tratar o la sobreentrenas lo único que hará será memorizar las muestras de entrenamiento, si es demasiado pequeña o no has escogido una buena y variada selección de muestras no logrará entenderlo o lo hará de una forma parcial. No te queda otra que probar y probar hasta encontrar el balance ideal para que la red pueda generalizar en base a su entrenamiento.

Toda su inteligencia reside en el peso de sus conexiones, en el caso de las redes multicapa, cada neurona recibe las señales de las neuronas de la capa anterior, multiplica cada señal por el peso asociado a cada conexión y hace un sumatorio de todas, si su valor es positivo la neurona excitará a las neuronas de la siguiente capa y si es negativo las inhibirá. A ésto se le denomina como función de propagación.
Generalmente se programa también una función de activación o transferencia, que sirve para normalizar la salida de la función de propagación dentro de un intervalo determinado, las más utilizadas son:

• Sigmoidea: 1/1+exp(-x) (para un intervalo de 0 a 1).
• Tangente hiperbólica:  tanh(x) (para un intervalo de -1 a 1).

Es también habitual realizar un escalamiento de la salida de la función de activación simplemente multicándolo por un valor de escala más la suma de un valor de desplazamiento. Integrándolo directamente en las funciones de activación que he puesto de ejemplo quedarían así:

• Sigmoidea: 1/1+exp(-2*s*(x+t))
• Tangente hiperbólica: tanh(s*(x+t))

Siendo x el valor de entrada, s la escala y t el desplazamiento.

Ejemplo de una red Perceptrón Multicapa (MLP) de 3 capas; una de entrada de 27 neuronas,
una capa oculta de 22 y una capa de salida con una neurona. Haciendo un total de 13.090 conexiones sinápticas.

Y ahora el mejor ejemplo de cómo las RNAs hacen lo que les da la gana. En los 80 los militares norteamericanos se gastaron un buen montón de millones de dólares en un proyecto para incorporar en sus tanques un sistema de detección de tanques enemigos. El sistema consistía en una cámara conectada a un ordenador que iba analizando constantemente las imágenes y avisaba en el caso de que detectase un tanque.

Para este problema decidieron usar una red neuronal. La entrenaron con 200 fotografías; 100 fotos de tanques ocultos tras arboledas y 100 de árboles sin tanques. Hasta aquí todo bien, el entramiento funcionó perfectamente y el sistema era capaz de clasificar las fotos del entrenamiento.



Llegó el momento de probarlo y… oh! sorpresa! El sistema fallaba por todos lados y no daba ni una! En primer lugar pensaron que había memorizado las fotos de entrenamiento (y por lo tanto estaría intentando recordar en lugar de generalizar), pero después de mucho investigar, comprobar, verificar, analizar  y gastar pasta, se dieron cuenta de que las 100 fotos con tanques las habían sacado en días nublados y las otras 100 sin tanques en días soleados, la red había aprendido a reconocer lo que era más evidente; el cielo!
Millones de dólares para que un tanque te diga si hace sol… Ummm, un poco caro, no?



Y ahora os dejo con un buen ejemplo muy original de una red neuronal de 10 millones de conexiones sinápticas y una tasa de aciertos del 80% que es capaz de adivinar en qué objeto estás pensando con menos de 20 preguntas.