jueves, 3 de abril de 2014

Redes de Hopfield

Las redes de Hopfield,  ―llamadas así en honor a su inventor John Hopfield―, son un tipo de red neuronal basadas en aprendizaje no supervisado de tipo hebbiano, es decir,  que a diferencia de las redes neuronales del tipo back-propagation feed-forward, no necesitan de un entrenamiento previo para especificar cuál es la respuesta correcta para un conjunto de patrones. 

En general, las redes de Hopfield recrean con más precisión el modelo natural del cerebro humano e imita en cierto modo la forma de procesar del  neocórtex, que parece almacenar los recuerdos usando una memoria asociativa. Por ejemplo, escuchar una canción de nuestra infancia puede evocar un recuerdo que permanece latente en nuestro inconsciente. Estos recuerdos pueden no estar muy claros o no ser muy exactos, de tal manera que, aunque permanezcan distorsionados, el cerebro tiende a recomponerlos. Es como si distinguiéramos a una persona a la que no hemos visto durante años por alguno de sus rasgos actuales.

Las redes de Hopfield tienen una gran aplicación para el reconocimiento óptico de caracteres (OCR) y para los captcha (sistemas que evitan que agentes software suplanten a humanos en formularios de registro Webs).

 
 ←
 (Hopfield)
Fuente:  Bashir Magomedov (CodeProject GPL3)

La arquitectura de las redes de hopfield se basa en una red monocapa con N neuronas cuyos valores de salida son binarios: 0/1 ó -1/+1. Se puede modelar una red de hopfield como un grafo no dirigido y completamente conectado, en donde cada nodo es una neurona sin una relación reflexiva y las aristas entre neuronas los pesos de entrada a cada una de ellas.

Las salidas (para un caso típico de implementación) se calculan como:

\[ a_i =\begin{cases}1 \hspace{1cm} si& \sum_j w_{ij}s_j > \phi_i \\-1 & \text{en otro caso}\end{cases} \]

y donde:
  • wij es el peso de la conexión de la neurona j con la i.  wii = 0  y wji = wij
  • sj es el estado de la neurona j. 
  • Φ es el umbral de activación de la neurona i.
de esta forma la función de activación se representa como:




Fuente: Wikipedia



Hopfield demostró que se podía definir una función de energía para cada posible patrón de activación o estado de la red: \[ Energía = -\frac12\sum_{i,j}{w_{ij}{s_i}{s_j}}+\sum_i{\theta_i\ s_i} \] donde este valor tiende a converger a un mínimo local para un estado estable de la red.

Para entender mejor los mecanismos matemáticos que hacen posible el reconocimiento de patrones con las redes de hopfield supongamos que tenemos los siguientes patrones de entrenamiento:
\[ A = \begin{bmatrix}1 & 0\\1 & 0 \end{bmatrix}  B = \begin{bmatrix}0 & 1\\0 & 1\end{bmatrix}   C = \begin{bmatrix}1 & 0\\0 & 1\end{bmatrix} \]
y queremos reconocer los siguientes patrones:
\[X= \begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}   e   Y =\begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}\]
  • En primer lugar obtenemos los vectores escalados en el rango +1/-1 que utilizando la fórmula (2A-1),(2B-1) y (2C-1) resultan: \[ A= (1,0,1,0)    B= (0,1,0,1)   C=(1,0,0,1) \\E_1 = (1,-1,1,-1)  \\E_2 = (-1,1,-1,1)   y   \\E_3 = (1,-1,-1,1) \]
  • En segundo lugar obtenemos los pesos: 
    • \[T_1 = \left[\begin{array}{rr} 1\\ -1\\ 1\\ -1\end{array}\right]\begin{bmatrix}1&-1&1&-1\end{bmatrix} - I=  \left[\begin{array}{rr}1&-1& 1 &-1\\-1& 1&-1& 1\\ 1&-1& 1&- 1 \\ -1 & 1& -1 & 1\end{array}\right]   -   I =\\ \left[\begin{array}{rr}0 & -1 & 1 & -1 \\ -1& 0 &-1 &1 \\ 1& -1 &0 &-1 \\ -1& 1 &-1& 0\end{array}\right]\]
    • \[T_2 = \left[\begin{array}{rr}-1 \\ 1 \\ -1 \\ 1\end{array}\right] \begin{bmatrix}-1&1&-1&1\end{bmatrix} - I=  \left[\begin{array}{rr}1& -1 & 1 & -1\\ -1 & 1 & -1 &1 \\ 1& -1& 1 &- 1 \\ -1 &1& -1 &1\end{array}\right]   -   I =\\ \left[\begin{array}{rr}0 & -1 & 1 & -1 \\ -1& 0 &-1 &1 \\ 1& -1 &0 &-1 \\ -1& 1 &-1& 0\end{array}\right]\]
    • \[T_3 = \left[\begin{array}{rr}1 \\ -1 \\ -1 \\ 1\end{array}\right] \begin{bmatrix}1&-1&-1&1\end{bmatrix} - I=  \left[\begin{array}{rr}1 & -1 & -1 & 1 \\ -1 & 1 & 1 &-1 \\ -1& 1& 1 &- 1 \\ 1 &-1& -1 &1\end{array}\right]   -   I =\\ \left[\begin{array}{rr}0 & -1 & -1 & 1 \\ -1& 0 &1 &-1 \\ -1& 1 &0 &-1 \\ 1& -1 &-1& 0\end{array}\right]\] 
  • A continuación se calcula la matriz general de pesos: \[T = T_1 + T_2 + T_3 = \left[\begin{array}{rr}0 & -3 & 1 & -1 \\ -3 & 0 & -1 &1 \\ 1& -1& 0 &- 3 \\ -1 &1& -3 &0\end{array}\right]  \] 
  • En el caso del patrón X se procede a escalarlo en valores -1/+1 : \[ E_3 = (1,-1,-1,1)\], y, determinando \[S = E_3\], es decir, \[ S_1 = 1; S_2 = -1; S_3 = -1 y  S_4 = 1 \] 
    • Primeramente obtenemos la energía: \[Energía = -\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N}T_{ij}S_iS_j = -\frac{1}{2}(0+3-1-1\\+3+0-1-1-1-1+0+3-1-1+3+0) = -2 \] 
    • Y aplicando el algoritmo iterativo...
    •  Iteración 1:
      • \[ S = E_3T = \begin{bmatrix}1 & -1 & -1 & 1\end{bmatrix} \left[\begin{array}{rr}0 & -3 & 1 & -1 \\ -3 & 0 & -1 & 1 \\ 1 & -1 & 0 & -3 \\ -1 & 1 & -3 & 0\end{array}\right] = \\ \begin{bmatrix}1 & -1 & -1 & 1\end{bmatrix} \]
      • La salida resulta ser la misma que la entrada así como la energía, por lo que el patrón queda reconocido al 100%. 
  • En el caso del patrón Y sabemos que \[ E = (-1,1,1,-1) \]
  • El proceso se sintetiza entonces aplicando el algoritmmo iterativo:
    • Iteración 1:
      • \[ S = ET = \begin{bmatrix}-1 &1 & 1& -1\end{bmatrix}\left[\begin{array}{rr}0 & -3 & 1 & -1 \\ -3 & 0 & -1 & 1 \\ 1 & -1 & 0 & -3 \\ -1 & 1 & -3 & 0\end{array}\right] = \\ \begin{bmatrix}-1 & 1 & 1 & -1\end{bmatrix}\]
      • Obteniéndose en este caso de nuevo la convergencia en la primera iteración, por lo que queda también reconocido al 100%
--------

Fuentes:
(1) Gonzalo Pajares Martinsanz, Jesús M. de la Cruz García. Ejercicios resueltos de Visión por Computador. Editorial Ra-ma 2007.
(2) A. García Serrano. Inteligencia Artificial. Editorial RC 2012.