Arhitecturi Neurale. Memorii Asociative Bidirectionale

Introducere

Inca de la începutul cercetarilor de inteligenta artificiala s-au conturat în acest domeniu doua directii rivale ce constituie si acum modelele dominante (paradigmele) în Inteligenta Artificiala.

Paradigma logico-simbolica presupune mecanisme de reprezentare simbolica a cunostintelor si utilizarea diferitelor modele logice pentru a deduce noi cunostinte din faptele memorate în baza de cunostinte a sistemului. De exemplu, programele care joaca sah si programele inteligente (numite Sisteme Expert) care rezolva probleme de mare complexitate dintr-un domeniu bine conturat reprezinta realizari notabile în cadrul acestei paradigme.

Paradigma conexionista a introdus un nou concept de calcul – calculul neuronal – si a generat realizari concrete cunoscute sub numele de retele neurale artificiale (pe scurt retele neurale).

In retelele neurale informatia nu mai este memorata în zone bine precizate, ca în cazul calculatoarelor standard, ci este memorata difuz în toata reteaua. Memorarea se face stabilind valori corespunzatoare ale ponderilor conexiunilor sinaptice dintre neuronii retelei.

Un alt element important, care este, probabil, principalul responsabil pentru succesul modelelor conexioniste, este capacitatea retelelor neurale de a învata din exemple. In mod traditional, pentru a rezolva o problema, trebuie sa elaboram un model (matematic, logic, lingvistic etc) al acesteia. Apoi, pornind de la acest model, trebuie sa indicam o succesiune de operatii reprezentând algoritmul de rezolvare a problemei. Exista, însa, probleme practice de mare complexitate pentru care stabilirea unui algoritm, fie el si unul aproximativ, este dificila sau chiar imposibila. In acest caz, problema nu poate fi abordata folosind un calculator traditional, indiferent de resursele de memorie si timp de calcul disponibile.

Caracteristic retelelor neurale este faptul ca, pornind de la o multime de exemple, ele sunt capabile sa sintetizeze în mod implicit un anumit model al problemei. Am putea spune ca o retea neuronala construieste singura algoritmul pentru rezolvarea unei probleme, daca îI furnizam o multime reprezentativa de cazuri particulare (exemple de instruire). Reteaua neuronala extrage informatia prezenta în multimea de instruire (învata din exemplele prezentate). In aceasta situatie se spune ca reteaua este instruita (antrenata). In faza de lucru – sau de referinta – reteaua va folosi informatia achizitionata în etapa de instruire pentru a trata situatii de aceeasi natura cu cele continute în multimea de instruire.

In cadrul modelelor conexioniste nu mai suntem obligati sa furnizam retelei neurale un algoritm determinist de rezolvare a unei probleme. Trebuie sa-i oferim doar o multime consistenta de exemple împreuna cu o regula de modificare a ponderilor interneurale. Pentru fiecare exemplu regula de instruire compara iesirea dorita (data de exemplu) cu iesirea reala a retelei si determina o modificare a ponderilor, în conformitate cu o strategie precizata. De regula, stabilirea ponderilor este un proces iterativ.

Capacitatea retelelor neurale de a rezolva probleme practice complexe utilizând o multime (uneori restrânsa) de exemple le confera un potential de aplicabilitate extrem de larg. Spectrul aplicatiilor merge de la sisteme de recunoastere a caracterelor (utilizate în trierea corespondentei), de recunoastere a semnaturilor (folosite în sistemul bancar) si recunoastere a vorbirii pâna la piloti automati si sisteme (în timp real) pentru controlul unor procese complexe. Acest spectru este în continua extindere si se considera ca, cel putin pentru viitorul apropiat, paradigma conexionista va polariza tot mai mult interesul cercetatorilor din domeniul inteligentei artificiale.

Scurt istoric

In mod obisnuit, se considera ca anulk 1943 marcheaza debutul calculului neuronal. La aceasta data apare primul model de neuron. Rezultat din colaborarea unui neurofiziolog cu un matematician (W.S. McCulloch si W. Pitts), acest model este, în linii generale, acceptat si astazi.

Progresele înregistrate în neurobiologie si psihologie au determinat aparitia unor modele matematice ale învatarii. Un astfel de model a fost propus în 1949 de catre D.O. Hebb. Modelul Hebb a reprezentat punctul de plecare în tentativele întreprinse î deceniul urmator de realizare a unor retele neurale artificiale capabile sa învete.

In 1958 Frank Rosenblatt a publicat p[rima sa lucrare despre perceptron. Acesta era “un model probabilistic pentru memorarea si organizarea informatiei în creier”. Un alt model de retea neuronala, cunoscut ca ADALINE (ADAptive LInear Neuron), a fost propus la începutul anilor ‘60 de catre Bernard Widrow. Retelele realizate în aceasta perioada au fost aplicate pentru rezolvarea unor probleme cum ar fi recunoasterea unor structuri specifice în electrcardiograme sau perceptia artificiala. Astazi putem spune ca acestea sunt aplicatii de recunoastere a formelor.

Primele succese ale retelelor neurale au determinat o mare emotie în lumea stiintifica. Specialistii erau aproape unanimi în a considera ca si alte procese asociate cu inteligenta si memoria umane pot fi modelate prin astfel de retele, eventual mai complicate.

Marvin Minsky, unul dintre pionierii cercetarilor privind retelele neurale, a întreprins o analiza lucida a posibilitatilor si limitelor modelelor neurale existente în epoca. El a demonstrat imposibilitatea principala a retelelor neurale cu un singur strat de a rezolva unele probleme relativ simple. De exemplu, functia logica SAU EXCULSIV (XOR) nupoate fi realizata (calculata) de o astfel de retea. Cartea lui M.Minsky si S.Papert ( Perceptrons, 1969), prin concluziile sale sceptice privind imposibilitatea retelelor multistrat de a depasi dificultatile perceptronului, pastrind insa caracteristicile care il fac interesant (liniaritatea, convergenta procedurii de instruire, simplitatea conceptuala ca model de calcul paralel), a marcat o scadere dramatica a interesului pentru aceasta directie de cercetare. A urmat aproape un deceniu de stagnare, in care putinii fideli ai domeniului au fost lipsiti de fondurile necesare unor cercetari de anvergura.

Aparitia in 1986 a cartii Parallel Distributed Processing, Explorations in the Microstructure of Cognition, de David Rumelhart,James McClelland si grupul PDP, se considera acum a fi momentul care a marcat relansarea cercetarilor privind modelele conexioniste. Interesul crescand pentru acest domeniu a dus la organizarea in 1987 a primei conferinte internationale de retele neurale. In prezent exista numeroase reviste de specialitate care publica articole cu caracter teoretic sau aplicativ privind retelele neurale si (cel putin) o revista de mare prestigiu consacrata exclusiv acestui domeniu:

IEEE Transactions on Neural Networks.

Calculul neural reprezinta acum un domeniu de cercetare fascinant si o provocare intelectuala si tehnologica majora. Retelele neurale au modificat imaginea noastra asupra proceselor de calcul si aspectelor algoritmice ale inteligentei artificiale si au furnizat psihologiei un nou model al proceselor mentale.

Prin aplicatiile în rezolvarea unor probleme dificile, cum sunt cele de estimare, identificare si predictie, a unor probleme de optimizare complexe, retelele neurale capata o pondere si un impact tot mai mari, nu doar în stiinta sau tehnologie, ci si în domeniul mult mai sensibil al vietii sociale. Retelele neurale pot reprezenta instrumente puternice în luarea deciziilor economice si chiar politice.

Pe plan mondial prin realizari deosebite se disting: S.Grossberg, H.Taylor, S.Yamakawa ce editeaza revista “Neural Networks”,Stephan Gallant “Neural Networks Learning and Expert System”(1993),Teuro Kokonen “Self organization and Associative Memory”(1988),V.Vemuri “Artificial Neural Networks”(1988),Helge Ritter ,T.Martinez, K.Schulten “Neural Computation and Self Organizing Map”(1992), A.Cichocki,Unmbhanen “Neural Netwarks for Optimization and Signal Processing” (1993).

Dintre cercetatorii români mentionam deosebitele contributii ale Doamnei profesoare Luminita State in cadrul Universitatii Bucuresti precum si profesorii D.Dumitru in cadrul facultatii Babes-Bolyai din Cluj si Hariton Costin profesor al Universitatii Tehnice Gh. Asachii din Iasi

.

Structura lucrarii .

Lucrarea contine trei capitole:

Capitolui I – Sunt prezentate elemente fundamentale privind arhitectura si functionarea retelelor neurale.Sunt descrise elementele de procesare,functiile semnal, tipurile de memorii, decodarea si encodarea precum si notiuni de stabilitate si convergenta.

Capitolul III – Este structurat pe doua teme principale: arhitecturile neurale feedforward si cele recurente.In prima parte sunt tratate :modelul lui McCullach-Pitts,perceptronul, memoria liniar asociativa, memoria liniar asociativa optimala,

adaline/madaline si backpropagarea. Sunt prezentate pentru fiecare dintre acestea topologiile retelelor, functiile criteriu , algoritmii precum si metode de inbunatatire si variante ale acestora,,precum si teoremele de convergenta.In cadrul lucrarii sunt detaliate diferitele variante ale backpropagarii.In partea a doua este tratata una din cele mai “puternice” retele ce apartine acestei clase,memoria asociativa bidirectionala BAM, amintindu-se si de modelele unilayer asincron -Hopfield si cel sincron -Little.

Capitolul III – Este consacrat descrierii aplicatiei realizata in mediul de programare Borland C++ 3.1 sub Windows, in care sunt implementati principalii algoritmi descrisi in lucrarea de fata .Aplicatia este un “recognizer” de caractere -OCR

Printre algoritmii implementati se disting OLAM care encodeaza optim esantionul de invatare precum si cea mai “puternica “ retea feedforward -BPN.Programul contine fisiere in care sunt retinute memoriile retelelor dupa ce acestea au fost instruite pe baza unor esantioane de exemple. Exista posibilitatea instruirii prin selectarea fisierului cu esantionul de test, si aplicarea comenzii de instruire.Programul prezinta diverse facilitati de testare: atat a exemplelor din esantioanele de instruire, perturbatii ale lor sau forme diferite de cele prezentate la instruire. Exista obtiuni de modificare a parametrilor ce intra in componenta algoritmilor. Pe baza compararilor sub forma de grafice pe care le permite aplicatia, exista posibnilitatea optimizarii algoritmilor prin gasirea valorilor optime ale parametrilor,precum si a compararii performantelor. Programul contine si un help in care sunt prezentate metodele abordate in aplicatie.

Capitolul I

1. Fundamentele arhitecturilor neurale

In acest capitol vom prezenta notiuni fundamentale si concepte matematice folosite pentru a descrie si analiza procesarea sistemelor neurale artificiale (ANS Artificial Neural System).Intr-un sens larg, ANS consta din trei elemente:

(1) o topologie organizata de elemente de procesare interconectate (retea sau sistem neural)

(2) o metoda de encodare a informatiei

(3) o metoda de decodare a informatiei

1.1. Elemente de procesare

Elementele de procesare PE se refera la noduri,memorii de scurta durata,neuroni, populatii sau unitati de prag logic,ce sun componente ale retelelor neurale si majoritatea, daca nu toate participa la calcul.Semnalele de intrare provin din mediu inconjurator sau de la iesirile altor PE-uri.Forma vectorilor de intrare

unde este nivelul ed activare al i-lea PE de intrare. PE sunt conectate intre ele , fiecare pereche conectata avand asociata o pondere numita si putere de conectare.

1.2. Functii prag

Forma functiei semnal f depinde de reteaua neurala studiata.Aceasta se mai numeste: functie neurala, functie de iesire, functie de comprimare sau functie de activare a neuronului. Intrarea este de domeniu infinit iar iesirea apartine unei clase prespecificate. Dupa regimul de functionare se impart in discrete si continuii. In cazul discret iesirile pot fi bipolare – {0,1} si polare – {-1,1}.In general se considera functii sky, unul dintre pionierii cercetarilor privind retelele neurale, a întreprins o analiza lucida a posibilitatilor si limitelor modelelor neurale existente în epoca. El a demonstrat imposibilitatea principala a retelelor neurale cu un singur strat de a rezolva unele probleme relativ simple. De exemplu, functia logica SAU EXCULSIV (XOR) nupoate fi realizata (calculata) de o astfel de retea. Cartea lui M.Minsky si S.Papert ( Perceptrons, 1969), prin concluziile sale sceptice privind imposibilitatea retelelor multistrat de a depasi dificultatile perceptronului, pastrind insa caracteristicile care il fac interesant (liniaritatea, convergenta procedurii de instruire, simplitatea conceptuala ca model de calcul paralel), a marcat o scadere dramatica a interesului pentru aceasta directie de cercetare. A urmat aproape un deceniu de stagnare, in care putinii fideli ai domeniului au fost lipsiti de fondurile necesare unor cercetari de anvergura.

Aparitia in 1986 a cartii Parallel Distributed Processing, Explorations in the Microstructure of Cognition, de David Rumelhart,James McClelland si grupul PDP, se considera acum a fi momentul care a marcat relansarea cercetarilor privind modelele conexioniste. Interesul crescand pentru acest domeniu a dus la organizarea in 1987 a primei conferinte internationale de retele neurale. In prezent exista numeroase reviste de specialitate care publica articole cu caracter teoretic sau aplicativ privind retelele neurale si (cel putin) o revista de mare prestigiu consacrata exclusiv acestui domeniu:

IEEE Transactions on Neural Networks.

Calculul neural reprezinta acum un domeniu de cercetare fascinant si o provocare intelectuala si tehnologica majora. Retelele neurale au modificat imaginea noastra asupra proceselor de calcul si aspectelor algoritmice ale inteligentei artificiale si au furnizat psihologiei un nou model al proceselor mentale.

Prin aplicatiile în rezolvarea unor probleme dificile, cum sunt cele de estimare, identificare si predictie, a unor probleme de optimizare complexe, retelele neurale capata o pondere si un impact tot mai mari, nu doar în stiinta sau tehnologie, ci si în domeniul mult mai sensibil al vietii sociale. Retelele neurale pot reprezenta instrumente puternice în luarea deciziilor economice si chiar politice.

Pe plan mondial prin realizari deosebite se disting: S.Grossberg, H.Taylor, S.Yamakawa ce editeaza revista “Neural Networks”,Stephan Gallant “Neural Networks Learning and Expert System”(1993),Teuro Kokonen “Self organization and Associative Memory”(1988),V.Vemuri “Artificial Neural Networks”(1988),Helge Ritter ,T.Martinez, K.Schulten “Neural Computation and Self Organizing Map”(1992), A.Cichocki,Unmbhanen “Neural Netwarks for Optimization and Signal Processing” (1993).

Dintre cercetatorii români mentionam deosebitele contributii ale Doamnei profesoare Luminita State in cadrul Universitatii Bucuresti precum si profesorii D.Dumitru in cadrul facultatii Babes-Bolyai din Cluj si Hariton Costin profesor al Universitatii Tehnice Gh. Asachii din Iasi

.

Structura lucrarii .

Lucrarea contine trei capitole:

Capitolui I – Sunt prezentate elemente fundamentale privind arhitectura si functionarea retelelor neurale.Sunt descrise elementele de procesare,functiile semnal, tipurile de memorii, decodarea si encodarea precum si notiuni de stabilitate si convergenta.

Capitolul III – Este structurat pe doua teme principale: arhitecturile neurale feedforward si cele recurente.In prima parte sunt tratate :modelul lui McCullach-Pitts,perceptronul, memoria liniar asociativa, memoria liniar asociativa optimala,

adaline/madaline si backpropagarea. Sunt prezentate pentru fiecare dintre acestea topologiile retelelor, functiile criteriu , algoritmii precum si metode de inbunatatire si variante ale acestora,,precum si teoremele de convergenta.In cadrul lucrarii sunt detaliate diferitele variante ale backpropagarii.In partea a doua este tratata una din cele mai “puternice” retele ce apartine acestei clase,memoria asociativa bidirectionala BAM, amintindu-se si de modelele unilayer asincron -Hopfield si cel sincron -Little.

Capitolul III – Este consacrat descrierii aplicatiei realizata in mediul de programare Borland C++ 3.1 sub Windows, in care sunt implementati principalii algoritmi descrisi in lucrarea de fata .Aplicatia este un “recognizer” de caractere -OCR

Printre algoritmii implementati se disting OLAM care encodeaza optim esantionul de invatare precum si cea mai “puternica “ retea feedforward -BPN.Programul contine fisiere in care sunt retinute memoriile retelelor dupa ce acestea au fost instruite pe baza unor esantioane de exemple. Exista posibilitatea instruirii prin selectarea fisierului cu esantionul de test, si aplicarea comenzii de instruire.Programul prezinta diverse facilitati de testare: atat a exemplelor din esantioanele de instruire, perturbatii ale lor sau forme diferite de cele prezentate la instruire. Exista obtiuni de modificare a parametrilor ce intra in componenta algoritmilor. Pe baza compararilor sub forma de grafice pe care le permite aplicatia, exista posibnilitatea optimizarii algoritmilor prin gasirea valorilor optime ale parametrilor,precum si a compararii performantelor. Programul contine si un help in care sunt prezentate metodele abordate in aplicatie.

Capitolul I

1. Fundamentele arhitecturilor neurale

In acest capitol vom prezenta notiuni fundamentale si concepte matematice folosite pentru a descrie si analiza procesarea sistemelor neurale artificiale (ANS Artificial Neural System).Intr-un sens larg, ANS consta din trei elemente:

(1) o topologie organizata de elemente de procesare interconectate (retea sau sistem neural)

(2) o metoda de encodare a informatiei

(3) o metoda de decodare a informatiei

1.1. Elemente de procesare

Elementele de procesare PE se refera la noduri,memorii de scurta durata,neuroni, populatii sau unitati de prag logic,ce sun componente ale retelelor neurale si majoritatea, daca nu toate participa la calcul.Semnalele de intrare provin din mediu inconjurator sau de la iesirile altor PE-uri.Forma vectorilor de intrare

unde este nivelul ed activare al i-lea PE de intrare. PE sunt conectate intre ele , fiecare pereche conectata avand asociata o pondere numita si putere de conectare.

1.2. Functii prag

Forma functiei semnal f depinde de reteaua neurala studiata.Aceasta se mai numeste: functie neurala, functie de iesire, functie de comprimare sau functie de activare a neuronului. Intrarea este de domeniu infinit iar iesirea apartine unei clase prespecificate. Dupa regimul de functionare se impart in discrete si continuii. In cazul discret iesirile pot fi bipolare – {0,1} si polare – {-1,1}.In general se considera functii neurale neliniare.

Prezentam in continuare cele mai intalnite functii neurale

(i) Functie liniara

f(x)=alfa*x

unde alfa apartine R , este o constanta care regleza marimea activarii x.

(ii) Functia prag asociata modelului McCullach-Pitts

(iii) Functia signum

(iv) Functia prag liniar (rampa)

unde apartine R,>0 -defineste nivelul de saturatie. Iesirea poate fi si un interval necentrat ex [0,1].

(V) Functia sigmoida (logistica)

f:R(0,1) f(x)=1/(1+e^(-kx))

unde k>0.Aceasta functie este folosita in statistica (distrib fct Gauss), chimie (descrierea reactiilor catalitice) si sociologie (crestarea populatiei umane).Nivelul de saturatie 0-1.

(vi) Functii de tip sigmoidal

a)

k aparine R>0.Pentru k=1 se obtine functia tangenta hiperbolica

b)

Functiile sigmoide reprezinta functii netede de functii prag liniar. Acesta sunt continue, derivabile si monoton crescatoare. Aceste proprietati sunt foarte convenabile pentru aplicatii. Ele pot produce valori de iesire intermediare celor doua valori extreme (0,1), ceea ce constitue o facilitate pentru calculul analogic si pentru modelarea unei logici multivalente.

1.3. Caracteristici topologice

Topologiile retelelor neurale sunt alcatuite din organizarea elementelor de procesare in straturi (campuri sau layere) si legarea lor prin ponderi de interconectare ( ponderi de conexiune sau ponderi sinaptice ). Caracteristicile topologice includ: tipuri de conexiuni, scheme de conectare si configuratii de campuri.

2.3.1. Tipuri de conexiuni

Exista doua tipuri primare de conexiuni: exciatoare si inhibitoare. Conexiunile excitatoare cresc activarea elementelor de procesare si sunt reprezentanti tipici pentru semnale pozitive. Conexiunile inhibatoare scad activarea elementelor de procesare si sunt reprezentanti tipici pentru semnale negative. Aceste conexiuni nu trebuie sa fie distincte.De obicei o parte ale conexiunilor vecine unui element de procesare au valori pozitive iar restul au valori negative.

2.3.2. Scheme de interconectare

Exista trei tipuri primare de scheme de interconectare a elementelor de procesare: in cadrul aceluiasi camp ,intre doua campuri diferite si recurente. Conexiunile in cadrul aceluiasi camp (intra-field) se mai numesc si conexiuni intra-layer sau conexiuni laterale si sunt conexiuni intre elementele de procesare ale aceluiasi layer. Conexiunile intre doua capuri diferite (intrer-field) se mai numesc si conexiuni inter-layer sau conexiuni intre campuri si sunt conexiuni intre elementele de procesare a doua layere diferite. Conexiunile recurente (recurent) sunt conexiuni de la un element de procesare la el insusi.

In conexiunile dintre campuri, semnalele se propaga in doua sensuri: feedforward sau feedback. Semnalele feedforward sunt indrptate pe o singura directie printre elementele de procesae. Semnalele feedback se propaga in ambele directii si/sau recursiv. Fig. descrie cele doua metode de decodare a informatiei.

2.3.2. Configuratii de campuri

Configuratiile de campuri (field configuration) combina campuri de elemente de procesare,scheme de conexiuni si fluxul de informatii intr-o arhitectura coerenta. Un camp care primeste semnal din exterior se numeste layer(camp) de intrare (input layer) iar cel care emite semnal in exterior se numeste layer de iesire (ouput layer). Orice layer care se interpune intre layerul de intrare si cel de iesire se numeste layer ascuns (hidden layer) si nu au contact direct cu exteriorul (doar elementele de procesare din layerele de intrare si iesire).

Figura ilustreaza topologi comune ale retelelor neurale.In fiecare caseta

sagetile indica fluxul informatiei.

Caseta (a) ilustreaza o retea neurala cu un layer cu feedback lateral

(b) ilustreaza o retea neurala cu doua layere cu feedforward

(c) ilustreaza o retea neurala cu trei layere cu feedback

(d) ilustreaza o retea neurala cu trei layere cu feedforward

O retea echivalenta cu cea descrisa in caseta (a) este reteaua neurala

in cross (crossbar).

O retea neurala in cross este o matrice de "bare de legatura" cu conexiuni adaptate pentru fiecare cross. Reprezentarea in cross a dus la implementarea hardware a retelelor neurale. Aceasta implementare se realizeaza inlocuind conexiunile adaptabile cu rezistori si plasind amplificatori (reprezentati cu triunghi ) la iesirea fiecarei linii (elem. de procesare) anterioare feedback-lui.

2.4. Memoria

2.4.1. Tipuri de forme

Retelele neurale stocheaza doua tipuri de forme (pattern-uri): forme spatiale si forme spatio-temporale. O forma temporala este o singura imagine. O forma spatio-temporala este o secventa(sir) de forme spatiale. O analogie avantajoasa este sa considerem o forma spatiala ca o secventa de film iar o forma spatiotemporala ca pe un film intreg. Multe dintre paradigmele descrise in aceasta lucrare sunt asociatorul de forme spatiale sau clasificatorul de forme spatiotemporale.

2.4.2. Tipuri de memorii

Exista trei tipuri diferite de memorii pentru asociatorul de forme spatiale: memorie cu acces aleator, memorie cu continut adresabil si memorie asociativa. Memoria cu acces aleator (RAM) este tipul de memorie conventional cu care lucreza calculatorul – memorarea adresei. Memoria cu continut adresabil(CAM) este gasita in unele calculatoare si echipamenta de procesare de semnal – memorea adresei intr-o variabila. Memoria asociativa (AM) este memoreaza variabile in variabile. Retelele neurale ucreaza cu memoriile de tip CAM si AM. Cand o retea neurala opereaza cu memorie CAM, stocheaza datele in stari stabile, in matrici de memorie W. Cand o retea neurala opereaza cu memorie AM, raspunde la iesire in functie de stimuli.

2.4.3. Mecanismul de memorare

Sunt doua tipuri primare de mecanisme de memorare: autoasociative si heteroasociative. O retea neurala este autoasociativa, daca memoria sa, W, stocheaza vectorul (forma) A1,A2,…,Am si este heteroasociativa , daca memoria sa ,W , stocheaza vectori pereche (A1,B1),(A2,B2),…,(Am,Bm). Un vector pereche se numeste forma asociata iar sirul de vectori pereche se numeste lista de asociere de lungime m.

2.5. Decodarea

Se presupune ca forma pereche (Ak,Bk) k=1,2,…,m , a fost stocata in W.Un mecanism decodare heteroasociativ este o functie g() care rimeste ca intrare W (memoria) si Ak (stimuli) si returneaza Bk (raspuns) la iesire.

Aceasta relatie se scrie:

Bk=g(Ak,W)

Folosind aceste notatii vom defini doua mecanisme primare de decodare ale

retelelor neurale: cel mai apropiat vecin si interpolare . Metoda cel mai apropiat vecin (neart-neightbor recall) gaseste intrarea stocata care potriveste cel mai bine stimulul si raspunsul cu iesirea care ii corespunde. Aceasta operatie poate fi conventional data de ecuatia:

Bk=g(A',W)

unde dist(A',Ak)=MIN(q=1 ..m) { dist(A',Aq) }

unde dist() este o functie distanta tipica Haming sau Euclidiana.Interpolarea(interpolate recall) accepta ca stimuli si interpoleaza, se poate si intr-un mod neliniar, intregul set de intrari stocate pentru a produce iesirea corespunzatoare.Presupunind ca interpolarea este liniara, aceasta operatie este data de ecuatia:

B'=g(A',W)

unde Ap<=A'<=Aq si Bp<=B'<=Bq pentru unele forme pereche (Ap,Bp) si (Aq,Bq).

2.6. Instruirea

Definim invatarea ca orice schimbare ce are loc asupra memoriei W,si se

defineste matematic:

Invatarea === dW/dt<>0

Toate metodele de invatare pot fi clasificate in doua categorii: invatarea supervizata si invatarea nesupervizata, desi aspecte din fiecare pot exista intr-o arhitectura data.Invatarea supervizata (supervised learning) este un proces care incorporeaza un profesor (with teacher) si/sau informatie globala. Tehnicile de invatare supervizata includ: decizia cand invatarea a fost terminata, decizia cat de mult si cat de des trebuie prezentata fiecare asociere pentru antrenare si informatii despre erorile intalnite.Invatarea supervizata se imparte in doua categorii: invatarea structurala si invatarea temporala .Invatarea structurala(structural learning) encodeaza bine mecanismele de memorare autoasociative si heteroasociative.Invatarea temporala (temporal learning) encodeaza o secventa de forme necesare pentru a obtine unele rezultate finale (asemenea unei secvente corecte de mutari necesare pentru a castiga un joc de sah) in W. Exemple de algoritmi de invatare supervizata: invatarea prin corectarea erorilor, invatarea prin intarire, invatarea stocastica si sisteme hardware. Invatarea nesupervizata (unsupervised learning) sau cum mai este numita auto-organizare (self-organization) este o procedura care nu include profesor din exterior dar include informatia locala si controlul intern. Invatare nesupervizata descopera proprietati comune ale elementelor prezezntate.Desi nu sunt sisteme de invatare, retelelor neurale conectate aleator li se acorda o mare atentie. Algoritmii dicutati mai jos vor fi reluati detaliat in urmatoarele sectiuni.

2.6.1. Invatarea prin corectarea erorilor

Invatarea prin corectarea erorilor (error correction learning) este o procedura de nvatare supervizata care ajusteaza ponderile conexiunilor dintre elementele de procesare proportional cu diferenta dintre valoarea dorita si cea calculata pentru fiecare element de procesare din layerul de iesire. Daca valoarea dorita a elementului j de procesare al layerului de iesire este cj si valoarea calculata a aceluiasi element de procesare este bj, atunci ecuatia generala pentru modificarea marimii conexiunii Wij este

delta Wij= alfa ai [cj-bj]

unde Wij este marimea conexiunii (memoriei) dintre ai si bj, si alfa este rata de invatare tipica 0<alfa<1 . O problema a invatarii prin corectarea erorii pentru retelele neurale a constituit=o inabilitatea de a extinde invatarea pentru retele neurale cu mai mult de 2 layere.

In mod specific, nu a fost definit modul inb care suma erorilor layerului ascuns participa la iesirea elementelor de procesare. Din fericire, acesta problema, cunoscuta ca problema "credit assignment" (Barto 1984, Minsky 61) a fost rezolvata (a se vedea Backpropagation si Masina Boltzman.).

2.6.2. Invatarea prin intarire

Invatarea prin intarire (reinforcement learning) este asemanatoare cu invatarea prin corectarea erorilor; ponderile sunt intarite in functie de propria contributie si putere (grad) la "performanta promta a actiunii". Diferenta este ca invatarea prin corectarea erorilor are nevoie de eroarea fiecarui element de procesare al layerului de iesire – un vector al val;orilor de eroare, pe cand invatarea prin intarire are nevoie doar de o valoare pentru a descrie performantele layerului de iesire – un scalar cu valoarea erorii (Windrow, Gupa & Matra) 1973, Williams 1986).

Ecuatia de invatare prin intarire (William 1987)

delta Wij = alfa[r- teta j]*eij

unde este o valoare scalara de succes (esec) provenita din exterior, teta j este valoarea pragului de intarire al j-lea element de procesare de iesire, eij este potrivire canonica a ponderilor dintre ale i-lea element de procesare si cel de al j-lea si alfa este o constanta (0<alfa<1) care regleza rata de invatare. Potrivirea canonica dintre al i-lea si al j-lea PE este dependenta de o distributie de probabilitate selectata cu atentie care este folosita pentru a determina daca valoarea de iersire calculata este egala cu valoareade iesire dorita si este definita:

unde gi este probabilitatea ca iesirea dorita sa fie egala cu iesirea calculata , definita

gi=Pr{bj=cj | Wj,A}

unde bj este valoarea calculata a PE j, cj este valoarea dorita pentru PE j, j este vectorul de ponderi asociat cu Pe j si A este vectorul intrarilor pentru elementul de procesare j.

2.6.3. Invatarea stochastica

Invatarea stochastica (stochastic learn) foloseste procese aleatoare,probabilitati si o relatie de energie pentru a ajusta ponderile conexiunilor memoriei (Ackley, Hilton & Sejnowski, 1985; Szu 1986).

Invatarea stochastica face o schimbare aleatoare de ponderi, determina energia rezultata dupa schimbare si retine ponderile schimbate dupa urmatorul criteriu:

(1) daca energia retelei neurale este scazuta dupa schimbarea aleatoare de

ponderi (i.e. sistemul este mai performant), se accepta scimbarea;

(2) daca energia este mai mare, se accepta schimbarea acordand-o la o dis-

tributie de probabilitate prealeasa, altfel

(3) nu se schimba nimic.

Acceptarea unor schimbari, in ciuda slabei performante, permite retelelor neu-

rale sa "scape" dintr-un minim de energie local pentru a atinge un minim de energie (local) mai bun, un proces denumit calire simulata (simulated annealing) (German & Geman, 1984; Kirkpatrick, Galat & Vecchi, 1983). Acest proces descreste incetprobabilitatea de a accepta schimbari ale ponderilor cand rezultatul este de performanta scazuta.

2.6.4. Sisteme hardware

Sistemele hardware sunt modele de retele neurale ale caror conexiuni si ponderi sunt predeterminate (harware) pentru retele neurale. Starile automate finite asemanatoare precum retelele neurale au fost astfel instruite incat sa recunoasca sensul limbajului. (Cotirel & Small 1983 & 1984. Fanty 1986) perspectiva (Feldman, 1980 & 1981, Fukushima 1960 & 1970; Coros & Migolla 1985), concepute din creier (Feldman, 1981) si relatiile cauzale (Kosko 1986).

2.6.5. Invatarea Hebiana

Invatarea Hebiana, numita astfel dupa Donald Hebb(1949) – care a sintetizat conceptul de invatare corelata dar nu a formalizat matematic, consta in ajustarea ponderilor conexiunilor, acordate cu corelarea valorilor a doua PE conectate. Hebb descrie aceasta idee in cateva pasaje din cartea " Organization of Behavior" (1949): "When an axon of cell A is near enough to excite a cell B and respectlly"(pg 15)

Putem ilustreaza o formula matematica simpla a regulii de invatare, unde valoarea ponderilor Wij este corelatia (multiplicarea) dintre ai elemente procesate si aj PE a ecuatiei de tip discret:

Wij=ai*aj

unde DWij reprezinta schimbarea in timp discret a lui Wij. Mai jos sunt date cateva extinderi ale acestei reguli de invatare. Sejrowski (1977a & 1977b) a util;izat corelatia (covarianta) valorilor activarilor elementelor de procesare in ecuatia

unde termenii parantezati reprezinta covarianta si 0<niu<1 unde niu este o rata de adaptare, costanta, (-) reprezinta media, si cantitatea dintre paranteze reprezinta variatia PE j. Sutton & Barto (1981a) au folosit corelatia valorii medii a lui ai cu variatia lui aj descrisa de ecuatia

Klopf (1986) propune o ecuatie de corelare discreta de timp denumita invatare prin conducerea intaririlor care coreleaza schimbarile in ai si cele din aj care se defineste

Cheung & Omidvar (1988) au creat o ecuatie de timp discret, o combinatie intre ecuatiile lui Klopf si Sutton-Barto, care coreleaza valoarea activarilor lui ai cu schimbarile din aj reglate de puterea valorii conexiunii curente si o constanta cum se vede din ecuatia

Trecand ecuatia Hebb simpla in timp continuu si scazand un termen, ecuatia

devine

Wij'=-Wij+ai aj

unde (') reprezinta dWij/dt. Grossbert (1968c & 1969b), Hopfield (1984) si multi altii au fost angajati in extinderea reguliide invatare Hebbiana in timp continuu care coreleaza valorile activarii dupa ce au trecut printr-o functie neliniara de prag. Aceasta regula de invatare, numita legea invatarii Hebbiene semnal (signal Hebbian learning law) este ilustrata in caseta (b) din figura si are ecuatia

Wij'=-Wij+S(ai)S(aj)

unde S() este o functie de prag sigmoidala. Kosko (1985, 1986) a folosit o versiune a ecuatiei in timp continuu a lui Klopf care coreleaza derivata de timp a functiei semnal. Aceasta regula – numita invatarea Hebbiana diferentiala (differential Hebbian learning) este ilustrata in caseta (c) a figurii sieste descrisa de ecuatia

Wij'=-Wij_S'(ai)S'(aj)

unde derivata functiei sigmoida in timp continuu este

S'(x)=S'(x)*x'

Regula invatarii Hebbiene diferentiale a fost reluata de catre Hintor & McClellad (1988) si Gluck, Parker & Reifsnidor (1988).

2.6.6. Invatarea competitiva si cooperativa

Procesele competitive si cooperative sunt descrise caretele neurale cu conexiuni recurente cu autoextragere si vecini-inhibitor (competitiva) si/sau vecini excitatori (cooperativa). Mai precis, sistemul diferential de ecuatii

dxi/dt=Fi(x1,x2,…, xn)=Fi(x), i=1,2,..,n este competitiv

daca Fi/xj0 oricare ar fi j<>i si cooperativ daca Fi/xj 0 oricare ar fi ji.

Invatarea competitiva introdusa de Grossby (1972b & 1976a) si

von den Malsburg (1973) si studiate intens de numerosi cercetatori estre o procedura de clasificare de forme pentru conexiunile conditionate intra-layer ale retelelor neurale cu doua layere. Formula este simpala (invingatorul ia tot), invatarea competitiva lucreza corect cu decodarea in maniera urmatoare:

(1) o forma de intrare este prezentata layerului de intrare FA al PE;

(2) elementele de procesare FA trimit activarilor lor de la FA la FB prin conexiunile intra-layer

3) fiecare PE din FB concureaza impreuna cu celelalte trimitand semnale pozitive lor insile (recurent self-excitation) si semnale negative tuturor vecinilor (lateral neighbar-inhibition)

(4) eventual PE FB cu activari (singurele active) importanta (mare) va fi singulary activ si toate celelalte anuleaza pasii (1)-(4).Elementele de procesare FB cu activarile mari se numesc FB-castigatoare. Odata ce competitia s-a incheiat, se inlocuiesc conexiunile dintre FA, FB- castigatoare dupa ecuatia:

Wij'=S(ai)[-Wij+S(bj)]

unde Wij este puterea conexiunii dintre al i-lea PE al lui FA si al j-lea PE din FB (bj) si S() este o functie sigmoida.In concluzie, ultima ecuatie ajusteaza automat acele conexiuni care sunt legate cu PE FB-castigatoare, lasand celelalte conexiuni neafectate. Mai general, activitatea FB este marire de contrast, dar nu din punctul de vedere ca numai o PE ramane activa.

O extensie a invatarii competitive Grossberg (1982a) este invatarea competitiv-cooperativa . O retea neurala cu invatare competitiva-cooperativa a separat conexiunile excitatoare (pozitive) si cele inhibatoare (negative) pentru fiecare PE. Ecuatia de invatare competitiva este cea de mai sus, dar dinamica activarilor este cu totul diferita. In Grossberg (1988) o explicatie a beneficiului acestei interactiuni este discriminarea semnalului si zgomotului care este concisa intr-o constructie pas cu pas a motivarii unui astfel de sistem.

2.6.7. Sisteme cu conexiuni aleatoare

Retelele neurale cu conexiuni aleatoare sunt retele fata invatare, studiate de Farley & Clork.Retelele neurale cu conexiuni aleatoare au fost analizate pentru a sprijini teoria conform careia creierul (la nivel micro) este intr-adevaro retea conectata aleator. Se spera ca stuiind acest tip de retele unele dintre secretele organizarii creierului vor putea fi descoperite.

2.7. STABILITATE SI CONVERGENTA

Procesarea retelelor neurale este guvernata de doua probleme: stabilitatea globala si convergenta.. Stabilitatea globala (global stability) este stabilizarea eventuala a activarilor tuturor PE pentru orice intrare initiala. Convergenta (convergence) este eventuala minimizare a erorii dintre iesirile EP dorite si cele calculate. Stabilitatea este o notiune de obicei asociata cu propagarea feedbak, iar convergenta, asociat cu notiunea de invatare supervizata. Exista trei teoreme generale pentru a demonstra stabilitatea unei clase vide de paradigme ale retelelor neurale care "angajeaza" feedback in timpul decodarii. Demonstrarea convergentei este specifica pentru fiecare paradigma a retelelor neurale.

2.7.1. O definitie a stabilitatii globale

Echilibrul si miscarile care sunt doar usor disturbate de devieri neglijabile, sunt numite stabile. Acelea care sufera disturbari importante sunt numite instabile. Global, toate retelele neurale stabile sunt definite ca sisteme dinamice nonliniare care memoreaza in mod rapid toate intrarile catre puncte fixe. Aceste puncte fixe, limita de convergenta, echilibru, etc., se gasesc unde informatia poate sa fie stocata in mod deliberat. Desi stabilitatea globala garanteaza ca toate intrarile sunt memorate catre puncte fixe, nu garanteaza ca va memora toate intrarile catre punctele fixe dorite.Sunt trei teoreme principale care sunt utilizate pentru a demonstra stabilitatea pentru "wide range" al paradigmelor retelelor neurale care aplica feedbak in timpul decodarii. Fiecare dintre aceste teoreme utilizeaza metoda directa Liapunov.

2.7.1.1. Metoda directa Liapunov

Metoda directa Liapunov studiaza stabilitatea, gasind anumite functii devariabile ale sistemelor dinamice, ale caror derivate in raport cu timpul saaibe proprietati specifice. Aceasta metoda este in contrast direct cu metodaalternativa de a studia stabilitatea unui sistem de ecuatii dinamice integrand aceste ecuatii ale miscarii. In esenta metoda directa Liapunov este o drumul cel mai scurt spre analiza stabilitatii globale a unui sistem de ecuatii posibil neliniare,diferentiabile. Cele patru proprietati specifice ale metodei directe Liapunov(Chet ayav, 1961) urmareste sa demonstreze stabilitatea globala a unui sistem de ecuatii

dx/dt=F(t,x1,x2,…,xn)=Xi dupa cum urmeaza:

(L1) Xi=0 daca xi=0 oricare ar fi i=1,2,…,n

(i.e. 0 doar in origine)

(L2) Xi este holomorfica

(i.e. prima derivata exista in toate partile domeniului dat)

(L3) suma xi<=H oricare ar fi t>=t0

unde t0 si H sunt constante si H este exista intotdeauna

(i.e xi este trunchiata)

(L4) V'=suma V/xi<0 oricare ar fi xi

unde V este functia de energie Liapunov de variabile Xi care translateaza ndimensiuni intr-una i.e. V: R. Metoda directa Liapunov stabileste care sistem va converge si care va deveni stabil global daca ambele proprietati sunt pentru o functie data de energie data,si cand pentru toate intrarile de sistem posibile X=(x1,x2,…,xn).

CAPITOLUL II

ARHITECTURI NEURALE

FEEDFORWARD SI RECURENTE

2.1. PRIMUL MODEL DE RETEA NEURALA

Modelul McCullach – Pitts

Modelul McCullach – Pitts (1943) este un sistem axiomatic inspirat de neuronul fiziologic (fara feedback). El asigura simularea circuitelor computationale.

Exemple: functiile booleene, mecanismul computational pentru structurile simbolice din limbajul calculului cu propozitii.

Axiomele McCullach – Pitts

1. Functiile de procesare a elementelor sunt de tipul totul sau nimic, adica iesire / intare

0/1 unde

1 – emite actiune potentiala

0 – potential de repaos.

Exista doua tipuri de conexiuni sinaptice:

excitatorii

inhibatorii.

2. Un neuron ramâne în starea de repaos daca cel putin o conexiune sinaptica

inhibatoare care conduce la acel neuron este activa.

3. Un neuron emite actiune potentiala (iesirea = semnal) daca un numar prestabilit

(n>1) daca conexiuni sinaptice spre acel neuron sunt active.

4. Transmiterea informatiei este instantanee cu exceptia conexiunilor sinaptice (delay

unit)pentru care timpul de întârziere este 1.

5. Arhitectura neural are sistemul de conexiuni invariant în timp.

Exemple:

– delay 1 2 N(t)=N(t-1)

– not 1 2 N(t)= N(t-1)

ON

– and 1 3 N(t)= N(t) N(t)

2

– or 1 3 N(t)= N(t-1) N(t-1)

2

– negarea 1 3 N(t)= N(t-1) N(t-1)

implicita 2

Sinteza unui circuit McCullach – Pitts

1

a 3

2

b 4

N(t)= N(t-1) N(t-1) N(t)= N(t-1) N(t-1)

N(t)= N(t-1)

deci N= N(t-1)( N(t-2) N(t-3) N(t)= N(t-1) N(t-1)

dar N(t)= N(t-1) deci N(t)= N(t-2) N(t-1).

2.2. ARHITECTURI NEURALE FEEDFORWARD

2.2.1. PERCEPTRONUL

2.2.1. 1. Perceptronul cu un singur strat

Perceptronul cu un singur strat este cea mai simpla retea neurala Valorile de intrare pot fi binare sau numere reale. Aceasta retea elementara a generat mult interes datorita abilitatii ei de a învata sa recunoasca forme simple.

Un perceptron capabil sa decidadaca un vector (o forma) de intrare apartine uneia dintre cele doua clase de instruire, notate A1 si A2, este reprezentat mai jos în figura:

X W t

Intrari y Iesire

X W

Perceptronul cu un singur strat

Acest perceptron este implementat cu un singur neuron. Fie

x= ,xR,

vectorul ce reprezinta intarile neuronului. Neuronul calculeaza suma ponderata

s=

a elementelor de intrare.

Admitem ca perceptronul are iesirile -1 si +1. Iesirea y este data de urmatoarea regula:

s>-t y=1 ,

s<-t y= – 1,

unde t este un prag al neuronului. Iesirea y= 1 corespunde faptului ca vectorul de intrare apartine clasei A1. Notam cu x vectorul de intrare extins,

x=

si cu v vectorul ponderilor la care adaugam o componenta egala cu pragul t:

v=.

Cu aceste notatii iesirea perceptronului este data de regula

vx>0 y=+1 ,

vx<0 y= – 1 .

De obicei vectorul v se numeste vector pondere. Alte denumiri utilizate sunt vector de separare sau vector solutie.

Ecuatia

vx=0

reprezinta ecuatia unui hiperplan care împarte spatiul vectorilor de intrare în doua regiuni de decizie. Asadar, perceptronul formeaza doua zone de decizie separate de un hiperplan.

Vectorii de intrare aflati în partea pozitiva a hiperplanului de decizie corespund clasei A1 iar cei situati de partea negativa sunt aferenti clasei A2. Vectorii aflati pe hiperplan nu corespund vreuneia dintre clase (nu determina o iesire a retelei). Hiperplanul de separare reprezinta deci o regiune de nedeterminare.

Vom face o normalizare de semn a vectorilor de intrare, punând

z=

Rezulta ca hiperplanul vz=0 este un hiperplan de separare pentru clasele A1 si A2 daca si numai daca exista inegalitatea

vz>0 ,zA1A2.

Daca pentru doua clase exista un hiperplan de separare, aceste clase se numesc liniar separabile.

Ponderile conexiunilor si pragul (componentele vectorului v) unui perceptron se pot adapta folosind un algoritm de instruire simplu, numit Algoritmul perceptronului. Acesta este un algoritm de învatare supervizata, utilizat pentru a gasi un vector pondere ce separa cele doua clase.

Procedura de instruire a perceptronului reprezinta o metoda iterativa pentru optimizarea unei functii criteriu. Ca functie obiectiv se alege suma distantelor punctelor eronat clasificate la hiperplanul determinat de un vector pondere v.

2.2.1.2. Functia de performanta

Admitem ca multimea de instruire este formata din perechile :

(x,y),(x,y),…,(x,y),

unde y este raspunsul corect (asteptat) pentru intrarea xretelei.

Notam cu E(v) multimea punctelor eronat clasificate de catre vectorul pondere v:

E(v) = { x | vx 0} .

Daca x E(v), atunci eroarea de clasificare e este distanta lui x la hiperplanul H avand ecuatia

vx = 0 .

Eroarea se scrie deci

e = d(x,H) .

Amintim ca ecuatia hiperplanului Hcare trece prin punctul x si este normal pe vectorul u se scrie se scrie:

u(x- x) = 0 .

Distanta de la vectorul x la hiperplanul Heste

d(x, H) = |u(x- x)| ∙||u|| .

Deoarece hiperplanul H considerat trece prin punctul x, considerand ||v||=1, avem:

d(x, H ) = |v( 0- x)|

si deci:

e = – v x.

Dorim sa determinam vectorul pondere v pentru care suma erorilor

J(v) = ,

este minima. Pentru minimizarea functiei de performanta J:RR folosim o metoda de tip gradient.

Valoarea functiei de performanta la pasul k al metodei gradient este

J(v) = ,

unde E=E(v) este multimea punctelor clasificate eronat de vectorul v.

2.2.1.3. Algoritmul de instruire

Metoda de tip gradient consta în construirea unui sir de vectori v,v,…,unde vectorul v se obtine din vectorul de la pasul k folosind regula

v = v+ah .

In aceasta expresie a este un numar pozitiv si reprezinta marimea deplasarii fata de v a vectorului pondere in directia data h. Vom numi hdirectie de coborâre. In metodele de gradient, drept directie de coborâre se considera antigradientul functiei de minimizat. In cazul nostru avem

h = – J(v) = –

tinând cont de regula de derivare pentru produsul scalar

,

obtinem

h = ,

Pasul metodei gradient devine asadar

v = v+a,

Pentru simplitatea algoritmului este mai convenabil ca, la fiecare pas, in loc de a determina multimea E sa se considere toate punctele din multimea e instruire. Vectorul vse modifica doar pentru punctele eronat clasificate de catre vectorul pondere v.

O alta posibilitate este de a forma cu vectorii x, x,…,x, considerati ciclic, un sir de instruire (x). In acest caz avem

x = x, n = 0, 1, 2,…

Procedura standard a perceptronului consta in considerarea la fiecare pas k al algorit-mului a unui singur obiect xdin sirul de instruire.x reprezinta intrarea retelei (vectorul de instruire prezentat retelei ) la pasul k al procedurii de instruire. Vectorul v se modifica daca xeste eronat clasificat de catre v. In caz contrar vectorul pondere ramane neschimbat:

v = v.

Luând a = c, unde c este o constanta pozitiva, regula de corectie se poate scrie:

v =

Constanta c reprezinta cresterea de corectie (rata de invatare sau rata de instruire) a retelei.

In continuare vom prezenta algoritmul standard pentru instruirea perceptronului cu doua clase de instruire.

La primul pas al algoritmului de instruire se initializeaza valorile ponderilor si pragul. Ponderile initiale sunt componentele vectorului .Se aleg pentru ponderile initiale numere reale mici si nenule. Se alege valoarea constantei de corectie c (de obicei 0< c 1). Constanta c controleaza rata de adaptare a retelei. Alegerea ei trebuie sa sadisfaca cerinte contradictorii :pe de o parte exista necesitatea de a obtine o adaptare rapida a ponderilor la intrari si pe de alta parte trebuie sa se tina seama de necesitatea ca menirea intrarilor precedente sa genereze o estimare stabila a ponderilor.

Algoritmul de invatare al perceptronului compara iesirea produsa de retea cu clasa co- respunatoare a vectorului de intrare. Daca s-a produs o clasificare eronata , atunci vectorul pondere este modificat. In caz contrar el ramane neschimbat.Daca la p pasi consecutivi nu se produce nici o modificare a vectorului pondere, atunci toti vectorii(formele) de instruire sunt corecti clasificati de ultimul vector pondere rezultat.Am obtinut un vector solutie si algorit-mul se opreste cu aceasta decizie. Procedura de instruire descrisa mai sus conduce la algorit-mul urmator pentru instruirea perceptronului:

ALGORITMUL PERCEPTRONULUI

P1. Se initializeaza ponderile si pragul.

Se aleg componentele w,…,w si ale vectorului v.

Se pune k:=1.(v este vectorul pondere la momentul initial) .

P2. Se alege constanta de corectie c>0.

P3. Se considera o noua forma de instruire.

Se prezinta retelei o noua forma de intrare x si intrarea dorita (asteptata) corespunzatoare

P4. Se calculeaza iesirea reala generata de perceptron. Iesirea reala este data de semnul expresiei (v)x.

P5. Conditia de oprire.

Se repeta pasul P6 pana când vectorul pondere nu se modifica la pasi consecutivi (p este numarul de ponderi de instruire)

P6. Se adapteaza ponderile si pragul.

Se modifica vectorul pondere folosind regula de corectie

v =

Se pune k:=k+1.

Observatie. Daca algoritmul s-a oprit normal, atunci vetorul v reprezinta o solutie a problemei de instruire. Reteaua care are ponderile date de acest vector a invatat (sa discrimineze ) cele doua clase de instruire.

Daca cele doua clase ce formeaza multimea de instruire nu sunt liniar separabile, atunci algoritmul perceptronului poate continua indefinit.In acest caz procesul de stabilire a ponderilor nu se stabilizeaza, oricât de multe iteratii s-ar efectua.Sirul (v) nu converge spre un eventual vector de separare aproximativ.Rezulta ca în algoritmul perceptronului este necesara o conditie de terminare suplimentara. care poate determina oprirea dupa un numar de iteratii considerat suficient pentru gasirea unui vector de separare (daca el exista).

Pasul P5 din algoritmul perceptronului trebuie, asadar, scris sub forma:

P5. Se repeta pasul P6 pâna când una dintre urmatoarele conditii este satisfacuta:

(I) vectorul pondere nu s-a schimbat la p iteratii consecutive;

(ii) k>N, unde N este numarul maxim de iteratii admise.

Observatie. Nu exista nici o metoda euristica prin care putem aproxima numarul de iteratii necesare pentru instruirea retelei. Numarul N se poate estima prin incercari succesive.

2.2.1.4. Teorema de convergenta

Vom demonstra ca pentru calse liniar separabile, algoritmul converge la un vector de separare.

Teorema de convergenta a pereceptronului.

Fie doua clase de instruire finite si liniar separabile.Fiecare element al multimii de invatare apare de o infinitate de ori in sirul de instruire . In aceste conditii algoritmul perceptronului conduce la un sir , care devine stationar de la un anumit indice, adica exista un intreg pozitiv N , astfle incat

Demonstratie: Pentru a simplifica problema presupunem ca c=1.Aceasta presupunere nu afecteaza generalitatea demonstratiei ( deoarece orice constanta c poate fi introdusa in vectorul de instruire ca o constanta de mormalizare). In plus mai presupunem ca sunt considerati doar indicii i pentru care se realizeaza o corectie.Putem deci scrie:

,

deci (1)

Deoarece clasele de instruire sunt liniar separabile, exista cel putin un vector solutie.Fie un vector solutie. Putem scrie

(2)

Cum este un vector solutie deducem ca

(3)

Din (2) si (3) rezulta ca avem inegalitatea

(4)

Din inegalitatea Schwartz-Cauchy

Obtinem ca

(5)

Din inegalitatile (4) si (5) rezulta ca

(6)

Pe de alta parte avem

avem

(7)

Daca notam

(8)

tinind cont de ipoteza ca la fiecare pas se face o corectie, adica

din (7) rezulta ca

(9)

Adunand inegalitatile (9) obtinute pentru k = 1, 2, …, i, rezulta inegalitatea

(10)

Comparand (6) si (10) se observa ca pentru valori ale lui i suficient de mari , aceste inegalitati sunt contradictorii, Indicele i nu poate fi maui mare decat care este o solutie a ecuatiei:

(11)

obtinuta prin egalarea partilor din dreapta a inegalitatilor (6) si (10).

Rezulta, asadar, ca, daca clasele sunt liniar separabile, algoritmul converge intr-un numar finit de pasi.

2.2.1.5. Algoritmul Gallant

S.Gallant (1986) a propus o modificare a algoritmului perceptronului, prin care acesta devine aplicabil chiar chiar si pentru clase neseparabile. Algoritmul urmareste determinarea unui vector pondere, numit optimal, capabil sa clasifice corect numarul maxim posibil de forme de instruire. Ideea esentiala a algoritmului propus de Gallant consta in a pastra in “buzunarul nostru“ vectorul pondere care a realizat cea mai lunga secventa de clasificari consecutive corecte, pâna la momentul curent.Clasificarile eronate determina o modificare a vectorului pondere, exact ca in algoritmul perceptronului.Clasificarile corecte pot determina o schimbare a vectorului memorat, lucru care se intâmpla daca vectorul curent clasifica in mod corect o secventa mai lunga decât cea realizata de ultimul vector memorat.Gallant a demonstrat ca pe masu ra ce numarul de iteratii creste, probabilitatea ca vectorului memorat sa fie optimal se apropie de unu. Este insa posibil ca numarul de iteratii care asigura obtinerea unui vector obtimal sa fie foarte mare.

Pentru completitudinea expunerii, dam mai jos pasii algoritmului Gallant de stabilire a unui vector pondere (aproape) optimal.

ALGORITMUL GALLANT AL PERCEPTRONULUI

P1. Initializarile.

Se alege rata de instruire c>0.

Se alege un vector de pondere v arbitrar.

Se alege N – numarul maxim de iteratii.

Se initializeaza vectorul aproximativ de separare punând

B:=v.

Se initializeaza numarul nB al formelor de instruire corect clasificate de vectorul B, punând nB:=0.

P2. Se repeta pasii P3-P7 pâna când este îndeplinita una din conditiile urmatoare:

(i) vectorul stare nu s-a schimbat la p pasi consecutivi. In acest caz avem n=p.

(ii) k> N.

In cazul (i) s-a obtinut un vector de separare. In cazul (ii) B este un vector aproximativ de separare.

P3. Se pune n:=0.

P4. Ajustarea ponderilor

Se prezinta retelei forma de instruire x.

Se initializeaza o variabila locala a, punând

a: =

Se modifica vectorul de pondere folosind regula perceptronului, adica punând

v :=

P5. Daca a=0 se pune

n:=n+1

si

k:=k+1.

Se merge la pasul P4.

P6. Modificarea continutului buzunarului.

Daca a=1, atunci se compara clasificarea realizatade vectorul vsi cea realizata de vectorul B (reprezentând “continutul buzunarului”).

(i) Daca n=0, atunci se trece la pasul P7.

(ii) Daca este îndeplinita conditia n>nB, atunci se pune

nB:=n

si

B:= v.

P7. Se pune k:=k+1.

Se trece la pasul P3.

Observatii:

(i) n reprezinta numarul de forme de instruire corect clasificate de vectorul pondere curent v.

(ii) B reprezinta cel mai bun vector pondere ce poate fi obtinut în Niteratii ale procesului de instruire.

Teorema de convergenta a algoritmului perceptronului modificat (algoritmul Gallant) se formuleaza astfel:

Teorema de convergenta a algoritmului lui Gallant.

Pentru orice probabilitate p<1, exista un numar N, astfel încât dupa nN iteratii ale algoritmului perceptronului modificat, probabilitatea ca vectorul memorat sa fie optimal depaseste p.

Daca multimea de instruire contine doua clase separabile, algoritmul Gallant va produce, conform teoremei de convergenta a perceptronului, un vector de separare. Pentru clase neseparabile, chiar pentru probleme de marime medie, nu este sigur ca vomobtine un vector optim într-un numar rezonabil de iteratii. Convergenta spre vectorul optim este asimptotica. Cu toate acestea, s-a constatat ca algoritmul produce vectori pondere satisfacatori, care aproximeaza numarul optim de clasificari corecte. Aceasta face ca algoritmul propus de Gallant sa aiba utilitate practica deosebita.

2.2.2 LAM – Memorie liniar asociativa

Modelul Hebb ( Asociator liniar )

Ori de cate ori o conexiune sinaptica coincide cu emiterea actiunii de raspuns a neuronului, ponderea conexiunii sinptice este argumentata (modificata) a.i. daca:

– efect excitator valoarea ponderii marita

– efect inhibitor valoarea ponderii micsorata.

– informatia asocierilor dintre si pentru toate exemplele din esantionul de instruire

unde

Definim si

Instruirea Hebb: -encodare

Decodare: -filtrare liniara la nivelul matricii de memorie si o filtare neliniara printr-o functie semnal.Raspunsul calculat : .Iesirea S(y) unde S functia semnal: prag sau S(x)=x.

Minimizarea erorii.Daca sunt vectori ortonormati, atunci memoria Hebb encodeaza fara eroare esantionul .Vom considera functia semnal S(x)=x ,

Se doreste , pentru forma de intrare . Avem:

,

deci putem memora perfect un numar de vectori N.

Daca =1, j =1,N , atunci:

,

unde= este zgomotul (perturbatia) indusa de restul formelor memorate asupra asocierii ().

2.2.3. OLAM – Memorie liniar asociativa optimala

Invatarea se face conform unei functii de performanta.Functia de performanta aleasa, care reprezinta masura erorii corespunzatorare arhitecturii, este eroarea medie patratica , realizandu-se astfel memorarea optimala pentru esantionul de invatare din punct de vedere al erorii medii patratice. Memoria obtinuta pe baza acestei functii de performanta se numeste OLAM ( optimal LAM ).

Definim si

( eroarea medie patratica corespunzatoare lui W)

Cautam solutie a problemei E(W).

Teorema Penrose Pentru orice matrice AM(R) exista si este unixca matricea XM(R) astfel încât

(1) AXA=A

(2) XAX=X

(3) (AX)=AX

(4) (XA)=XA

X=A – pseudo-inversa Penrose corespunzatoare lui A.

Teorema lui Greville: Metoda iterativa de calcul a pseudo inversei:

Fie AM(R). Notam cu coloanele matricii A si

M (R), unde este prima coloana din A, respectiv .

Regula de clcul:

unde

si

Instruirea: Pentru esantionul de invatare

Definim si

Matricea de memorie este

Teorema W= X solutie a problemei variationale E(W).

Demonstratie: E(W)=,

, ’

E(W)== .

tr(AA)= tr(AA)=

E(W)=tr(()())

()()= () ()= ()

()=+ EMBED Equation.2 ++=+ deoarece ()()= =

deoarece X()= si

unde: , ,

=

= , WM(R) =

Pentru

Deci solutie a problemei variationale q.e.d.

2.2.4 ADALINE / MADALINE

Conceptul de ADALINE ( Adaptive Linear Neuron) a fost introdus de Windrowsi Hoff in 1959, iar cel de MADALINE ( many adaptive linear neurons) a fost formulat de Winter si Baxter in 1987 consta din compunerea a mai multor retele adaline.

Windrow a considerat esantioane bernouliene asupra repartitiei de functie de densitate . Deci vector aleator repartizat , independenti, raspunsurile corecte sun vectori aleatori.

= var.aleatoare;=var. aleatoare;W=vector constant.

unde : , ,

2.2.4.1 Functia de performanta

Se foloseste o metoda de tip gradient pentru cautarea unui punct de minim: directia celei mai rapide coborâri =RW=q,

W=

, variabila aleatoare.

2.2.4.2 Algoritmi de instruire

Algoritm de instruire de tip corectare a erorilor ADALINE (regula , regula Widrow ):

():W unde

In continuare vom prezenta doi algoritmi:

MRI – Widrow 1960

MRII – Windrow,Winter,Baxter 1987

Intrarile si iesirile sunt bipolare.Reteaua contine un layer ascuns.Functia prag

Algoritmul MRI

P0. Initializam si cu valori aleatoare din intervalul [0,1).Selectam valoarea initiala pentru rata de instruire .

P1. Atata timp cat conditia de oprire nu este indeplinita efectuez P2 – P8

P2. Pentru fiecare pereche ((),) cu ,, din secventa de instruire repeta P3 -P7.

P3. Aplic forma () unitatilor din .

P4. Calculam activarile corespunzatoare neuronilor din

P5. Calculam iesirea corespunzatoare neuronilor din

P6. Calculam activarea neuronului din layerul

si iesirea: y = S(a)

P7. Calculam eroarea (y-) si reactualizam ponderile sinaptice

– daca y = atunci ponderile sinaptice raman nemodificate.

– daca y atunci:

a) daca =1 atunci se reactualizeaza ponderile sinaptice aferente neuronului pentru care activarea este mai apropiata de zero.

b) daca = atunci se reactualizeaza ponderile sinaptice aferente neuronului pentru care activarea pozitiva

P8. Verificam conditia de oprire. Daca la sfarsitul unei epoci nu au survenit modificari ale vectorilor sinaptici (daca fluctuatiile sunt foarte mici) respectiv daca P2 a fost efectuat de un numar prestabilit de ori, atunci STOP, altfel continua .

Algoritmul MRII

P0. Initializarea ponderilor W, b, bsi a lui .

P1. Efectuam pasii P2 – P8 pâna când conditia de oprire este îndeplinita.

P2. Pentru fiecare pereche bipolara din S efectuam P3 – P7.

P3-P6. Calculeaza iesirea ca la MRI.

P7. Evalueaza eroarea si rectualizeaza ponderile.

Daca yatunci pentru fiecare unitate a layerului ascuns F, a carui activare este suficient de apropiata de zero ((-0.25, 0.25)) efectuam P7a si P7b. Unitatile din Fsunt solicitateîn ordinea crescatoare a magnitudinilor valorilor absolute corespunzatoare activarilor interne.

P7a. Modifica iesirea unitatilor selectate

(daca z=1 atunci z= -1 si daca z= -1 atunci z=1)

P7b. Reactualizeaza raspunsul retelei.

Daca eroarea este limitata, atunci reactualizeaza ponderile sinaptice corespunzatoare unitatii conform regulii si noua valoare de iesire ca raspuns corect.

Observatie: fiecare z, z este câte o ADALINE.

P8. Verifica conditia de oprire ca la algoritmul MRI.

2.2.5. BNP -BACK PROPAGARE

2.2.5.1. Introducere

In acest capitol vom prezenta algoritmul de propagare înapoi a erorii pentru instruirea retelelor neuronale cu unul sau mai multe straturi ascunse. Vor fi studiate unele variante ale acestui algoritm si vor fi facute o serie de consideratii euristice utile pentru proiectarea unei retele caere foloseste algoritmul de propagare înapoi sau algoritmul de retro-propagare.

Algoritmul de propagare înapoi (Back Propagation, BP) este considerat, în mod uzual, ca fiind cel mai important si mai utilizat algoritm pentru construirea neuronale. Rapida sa popularitate a constituit un factor important în revigorarea directiei conexioniste, în Inteligenta Artificiala. El are o istorie interesanta, care va fi amintita pe scurt în continuare.

Ideea propagarii înapoi a fost redescoperita de mai multe ori. Primul care a utilizat aceasta tehnica a fost Paul Werbos (1974), însa el nu a exploatat posibilitatile metodei de a genera ponderile de conexiune pentru neuronii straturilor intermediare (ascunse). Algoritmul a fost redescoperit de David Parker (1982) si popularizat de catre Rumelhart si grupul PDP în cunoscutele volume “Parallel Distributed Processing”(1986). Autorii din grupul PDP au sugerat ca algoritmul de propagare înapoi sau regula delta generalizata (cum au numit-o ei) poate depasi limitarile algoritmului perceptronului, asa cum au fost enumerate de Minsky si Papert (1969). De asemenea, algoritmul de propagare înapoi a fost considerat un succes al directiei pe care “conexionismul” o reprezinta în Inteligenta Artificiala.

Algoritmul de retro-propagare a ajuns rapid sa domine literatura consacrata retelelor neuronale. In practica, algoritmul a fost utilizat, de exemplu, în cadrul unui experiment interesant pentru a sintetiza vocea dintr-un text scris, fara a face apel la reguli ale unui sistem expert (Sejnowski si Grossberg, 1987). O banda magnetica continea o bogata experienta de instruire. Rasunetul pe care acest experiment l-a avut, si nu doar printre specialisti, a determinat popularizarea sa rapida ca “un nou algoritm de instruire care învata din experienta”. S-a apreciat ca algoritmul de backpropagare ar putea avea numeroase aplicatii potentiale: recunoasterea în timp real a vorbirii, traducerea automata, roboti inteligenti care se auto-depaneaza, vedere artificiala etc. Psihologii si neurofiziologii au cautat sa identifice algoritmul de propagare înapoi

în functionarea creierului uman si a sistemului nervos central.

Pe de alta parte, popularitatea acestei metode de învatare a provocat si numeroase critici. Din punct de vedere algoritmic, propagarea înapoi foloseste pentru instruire o informatie nelocala. Uneori algoritmul nu converge sau, daca ajunge la o solutie, aceasta reprezinta un minim local. De asemenea, timpul de instruire este relativ ridicat datorita unui factor de învatare desemnat interactiv. Din punct de vedere neurofiziologic, cel putin pâna acum, nu s-a descoperit motivatia (analogia) biologica a algoritmului de retro-propagare.

Algoritmul de propagare înapoi este o metoda de instruire în retelele neuronale multistrat cu transmitere înainte (feedforward) , în care se urmareste minimizarea erorii medii patratice printr-o metoda de gradient.

Este interesant de comparat aceasta procedura cu algoritmul Widrow-Hoff (regula delta). In timp ce algoritmul de propagare înapoi actioneaza asupra unei arhitecturicu mai multi neuroni organizati în straturi multiple, dintre care unele straturi sunt ascunse iar neuronii au functii de iesire sigmoidale, algoritmul Widrow-Hoff opereaza pe un model cu un singur neuron, având drept functie de activare o functie liniara (de regula functia ). Functia de performanta (eroarea retelei) poate avea în algoritmul delta generalizat un minim local, desi nu avem certitudinea ca metoda de minimizare a erorii patratice va conduce catre o solutie globala.

2.2.5.2. Arhitectura multistrat a retelelor neuronale

Retelele nuronale considerate pana acum au fost, cu putine exceptii, retele simple, cu doua straturi, in care o multime de forme(obiecte) de intrare este transformata intr-o multime de forme de iesire peste un camp de iesire. In astfel de arhitecturi nu exista nici o unitate ascunsa, ele contin doar unitati de intrare si unitati ( neuroni ) de iesire. Deci, nu are loc nici o reprezentare interna a formelor de intrare . Codificarea formelor furnizata de intrarea retelei este suficienta.

Caracteristica esentiala a retelelor cu doua straturi este ca ele proiecteaza forme de intrare similare in forme de iesire similare, fapt ce permite sa faca generalizari rezonabile si sa prelucreze acceptabil forme care nu li s-au mai prezentat niciodata. Similaritatea formelor intr-un sistem de Prelucare Paralela Distribuita este masurata prin gradul lor de suprapunere. Suprapunerea formelor nu este determinata de metoda de invatare, ci este realizata in afara sistemului, de catre sursa formelor de intrare.

Restrictia ca forme de intrare sa conduca la iesiri similare poatew genera o adaptabilitate a sistemului de a invata anumite functii (proiectii sau transformari ) intrarea – iesirea. Sa admitem ca reprezentarea furnizata retelei de lumea exterioara este realizata astfel incat structurile de similaritate ala formelor de intrare si de iesire sunt foarte diferite. In acest caz, o retea care nu construieste o reprezentare interna, deci nu are unitati ascunse, va fi incapabila sa realizeze functia necesara. Un exemplu clasic in acest sens este problema realizarii functiei sau exclusiv(exclusive OR, XOR), ilustrata in Tabelul 1.

Observam ca formele cele mai nesimilare (0 0 si 1 1) genereaza valori de iesire identice.Aceasta problema si multe altele asemanatoare cu ea nu pot fi rezolvate de retele fara unitati ascunse, capabile sa creeze prpria reprezentare interna a datelor de intrare.

Daca formele de intrare sunt modificate, astfel incat sa contina o a treia intrare avand valoarea 1, numai daca primele doua intrari au valoarea 1 (conform Tabelului 2), atunci un sistem cu doua straturi (fara campuri ascunse) ar putea fi (in anumite conoditii) capabil sa rezolve problema XOR.

Minsky si Papert (1969) au intreprins o analiza atenta a conditiilor in care retelele cu doua straturi sunt in stare sa realizeze functii cerute. Ei au aratat ca intr-un numar mare de cazuri interesante, retelele de acest tip nu pot rezolva problemele respective. Pe de alta parte cei doi autori au considerat si un model ce contine un strat de unitati ascunse de tipul perceptronului simplu. Satratul ascuns realizeaza o extindere a formrlor de intrare, in sensul ca exista intotdeauna o recodificare, adica o reprezentare interna convenabila a formelor in unitati ascunse. Prin aceasta recodificare, similaritatea formelor in raport cu unitatile ascunse permite realizarea oricarei functii (transfer) de la campul de intrare la cel de iesire.

In cazul problemei XOR, adaugarea celei de-a treia caracteristici schimba structura de similaritate a formelor suficient de mult pentru a permite invatarea unei solutii.

Dupa cum se observa in Figura 2, problema XOR poate fi rezolvata cu un singur neuron ascuns. Cifrele asociate sagetilor indica ponderile conexiunilor, numerele din noduri arata valoarea pragului iar linia punctata desemneaza o conexiune inhibitoare (cu pondere negativa).

Pragul t=1.5 al unitatii ascunse ne asigura ca aceasta unitate va fi activata numai daca ambele intrari sunt 1. Ponderea -2 a conexiunii ascunse cu neuronul de iesire ne indica o conexiune inhibitoare, care ne asigura ca unitatea de iesire nu va fi activata cand ambele intrari sunt 1. Din punctul de vedere al iesirii, neuronul ascuns este tratat ca si un alt neuron de intrare. Este ca si cum formele de intrare ar avea nu doua ci trei elemente binare , confor Tabelului 2.

Este interesant de remarcat ca in arhitectura din Figura 2, neuronii de intrare sunt conectati cu neuroni apartinand la doua straturi difwerite, lucru care de regula nu apare in cazul retelelor multistrat.

Reprezentarea interna realizata de unitatile ascunse poate fi considerata drept o memorie asociativa. Utilizarea acestei memorii impreuna cu marirea dimensiunii formelor de intrare (uneori si a celor de iesire) reprezinta o metoda utila pentru rezolvarea unor probleme de instruire dificile.

In cazul retelelor neurale fara neuroni ascunsi, exista algoritmi de instruire, cum sunt algoritmul perceptronului si procedura Windrow-Hoff, care functioneaza pentru o mare variretate de probleme.In retelele cu neuroni ascunsi , nu exista un algoritm de instruire simplu care sa prezinte caracteristici comparabile.

2.2.5.3. Topologia retelei

Algoritmul de backpropagation este un algoritm de coborâre pe gradient. Invatarea este de tip supervizata. Arhitectura feedforward cu unul sau mai multe layere ascunse.

1 j m

1 ………………. q …………………. p

1 i n

Unitatile q si j realizeaza o filtrare neliniara a activarii unitatii cu cate o functie semnal

Propagarea informatiei in arhitectura este unidirectionat

.

Instruirea se face pe baza unui esantion de exemple

,

Transferarea de la la a informatiei se realizeaza prin filtrarea la nivelul fiecarui etaj:

– liniara prin intermediul matricilor sinaptice

– neliniara prin intermediul functiilor semnal selectate.

Matricile de memorie este np+pm dimensionala depinzand de matricile W si V:

Vectorul de intrare .

3.2.5.nr. Functia de performanta

Eroarea totala este: – eroarea globala relativ la esantionul S si care reprezinta functia de performanta. Se foloseste algoritm de cautare de tip gradient pentru minimizarea erorii (np+pm – dimensional).

C – activarea rezultata prin neuronul j din F pentru forma x.

h – activarea rezultata pentru neuronul q din Fpentru forma x.

Y= j=1,…,m

=

h=

.

2.2.5.4. Algoritm de instruire

Teorema

Demonstratie:

Daca S(x)=

. q.e.d.

S se numeste velocitate (viteza de transmitere a informatiei la nivelul neuronului j).

Notatii:

– masura informationala a erorii comise la nivelul lui j pentru fiecare forma x.

Deci – factorul de corectie pentru w.

si – factorul de corectie pentru v

Deci =

Algoritmul BPN

P0. Neuronii au un coeficient de deplasare (bias) – pondere a unei intrari suplimentare

Initializam ponderile sinaptice (v),(w) prin valori mici.

P1. Cat timp nu (conditie oprire ) executa P2-P9

P2. Pentru fiecare (x, ) executa P3-P8

Propagarea feedforward:

P3. Aplica layerului si propaga , i = catre toate unitatile din

P4. Pentru fiecare neuron din

calculam activarea

se apilca si se propaga valoarea calculata catre toti neuronii din

P5. Pentru fiecare neuron din

calculam activarea

c=w+

calculam iesirea

y=

Backpropagarea erorii

P6. Fiecare unitatedin primeste componenta asociata din raspunsul corect a (target)si calculeaza

Calculam corectia pentru ponderile w

=

=

Transmite catre valorile astfel calculate.

P7. Pentru fiecare unitate din calculam termenii de corectie

Calculam coeficientii de corectie

Calculam corectia pentru ponderile v

P8. Reactualizam sistemul de ponderi:

Pentru fiecare unitate : , q = o,p

Pentru fiecare unitate : , i = o,n

P9. Verific conditia de oprire a procesului de instruire (numarul de pasi sau prag pentru eroare)

Modul de operare:

P0. Initializez , prin valori determinate in procesul de invatare

P1. Pentru fiecare forma de test x execut P2-P4

P2. Aplic x layerului

P3. Pentru q=o,p calculam

P4. Pentru j=o,m calculam

Rasupuns:

2.2.5.5. Variante ale algoritmului de Backpropagare

2.2.5.5.1. Varianta momentum

Rumelhart, Hinton si Wiliams (1986) au propus o alta metoda pentru marirea vitezei de convergenta a algritmului de propagare inversa. Tehnica acestor autori consta in adaugarea unui termen , numit moment , la corectia ponderii. Acest termen moment este proportonal cu precedenta modificare a ponderii si determina ca aceasta variatie sa se faca in acea directie cu cea a corectiei precedente. Putem astefel afirma ca reteaua a devenit mai “conservatoare” in sensul ca directiile noi nu sunt favorizate.

Regula de corectie pentru neuronii stratului de iesire se va scrie sub forma:

unde reprezinta termenul moment.Termenul moment se defineste ca:

Coeficientul al momentului se alege de obicei in jurul valorii 0.9.Coeficientul determina efectul precedentei schimbari a poderiii asupra directiei curente de miscare in spatiul vectorilor pondere.

Este interesant de cercetat efectul considerarii termenului moment in regula de ajustare asupra miscarii vectorului pondere.

Acest efect a fost studiat pentru diferite aliuri ale functiei de eroare. De exemplu suprafata de eroare poate prezenta “vai” adinci si inguste, susceptibile sa contina puncte de minim. Folosin metoda momentului, reteaua tinde sa urmeze fundul “vailor” in loc sa trreaca rapid dintr-o parte in alta a acestora. Asadr metoda momentului permite o tratare corecta (o “filtrare”) a variatiilor bruste ale suprafetei de eroare. In prezenta unei astfel de suprafete accidentate, pentru a preveni erorile (oscilatiile) divergente (indepartarea de la un punct de minim), este necesar sa se faca pasi foarte mici, ceea ce determina un progres lent al instruirii. Adaugarea unui termen suplimentar in regula de corectie permite ca pasii efectivi ai modificarii vectoruluipondere sa fie mai mari , fara ca prin aceasta sa se treaca peste punctele de minim.

Pentru scopuri practice, rata de invatare se poate alege cat mai mare posibil, cu conditia de a nu conduce la oscilatii. Dupa cum am vazut una dintre tehnicile de marire a vitezei de invatare este includerea termenului moment.Experimental se poate constata ca obtinemacelasi rezultat luand =0 si reducand valoarea lui , ceea ce are ca efect instruirea lenta. Invatarea este mult mai rapida pentru valori mari ale coeficientilor

si .

Se constata ca nici una din metodele de instruire analizata nu reprezinta un panaceu. tehnica momentului functioneaza bine pentru unele probleme dar are un efect redus, sau chiar negativ, in cazul altor aplicatii.

2.2.5.5.2. Varianta netezirii

Sejnowski si Rosenberg (1987) au propus o generalizare a metodei momentului bazata pe o netezire exponentiala . Pentru anumite aplicatii, aceasta tehnica este superioara metodei momentului. Regula de corectie folosita este

unde:

In aceasta formula si are semnificatia unui coeficient de netezire.

Se observa ca daca =0, regula se reduce la forma standard a algoritmului de backpropagare. Acum netezirea este minima si intreaga corectie provine din schimbarea nou calculata.

Daca =1 obtinem

In acest caz, noua ajustare calculata este ignorata si se repeta ajustarea precedenta deorece avem

Daca , atunci corectia ponderii este netezita cu o cantitate proportionala cu .

2.2.5.5.3. Varinata Batch-updating

Spre deosebire de algoritmul de backpropagare unde reactualizarea sistemului de ponderi () , () se facea dupa fiecare prezentare a unei perechi , aici,strategia este ca, corectiile sa fie acumulate dar neaplicate pe durata unei epoci.

Euristica: Reacualizarile sunt efectuate la sfarsitul unei epoci prin utilizarea coeficientului de actualizare ce rezulta prin medierea coeficientilor acumulati.Apare un efect de “netezire” a coeficientilor de corectie, din care rezulta o eficienta mai mare in sensul timpului de instruire, dar posibila degradare a calitatii punctului calculat la terminarea procesului (posibil punct de minim local in loc de minim global).

2.2.5.5.4. Varianta Delta-har-Delta

Spre deosebire de algoritmul de backpropagare unde rata de invatare era constanta, aici, pentru fiecare conexiune sinptica rata de invatare proprie este variabila in timp.

Euristica: Daca la nivelul unei conexiuni sinaptice pe o anumita durata de timp survin modificari in aceiasi directie ((,), semnul modificat) atunci rata de invatare aplicata in reactualizarea acelei ponderi sinaptice trebuie incrementata.In caz contrar rata de invatare trebuie decrementata.

Definim:

pentru

pentru

unde constanta.

valorile optime ale constantelor fiind : = 0.035 si = 0.333

2.2.5.5.5. Varinata a doua a ratei de instruire variabile

Regulile de corectie corespunzatoare acestei metode sunt:

In general se considera ca = , pentru fiecare pas k al metodei.

Pentru a evita oscilatiile care pot aparea in jurul solutiei potime, este necesar ca ratele de instruire sa descreasca in timp. Aceasta descrestere nu trebuie sa fie nici prea rapida, nici prea lenta. Admitem ca sirul descreste suficient de lent daca seria sumelor partiale este divergenta.Deci avem conditia

Cu cat coeficientii descresc mai lent, cu atat mai rapid decurge instruirea retelei.

Conditia ca sirul () sa descreasca suficient de rapid se eprima prin cerinta ca seria patratelor acestor coeficienti sa fie convergenta, adica

Cu cat coeficientii descresc mai repede, cu atat vectorul pondere “uita” formele deja invatate.

Daca rata de invatare la pasul k este

atunci cele doua conditii precedente sunt satisfacute.

Conditiile stabilite anterior reprezinta pentru cazul backpropagarii, o formula matematica a ceeea ce Grossberg numeste dilema stabilitate-plasticitate. Conform acestei dileme, o retea neurala trebuie sa satisfaca doua conditii contradictorii:

(i) pe de o parte reteaua trebuie sa fie suficient de stabila pentru a-si aminti formele invatate anterior si

(ii) pe de alta parte, reteaua trebuie sa fie suficient de plastica pentru a putea invata noi forme.

Sa mai notam ca, in cazul algoritmului Windrow – Hoff conditii analoage cu cele de mai sus garanteaza convergenta algoritmului. In cazul algoritmului de backpropagare, conditiile privind coeficientii nu garanteaza convergenta, ci asigura doar o comportare “rezonabila” a algoritmului.

2.2.5.5.6.Varianta algoritmului robust

Statistica robusta (Huber 1981) reprezinta o tehnica utila pentru ameliorarea procesului de invatare. Robustetea se refera la insensibilitatea algoritmilor la mici perturbatii ale densitatii de probabilitate. Daca se presupune o anumita lege a distributiei de probabilitate (normala Cauchy, etc.), robustetea poate insemna aplicabilitatea metodelor de estimare atunci cand densitatea de probabilitate contine deviatii de la legea considerata.

In practica, estimatorii statistici robusti ignora obiectele de instruire ce reprezinta puncte izolate. Punctele atipice (izolate) corespund unor observatii putin frecvente, ce difera semnificativ de celelalte situatii intalnite. In cazul nostru o observatie este o pereche intrare-iesire (). Punctele izolae pot altera rezultatele algoritmului standard (nerobust) de backpropagare. Aceasta descriere poate sa determine o incetinire a convergentei sau sa duca sistemul spre o stare de minim local mai putin reprezentativa.

Din discutia referitoare la algoritmul Widrow – Hoff, retinem ca masurile de eroare de tipul eroriimedii patratice tind sa suprapondereze punctele izolate din multimea de instruire.Din acest punct de vedere, eroarea absoluta

este preferabila erorii patratice. Eroarea absoluta considerata tinde sa atenueze mai bine observatiile(datele) externe.

Backpropagarea robusta inlocuieste , in formula de mai sus, eroarea scalara

prin estimarea s(), unde s este o functie de suprimare a erorii.

Functia de suprimare liniara

nu este robusta.

Sa consideram o distributie normala a datelor de intrare. Aceasta revine la presupunerea ca datele sunf formate din puncte care se aglomereaza, formand clase sferice sau elipsoidale, in jurul unui punct prototip. Prototipul corespunde unei valori medii a datelor. In acest caz, functia prag

s(x)=max[-t,min(t,x)] ,

unde t este un prag convenabil, furnizeaza un estimator robust.

Daca densitatea de probabilitate respecta distributia Cauchy avand forma

sau o distributie asemanatoare cu dispersie infinita, atunci

reprezinta o estimare robusta a erorii.

In acest caz , s() se apropie de zero pentru erori foarte mari si aproximeaza pentru valori mici ale erorii.

Putem da, acum, algoritmul robust de backpropagare corespunzator distributiei Cauchy.

Corectia pentru neuronii campului de iesire se scrie facand inlocuirea

s()

Regula de corectie va fi:

si

2.3. ARHITECTURI NEURALE RECURENTE

2.3.1. Introducere

In aceasta sectiune vom studia diferite modele de retele neurale (RN) folosite pentru a memora si regasi asociatii. Memoria asociativa este una dintre functiile fundamentale ale mintii umane. Asociatiile care se considera în retelele neurale au o forma simpla. In mod uzual, printr-o asociatie întelegem o pereche ordonata de forme (R,S) unde R este forma cheie iar S este forma asociata. In acest caz, o forma este un vector de componente reale.

Multimea de instruire consta dintr-o lista de asociere formata din perechile

(R, S), (R, S), … , (R, S),

unde toti vectorii Rau aceeasi dimensiune n iar vectorii Ssunt m-dimensionali. In retelele asociative, asociatiile vor fi memorat în conexiunile ponderilor neurale. Reprezentarea fiecarei asociatii va fi distribuita peste mai multe conexiuni si, reciproc, fiecarte conexiune este implicata în memorarea mai multor asociatii.

In cele ce urmeaza, vom considera modele de retele neurale asociative (RNA) binare (având doua valori ale semnalului de iesire). Acestea au la baza neuronul clasic McCullock – Pitts. Un exemplu de retea neurala artificiala binara este memoria asociativa bidirectionala (BAM).Modelul autoasociativ al lui Hopfield (memoria sau reteaua Hopfield) este un alt model de retea neurala care s-a impus în teoria si practica conexionismului.

2.3.2. Memorii asociative bidirectionale

2.3.2.1. Notiuni de baza

O retea asociativa bidirectionala (Kosko, 1987) este o retea neuronala ce consta din doua straturi de neuroni complet interconectate. Doi neuroni din acelasi strat nu sunt interconectati, însa fiecare neuron poate avea (sau nu ) o legatura cu el însusi. Toate conexiunile interneuronale sunt bidirectionale. Informatia circula Intre cele doua straturi, în ambele sensuri. daca dinamica straturilor conduce la o comportare de ansamblu stabila a retelei, atunci structurile de acest tip se numesc memorii asociative bidirectionale (BAM).

2.3.2.2. Asociatorul liniar

Consideram multimea de instruire compusa din perechile

(x, y), (x, y), … , (x, y),

unde xR si xR. Ca de obicei, vom considera ca xsi y sunt vectori coloana si presupunem ca vectorii x sunt ortonormati:

|| x||=1, I=1,2, … , p

(x, x)=0, ji.

Aceste conditii se mai pot scrie sub forma

(x) x=,

unde este simbolul lui Kronecker.

In acest caz, putem construi o memorie interpolatorie definind functia

A(x)=()x.

Vectorii fiind ortonormati, avem

A(x)=.

Am obtinut, deci

A(x)= y.

Daca x este un vector astfel încât

x= x+d,

atunci iesirea corespnzatoare este

A(x)=()( x+d)= x+()d.

Cu notatia

e=()d,

iesirea retelei se mai poate scrie

A(x)= y+e.

Acest mecanism de memorare a listei de asociere

(x, y), (x, y), … , (x, y),

poate fi considerat drept o varianta a legii de învatare a lui Hebb si se numeste regula produsului exterior.

Se pune în mod natural întrebarea, ce ponderi trebuie sa aiba reteaua, pentru ca ea sa realizeze functia A. Examinând expresia acestei functii, rezulta ca putem defini ponderile asociatorului liniar ca fiind elementele unei matrici W, unde

W=.

Se observa ca matricea ponderilor este suma matricelor de corelatie ale formelor din multimea de instruire.

Fie r un neuron din câmpul de iesire F si s un neuron din câmpul de intrare F. Ponderea w a conexiunii (r,s) se va scrie

w=.

Functia A se poate scrie, acum, sub forma

A(x)=Wx.

Sa notam ca W nu este, de regula, simetrica. Ponderea conexiunii (r,s) nu este, deci, egala cu cea a conexiunii (s,r):

w w, pentru rs.

Notam cu X matricea (n x p), având pe coloana i componentele vectorului x:

X=( x,x, … , x).

Notam, de asemenea, cu Y matricea (m x p ) ce are pe coloana i vectorul y:

Y=( y,y, … , y).

Cu aceste notatii, matricea W a ponderilor conexiunilor se va scrie sub forma

W=YX.

2.3.2.3. Functionarea Asociatorului Liniar

Dupa calcularea matricei W, daca retelei asociative I se prezinta vectorul sde intrare x, ea va genera vectorul de iesire y, unde

y=A(x)=Wx.

Tinând cont de forma matricei W, iesirea retelei se scrie

y=x=.

Se observa ca iesirea y a retelei neurale este o combinatie liniara a vectorilor

y,y, … , y

Coeficientii acestei combinatii liniare sunt produsele scalare

xx,xx, … , xx.

Din acest motiv, o astfel de retea se numeste Asociator liniar.

Consideram, acum, un caz particular de asociator liniar. Daca formele fiecarei asociatii coincid, adica daca avem y= x , i=1,2, … , p,

atunci obtinem o retea numita Asociator liniar. In acest caz, matricea W a conexiunilor este suma matricelor de autocorelatie corespunzatoare vectorilor de instruire

x,x, … , x.

Avem, deci

W=.

In general, un autoasociator este o retea instruita sa reproduca elementele unei multimi de învatare

x,x, … , x.

Daca retelei i se prezinta vectorul x, se doreste ca, dupa câteva iteratii (sau chiar dupa una singura), iesireas retelei sa fie, de asemenea, x. Astfel, reteaua a memorat (codificat) multimea de instruire.

Este interesant de remarcat în cazul autoasociatorilor, ca si al oricarei memorii, comportarea acestora când li se prezinta intrari ce difera usor de exemplele de instruire deja memorate. Daca intrarea este apropiata (în sensul unei anumite distante) de x, atunci reteaua tinde sa reproduca forma x. Rezulta, astfel, ca autoasociatorii pot fi considerati ca fiind memorii adresabile prin continut. Exemplele de instruire memorate reprezinta cunostinte învatate (ce pot fi considerate drept “amintiri”). Autoasociatorul va fi capabil sa regaseasca o informatie completa, pornind de la elemente partiale (incomplete) sau de la versiuni distorsionate ale respectivei informatii.

Aceaste discutie poate fi extinsa si la modele mai generale de memorii implementate cu retele neurale, consideratiile precedente ramânând valabile.

Revenind la Asociatorul liniar, sa notam ca acesta nu implica nici o instruire. Matricea W a ponderilor se calculeaza pornind de la formele multimii de învatare si aceasta matrice nu se modifica în cursul functionarii retelei.

De asemenea, Asociatorul liniar prezinta fenomenul de regasire perfecta (“perfect recall”):

A(x)=W x= x, I=1,2, … , p.

Daca vectorii xnu mai sunt ortogonali, regasirea cu regula Hebb considerata (legea porodusului exterior) nu mai este perfecta.

Deoarece vectorii x sunt din R, rezulta ca exista cel mult n vectori reciproc ortogonali. Aceasta înseamna ca n este numarul maxim de vectori ce pot fi memorati cu regasire perfecta, folosind agoritmul de învatare bazat pe regula Hebb considerata.

O alta regula de regasire se poate defini folosind produsul boolean a doi vectori. Sa admitem ca vectorii xsi yau componentele 0 si 1. In acest caz, matricea W se defineste ca

W= ,

unde cu am notat suma booleana. Rezulta ca ponderea conexiunii (i, j) se va scrie

w=yx … yx.

2.3.2.4. Memorii Liniare Optimale

In cazul în care vectorii xnu sunt ortonormali, putem sa definim o masura a erorii Asociatorului liniar. Daca r este iesirea reala a asociatorului si yeste iesirea dorita, se defineste eroarea asociata perechii (x ,y) ca fiind

e=, i=1, … , p.

Eroarea totala E este suma erorilor corespunzatoare celor p vectori de intrare. Avem, deci

E= .

Putem deduce ca matricea W a ponderilor pentru care aceasta eroare este minima are forma

W=YX,

unde Xeste pseudoinversa sa este

X=(XX) X.

Memoriile asociative liniare optimale sunt retele în care ponnderile sunt date de matricea W ce minimizeaza eroarea E. Algoritmul recursiv al lui Greville furnizeaza o metoda iterativa eficienta pentru calculul pseudoinversei.

2.3.3. Functionarea memoriilor asociative bidirectionale

2.3.3.1. Stabilirea ponderilor

Consideram o memorie asociativa bidirectionala (BAM) compusa din straturile (câmpurile) F si F. Fiecare neuron poate avea si o legatura spre el însusi, care corespunde unei bucle în graful ce descrie topologia retelei.

Admitem ca multimea de instruire este formata din perechile

(x,y),(x,y),…, (x,y),

unde xB, yB. Prin B am notat fie cubul boolean n-dimensional {0,1}, fie cubul {-1,1}.

Spre deosebire de cele mai multe retele, ponderile BAM nu se determina printr-un mecanism iterativ de instruire. Ca si în cazul Asociatorului liniar, aceste ponderi se calculeaza o singura data si ramân neschimbate pe toata durata functionarii retelei.

Desi vectorii x,x,…, x nu sunt, în general, ortonormati, putem alege matricea W a ponderilor ca fiind data de formula utilizata penmtru asociator. Vom considera ca W este suma matricelor de corelatie

yx , i=1,2, … , p .

Vom avea, deci

W= yx.

W este o matrice (mn) si da ponderile conexiunilor de la stratul F spre stratul F. Linia J a matricei contine ponderile conexiunilor neuronului J din câmpul de iesire. Ponderile conexiunilor de la câmpul F la Fsunt date de matricea W. Asadar, coloana I a matricei W contine ponderile conexiunilor neuronului I din câmpul F. Matricea W codifica primele p perechi de forme. Pentru a se codifica o noua pereche (x,y) se calculeaza matricea de corelatie

w=y (x)

si se aduna w la matricea W.

Daca x{0,1}, matricea W se poate defini în mod alternativ, ca fiind

W= yx,

unde cu am notat suma booleana.

Valorile -1 si 1 sunt mai potrivite decât 0 si 1 pentru codificarea starilor, deci primul poas este de a converti {0,1} în {-1,1}.

2.3.3.2. Dinamica BAM-urilor

Dupa stabilirea matricei ponderilor, o memorie asociativa bidirectionala poate fi folosita pentru a regasi o anumita informatie atunci când se prezinta retelei o anumita informatie-cheie. De exemplu, informatia regasita poate fi numarul de telefon al unei persoane. Daca informatia necesara este doar partial cunoscuta (se stie, de exemplu, doar numele unei persoane ) sau daca ea este distorsionata (numele sau adresa sunt inexacte), reteaua este capabila sa furnizeze, totusi, numarul de telefon corect, completând sau restabilind si informatia-cheie.

2.3.3.2.1. Dinamica neuronilor individuali

Vom scrie, acum, o BAM discreta aditiva. In aceasta memorie, timpul are valori discrete, iar functia neuronala este o functie prag.

Fie x(t) vectorul format din starile neuronilor stratului F la timpul t . Componentele acestui vector pot fi {0,1} sau {-1,1}. x(t) reprezinta starea neuronului I din câmpul F la timpul t. Notam cu Sactivarea neuronului I.

Intrarile neuronului i din câmpul F sunt date de iesirile y(t), j=1,2, …, m, ale neuronilor din stratul F. Se poate scrie deci activarea Ssub forma

S= , I=1, … , n.

Termenul Icorespunde unei intrari externe a neuronului I.

Activarea R a neuronului j din stratul F se calculeaza folosind iesirile

x(t) , i=1, … , n,

ale neuronilor din stratul F. La momentul t, aceasta activare este

R= , j=1, … , m.

Termenul J corespunde unei eventuale intrari din exterior a neuronului j.

Daca starile neuronilor sunt 0 si 1, atunci starea neuronului i la momentul (t+1) va fi x(t+1), unde

x(t+1)=

Starea neuronului j din câmpul F la momentul (t+1) este y(t+1), unde

y(t+1)=

Am notat cu usi v pragurile celor doi neuroni. In cazul neuronilor bipolari (cu starile -1 si +1), expresiile de mai sus se vor modifica punând

x(t+1)=-1 , daca

si, respectiv

y(t+1)=-1 , daca .

Putem absorbi pragul în matricea ponderilor procedând în modul uzual, adica adaugând vectorilor x(t) si y(t) o ultima componenta egala cu 1.

2.3.3.2.2. Modelul de activare

Pentru schimbarea starilor, putem folosi fie un model sincron, fie unul asincron de activare. Intr-un model sincron, neuronii unui câmp se actualizeaza simultan.

Intr-un model de activare asincron, la fiecare moment se actualizeaza o submultime a neuronilor din câmpurile F sau F. Daca activarea neuronilor este aleatoare, atunci comportarea acestora se asimileaza cu proces aleator scalar iar functionarea retelei se poate descrie ca un proces aleator vectorial.

Daca, la un moment t, se schimba starea unui singur neuron, atunci avem de-a face cu un proces asincron simplu.

Se poate defini, astfel, în mod abstract, o memorie asociativa bidirectionala ca fiind un sistem S cu sapte componente: S=( F,F, W,I,J,U,V), unde F si F au semnificatiile cunoscute. I si J sunt vectori coloana ce desemneaza intrarile din mediu. U si V sunt vectori coloana reprezentând pragurile neuronilor din câmpul F si respectiv F (vectorii I si U sunt n-dimensionali iar vectorii J si V au câte m componente).

2.3.3.3. Functionarea BAM-urilor. Exemple

Vom considera câteva exemple de functionare a memoriilor asociative bidirectionale. Aceste exemple încedarca sa puna în evidenta diferitele situatii ce pot sa apara în legatura cu regasirea unor forme memorate.

Exemplul 1.

Consideram o memorie asociativa bidirectionala bipolara având n=8 neuroni pe stratul de intrare F si m=5 neuroni pe câmpul F. Consideram, în plus, toate pragurile egale cu zero: u= v=0 , oricare ar fi i si j.

Fie o multime de instruire formata din vectorii (x,y) si (x,y), unde

x=, y=

x=, y=.

Fie vectorul de intrare

x(0)=.

Dorim sa construim o retea capabila sa recunoasca faptul ca x(0) este o versiune distorsionata a lui x. Matricea ponderilor retelei este

W= y(x)+ y( x) .

Se obtine

W=.

Folosind un model de activare sincron, activarile neuronilor din stratul F sunt:

R=R=8,

R=4,

R= – 4,

R= – 8.

Luam, de exemplu,

y(0)=y

si calculam starea y(1) a neuronilor din stratul F la momentul t=1:

y(t+1)= , j=1, … , 5.

Obtinem, astfel

y(1)=.

Cu vectorul y, calculam activarile neuronilor din stratul F:

S=.

Gasim valorile

S=S=4,

S=S= – 6,

S=S= – 4,

S=S= 6.

Vectorul de stare pentru neuronii din Fla momentul t=1 va fi

x(1)=,

care este chiar x Propadând aceasta stare înainte, spre câmpul F, obtinem

y(2)= y(1)= y

si deci, avem

(x(2),y(2))= (x(1),y(1))=( x,y).

Rezulta ca reteaua s-a stabilizat de la prima iteratie,realizându-se echilibrul bidirectional. S-a obtinut astfel ca x(0) produce raspunsul ysau, echivalent, ca x(0) este o versiune distorsionata a lui x.

Exemplul 2.

Consideram reteaua si multimea de instruire din exemplul anterior si dorim sa vedem cum se comporta aceasta retea daca vectorul de intrare x(0) difera mult fata de x si x.

Alegem, de exemplu,

x(0)=.

Gasim activarile

R=R=4,

R= – 8,

R= 8,

R= – 4.

Rezulta ca

y(1)=.

Activarile stratului F produse de y(1) sunt:

S=S= – 4,

S=S= – 6,

S=S= 4,

S=S= 6.

Vectorul de stare asociat este

x(1)=,

si el produce, în F, activarile

R=R= R=8,

R= R= – 8.

Vectorul de stare generat deaceste activari este

y(2)=.

Se observa ca

y(2)= y(1).

Rezulta ca, în continuare, vom avea

x(2)= x(1)

si, deci

(x(2)y(2))= (x(1)y(1)),

adica reteaua s-a stabilizat.

Este interesant de observat ca solutia gasita indica un punct de echilibru (x(1)y(1)) care nu coincide cu nici una dintre perechile de instruire. Astfel, distanta Hamming între x(1) si x este 3, iar cea dintre y(1) si y este 2.

2.3.3.4. Algoritmul BAM

Considerentele anterioare, precum si exemplele precedente ne permit sa formulam un algoritm pentru memorarea si regasirea informatiei într-o memorie asociativa bidirectionala. Vom lua cel mai general dintre modelele considerate, adica modelul

(F,F,W,I,J,U,V).

Algoritmul de regasire corespunzator acestui model este prezentat în continuare.

Algoritmul de memorare si de regasirea informatiei în memoriile asociative bidirectionale

P1. Se construieste matricea W aponderilor, folosind o multime de instruire formata

din perechile de asociatii

(x,y), … , (x,y).

W=

P2. Se pune t:=0.

P3. Se initializeaza starile neuronilor din câmpul F folosind un vector arbitrar y(0).

P4. Se prezinta retelei un vector x=x(0) (fortând la x(0) iesirile neuronilor din câmpul F). Se urmareste regasirea vectorului xdin multimea de instruire, cel mai apropiat de x(0) în sensul distantei Hamming.

P5. Se propaga informatia de la câmpul F spre stratul F si se actualizeaza starea neuronilor din F.

Prin urmare, acest pas presupune urmatoarele:

(i ) alegerea strategiei de actualizare, sincrona sau asincrona;

(ii) calcularea vectorului R al activarilor,

R=Wx(t)+J;

(iii) calcularea vectorului de stare y(t+1) al neuronilor din F comparând componentele lui R cu pragurile corespunzatoare; se utilizeaza regula de evolutie

y(t+1)=

P6. Informatia stratului F se propaga înapoi spre câmpul F. Se actualizeaza neuronii câmpului F. Aceasta implica faptul ca

(i) se alege o strategie de actualizare;

(ii) se calculeaza vectorul S al activarilor,

S=Wy(t)+I;

(iii) se calculeaza vectorul de stare x(t+1) al neuronilor din câmpul Ffolosind regula

x(t+1)=

Observatie: Pentru neuronii bipolari, se pune

x(t+1)= – 1, daca S<u

si, respectiv

y(t+1)= – 1, daca R<v.

P7. Se pune t:=t+1. Se repeta pasii P5 si P6 pâna când starea nici unui neuron nu se mai schimba.

In acest algoritm se prezinta retelei (memoriei asociative) un vector x(0) care contine o informatie despre vectorul xdorit, dar nu stim nimic despre vectorul y asociat Se spera ca, la echilibru, sa obtinem o stare (x,y), unde x este vectorul xdin multimea de instruire, care este cel mai apropiat de x(0).

Algoritmul precedent functioneaza bine daca reteaua nu este supraîncarcata (multimea de instruire nu este prea mare). In cazul supraîncarcarii, apare un fenomen de interferenta datorata faptului ca formele de învatare sunt prea apropiate. Interactiunea dintre aceste forme poate genera stari de echilibru false, analoage cu punctele de minim local ale unei functii de performanta.

Putem considera, acum, si un model simplificat de memorie asociativa bidirectionala, în care nu exista intrari din mediu. Acest model este descris de sistemul

(F,F,W,I,J,U,V).

Vectorii de activare se vor calcula cu relatiile

R=Wx(t)

si, respectiv

S=Wy(t+1).

Algoritmul general prezentat mai sus nu mai necesita alte modificari.

2.3.4. Stabilitatea memoriei asociative bidirectionale

2.3.4.1. Stabilitate bidirectionala

Diferite metode de schimbare asincrona a starilor nu conduc, în general, la acelasi punct de echilibru, insa ele tind sa produca acelasi echilibru, tendinta care se anuleaza cu distanta. Aceasta comportare evidentiaza proprietatea de memorie adresabila prin continut a retelelor de tipul memoriei asociativebi bidirectionale.

In cazul unei memorii asociative bidirectionale, vectorii x si y se schimba in functie de timp, formand un sistem dinamic. Studiul acestui sistem dinamic poate furniza raspunsuri la intrebarile urmatoare:

(i) exista o solutie a problemei de instruire ?

(ii) daca solutia exista, va converge sistemul spre aceasta solutie intr-un timp finit ?

Fie (F,F,W,I,J,U,V) un sistem BAM general. Spunem ca ccest sistem este bidirectional stabil (bistabil ), daca orice intrare conduce la un echilibru de punct fix. tabilitatea bidirectionala astfel stabilita este un exemplu de stabilitate globala sau absoluta. Aceasta stabilitate reprezinta un echilibru dinamic. Acealasi semnal informational parcurge reteaua inainte si inapoi, realizand un punct fix bidirectional (bipolar).

Fie x intrarea unei memorii asociative bidirectionale. Putem reprezenta modul in care aceasta memorie se echilibreaza la punctul fix bidirectional (x, y) prin urmatoarea schema:

……………………………………

2.3.4.2. Consideratii elementare privind functiile Liapunov

Metoda functiilor Liapunov reprezinta un instrument puternic in studiul stabilitatii globale a sistemelor dinamice. Daca putem asocia sistemului o astfel de functie, atunci el este stabil. In caz contrar, nu se poate afirma nimic despre stabilitatea sa. Aceasta abordare este pur calitativa: ea indica doar existenta punctelor de echilibru, dar nu si numarul, pozitia sau natura lor.

In cazul memoriei asociative bidirectionale, stabilitatea asigura ca o regasire a informatiei are loc atunci cand retelei I se prezinta un stimul (o forma) de intrare, fara a sti, insa, care vector anume va fi regasit. Aceeasi problema apare si in cazul retelelor neuronale utilizate pentru rezolvarea problemelor de optimizare combunatoriala. In cazul din urma, stabilitatea implica doar faptul ca reteaua va atinge un punct de echilibru asociat unui minim local al functiei criteriu asociata problemei de optimizare combinatoriala.

O functie Liapunov este o functie de variabilele de stare ale sistemului, marginita si descrescatoare în raport cu timpul.

In cazul memoriei asociative bidirectionale, o functie Liapunov este o functi L,

L: ,

unde B este cubul n-dimensional boolean {0,1} sau cubul bipolar {-1,1}. Evident, L satisface conditiile de marginire si monotonie. Admitem ca fiecare variabila xa functiei L depinde de parametrul timp.

Fie L: o functie Luiapunov. Consideram ca L este derivabila in raport cu toate variabilele si ca toate variabilele sunt derivabile in raport cu timpul. Putem, deci, scrie

.

Am notat cu derivata in raport cu timpul a variabilei x.

2.3.4.3. Sisteme dinamice stabile

Vectorul de stare este o stare de echilibru daca

O stare de schilibru x este (uniform) stabila daca este indeplinita conditia

Aceasta definitie relefeaza faptul ca traiectoria sistemului poate fi facuta sa ramana in vecinatatea starii de echilibru daca starea initiala x(0) este suficient de apropiata de .

O stare de echilibru este convergenta daca exista astfel incat

Conform acestei definitii, daca stareas initiala x(0) este destul de apropiata de atunci traiectoria va converge spre .

Stabilitatea si convergenta sunt proprietati independente. In cazul stabilitatii, traiectoria sistemului poate sa nu atinga punctul de echilibru.

Starea de echilibru este asimetric stabila daca este o stare stabila si convergenta.

Se poate arata ca un sistem dinamic este intr-un punct de echilibru stabil daca exista o functie Liapunov L care descreste de-a lungul traiectoriilor, adica

L(x(t))0.

Un sistem dinamic este asimptotic stabil daca I se poate asocia o functie Liapunov care descreste strict de-a lungul traiectoriilor, adica avem

L(x(t))<0

pentru orice traiectorie posibila a sistemului.

Intr-un echilibru stabil, traiectoria poate sa oscileze arbitrar aproape de punctul de echilibru, fara a-l putea atinge. In cazul echilibrului asimptotic stabil, traiectoria atinge echilibrul si, in general, convergenta spre echilibru are o viteza exponentiala (Anderson si Moore, 1979).

Monotonia unei functii Liapunov reprezinta o conditie suficienta, dar nu si necesara, pentru stabilitate. Inabilitatea de a asocia sistemului o functie Liapunov nu ne permite sa tragem nici o concluzie privitoare la stabilitate, insa gasirea unei astfel de functii (de orice forma) demonstreaza stabilitatea. Din pacate, in afara functiilor patratice nu avem o procedura universala de generare a functiilor Liapunov.

Exemple:

2.3.4.4. Functia de energie pentru retele neurale

Energia unui sistem fizic poate fi deseopri interpretata drept o functie Liapunov a sistemului. prin analogie cu un sistem fizic, se poate defini energia unei retele neuronale, lucru efectuat de Hopfield (1982). O forma patratica depinzand de variabilele de stare ale sistemului (sau de viteze) poatre fi considerata ca fiind energia potentiala (sau cinetica) a sistemului.

Sa consideram un sistem fizic cu n variabile si fie E energia sa potentiala. Coordonata xse va interpreta ca deplasarea fata de echilibru a particulei I, apartinand sistemului. Originea este, asadar, un punct de echilibru in raport cu energia potentiala. Putem admite ca energia potentiala in origine este zero,. Energia potentiala E depinde doar de coordonate:

E=E(x, … , x).

Presupunem ca E admite o dfezvoltare in serie Taylor in jurul originii. Putem deci scrie

E(x)=E(0)+

unde derivatele sunt luate intr-un punct dintr-o vecinatate a originii. Pentru deplasari mici, termenii de ordin superior pot fi neglijati.

Originea este un punct de echilibru doar daca ea este un punct de minim al energiei. In acest caz, in orice vecinatate a originii avem

, I=1,2, … , n.

neglijand termenii de ordin superior si tinand cont de conditia

E(0)=0,

obtinem, pentru energia potentiala, aproximatia

E(x)

Notam

A=.

Matricea A cu elementele A este simetrica. Aproximatia energiei se poate acum scrie

E(x)=.

Am obtinut, astfel, o aproximatie a energiei care are forma functiei Liapunov considerata in sectiunea precedenta. Asadar, functia

E:RR

avand expresia

E(x)= –

poate fi considerata o functie Liapunov utila in studiul echilibrului retelelor neuronale. Aceasta functie are semnificatia unei energii.

Am vazut ca o functie ce candideaza pentru alegerea ca functie Liapunov a unui sistem trebuie sa fie crescatoare si marginita. Formele patratice consioderate mai sus pot creste nemarginit (in valoare absoluta) cu cresterea variabilelor de stare. Din acest motiv, folosim ca variabile de stare nu activarile neuronale, ci semnalele de iesire neliniare ale neuronilor (a caror valoare maxima este, de regula, egala cu 1)

Functiile Liapunov permit descrierea comportarii globale a retelelor neuronale. Pe masura ce valoarea functiei Liapunov asociate descreste, sistemul trece prin stari tranzitorii. Punctul pentru care descresterea inceteaza corespunde echilibrului sistemului. Acest punct poate sa corespunda terminarii procesului de instruire.

Daca functia Liapunov este asociata unei memorii asociative bidirectionale, atunci punctul de echilibru corespunde regasirii unei informatii (forme). Daca reteaua rezolva o problema de optimizare combinatoriala, atunci punctul de echilibru indica solutia problemei (un punct de optim al functiei criteriu asociate problemei)

.

2.3.4.5. Stabilitatea BAM-ului

Pentru studiul stabilitatii memoriei asociative bidirectionale, vom considera diferite functii Liapunov de tip energie. Stabilirea acestor functii depinde de complexitatea retelei. Luam, pentru inceput, cazul standard, in care pragul fiecarui neuron este zero si intrarile din mediu sunt nule, adica:

I=0, u=0, i=1, … , n.

si

J=0, v=0, j=1, … , m.

Acest model de memorie asociativa se noteaza cu (F,F,W). Pentru el putem construi o functie Liapunov simpla. Considerand starile neuronilor bipolare (-1 si 1), definim functia de energie

E(x,y)=-yWx,

unde W este matricea ponderilor retelei.

Functia energie considerata se mai scrie sub forma

E(x,y)= -.

Dorim sa aratam ca E se comporta ca o functie Liapunov. Aceasta presupune sa demonstram ca energia descreste de-a lungul traiectoriilor reprezentate de starile discrete ale retelei. Descresterea are loc pentru orice schimbari (sincrone sau asincrone) ale starilor. Urmatoarea teorema privind functia de energie ne ajuta sa obtinem un raspuns referitor la existenta starilor stabile ale memoriei asociative bidirectionale.

Teorema BAM. Pentru orice memorie asociativa bidirectionala asociata modelului (F,F,W) sunt adevarate urmatoarele afirmatii:

(i) Orice schimbare a vctorilor de stare x si y in timpul functionarii retelei produce o descrestere a functiei E, ce reprezinta energia retelei, unde

E(x,y)=-yWx,

(ii) Functia energie este marginita. Valoarea minima a energie este

E=-.

(iii) Energia variaza in cantitati discrete. Variatia energiei nu poate fi niciodata arbitrar de mica (nu exista nici o schimbare a starii neuronilor pentru care energia sa fie oicat de mica).

Demonstratie:

(i) Presupunem ca cel putin un neuron isi schimba starea de la momentul t la (t+1), ceea ce ne permite sa adoptam orice strategie de actualizare (sincrona, asincrona sau simplu asincrona). Consideram ca neuronul r din stratul F si-a schimbat starea. Pentru a calcula variaia energiei produsa de aceasta schimbare, energia retelei va fi scrisa sub forma

E= E(x,y)= -.-.

Fie noua stare a neuronului r si E energia corespunzatoare. Energia E se poate scrie

E= E(x,y)= -.-.

Variatia E a energiei este

E=E-E=(y-)=(y-)R.

Pentru a gasi semnul acestei variatii, consideram cele trei situatii posibile:

(a) y=1, =-1.

Cazul =-1 se obtine daca activitatea neuronului r este negativa, adica

R=<0.

Cum y->0, rezulta imediat ca avemE<0.

(b) y=-1, =1

Tranzitia corespunzatoare acestui caz se poate realiza numai daca activarea este strict pozitiva (R>0). Acum, y-<0 si deci, din nouE<0.

(c) y=.

Rezulta E=0.

Am obtinut ca in orice situatie avem E0.

Consideram cazul general cand se schimba starea mai multor neuroni. Acum variatia energiei este

E ==.

Cum fiecare dintre cei m termeni din aceasta suma este negativ sau zero, rezulta ca energia descreste.

Schimbarea starilor pentru Fse trateaza analog.

(ii) Deoarece xsi y iau doar valorile 1 si -1, rezulta ca E este marginita superior. Din inegalitatea

-|w| |xy| xwy| w| |xy|,

rezulta ca

-|w| E(x,y) |w|.

cum ponderile conexiunilor sunt finit, rezulta ca functia energie este marginita. Se observa imediat ca energia poate atinge valoarea minima

E=-|w|.

(iii) Tinand cont de forma variatiei energiei, rezulta ca aceasta nu poate fi arbitrar de mica. La orice schimbare a starii neuronilor, energia inregistreaza un salt discret.

2.3.4.6. Stabilitatea BAM-ului. Cazul general

Fie (F,F,W,I,J,U,V) un sistem BAM general. Este natural ca energia acestui sistem sa inglobeze si pragurile neuronilor, precum si intrarile exterioare. Acestea din urma apar in expresia activarii. Energia asociata starii (x,y) a retelei se defineste cu expresia

E(x,y)= – yWx -(I-U)x-(J-V)y,

unde am notat

I=, J=.

U si V sunt vectori avand drept componente pragurile neuronilor, adica

U=, V=.

Energia E se poate scrie

E(x,y)= – xwx–-.

Vom arata ca aceasta energie reprezinta o functie Liapunov pentru memoria bidirectionala considerata.

Variatia energiei datorita schimbarii starii neuronilor din campul F este

.

Analog, variatia energiei la schimbarea starii neuronilor din stratul F va fi

.

Expresiile pentru sisunt valabile atat pentru un model de activare sincron, cat si pentru o activare asincrona. In cazul modelului asincron, acei neuroni I din F ce nu-si modifica starea sunt caracterizati de . O situatie similara are loc si pentru campul F.

Din expresia variatiei energiei, se deduce imediat ca inegalitatea

E0

are loc pentru orice schimbare a starii retelei.

pentru determinarea marginii superioare si inferioare a energiei, o vom scrie sub forma

E(x,y)= – yWx -(I-U, x)-(J-V,y),

unde am utilizat produsul scalar

(a,b)= ab.

Tinand cont de inegalitatea Cauchy-Schwartz

(a,b)||a||*||b||,

obtinem ca, pentru orice stare (x,y), avem

(I-U, x) ||I-U|| ||x||,

(J-V,y) ||J-V|| ||y||.

Deoarece xeste -1 sau 1, rezulta ca

||x||=n

si

||y||=m.

Rezulta, astfe, ca energia satisfacew inegalitatea

E(x,y) |w|- n||I-U||- m||J-V||.

Aceasta inegalitate se mai oate scrie sub forma

E(x,y) |w|- [n]-[ m].

Am gasit, asadar, o margine inferioara a energiei.

Similar, se arata ca energia este marginita si superior. In concluzie, rezulta ca energia introdusa este o functie Liapunov pentru o memorie asociativa bidirectionala generalizata.

ANEXA

Aplicatia implementeaza principalii algoritmi descrisi in lucrara de fata.

A fost realizata in mediul de programare Borland C++ 3.1 sub Windows, in care sunt implementati principalii algoritmi descrisi in lucrarea de fata .Aplicatia este un “recognizer” de caractere -OCR Printre algoritmii implementati se disting OLAM care encodeaza optim esantionul de invatare precum si cea mai “puternica “ retea feedforward -BPN.Programul contine fisiere in care sunt retinute memoriile retelelor dupa ce acestea au fost instruite pe baza unor esantioane de exemple. Exista posibilitatea instruirii prin selectarea fisierului cu esantionul de test, si aplicarea comenzii de instruire. Esantioanele de exemple de invatare literele sunt date sub forma de vectori. Aranjarea lor in esantioanele de test este semnificativa pentru performantele retelelor. Se observa funcionare diferita a retelelor pentru prezentarea literelor grupate in secventa de instruire si prezentarea aleatoare.Formele de invatare din cadrul unei clase nu trebuie sa fie prea diferite, pentru ca la decodare nu s-ar mai gasi clasa specifica, dar nici prea apropiate pentru a nu limita performantele retelei. Programul prezinta diverse facilitati de testare: atat a exemplelor din esantioanele de instruire, perturbatii ale lor sau forme diferite de cele prezentate la instruire. Exista obtiuni de modificare a parametrilor ce intra in componenta algoritmilor. Pe baza compararilor sub forma de grafice pe care le permite aplicatia, exista posibnilitatea optimizarii algoritmilor prin gasirea valorilor optime ale parametrilor,precum si a compararii performantelor. Programul contine si un help in care sunt prezentate metodele abordate in aplicatie.

Bibliografie

1. Amari, S., Neural Theory of Association and Concept Formation, Biological Cybernetics, 26 (1977), p. 175-185.

2.Anderson, J.A., A Simple Neural Network Generating an Associative Memories Mathematical Biosciences, 14 (1972), 197- 220.

3. A. Blum – Neural NetWorks in C++: An Object – Oriented Framework for Building Connectionist Systems (John Wiley & Sons , 1992)

4. Cohen, M.A., Grossberg, S.G., Absolute Stability of Global Pattern Formation and Parallel Memory Storage by Competitive Neural Networks, IEEE Trans. SMC 13 (1983) ,815-826.

5. Dumitrescu, D., Hariton, C., Retele neuronale, Ed. Teora, 1996

6.Gallant, S.I., Optimal Linear Discriminants, Proc. 8-th Int. Conf. on Pattern Recognition, Paris, 1986, 849- 852.

7.Kosko, B., Adaptive Bidirectional Associative Memories, Applied Optics, USA, 26(1987),4947-4960.

8. Kosko, B.,Competitive Bidirectional Memories, Proc. IEEE First. INT. Conf. Neural Networks, San Diego, 1987, II, 759-766.

9. Kosko, B., Constructing an Associative Memories, Byte, 12 (1987), 137-144.

10.Kosko, B., Bidirectional Associative Memories, IEEE Trans. SMC, 18(1988),49-60.

11.Minsky, M., Papert, S., Perceptrons. An Introduction to Computational Geometry, MIT Press, Cambridge, MA, 1969.

12.Rosenblatt, F., Principles of Neurodinamics, Spartan Book, New York, 1962.

13. Simson, P., Artificial Neural Systems, Pergamon Press 1990.

14.Teuro Koleonen – Seff organization and Associative Memory (ed. Springer – Veilag – 1988)

15.Widrow, B., Winter, R.G., Baxter, R.A., Learning Phenomena in Layered Neural Networks, Proc.First Int. Conf. on Neural Networks, IEEE, 1987, vol. II, 411- 429.

16. Widrow, B., Hoff, M.E., Adaptive Switching Circuits, Inst. of Eng., Western Electronic Show and Convention, Conv. Record, 4, IRE, 1960, 96-104.

17.Winter, R., Widrow, B., MADALINE RULE II: a Training Algorithm for Neural Networks, Proc. of IEEE 2-nd Int. Conf. on Neural Networks, San Diego, CA, 1988, vol.1, 401-408.