Download La Máquina de Boltzmann

Instituto Tecnológico Autónomo de México
“Máquina de Boltzmann
Simulated Annealing”
Redes Neuronales
Dr. Ángel Kuri
Renato Callejo Castilla 51373
José Alberto Cisneros 51394
Federico Fricke
.
Ricardo Falcón
51681
Ignacio Aldasoro
55917
Luis Alfredo Martínez 51577
Teoría de la Información.
En 1948 Claude Shannon publicó un artículo histórico donde propone una teoría
para el estudio de la información que después será adoptada y utilizada por las personas
dedicadas al estudio de las ciencias de la computación.
En su artículo, Shannon definió una función que nos dice que tanta información
nos aporta un suceso estocástico con probabilidad de ocurrencia conocida. Dicha función
está descrita en la siguiente expresión:
1
,donde P(S) es la probabilidad de que el suceso S ocurra.
I ( S )  log b
P( S )
Esta función I está definida para una b (base del logaritmo) arbitraria. Sin embargo, hay
bases que se utilizan con mayor frecuencia. De hecho, si tenemos b=2 decimos que las
unidades de dicha función son bits. Para b=e (el número de Euler), las unidades se llaman
nats. De todas formas, podemos observar que I(S) es inversamente proporcional a la
probabilidad de que S suceda. Esto se puede interpretar como que un suceso poco
probable suceda nos da más información que cuando sucede un acontecimiento muy
probable. Notemos que un suceso que tiene probabilidad uno (ocurre casi seguramente)
no nos aporta ninguna información al ocurrir.
Ahora sea S una sucesión de acontecimientos {S1,S2,...,Sn} cada uno con
probabilidad {P(S1),P(S2),...,P(Sn)}. Definimos I(S) como una variable aleatoria discreta
y su esperanza E[I(S)] representa la “información promedio” que aporta la observación
de S. Resulta que dicha información esta dada por la expresión:
n
n
i 1
i 1
 I    P( S i ) I ( S i )   P( S i ) log P( S i )
Esta función se define como la entropía de S en analogía con el concepto físico que mide
la cantidad de desorden de un sistema termodinámico (a mayor entropía, mayor desorden
en el sistema.).
También se define la ganancia de información (o divergencia asimétrica) de un
sistema Sa con respecto a otro sistema Sb con la ecuación:
n
P( S ia )
G   P( S ia ) log(
)
P( S ib )
i 1
Notemos que al expandir el logaritmo obtener la siguiente interpretación.
n
n
i 1
i 1
G   P( S ia ) log( P( S ia ))   P( S ia ) log( P( S ib ))
La función G nos da una medida de Sa a partir de la fuente de información Sb. Si tenemos
dos fuentes de información muy “parecidas” G debe se pequeña. En el algoritmo de
aprendizaje de Boltzmann se minimiza un múltiplo de dicha función G.
Conceptos de Mecánica Estadística
La mecánica estadística es la rama de la física que estudia sistemas con gran
número de partículas tales no podemos conocer las caracterísicas de dichos sistemas
estudiando cada partícula de una manera individual. En general, estas características las
podemos conocer estudiando una colección finita de sistemas idénticos. A esta colección
se le llama un ensamble y está definido por el promedio de los sistemas que lo
constituyen, así como por las variaciones estadísticas sobre el promedio.
Así, podemos definir la energía promedio del sistema como sigue:
 E   r E r Pr donde, Pr expresa la probabilidad de tener algún estado con energía Er.
Dada una temperatura T, se puede asegurar experimentalmente, que un ensamble
con estas características, alcanza su equilibrio térmico (la energía no cambia
significativamente), sólo cuando la distribución de las probabilidades de estar en estados
con energía Er es:
E
1
exp(  r )
Z
k BT
donde T es la temperatura en grados Kelvin; kB es la constante de Bolzmann
(kB=1.39*10-23 J/K) y Z es la función de partición, que corresponde al factor de
normalización de la distribución. Z está dada por:
E
Z   exp(  r )
k BT
r
En esta distribución los estados con menor energía tienen una mayor probabilidad
de ocurrir y al disminuir la temperatura T, la probabilidad se concentra en los estados de
menor energía.
La entropía del sistema se define esencialmente de la misma manera que en la
teoría de información.
Pr 
Proceso de recocido
El proceso de “annealing” (recocido-templado) consiste en recorrer isotermas del
sistema para alcanzar un mínimo global en la energía del sistema para evitar terminar en
un mínimo local en el proceso de descenso energético. Empezando con temperaturas
elevadas y disminuyéndolas hasta alcanzar el equilibrio térmico se puede asegurar que, a
cierto nivel de temperatura, la variación de los mínimos es despreciable. Una idea
intuitiva de esto está en la limitación probabilística de estar en estados de energía
mínima, dado por la mecánica estadística, al disminuir la temperatura.
La simulación de este proceso en una red neuronal consistirá en encontrar
mínimos a la energía de un estado estocástico de la red, que definiremos más adelante,
para una sucesión decreciente de parámetros T.
La Máquina de Boltzmann
La máquina de Boltzmann es útil para el reconocimiento de patrones, intentando
recuperar información no disponible de un estado (es decir completando las partes que no
conocemos)
Las redes de Boltzmann consisten en neuronas conectadas entre sí que pueden
estar conectadas bidireccionalmente y que tienen salidas binarias. Las neuronas se
distinguen en dos grupos: las visibles y las no visibles. Las primeras constituyen la
interfaz de la red y las segundas son sólo para un mejor desempeño de la red. Hay dos
arquitecturas principales para las máquinas de Boltzmann: Completación de Boltzmann y
la red de Boltzmann de entrada-salida.
La diferencia está en la capa visible, pues en las de completación sólo hay un tipo
y están conectadas entre ellas de forma bidireccional (todas las neuronas con todas,
inclusive las no visibles); en la red de entrada-salida las visibles se dividen en las
neuronas de entrada y en las de salida, siendo las de entrada únicamente conectadas
unidireccionalmente con la capa no visible y las neuronas de salida. Las de salida se
conectan con todas las que no son de entrada de forma bidireccional.
La característica principal de las redes de Boltzmann es que la función de salida
es estocástica con probabilidad:
1
Pk 
net k
1  exp( 
) ,
T
donde netk es la diferencia de energía en el sistema cuando x k=0 y xk=1(donde xk
es la salida de la k-ésima unidad) y está dada por la siguiente expresión:
n
net k   wkj x j
j 1
J k
El parámetro T representa la temperatura del sistema.
Para simular el proceso del annealing usamos el siguiente algoritmo.
Sea x’ el vector de entrada con componentes desconocidos.
1. Asignar los valores conocidos del vector de entrada x’ a las neuronas
visibles.
2. Imputar todas los valores desconocidos y de las neuronas no visibles con
valores aleatorios en el conjunto {0,1}.
3. Seleccionar una unidad xk aleatoriamente y calcular su valor de entrada a
la red (netk)
4. Sin importar el valor actual de la unidad seleccionada, asignar el valor
xk=1 con probabilidad Pk (definida anteriormente). Esta elección
estocástica se puede implementar con una comparación entre Pk y un valor
z seleccionado al azar de la distribución uniforme. Con z entre 0 y 1 y
menor o igual que Pk.
5. Repetir los pasos 3 y 4 hasta que todas la unidades tengan una
probabilidad de ser seleccionadas para una actualización. Este número de
actualización de unidades se llama ciclo de procesamiento. El realizar un
ciclo completo no garantiza que todas la unidades hayan sido actualizadas.
6. Repetir el paso 5 hasta llegar al equilibio térmico.*
7. Bajar la temperatura T y repetir pasos 3 a 7.
La convergencia al estado de mínima energía se asegura por el teorema de
German y German que asegura que si las temperaturas del k-ésimo paso del algoritmo
T0
está acotada inferiormente por
donde T0 es una constante suficientemente
log( 1  k )
grande se alcanzará un estado de energía con diferencia ε al estado de mínima energía.
El algoritmo se detiene cuando T se ha reducido hasta un valor pequeño. Cuando
esto sucede la red se ha estabilizado y el resultado final será las salidas de las neuronas
visibles. Esperamos que el resultado final sea un vector x que tenga todos sus
componentes conocidos.
Aprendizaje en las máquinas de Boltzmann.
El aprendizaje en la máquina de Boltzmann se fundamenta en el annealing
simulado y de ahí su origen estocástico. Utiliza además, el método de descenso de
gradiente sobre la función de divergencia asimétrica definida anteriormente.
Dado que las salidas de las neuronas son de carácter probabilístico, el aprendizaje
de Boltzmann intentará distribuir estas salidas de acuerdo a la muestra de los vectores
utilizados en el proceso de aprendizaje. El problema es, ahora, determinar la distribución
de los vectores de entrenamiento. Como en la mayoría de los casos no tenemos más
información para elegir esta distribución elegiremos la uniforme.
Distingamos dos modos de operar de la red: el primero, tendiendo las neuronas
visibles fijas y el segundo, con dichas neuronas libres. En ambos casos el objetivo es que
después de realizar el proceso de annealing se espere un estado de energía mínimo.
Recordando nuestra fórmula de divergencia asimétrica entre dos fuentes de
información:
n
P( S ia )
G   P( S ia ) log(
),
P( S ib )
i 1
modelaremos la fuente ‘b’ como los resultados frecuentistas de la red de Boltzmann en
un estado libre y a la fuente ‘a’ como la distribución dada por la misma red, ahora fijando
las muestras. Asi para minimizar G (que mide la “distancia” relativa entre las fuentes)
buscaremos adecuar los dos modelos trabajando sobre los dos pesos de la red.
G
Para poder trabajar con el método del gradiente busquemos primero
.
wij
Definamos, ahora, como{Vm} al conjunto de vectores de entrenamiento (relacionados
solamente con las neuronas visibles) y {Hn} al conjunto de vectores que representan los
posibles estados de las neuronas escondidas. Definimos P+(Vm) como la probabilidad de
que la máquina tenga sus neuronas visibles en el estado Vm dado que hay alguna muestra
asignada y fija en las neuronas visibles y P-(Vm) como la probabilidad de que las
neuronas visibles tengan el estado Vm con las neuronas visibles libres.
Reexpresando G en términos de nuestro problema, obtenemos:
P  (V )
G   P  (Vm ) ln(  m ) y a partir de su derivada, obtenemos
P (Vm )
m
P  (V ) P  (Vm )
G
   m
, Pues P+(Vm) es independiente de wij ya que las neuronas
wij
wij
m P (Vm )
de entrada están fijas. Veamos que P  (Vm )   P  (Vm  H n ) ; y como el estado
n
Vm  H n se alcanza en el equilibrio térmico del annealing la probabilidad de estar en
este estado se distribuye como Boltzmann bajo su energía , es decir,
E
1
P  (Vm  H n )  exp(  mn ) , donde:
Z
T
1
con xmni la salida de la neurona i en el estado Vm  H n ; es la
Emn    wij ximn x mn
j
2 i j
j i
energía asociada a tal estado.
E
Z   exp(  mn ) es la función de partición en la distribución de Boltzmann.
T
m,n
E
E
exp(  mn )
exp(  mn )
P  (Vm )

E
1
Z
mn
T
T
 

2
wij
T n
Z
wij
wij
Z
n
E mn
  ximn x mn
j
wij
E
Z
1
  exp(  mn ) ximn x mn
j
wij T n
T
Considerando que:
P

(Vm )  1
m
y que
P  ( H n Vm )  P  ( H n Vm )
wij   ( pij  pij )
Concluimos que
pij   P  (Vm  H n )ximn x mn
j
m,n
pij   P  (Vm  H n )ximn x mn
j
m,n
Las cantidades p+ij y p-ij representan la probabilidades de coocurrencia de que las
neuronas i y j estén activas (xi=1 y xj=1) al mismo tiempo. En el algoritmo estimaremos
estas cantidades y así modificar los pesos. Ahora podemos dar el algoritmo:
1.- Fijar algún vector de entrenamiento para las neuronas visibles
2.- Realizar el proceso de annealing hasta que se alcance el equilibrio a la temperatura
mínima
3.- Realizar este proceso varias veces y para cada uno de ellos determinar qué pares de
neuronas conectadas están activas simultánemente
4.-Estimar la coocurrencia (clamped) para el vector de entrenamiento
5.- Repetir de 1 a 4 para cada vector de entrenamiento y estimar p+ij.
6.- Liberar las neuronas visibles y realizar el proceso de annealing hasta que se alcance
el equilibrio a la mínima temperatura
7.-Realizar este proceso muchas veces y después de cada una determinar los pares de
neuronas conectadas que están activas simultáneamente
8.-Estimar la coocurrencia con el paso 7
9.- Repetir del 6 al 8 el mismo número de veces que se repitió el paso 5 y estimar p-ij
w   ( pij  pij )
10.- Calcular y aplicar los cambios de pesos ij
wij
11.- Repetir del 1 al 10 hasta que
sea muy pequeño.
Costos computacionales de la Máquina de
Boltzmann
El gran problema de la máquina de Boltzmann es la lentitud de convergencia y
complejidad del algoritmo, pues dentro de él hay 4 ciclos anidados:
-Ajustar los pesos hasta alcanzar un mínimo satisfactorio.
-Cada iteración que estima pij en el modo libre y para el modo fijo.
-Para cada estimación, realizar el proceso de annealing.
-A cada temperatura, buscar equilibrio térmico.
Además, dentro del proceso de annealing, no podemos realizar el decenso de
temperaturas tan brusco como se quiera, pues para que la red se estabilice en un nivel de
energía suficientemente bajo (alguno que otorgue una estabilidad suficiente a la red), las
temperaturas en cada iteración están acotadas inferiormente por el teorema de German y
German.