Universitatea Politehnica Bucuresti

Neuroinformatica aplicata

- Modelul Hopfield-

Mihai Preda IISC

1. Introducere

In mare, retelele neuronale se pot imparti in doua tipuri: retele neuronale

feed-back (arhitectura poate fi prezentata sub forma unui graf unidirectional) si

retele neuronale feed-forward (neuronii sunt aranjati in straturi, avand sinapse ce

conecteaza aceste straturi).

O conexiune (sinapsa) dintre o pereche de neuroni intr-o retea feed-back

este caracaterizata de catre o pondere sinaptica. O valoare mai mare a ponderii

sinaptice dintre o pereche de neuroni indica tendinta acestora sa fie activi

simultani. Ponderea sinaptica este determinata de catre regula de invatare

folosita in reteaua neuronala, ce este reprezentata ca o matrice sinaptica. In

cazul in care iesirea fiecarui neuron este conectata la ceilalti neuroni, reteaua

este pe deplin conectata. Daca iesirea unui neuron este conectata la intrarea

aceluiasi neuron, se spune despre acesta ca are o caracteristica de feedback

catre sine. Intr-o retea neuronala pe deplin conectata de tip feed-back, in cazul in

care ponderea sinaptica a neuronului j catre neuronul i (Jij) este egala cu

ponderea sinaptica dintre neuronul t catre neuronul j (Jji) pentru toate perechile

de neuroni, atunci matricea sinaptica este simetrica.

2. Modelul Hopfield

Modelul Hopfield a fost propus de catre John Hopfiled, membru al

California Institute of Technology, la inceputul anilor 80. Publicarea lucrarii sale a

contribuit intr-un mod semnificativ la cercetarile in domeniul retelelor neuronale

artificiale. El a demonstrat ca un ansamblu de unitati simple de procesare pot

avea un potential ridicat de calcul, atunci cand sunt unite intr-o retea.

Dinamica modelului Hopfield este diferita fata de cea a modelului asociativ

liniar prin faptul ca el calculeaza in mod recursiv pana in punctul in care sistemul

devine stabil. In figura de mai jos avem un model de retea Hopfield cu 6 unitati,

in care fiecare nod este conectat cu toate celelalte noduri din retea.

2

Fig 1 – Modelul Hopfield

Spre deosebire de modelul asociativ liniar, care este format din doua

straturi de unitati de procesare, unul fiind stratul de intrare, iar cel de-al doilea

stratul de iesire, modelul Hopfield este format dintr-un singur strat de elemente

de procesare, fiecare unitate fiind conectata cu toate celelalte din retea.

Ponderea conexiunii matricei W pentru acest tip de retea este simetrica, wij = wji,

pentru i, j = 1,2,…,m. Fiecare unitate are o intrare externa suplimentara, Ii.

Aceasta intrare suplimentara duce la o modificare in calculul intrarii unitatilor:

intrareaj = , unde j = 1,2… , m.

De asemenea, spre deosebire de modelul asociativ liniar, unitatile din

modelul Hopfield functioneaza atat ca unitati de intrare, cat si de iesire. O

pereche asociata este stocata prin calculul matricei ponderate:

wk = xkTyk, unde yk = xk.

pentru a stoca p perechi diferite. Deoarece modelul Hopfield este un model de

memorie autoasociativ, esantioanele sunt stocate in memorie.

Dupa codare, reteaua poate fi folosita pentru decodare. Decodarea in

modelul Hopfield este realizata printr-o cautare colectiva si recursiva pentru un

esantion stocat, dat fiind un stimul initial. Dat fiind stimulul initial X, decodarea

este realizata prin calculul intrarii nete a unitatii si determinarea iesirii acestor

unitati prin folosirea functiei de iesire pentru producerea esantionului X’.

Esantionul X’ este trimis inapoi catre unitati, pentru a se produce esantionul X’’.

3

Esantionul X’’ este din nou trimis catre unitati pentru a fi produs esantionul X’’’.

Procesul este repetat pana cand reteaua se stabilizeaza pe un esantion stocat in

care calculele viitoare nu schimba iesirea unitatilor.

In cazul in care esantionul de intrare X este incomplet sau contine anumite

distorsiuni, esantionul stocat pentru care reteaua se stabilizeaza este

asemanator lui X. Aceasta trasatura este folosita in diverse aplicatii de procesare

de imagini.

In timpul decodarii, sunt o serie de modalitati ce pot fi folosite pentru

actualizarea iesirii unitatilor. Modalitatile de actualizare pot fi sincrone (paralele),

asincrone (secventiale) sau o combinatie intre cele doua (hibride).

Folosind modalitatea de actualizare sincrona, iesirea unitatilor este

actualizata ca un grup, inaintea trimiterii rezultatelor catre retea. In cazul

actualizarii asincrone, iesirile unitatilor sunt actualizate in aceeasi ordine

(aleatoare sau secventiala) si iesirea este trimisa catre retea dupa fiecare

actualizare in parte. Prin folosirea metodei hibride, subgrupuri ale unitatilor sunt

actualizate sincron in timp ce unitatile din fiecare subgrup sunt actualizate

asincron. Alegerea tipului de actualizare afecteaza in mod direct convergenta

retelei.

In cazul modelului lui Hopfield discret, unitatile folosesc o functie de iesire

bipolara usor modificata, in care starile unitatilor, iesirile acestora nu se schimba

in cazul in care starea actuala este egala cu o valoare de prag:

unde i=1,2,….,m si t reprezinta timpul.

O proprietate caracteristica retelelor de tip recurent este faptul ca starea

lor poate fi descrisa de catre functia de energie. Aceasta este folosita pentru a

demonstra stabilitatea retelelor. In cazul modelului Hopfield discret avand wii=0 si

wij=wji, folosind modul de actualizare asincron, functia de energie E este definita

ca:

4

unde minimul energiei corespunde cu energia esantioanelor stocate. S-a

demonstrat faptul ca energia modelului Hopfield discret scade sau ramane

neschimbata dupa fiecare actualizare a unei unitati. Astfel, reteaua va converge

catre un minim local ce corespunde unui esantion stocat. Esantionul respectiv

catre care reteaua converge depinde de esantionul de intrare si de matricea

conexiunilor. Energia modelului Hopfield discret este marginita de catre:

pentru toate xk, k=1,2,….,p.

Modelul Hopfield continuu reprezinta generalizarea unui caz discret.

Unitatile folosesc o functie continua de iesire, cum ar fi de exemplu functia

hiperbolica tangenta. Fiecare unitate are asociata o capacitate C i si o rezistenta

ri. Ecuatia de stare a fiecarei unitati este:

unde:

Ca si in cazul anterior, al modelului discret, exista o functie de energie ce

caracterizeaza modelul Hopfield continuu. Aceasta este data de:

unde f este functia de iesire ale unitatilor.

Se poate demonstra ca de/dt =0 atunci cand w ij=wji. Astfel, energia

modelului continuu scade sau ramane aceeasi. Energia minima a modelului

continuu exista si in modelul discret folosind calculul analog.

Reteaua Hopfield este o retea neuronala conectata, de tip feed-back,

formata din N neuroni. Aceasta este definita in mod unic de perechea (J, Ө),

unde J este o matrice simetrica N x N si 0 este vectorul de prag N x 1, avand

5

componentele Өi, care este pragul pentru neuronul t. Fiecare alegere diferita a lui

J si O duce la o retea Hopfield diferita, cu N neuroni.

Nivelul activitatii unui neuron (δi) este numita starea neuronului. Neuronii

din modelul Hopfield sunt de tip doua stari. Acestia au asignata valoarea 0 pentru

starea inactiva si 1 pentru starea activa. Neuronii cu doua stari ce au asignata o

valoare de +1 pentru starea activa si de -1 pentru starea inactiva, se numeste

neuorni bipolari. Reprezentarile binare (0,1) si bipolare (-1,1) ale neuronilor sunt

echivalente. Starile acestor neuroni sunt descrise ca:

δibipolar = 2δi

binar – 1, vi = 1,2, … , N

Starea tuturor neuronilo (δi pentru orice i) la orice moment de timp t, este

starea retelei Hopfield si este reprezentata de catre un vector de stare ε. Starea

unei retele Hopfield poate fi imaginata ca niste activitati de rutina ale neuronilor si

de aceea se mai numeste si tipar. Starile stabile ale unei retele Hopfield sunt

starile retelei ce nu se schimba in timpul functionarii normale a retelei neuronale.

Procesul de invatare in cadrul retelei Hopfield este procesul in care

anumite starile ale retelei devin stari stabile. Acest lucru este realizat prin

determinarea matricei sinaptice si a vectorului de prag. Sunt doua tipuri de

invatare si anume cel supervizat si cel nesupervizat. In cadrul invatarii

supervizate, reteaua este aprovizionata cu o secventa de exemple. Fiecare

exemplu duce la starea dorita de iesire pentru un vector de intrare dat. In mod

normal, procesul de invatare este continuat pana cand reteaua neuronala

cunoaste toate exemplele. In cadrul invatarii nesupervizate, setul consta in

vectori de stare care vor deveni vectori stabili ai retelei.

Vectorii de stare P, εiμ (μ= 1,2, ….., P; t=1,2,…., N), ce vor deveni stari

stabile ale retelei Hopfield cu N neuroni, poarta denumirea de vectori candidati. N

reprezinta numarul de neuroni, iar P reprezinta numarul de vectori candidati.

Multimea vectorilor care converg catre un vector stabil reprezinta

multimea agreata pentru εμ. Raza unei sfere din jurul fiecarui vector stabil, prin

care fiecare vector din sfera converge catre un vector stabil intr-un singur pas

reprezinta raza direct agreata.

6

Viteza de convergenta reprezinta numarul de pasi prin care o retea trebuie

sa treaca pentru a converge catre un punct final, data fiind starea initiala.

Procesul de invatare prezinta o serie de dificultati. Nu intotdeauna este

posibil sa cream o retea Hopfield, deoarece o parte dintre vectorii candidati nu se

pot transforma in membrii stabili ai retelei.

Regulile de invatare pot fi clasificate in reguli de invatare locala si reguli de

invatare nelocala, in functie de natura informatiei folosite pentru a construi

reteaua Hopfield. Informatia prezenta fizica la nivelul sinapselor este numita

informatie locala. Modificarile ponderilor sinaptice in cadrul invatarii locale depind

doar de activitatea locala, in schimb in cazul invatarii nelocale se tine cont si de

activitatea in sinapsele vecine.

O regula folosita pentru evaluarea starii unuia sau mai multor neuroni in

cazul conditiilor actuale si schimbarea acesteia in caz de nevoie, este numita o

regula de tranzitie, regula de activare sau regula de actualizare. Fiecare neuron

in parte primeste un stimul extern sub forma unei stari initiale si intrari ponderate

de la alti neuroni, starea rezultata fiind evaluata folosind regula de actualizare.

Dupa crearea retelei Hopfield, aceasta detine un vector de stare initiala. In

cazul unei retele cu N neuroni de tip doua stari, vectorul de stare initiala poate fi

oricare dintre cei 2N vectori. Regula de actualizare si modul in care aceasta se

aplica reprezinta dinamica modalitatii de calcul. Aceasta utilizeaza suma starilor

conexiunilor si ponderile conexiunilor pentru determinarea starii urmatoare.

Suma este numita potentialul neuronului. In functie de relatia dintre potentialul si

pragul unui neuron, se determina urmatoarea stare. In reteaua Hopfield, regula

de actualizare este discreta in timp. In timpul fiecarui interval, starea unui

(actualizare asincrona) sau a mai multor (actualizare sincrona) neuroni, este

evaluata. In cazul actualizarii asincrone, neuronul ce trebuie actualizat intr-o

unitate de timp este selectat aleator sau intr-o modalitate deterministica. In cazul

actualizarii sincrone, atunci cand toti neuronii sunt actualizati intr-o unitate de

timp, se realizeaza o procedura in paralel.

3. Aplicatii ale modelului Hopfield

7

Retelele neuronale precum modelul Hopfield au diverse aplicatii. In

general sunt folosite pentru:

- memorii asociative: reteaua are capacitatea de a stoca anumite stari,

esantioane

- optimizare combinationala: in cazul in care problema este modelata

corespunzator, reteaua poate oferi un minim sau o solutie a acesteia

In general, reteaua este folosita pentru a se calcula rezultatul unor date de

intrare ce erau oferite modelului neuronal. Una dintre cele mai utilizate aplicatii

este invatarea de tip Hebbian.

In cazul acestui tip de invatare, ponderea matricei rezulta din invatarea

nesupervizata. Putem considera faptul ca incercam sa stimulam esantioanele din

retea pentru a se recunoaste unul dintre ele, chiar daca la intrare se ofera un

semnal foarte distorsionat de zgomot. Faza de invatare este formata din

invatarea diferitelor esantioane pentru a se seta ponderea marginilor. Pentru

fiecare esantion, putem sintetiza faza de invatare ca:

- in cazul in care doua unitati au aceeasi stare de activare ({1, 1} {-1, -1}),

semnificatia conexiunii creste (wij creste)

- in cazul in care doua unitati au stari opuse de activare ({-1, 1}),

semnificatia conexiunii scade

Folosind aceasta regula, W va stoca esantioane si va lasa reteaua va

converge catre acestea.

Ponderea matricii este modificata in functie de esantionul m pe care dorim

sa-l stocam. Aceste esantioane reprezinta starea stabila la care dorim sa

ajungem. Ponderile sunt modificate, de exemplu:

wij’=wij+єxixj

sunt iterate de mai multe ori pentru fiecare esantion. xi si xj reprezinta starea

unitatilor i si j ce vor fi invatate.

є este o constanta folosita pentru a impiedica conexiunea de a deveni

prea mare sau prea mica (de exemplu ε=1/m). Atunci cand m=1, reteaua

converge catre esantionul dorit.

8

S-a demonstrat faptul ca reteaua Hopfield poate stoca doar aproximativ

0.14 x n esantioane (n reprezinta numarul de unitati din retea).

Reteaua Hopfield poate folosita pentru o problema combinationala. Daca

aceasta poate fi scrisa intr-o forma isomorfica fata de functia de energie, reteaua

este capabila sa gaseasca un minim local al functiei, dar nu se poate garanta ca

solutia este optima.

Problema vanzatorului ambulant este una folosita in optimizarea

combinationala. Fiind data o lista cu orase si distantele dintre ele, scopul este de

a gasi cel mai scurt traseu prin care se viziteaza fiecare oras o singura data.

Drumul trebuie sa treaca prin n orase: S1, S2, …, Sn. Fiecare oras trebuie vizitat o

singura data, iar vanzatorul trebuie sa se intoarca in punctul de plecare, costul

drumului fiind minim. Reteaua poate fi reprezentata ca:

in care randurile sunt orasele, iar coloanele timpul. Prin presupunere, coloana

(n+1) este prima care pastreaza ciclul. De asemenea, un singur 1 trebuie sa

apara pe fiecare linie si coloana, pentru ca vanzatorul sa viziteze o singura data

fiecare oras.

Distanta dintre orasele Si si Sj este dij. Pentru a gasi cea mai scurta cale,

reteaua va minimiza functia urmatoare:

Prima parte a ecuatiei, L, reprezinta lungimea totala a drumului. xi,k=1

inseamna faptul ca orasul Si a fost vizitat la momentul k (in caz contrar xi,k=0),

astfel incat, in cazul in care xi,k=1 si xi,k+1=1 (Si a fost vizitat la momentul k si Sj a

fost vizitat la momentul k+1), distanta va fi adaugata valorii L.

9

A doua parte o reprezinta conditia: o singura vizita in fiecare oras.

va fi minim (=0) daca pentru fiecare i (oras), suma pentru j (timp) este

1, ceea ce inseamna ca fiecare oras a fost vizitat o singura data.

va fi minima daca pentru fiecare moment de timp (k=1…n), vanzatorul va vizita

un singur oras.

μ este un parametru ce nu poate fi setat la valoarea pe care o dorim prin

mai multe incercari, in functie de rezultatele obtinute. Daca μ este mic, conditia

nu se va respecta. In schimb, daca este prea mare, sistemul va fi constrans

serios iar L va fi ascuns, astfel incat minimizarea lui Etsp nu va tine cont de

distanta dintre orase.

Ponderile dintre unitati vor deveni: wik,jk+1 = -dij+tik,jk+1 unde:

1. caz – daca unitatile apartin aceluiasi rand sau coloana; 2. in rest;

iar pragul trebuie setat ca –μ/2.

Reteaua nu va fi capabila sa gaseasca drumul minim, dar solutiile sunt in

continuare aproximate. In cazul in care numarul oraselor este mare (>100), sunt

o serie de drumuri minime, astfel incat nu putem demonstra daca solutia oferita

de sistem este o aproximare buna.

10