7.2 Redes de Hopfield

Las redes de Hopfield son probablemente las mejor entendidas de redes recurrentes. Tienen conecciones bidireccionales con pesos simétricos (i.e., $W_{i,j} = W_{j,i}$). Todas las unidades son tanto unidades de entrada como de salida. La función de activación es la función signo, y los valores de activación pueden ser sólo $\pm 1$.

Una red de Hopfield funciona como una memoria asociativa. Despues de entrenarse con un conjunto de ejemplos, un nuevo estímulo causa la red a ``asentarse'' en un patrón de activación correspondiente al ejemplo de entrenamiento que se parece más al nuevo estímulo.

Esto es, se alimenta un patrón de entrada y se observa su salida. La salida se vuelve a alimentar a la red y se ve la nueva salida. Este proceso continua hasta que no hay cambios en la salida.

Uno de los resultados teóricos interesantes es que una red de Hopfield puede almacenar en forma confiable hasta: $0.138N$ ejemplos de entrenamiento (donde $N$ es el número de unidades de la red).

Cada neurona tiene un estado interno $u_i$ y uno externo $v_i$. Los valores internos son continuos y los externos binarios. La actualización y relación entre estos valores es:

$$u_i(t+1) = \sum_{j=1}^n W_{i,j} v_j(t) + I_i$$

$$v_i(t+1) = f(u_i) = \left \{ \begin{array}{ll} 1 & \mbox{si } u_i > 0 \\ 0 & \mbox{si } u_i \leq 0 \end{array}\right .$$

donde $I_i$ es una constante externa de entrada a la neurona $i$ y $f()$ es la función de transferencia entre los estados internos y externos.

Las neuronas se actualizan es forma aleatoria.

La siguiente función de energía es la que se minimiza, esto es, el mínimo local de la función de energía corresponde con la energía del patrón almacenado.

$$E_d = - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n W_{i,j} v_i v_j - \sum_{i=1}^n I_i v_i$$

Las funciones de actualización hacen un gradiente decendiente en la función de energía.

Tambén existe una versión continua de redes de Hopfield..

Para aplicarla a un problema de optimización combinatoria, se tienen que seleccionar pesos y entradas externas que representen en forma adecuada la función a minimizar.

En el caso de TSP, se puede hacer la siguiente formulación:

$$X_{i,j} = \left \{ \begin{array}{ll} 1 & \mbox{si la ciudad ... ...ici\'{o}n } j \\ 0 & \mbox{de otra forma} \end{array}\right .$$

La función objetivo y las restricciones las podemos expresar como:

$$\mbox{minimizar } \sum_{i=1}^N \sum_{k=1,k \neq i}^N \sum_{j=1}^N d_{ik} X_{ij} (X_{j,j+1} + X_{k,j-i})$$

$$\mbox{sujeto a:} \sum_{i-1}^N X_{ij} = 1 \forall j$$

$$\sum_{i-1}^N X_{ij} = 1 \forall j$$

$$\sum_{j=1}^N X_{ij} = 1 \forall i$$

$$X_{ij} \in \{0,1\} \forall i,j$$

Para aplicarlo, las restricciones del problema se añaden a la función objetivo. Una posible formulación para $N$ ciudades es:

$$\begin{array}{ll} E = & \frac{A}{2} \sum_{j=1}^N \sum_{i=1}^... ...\sum_{j=1}^N d_{ik} X_{ij} (X_{k,j+1} + X_{k,j-1}) \end{array}$$

Los primeros dos términos dicen que no puede existir más de un ``1'' por columna y por renglón respectivamente, el tercer término aseguro que existan $N$ elementos ``prendidos'' en la matríz de solución y el último término minimiza la longitud del circuito.

En la formulación original de Hopfield y Tank (85) usaron los siguientes valores: $A=B=D=500$ y $C=200$.

Para ponerlo en términos de la función de energía de Hopfield, introducimos la función delta de Kronecker:

$$\delta_{ab} = \left \{ \begin{array}{ll} 1 & \mbox{si } a = b \\ 0 & \mbox{si } a \neq b \end{array}\right .$$

y expresamos la función de energía como:

$$\begin{array}{lll} E = & - \frac{1}{2} \sum_{i=1}^N \sum_{j=... ...{i=1}^N \sum_{j=1}^N [C N] X_{ij} + \frac{C N^2}{2} \end{array}$$

Lo que nos deja (ignorando la constante):

$$W_{ijkl} = -A \delta_{ik} (1 - \delta_{jl}) - B \delta_{jl} ... ...lta_{ik}) - C - D \delta_{ik}(\delta_{l,j+1} + \delta_{l,j-1})$$

$$I_{ij} = CN$$

Una vez hecha la formulación, se usan valores aleatorios para los estados iniciales y se actualizan los valores internos y externos de acuerdo a las ecuaciones de actualización de $u_i(t+1)$ y $v_i(t+1)$ descritas anteriormente, seleccionando la neurona a actualizar de forma aleatoria.

Cláramente es difícil expresar problemas de optimización e incorporar las restricciones del problema, además que al seguir un gradiente decendiente es fácil de caer en mínimos locales.