2. Rekurentné siete

Neurónové siete sa podľa toho, akým spôsobom sú v nich navzájom prepojené neuróny, delia na dva základné typy:

Feed-forward (dopredné) siete, medzi ktoré patria napríklad viacvrstvové perceptróny, majú štruktúru, ktorá dovoľuje usporiadať neuróny do niekoľkých vrstiev tak, aby všetky prepojenia v sieti viedli od neurónu v nižšej vrstve smerom k neurónu v niektorej z vyšších vrstiev, nikdy však nie naopak. Sieť teda prenáša vstupný signál postupne cez všetky sieťové vrstvy smerom k výstupu. Tomuto procesu hovoríme dopredné šírenie signálu v neurónovej sieti. Pretože feed-forward siete majú vrstvovú štruktúru, ich učiace algoritmy sú pomerne jednoduché a ľahko implementovateľné (nemajú veľkú výpočtovú zložitosť).

Rekurentné siete (siete so spätnou väzbou) sú zovšeobecnením feed-forward sietí. Dovoľujú prepojenia medzi neurónmi v oboch smeroch a dokonca prepojenie neurónu samého so sebou. Tým sa komplikuje úloha hľadania vhodných učiacich algoritmov. Tieto majú väčšinou oveľa väčšie časové a pamäťové nároky ako algoritmy na učenie feed-forward sietí. Rekurentné siete sú však svojou štruktúrou prispôsobené na vytvorenie lepšej vnútornej reprezentácie vstupných údajov a na uchovávanie svojich predošlých stavov, z čoho vyplýva ich schopnosť prostredníctvom spätného šírenia signálu adaptovať sa aj na zložitejšie úlohy, než aké je možné riešiť pomocou sietí s feed-forward architektúrou.

V tejto kapitole najprv uvedieme základné rozdelenie typov rekurentných sietí. Potom sa budeme postupne venovať niektorým druhom sietí, pričom popíšeme ichh architektúru, spôsob práce možnosti ich praktického využitia na riešenie rôznych druhov problémov.

2.1 Klasifikácia rekurentných sietí

Okrem všeobecnej klasifikácie neurónových sietí (kap 1.2) rozdeľujeme rekurentné siete podľa niekoľkých ďalších kritérií.

Prvým z nich je stupeň využitia spätných prepojení v sieťovej architektúre, pričom rozlišujeme siete na

Čiastočne rekurentné siete môžeme považovať za podmnožinu plne rekurentných sietí, ak chýbajúce spätné prepojenia nahradíme prepojeniami s konštantnými váhami w_ij=0. Preto všetky učiace algoritmy pre plne rekurentné siete môžeme použiť aj pre siete s čiastočnou rekurenciou.

Podľa toho, v akom vzájomnom vzťahu sú prepojenia medzi dvoma neurónmi v sieti, delíme rekurentné siete na tie, ktoré majú

Pre siete, ktoré nemajú symetrické prepojenia, nie je zaručený ich prechod do stabilného stavu (situácia, keď sa stav siete nemení), zatiaľ čo siete, ktoré spĺňajú podmienku symetrie, vždy tento stabilný stav dosiahnu.

Posledným kritériom je charakter signálov, ktoré vstupujú do siete. Podľa neho rozoznávame siete, ktoré majú

Pre siete so spojitým vstupom je veľmi dôležitý spôsob, akým je reprezentovaný čas a veličiny, ktoré sú na ňom závislé.

2.2 Hopfieldova sieť

Hopfieldova sieť so svojím učiacim algoritmom patrí do triedy plne rekurentných sietí s binárnym vstupom, trénovaných bez dozoru. Po prvýkrát ju popísal J.J.Hopfield v roku 1982. Pracuje ako asociatívna pamäť, ktorej úlohou je uchovávať určité vzory a rekonštruovať nekompletný alebo poškodený vstup tak, aby skonvergoval k jednému z týchto vzorov. Architektúru Hopfieldovej siete pozostávajúcej zo štyroch neurónov ukazuje obr. 2.1.

graph obr2_1.pcx

obr. 2.1 Architektúra Hopfieldovej siete

Topológia siete. Každý neurón v sieti je prepojený so všetkými ostatnými neurónmi, pričom prepojenia sú symetrické, to znamená, že w_ij=w_ji pre i,j=1,...,n. Žiaden neurón však nemá prepojenie samého so sebou, teda w_ii = 0 pre i=1,...,n.

Neuróny sa môžu nachádzať v dvoch stavoch - jeden z nich je charakterizovaný aktivačnou hodnotou +1 a druhý aktivačnou hodnotou -1. Stav i-teho neurónu označíme s_i. Teda platí s_i = ± 1.

Aktivačná hodnota (stav) každého neurónu je daná vzťahom

(2.1)

kde h_i je celkový vstup do i-teho neurónu a x₁,...,x_n sú vstupné hodnoty neurónov, ktoré spolu tvoria vstupný vektor x=(x₁,...,x_n), pričom platí, že x_i = ± 1. Pre Hopfieldovu sieť budeme používať aktivačnú funkciu g(x)=sgn(x) – tvrdé ohraničenie (1.2). Vektor aktivačných hodnôt (stavov) všetkých neurónov s=(s₁,...,s_n) tvorí stav siete.

Pre jednoduchosť pridáme do siete dodatočný neurón s konštantným výstupom -1, takže ďalej môžeme uvažovať prahové hodnoty q _i = 0 a vzťah (2.1) napísať v tvare

(2.2)

Práca siete spočíva v tom, že stavy neurónov v čase t sú opäť použité na vstupe siete v čase t+1, takže

a teda sieť v každom časovom kroku upravuje stavy neurónov podľa pravidla

(2.4)

až kým sa stav siete nezmení v dvoch po sebe nasledujúcich krokoch, teda nastane rovnosť

s_i(t)= s_i(t+1)= s_i pre i=1,...,n (2.5)

Tento stav siete s=(s₁,...,s_n) nazývame stabilným stavom.

Aktivačné hodnoty (stavy) s_i neurónov po konvergencii tvoria výstup siete, teda

y_i = s_i pre i=1,...,n (2.6)

Všetky vektory y=(y₁,...,y_n), ku ktorým skonverguje sieť, ak na jej vstup podávame rôzne vektory x=(x₁,...,x_n), nazývame exemplárnymi vzormi siete. Pre každý exemplárny vzor teda platí po dosadení (2.5) do rovnice (2.4)

pre i=1,...,n (2.7)

Energetická funkcia. V každom časovom okamihu môžeme definovať celkovú energiu siete pomocou energetickej funkcie

(2.8)

pričom úlohou siete je dosiahnuť stav s čo najmenšou energiou. Energetická funkcia E je funkcia n premenných s₁,...,s_n a dosahuje na svojom definičnom obore lokálne maximá a minimá. Bolo pritom dokázané [3], že funkcia E dosahuje svoje lokálne minimá práve pre vektory x, ktoré sú exemplárnymi vzormi siete. Podmienka konvergencie siete k exemplárnemu vzoru a podmienka dosiahnutia lokálneho minima energetickej funkcie E sú teda ekvivalentné.

Chceme ukázať, že sieť pomocou pravidla (2.4) mení stavy neurónov tak, že postupne znižuje svoju celkovú energiu. V každom časovom kroku sa energia siete zmení o hodnotu D E, pričom

(2.9)

Nech v danom časovom kroku prejde neurón k zo stavu s_k(t) do stavu s_k(t+1) = -s_k(t), stavy ostatných neurónov sa pritom nemenia, teda s_i(t+1) = s_i(t) pre i1 k. Potom (2.9) môžeme ďalej upraviť

Pre zmenu energie siete pri prechode neurónu k zo stavu s_k(t) do stavu s_k(t+1) teda platí

(2.10)

Keďže s_k(t+1) = -s_k(t), upravíme (2.10) do konečnej podoby

(2.11)

Rozlíšime dva prípady:

(1) s_k(t)=-1 s_k(t)=-1 ? s_k(t+1)=g(h_k(t))=sgn(h_k(t))=1 ? h_k(t) 3 0

s_k(t)=-1 & h_k(t)3 0 ? D E = s_k(t)h_k(t) L 0

(2) s_k(t)=1 s_k(t)=1 ? s_k(t+1)=g(h_k(t))=sgn(h_k(t))=-1 ? h_k(t) < 0

s_k(t)=1 & h_k(t)< 0 ? D E = s_k(t)h_k(t) < 0

Vidíme teda, že D E L 0 v oboch prípadoch, čo znamená, že každá zmena stavu neurónu podľa pravidla (2.4) vedie k zníženiu celkovej energie siete. Keďže s_i sú diskrétne veličiny s_i = ± 1, po konečnom počte krokov sieť dosiahne lokálne minimum, čo je ekvivalentné s tým, že skonverguje k niektorému exemplárnemu vzoru.

Nastavenie váh prepojení. Ak chceme dosiahnuť, aby si Hopfieldova sieť zapamätávala určité vzory, musíme nájsť spôsob, ako nastaviť váhy w_ij na

príslušné hodnoty tak, aby sieť vždy skonvergovala k jednému z

týchto vzorov.

Ak má sieť uchovávať jeden vzor x=(x₁,...,x_n), nastavíme váhy prepojení na hodnoty

ak i1 k

ak i=k (2.12)

Úlohou je dokázať, že pre sieť s takto nastavenými váhami je vektor x jej exemplárnym vzorom. Musí teda platiť rovnosť (2.7). Ak do jej pravej strany dosadíme za w_ij, dostaneme

a teda vektor x je exemplárnym vzorom siete s váhami w_ij nastavenými podľa (2.12).

Ak má sieť uchovávať m vzorov x^k=(x₁^k,...,x_n^k), kde k=1,...,m, nastavíme váhy prepojení podľa pravidla

ak i1 j

ak i=j (2.13)

Sieť s takto nastavenými váhami pri dodržaní istých podmienok uchováva vzory x^k a správne rozpoznáva nekompletné alebo poškodené vstupné vektory.

Zhrnieme teraz celý algoritmus práce Hopfieldovej siete:

Algoritmus pre Hopfieldovu sieť

1.krok: Priradenie váh prepojeniam

ak i1 j

i,j=1,...,n

ak i=j

2.krok: Inicializácia siete neznámym vstupným vzorom x=(x₁,...,x_n)

s_i(0)= x_i i=1,...,n

kde s_i(0) je stav i-teho neurónu v čase t=0

3.krok: Iterácia, kým sieť neskonverguje

i=1,...,n

4.krok: Ohodnotenie výstupného vektora

y_i = s_i i=1,...,n

Obmedzenia siete. Hopfieldova sieť má niekoľko základných obmedzení, ktoré podmieňujú jej schopnosť plniť úlohu asociatívnej pamäti. Prvým je obmedzenie počtu vzorov, ktoré je sieť schopná uchovávať. Bolo dokázané (Amit, 1989), že ak máme sieť pozostávajúcu z n neurónov, pre počet exemplárnych vzorov m platí ohraničenie m L 0.15*n na to, aby vstupné vzory boli správne rozoznané s pravdepodobnosťou 0.99. Táto nerovnosť platí pre siete s veľkým počtom neurónov.

Ďalšou podmienkou je, aby vzájomná korelácia (súvsťažnosť) vzorov potrebných na uchovanie bola čo najmenšia alebo žiadna. Mierou korelácie dvoch vzorov a, b môže byť

(2.14)

Z tejto rovnosti vyplýva, že u Î á -1,1n . Ak u je blízke 0, hovoríme, že korelácia medzi vzormi a a b je malá.

Ďalšou mierou korelácie je funkcia

(2.15)

ktorá sa tiež nazýva Hammingova vzdialenosť a nadobúda hodnoty z intervalu á 0,nn . Pritom koreláciu medzi vzormi považujeme za malú, ak hodnota h je blízko (1/2)n.

Počas práce Hopfieldovej siete môže tiež dôjsť k situácii, keď sieť opakovane prechádza medzi dvoma stavmi, ktoré majú rovnakú hladinu energie, čo zabraňuje konvergencii. Tento jav sa nazýva oscilácia siete.

Zhrnutie. Ak zohľadníme hlavné obmedzenia Hopfieldovej siete, táto nachádza

veľké uplatnenie najmä pre problémy rozpoznávania vzorov s binárnou reprezentáciou. Takými sú napríklad čierno-biele obrazy reprezentované pomocou matice pixelov, pričom každý bod obrazu má hodnotu -1 (biely) alebo 1 (čierny). Vhodná je tiež pre použitie pre optimalizačné problémy.

2.3 Metóda simulovaného žíhania

Algoritmus práce Hopfieldovej siete je jedným z tých algoritmov, ktoré využívajú metódu stáleho znižovania energie. To znamená, že Hopfieldova sieť v každom kroku upravuje stavy svojich neurónov tak, aby sa čo najviac znížila celková energia siete definovaná vzťahom (2.8). Výsledkom tohto procesu je stav, v ktorom energetická funkcia nadobudla lokálne minimum, ktoré zodpovedá jednému z uchovávaných vzorov.

Existuje však množstvo problémov, při ktorých úlohou neurónovej siete je dosiahnuť globálne minimum, to znamená stav, v ktorom má energetická funkcia najmenšiu hodnotu. Algoritmy založené na metóde stáleho znižovania energie nie sú pre tento typ problémov prakticky využiteľné, pretože znižovanie energie v

každom kroku znemožňuje sieti, ktorá dosiahla lokálne minimum, preskočiť tento stav a ďalej pokračovať v hľadaní stavu, ktorý zodpovedá globálnemu minimu. V tomto prípade hovoríme, že sieť uviazla v lokálnom minime. Preto musíme hľadať algoritmy, ktoré vedia predísť uviaznutiu a pomocou ktorých sieť dokáže

prejsť do stavu s minimálnou energiou. Jedným z nich je algoritmus nazvaný simulované žíhanie, ktorý je vhodný najmä pre rekurentné siete s veľkým počtom neurónov. Vyvinul ho v roku 1983 Kirkpatrick a kol. a je základom práce Boltzmanovej sietí, ktorej je venovaná kap.2.4.

Jeho základnou myšlienkou je umožniť sieti aj prechod do stavu s vyššou energiou, než akú mal predošlý stav, pričom počet takýchto prechodov je vždy menší ako počet krokov, pre ktoré je D E<0, takže celkovo sa zachováva základná podmienka znižovania energie siete.

Fyzikálne základy. Metóda simulovaného žíhania má svoj pôvod vo fyzikálnom procese žíhania látky, počas ktorého sa častice danej látky snažia zaujať stavy s čo najmenšou energiou. Prvou fázou je zohriatie látky na teplotu, pri ktorej sa stáva kvapalnou a jej častice sú usporiadané náhodne. Táto teplota sa potom postupne znižuje, pričom častice sa premiestňujú v snahe dosiahnuť teplotnú rovnováhu - stav s najmenšou energiou pri danej teplote. So znižujúcou sa

teplotou postupne vytvárajú mriežkovú štruktúru, ktorá predstavuje stav s minimálnou celkovou energiou sústavy. Počas tohto procesu musíme dbať na to, aby počiatočná teplota bola dosť vysoká na to, aby mali častice dostatočnú kinetickú energiu na premiestňovanie, a aby fáza ochladzovania mala primeranú rýchlosť. Príliš rýchle znižovanie teploty znamená, že častice nemajú dostatok času na

dosiahnutie teplotnej rovnováhy, čo sa prejavuje nepravidelnou štruktúrou mriežky a lokálnymi chybami (defektmi). Pri vyšších teplotách sa vytvárajú základné črty budúceho usporiadania, zatiaľ čo pri nižších teplotách prídu na rad menšie zmeny vedúce ku konečnému tvaru kryštalickej mriežky.

Ak v úvahách o tomto procese nahradíme častice látky stavmi neurónov v sieti a celkovú energiu sústavy častíc energiou siete vyjadrenou pomocou energetickej funkcie E, dostávame základné myšlienky, ktoré viedli k odvodeniu matematického ekvivalentu tohto fyzikálneho procesu, ktorý bol podľa neho nazvaný simulovaným žíhaním.

Teplotná rovnováha. Ako sme už spomenuli, častice látky majú pri každej teplote snahu usporiadať sa tak, aby dosiahli rovnovážny stav. Jednoduchým algoritmom, ktorý simuluje tento proces pre neurónové siete, je Metropolisov algoritmus, navrhnutý v roku 1953.

V každom jeho kroku je náhodne vybratý jeden neurón a je vypočítaná zmena energie siete D E pre prípad, že sa zmení jeho stav. Celková energia siete je pritom daná vzťahom (2.8) rovnako ako pre Hopfieldovu sieť.Ak D E L 0, zmenu stavu neurónu akceptujeme a krok opakujeme s touto novou konfiguráciou siete. Ak však D E > 0, nový stav bude akceptovaný s pravdepodobnosťou

(2.16)

kde T je konštanta, ktorú budeme nazývať teplotou systému pre jej funkciu, ktorá je analogická s fyzikálnou teplotou.

Pravdepodobnosť, že sieť sa nachádza v stave a , je vyjadrená pomocou Boltzmannovej distribučnej funkcie

(2.17)

kde Ea je celková energia siete v stave a a Z je funkcia rozdelenia definovaná vzťahom

(2.18)

Na implementáciu pravdepodobnosti môžeme použiť generátor náhodných čísiel z intervalu (0,1). Náhodne vybraté číslo c porovnáme s hodnotou pravdepodobnostnej funkcie (2.16). Ak c < P(D E), potom nový stav neurónu akceptujeme, inak sieť zostáva pre ďalší krok vo svojom pôvodnom stave.

Algoritmus simulovaného žíhania používa variáciu tejto metódy, pričom na výpočet pravdepodobnosti použijeme sigmoidálnu funkciu podľa (1.5)

(2.19)

kde h_i je celkový vstup do i-teho neurónu, ktorý sme náhodne vybrali, aby sme zmenili jeho stav. Potom jeho nový stav bude 1, ak pre náhodne vybraté číslo c z intervalu (0,1) platí c L p, inak ho nastavíme na -1. Celý postup potom opakujeme dostatočný počet krát na to, aby sieť mohla dosiahnuť rovnovážny stav pri danej teplote T.

Znižovanie teploty. Dôležitou podmienkou pre úspešný priebeh simulovaného žíhania je rýchlosť, akou postupne znižujeme teplotu od počiatočnej hodnoty až po konečný stav, v ktorom má sieť minimálnu energiu. Bolo dokázané (Geman a Geman, 1984), že ak pre každú teplotu T_k použitú v k-tom kroku simulovaného žíhania platí nerovnosť

(2.20)

kde T₀ je dostatočne veľká počiatočná teplota, potom sieť s pravdepodobnosťou 1 skonverguje do stavu s minimálnou energiou. Teplota T_k sa pre k ® Y asymptoticky blíži k hodnote 0, pri ktorej je tento algoritmus totožný s algoritmom pre Hopfieldovu sieť.

Postupnosť {T_k;k=0,1,...} nazývame tabuľkou ochladzovania. Pre postupnosť teplôt spĺňajúcich podmienku (2.20) je však konvergencia príliš pomalá na to, aby sa dala prakticky použiť. Musíme ju preto nahradiť aproximáciou pozostávajúcou z konečného počtu teplôt. Týmto krokom stratíme istotu, že sieť skutočne nájde globálne minimum, avšak pre vhodne zvolenú aproximáciu sú výsledky väčšinou veľmi blízke optimálnemu riešeniu. Jedným zo spôsobov znižovania teploty je tabuľka ochladzovania navrhnutá Kirkpatrickom a kol. v roku 1983. Riadi sa nasledujúcimi pravidlami:

2. Teplota sa postupne znižuje podľa pravidla

T_k = a T_k-1 k=1,2,...

Keďže sme objasnili všetky kroky metódy simulovaného žíhania, môžeme teraz zhrnúť celý jej algoritmus:

Algoritmus simulovaného žíhania

2.krok: Náhodne vyberieme neurón i (i=1,...,n)

3.krok: Vypočítame celkový vstup do i-teho neurónu

4.krok: Vypočítame hodnotu pravdepodobnostnej funkcie

5.krok: Vyberieme náhodné číslo c a položíme

s_i = 1 ak c L p

s_i = -1 ak c > p

7.krok: Zvýšime číslo cyklu k o 1, znížime teplotu podľa pravidla

T_k = a T_k-1

Konvergencia algoritmu. Chceme ukázať, že pomocou metódy simulovaného žíhania je neurónová sieť schopná dosiahnuť globálne minimum svojej energetickej funkcie. Najprv dokážeme, že zmena stavu neurónu podľa tohto algoritmu vedie ku zníženiu energie E s pravdepodobnosťou p > 1/2. Podľa vzťahu (2.10) a (2.11) vieme zmenu energie E pri prechode neurónu i zo stavu s_i(t) do stavu s_i(t+1)= -s_i(t) vyjadriť ako

(2.22)

Vypočítame pravdepodobnosť, že pri tejto zmene je D E<0.

Pre s_i(t)=-1 zo vzťahu (2.22) vyplýva, že pre D E<0 platí h_i>0

a keďže

Pre s_i(t)=1 je h_i(t)<0 a pre pravdepodobnosť p platí

a keďže

Sieť teda s pravdepodobnosťou p > 1/2 prejde do stavu s nižšou energiou.

Z uvedeného vyplýva, že energia siete sa pravdepodobnostne znižuje ku svojmu minimu, a teda pri voľbe takej tabuľky ochladzovania, ktorá spĺňa podmienku (2.20), sieť dosiahne stav s minimálnou energiou.

Zhrnutie. Simulované žíhanie sa stalo základom algoritmu práce Boltzmannových sietí, je však možné ho použiť pre všetky typy úloh, kde je potrebné nájsť globálne minimum energetickej funkcie. Je možné pomocou neho riešiť napríklad problémy kombinatorickej optimalizácie, kde úlohou je nájsť najlepšie riešenie spomedzi veľkého, ale konečného počtu rôznych riešení. V roku 1984 ho Tank a Hopfield s úspechom použili na riešenie problému obchodného cestujúceho, ktorý je jedným z najznámejších úloh kombinatorickej optimalizácie.

2.4 Boltzmannova sieť

Ďalšou zo sietí, ktoré obsahujú rekurentné prepojenia, je Boltzmannova sieť, ktorú vyvinuli Ackley, Hinton a Sejnowski v roku 1985. Je rozšírením Hopfieldovej siete, s ktorou má niekoľko spoločných vlastností. Obe patria do triedy plne rekurentných sietí s binárnym vstupom, teda každý ich neurón sa môže nachádzať v stave s aktivačnou hodnotou -1 alebo +1 (resp. 0 alebo 1). Obe siete majú symetrické prepojenia, teda w_ij = w_ji pre všetky váhy prepojení v sieti, pričom platí w_ii = 0, čo znamená, že žiaden neurón nie je prepojený sám so sebou. Na rozdiel od Hopfieldovej siete však Boltzmannova sieť obsahuje skryté neuróny, čo jej umožňuje lepšie reprezentovať zložitejšie vzťahy medzi vstupnými veličinami. Zmeny stavov neurónov v Boltzmannovej sieti prebiehajú podľa stochastických pravidiel (pravidlá obsahujúce v sebe pravdepodobnosť), zatiaľ čo Hopfieldova sieť sa pri výpočte stavov neurónov riadi deterministickými pravidlami. V Hopfieldovej sieti sú váhy pevne nastavené na začiatku celého procesu a počas činnosti siete sa už nemenia. Na rozdiel od toho činnosť Boltzmannovej siete v sebe zahŕňa aj fázu učenia, v ktorej sa váhy prepojení adaptujú na základe vzoriek tréningovej množiny.