7.1.1 Máquinas de Boltzmann Secuenciales

Dada una máquina de Boltzmann en una configuración $k$, la configuración vecina $k_u$ se define como la configuración que se obtiene del estado $k$ al cambiar el estado de una unidad $u$ (de 0 a 1 o viceversa).

$$k_u(v) = \left \{ \begin{array}{ll} k(v) & \mbox{ si } v \neq u \\ 1 - k(v) & \mbox{ si } v = u \end{array} \right .$$

La vecindad se define como todos los estados de configuraciones vecinas a la configuración $k$.

Si $C_u$ denota todas las conecciones que inciden en la unidad $u$ (eliminando $\{u,u\}$), y sea $C'= C - C_u - \{u,u\}$. La diferencia de consenso entre las configuraciones $k$ y $k_u$ se denota como:

$$\triangle C_k(u) = C(k_u) - C(k)$$

Dado que la contribución de las conecciones en $C'$ al consenso es igual para $k$ que para $k_u$, se obtiene:

$$\begin{eqnarray*} \triangle C_k(u) & = & \mbox{ } \left [ k_u(u)\sum_{\{u,v\} \i... ...{\{u,v\} \in C_u} w_{\{u,v\}} k(v) + k^2(u) w_{\{u,u\}} \right ] \end{eqnarray*}$$

que nos da al cambiar $k_u(v)$ por $1-k(v)$ y desarrollar:

$$\triangle C_k(u) = (1 - 2k(u)) \left [ \sum_{\{u,v\} \in C_u} w_{\{u,v\}} k(v) + w_{\{u,u\}} \right ]$$

Básicamente lo que dice es que el efecto del consenso, resultando de cambiar el estado de la unidad $u$, está completamente determinado por los estados de los vecinos y de sus fuerzas de conección.

Por lo mismo una unidad puede ser evaluada localmente, lo cual es muy importante por su potencial paralelización.

Una configuración de máximo local es aquella en donde no se puede aumentar cambiando transiciones de un solo estado.

Ejemplo: Las figuras 7.2 y 7.3 muestra un ejemplo de una máquina de Boltzmann.

Figura 7.2: Ejemplo de una máquina de Boltzmann después de haber llegado a un mínimo.

Figura 7.3: Diferentes estados vecinos para el ejemplo de la máquina de Boltzmann.

Como en el caso de recocido simulado, se puede usar el concepto de cadenas de Markov para describir las transiciones de estado de una máquina de Boltzmann.

En una máquina secuencial consiste de dos pasos:

1. Dada una configuración $k$, seleccionar una unidad $u$ en donde posiblemente se va a cambiar su estado y por lo tanto generar una configuración vecina $k_u$.
2. Evaluar si la configuración $k_u$ se acepta o no.

También se introduce un parámetro de control $c$, que determina la probabilidad de aceptación de una transición.

La probabilidad de transición $P_{kl}(c)$ de la configuración $k$ a la $l$ se define como:

$$P_{kl}(c) = {\bf P}_c\{X(m) = l \mid X(m - 1) = k\}$$

$$P_{kl}(c) = \left \{ \begin{array}{ll} G(u) A_k(u,c) & \mbox{... ... si } l = k \\ 0 & \mbox{ de otra forma} \end{array} \right .$$

donde $G(u)$ denota la probabilidad de generar una transición de estado de la unidad $u$, $A_k(u,c)$ denota la probabilidad de aceptación de la transición, y $c$ denota el parámetro de control.

La probabilidad de generación se escoge normalmente de forma uniforme sobre las posibles unidades e independiente de la configuración $k$ o el parámetro de control $c$.

La probabilidad de aceptación se escoge como:

$$A_k(u,c) = \frac{1}{1 + exp(\frac{- \triangle C_k(u)}{c})}$$

Esto difiere un poco de la probabilidad de aceptación del algoritmo de recocido simulado, pero en realidad muy poco. Ambas probabilidades dan la misma distribución estacionaria y tienen las mismas propiedades de convergencia.

La figure 7.4 muestra esta función para varios valores de $c$.

Figura 7.4: Probabilidad de aceptación para diferentes valores de $c$.

Se puede probar que las máquinas de Boltzmann convergen asintóticamente al conjunto de configuraciones globales óptimas basandose en la existencia de una distribución estacionaria.

Como en recocido simulado, se tiene que hacer una aproximación en tiempo finito al especificar los parámetros que determinan el esquema de enfriamiento.

El esquema es básicamente el mismo que se sigue para el recocido simulado.

Pesos positivos (negativos) en las auto-conecciones indican una tendencia a estar las unidades prendidas (apagadas) y entre las conecciones con otras unidades indican que deben de estar las dos unidades conectadas prendidas.