Màquina de Boltzmann

Una màquina de Boltzmann és un tipus de xarxa neuronal recurrent estocàstica. El nom li fou donat pels investigadors Geoffrey Hinton i Terry Sejnowski. Les màquines de Boltzmann poden considerar-se com la contrapartida estocàstica i generativa de les xarxes de Hopfield. Van ser dels primers tipus de xarxes neuronals capaços d'aprendre mitjançant representacions internes, són capaços de representar i (amb temps suficient) resoldre complicats problemes combinatoris. No obstant això, a causa d'una sèrie de qüestions que s'aborden més endavant, les màquines de Boltzmann sense restriccions de connectivitat no han demostrat ser útils per resoldre els problemes que es donen en la pràctica en l'aprenentatge o inferència de les màquines. Tot i així resulten interessants en la teoria a causa de la localització ia la natura hebbiana del seu algorisme d'entrenament, així com per la seva paral·lelisme i per la semblança de la seva dinàmica a fenòmens físics senzills. Si es limita la connectivitat, l'aprenentatge pot ser prou eficaç com per ser útil en la resolució de problemes pràctics.

En mecànica estadística es denominen distribucions de Boltzmann i són utilitzes en funcions de mostreig.

Estructura

Les màquines de Boltzmann, igual que les xarxes de Hopfield, Tenen unitats amb una "energia" definida per a la xarxa. També disposa d'unitats binàries, però a diferència de les xarxes de Hopfield, les unitats d'una màquina de Boltzmann són estocàstiques. L'energia global, ${\displaystyle E}$, en una màquina de Boltzmann és idèntica en forma a la d'una xarxa de Hopfield:

${\displaystyle E=-\sum _{i<j}w_{ij}\,s_{i}\,s_{j}+\sum _{i}\theta _{i}\,s_{i}}$

On:

• ${\displaystyle W_{ij}}$ és la força de connexió entre la unitat ${\displaystyle j}$ i la unitat ${\displaystyle i}$.
• ${\displaystyle S_{i}}$ és l'estat, ${\displaystyle s_{i}\in \{0,1\}}$, de la unitat ${\displaystyle i}$.
• ${\displaystyle \Theta _{i}}$ és el llindar de la unitat ${\displaystyle i}$.

Les connexions d'una màquina de Boltzmann tenen dues limitacions:

• Cap unitat es connecta a si mateixa.
• ${\displaystyle W_{ij}=w_{ji}\qquad \forall i,j}$. (Totes les connexions són simètriques.)

Probabilitat d'estat d'una unitat

L'increment d'energia global que resulta d'una sola unitat ${\displaystyle i}$ sent 0 (off) davant 1 (on), expressada com ${\displaystyle \Delta E_{i}}$, ve donada per l'expressió:

${\displaystyle \Delta E_{i}=\sum _{j}w_{ij}\,s_{j}-\theta _{i}}$

Això es pot expressar com la diferència d'energia entre dos estats:

${\displaystyle \Delta E_{i}=E_{\text{i = off}}-E_{\text{i = on}}}$

A continuació substituïm l'energia per a cada estat amb la seva probabilitat relativa d'acord amb el factor de Boltzmann (la propietat de la distribució de Boltzmann en la qual l'energia d'un estat és proporcional al menys logaritme de probabilitat d'aquest estat):

${\displaystyle \Delta E_{i}=-k_{B}\,T\,ln(p_{\text{i = off}})--k_{B}\,T\,ln(p_{\text{i = on}})}$

On ${\displaystyle k_{B}}$ és la constant de Boltzmann i s'engloba dins de la noció artificial de temperatura ${\displaystyle T}$. A continuació es reordenen els termes considerant que la probabilitat que una unitat estigui en on i en off és un:

${\displaystyle {\frac {\Delta E_{i}}{T}}=ln(p_{\text{i = on}})-ln(p_{\text{i = off}})}$

${\displaystyle {\frac {\Delta E_{i}}{T}}=ln(p_{\text{i = on}})-ln(1-p_{\text{i = on}})}$

${\displaystyle {\frac {\Delta E_{i}}{T}}=ln({\frac {p_{\text{i = on}}}{1-p_{\text{i = on}}}})}$

${\displaystyle -{\frac {\Delta E_{i}}{T}}=ln({\frac {1-p_{\text{i = on}}}{p_{\text{i = on}}}})}$

${\displaystyle -{\frac {\Delta E_{i}}{T}}=ln({\frac {1}{p_{\text{i = on}}}}-1)}$

${\displaystyle \exp(-{\frac {\Delta E_{i}}{T}})={\frac {1}{p_{\text{i = on}}}}-1}$

Finalment podem resoldre per ${\displaystyle p_{\text{i = on}}}$, la probabilitat que la unitat ${\displaystyle i}$ estigui en on .

${\displaystyle P_{\text{i = on}}={\frac {1}{1+\exp(-{\frac {\delta E_{i}}{T}})}}}$

On l'escalar ${\displaystyle T}$ es refereix a com està la temperatura en el sistema. Aquesta relació és la font de la funció logística que es troba en les expressions de probabilitat de les diferents variants de la màquina de Boltzmann.

Estat d'equilibri

La xarxa s'executa repetidament escollint una unitat i establint el seu estat d'acord amb la fórmula anterior. Després d'executar durant prou temps a una certa temperatura, la probabilitat de l'estat global de la xarxa va a dependre només de l'estat global d'energia, d'acord amb una distribució de Boltzmann. Això significa que els logaritmes de les probabilitats dels estats globals es tornaran lineals en les seves energies. Aquesta relació es compleix quan la màquina està "a equilibri termodinàmic", el que significa que la distribució de probabilitat dels estats globals ha convergit. Si comencem a fer funcionar la xarxa a alta temperatura, i descendeix gradualment fins a arribar a un equilibri termodinàmic a una baixi temperatura, estarem garantint la convergència a una distribució on el nivell d'energia fluctuï voltant del mínim global. Aquest procés s'anomena Simulated annealing (SA) o temperat simulat.

Per entrenar la xarxa de manera que la possibilitat que convergeixi en un estat global s'ajusti a una distribució externa, caldrà establir els pesos perquè els estats globals amb major probabilitat tinguin l'energia més baixa. Per això s'usa el següent mètode d'entrenament.

Entrenament

Les unitats de la màquina de Boltzmann es divideixen en unitats "visibles", V, i unitats "ocultes", H. Les primeres són les que rebran informació del "entorn", per exemple la sèrie d'entrenament podria ser un conjunt de vectors binaris aplicat sobre les unitats V. La distribució en el conjunt d'entrenament es denota ${\displaystyle P^{+}(V)}$.

A les màquines de Boltzmann, com ja s'ha dit, la distribució dels estats globals convergeixen fins a un equilibri termodinàmic. Després que marginalitzar per sobre de les unitats visibles ${\displaystyle V}$, la convergència de la distribució es pot denotar com ${\displaystyle P^{-}(V)}$.

El nostre objectiu és apropar la distribució "real" ${\displaystyle P^{+}(V)}$ a l'expressió ${\displaystyle P^{-}(V)}$, la qual és produïda eventualment per la màquina. Per mesurar la similitud entre les dues distribucions es fa servir la divergència de Kullback-llegible, ${\displaystyle G}$:

${\displaystyle G=\sum _{v}{P^{+}(v)\ln \left({\frac {P^{+}(v)}{P^{-}(v)}}\right)}}$

On el sumatori és superior a tots els possibles estats de ${\displaystyle V}$. ${\displaystyle G}$ varia en funció dels pesos, ja que aquests determinen l'energia d'un estat, i l'energia al seu torn determina ${\displaystyle P^{-}(v)}$, segons la distribució de Boltzmann. Per tant, podem utilitzar un algorisme de descens de gradient sobre ${\displaystyle G}$ per a un pes determinat, ${\displaystyle w_{ij}}$, que es canviarà restant la derivada parcial de ${\displaystyle G}$ respecte al pes.

L'entrenament d'una màquina de Boltzmann consta de dues fases, que es van canviant iterativament entre elles. Una és la fase "positiva" en què els estats de les unitats visibles es subjecten a un vector d'estat binari particular, mostra del conjunt d'entrenament (d'acord amb ${\displaystyle P^{+}}$). L'altra és la fase "negativa", en què a la xarxa se li permet executar lliurement, és a dir, els estats de les unitats no estan determinats per dades externes. Sorprenentment, el gradient respecte a un pes determinat, ${\displaystyle w_{ij}}$, està donat per una equació molt senzilla (demostrada per Ackley et al.):

${\displaystyle {\frac {\partial {G}}{\partial {w_{ij}}}}=-{\frac {1}{R}}[p_{ij}^{+}-p_{ij}^{-}]}$

On:

• ${\displaystyle P_{ij}^{+}}$ és la probabilitat que tant les unitats i com j estiguin activades quan la màquina estigui en equilibri durant la fase positiva.

• ${\displaystyle P_{ij}^{-}}$ és la probabilitat que tant les unitats i com j estiguin activades quan la màquina estigui en equilibri durant la fase negativa.

• ${\displaystyle R}$ denota la taxa d'aprenentatge.

Aquest resultat es dedueix del fet que en l'equilibri termodinàmic la probabilitat ${\displaystyle P^{-}(s)}$ de qualsevol estat global ${\displaystyle s}$ quan la xarxa està funcionant lliurement ve donada per la distribució de Boltzmann (d'aquí el nom de "màquina de Boltzmann").

Sorprenentment, aquesta regla d'aprenentatge és bastant plausible des del punt de vista biològic pel fet que l'única informació necessària per canviar els pesos és proporcionada per de manera "local". És a dir, la connexió (o sinapsi utilitzant terminologia biològica) no necessita més informació que la que subministren les dues neurones que connecta. Això és molt més realista biològicament parlant que el que passa amb la informació que necessiten molts altres algorismes d'entrenament de xarxes neuronals, com per exemple el de retropropagación.

En l'entrenament d'una màquina de Boltzmann no s'utilitza l'algorisme EM, molt utilitzat en Aprenentatge automàtic. Minimitzar la divergència KL, és equivalent a maximitzar el logaritme de la versemblança de les dades. Per tant, el procediment d'entrenament porta a terme un gradient d'ascens sobre el logaritme de versemblança de les dades observades. Això contrasta amb l'algoritme EM, on la distribució posterior dels nodes ocults ha de ser calculada abans de la maximització de la versemblança duta a terme en el pas M.

En entrenament de biaixos és similar, però fa servir només l'activitat d'un sol node:

${\displaystyle {\frac {\partial {G}}{\partial {\theta _{i}}}}=-{\frac {1}{R}}[p_{i}^{+}-p_{i}^{-}]}$

Problemes en l'aplicació pràctica

Les màquines de Boltzmann presenten un greu problema pràctic, i és que l'aprenentatge sembla deixar de produir correctament quan la màquina s'amplia a una mica més gran que una màquina trivial. Això es deu a una sèrie d'efectes, els més importants dels quals són:

• El temps que la màquina necessita per recopilar les estadístiques d'equilibri creix exponencialment amb la mida de la màquina, i amb la magnitud de la força de les connexions.
• La forces de les connexions són més flexibles quan les unitats connectades tenen probabilitats d'activació intermèdies entre zero i un, portant a l'anomenada trampa de variància. L'efecte net és que el soroll fa que les forces de les connexions es tornin aleatòries fins que les activitats es saturen.

Màquina de Boltzmann restringida

Tot i que l'aprenentatge és en general poc pràctic en les màquines de Boltzmann, pot arribar a ser molt eficient en una arquitectura anomenada Màquina de Boltzmann restringida o MBR ( RBM en anglès: Restricted Boltzmann Machine ). Aquesta arquitectura no permet les connexions entre les unitats de les capes ocultes. Després d'entrenar a una MBR les activitats de les seves unitats ocultes poden ser tractades com a dades per a l'entrenament d'una MBR de nivell superior. Aquest mètode d'apilament MBR fa que sigui possible entrenar moltes capes d'unitats ocultes de manera eficient i que cada nova capa sigui afegida per millorar el model generatiu principal.

Història

La màquina de Boltzmann és una versió del mètode de Monte Carlo de les xarxes de Hopfield.

Es creu que la idea d'utilitzar models d'Ising per a la inferència va ser descrita per primera vegada per Geoffrey E. Hinton i Terrence J. Sejnowski^[1][2]

La mateixa idea d'aplicar el model d'Ising amb el mostreig de Gibbs temperat també és present en el projecte de Douglas Hofstadter Copycat.^[3][4]

Idees similars (canviant el signe de la funció d'energia) també es poden trobar a la "Teoria de l'Harmonia" de Paul Smolensky.

L'analogia explícita extreta de la mecànica estadística en la formulació de la màquina de Boltzmann ha portat a la utilització d'una terminologia presa de la física (per exemple, "energia" en lloc de "harmonia"), que s'ha convertit en estàndard en el camp. L'adopció generalitzada d'aquesta terminologia pot haver estat encoratjada pel fet que el seu ús ha portat a importar una varietat de conceptes i mètodes presos de la mecànica estadística. Tanmateix, no hi ha cap raó per pensar que les diverses propostes per a l'ús de temperat simulat per a la inferència descrites anteriorment no siguin independents. (Helmholtz, va fer una analogia similar en l'inici de la psicofísica.)

Els models d'Ising es consideren en l'actualitat com un cas especial dels camps aleatoris de Markov, que troben una àmplia aplicació en diversos camps, com els de la lingüística, robòtica, visió artificial i intel·ligència artificial.

Bibliografia

• Fort, J. C.; Gerschenfeld, A. «El naixement d'un ordinador neuronal: La màquina de Boltzmann». Internacional Científic, 8, 1988, p. 614.
• Ackley, D. H.; Hinton, G. E., Sejnowski, T. J. «Hinton/absps/cogscibm.pdf A Learning Algorithm for Boltzmann Machines» (en anglès). Cognitive Science, 9, 1985, p. 147-169.
• Hinton, G. E.; Sejnowski, T. J. «hinton/absps/pdp7.pdf Learning and Relearning in Boltzmann Machines» (en anglès). Parallel Distributed Processing: Explorations in the micro of Cognition. Volume 1: Foundations. MIT Press, 1986, p. 282-317.
• Hinton, G. E. «Hinton/absps/nccd.pdf Training Products of Experts by minimitzant Contrastive Divergence» (en anglès). Neural Computation, 14, 2002, p. 1771-1800.
• Hinton, G. E.; Osindero, S.; Teh I. «Hinton/absps/fastnc.pdf A fast learning algorithm for deep Belief nets» (en anglès). Neural Computation, 18, 2006, p. 1527-1554.

Referències

1. Geoffrey E. Hinton & Terrence J. Sejnowski, Analyzing Cooperative Computation. In Proceedings of the 5th Annual Congress of the Cognitive Science Society, Rochester, NY, May 1983.
2. Geoffrey E. Hinton & Terrence J. Sejnowski, Optimal Perceptual Inference. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR), pages 448-453, IEEE Computer Society, Washington DC, June 1983.
3. Hofstadter, Douglas R., The Copycat Project: An Experiment in Nondeterminism and Creative analogia. MIT Artificial Intelligence Laboratory Memo No 755, January 1984.
4. Hofstadter, Douglas R., A Non-deterministic Approach to Analogy, Involving the Ising Model of Ferromagnetism. In E. Caianiello, ed. The Physics of Cognitive Processes. Teaneck, NJ: World Scientific, 1987.

Enllaços externs

• Article a Scholarpedia per Hinton sobre les màquines de Boltzmann (anglès)
• Discurs de Geoffrey Hinton a Google (anglès)