Algoritmy a struktury neuropočítačů

ASN - P2

• Topologie neuronových sítí, principy učení

• Samoorganizující se neuronové sítě

• Kohonenovy mapy

Topologie neuronových sítí

(struktura, geometrie, architektura)

Uspořádání výkonných jednotek - neuronů (units,

neurons) a jejich vzájemné propojení.

propojení - orientované grafy:

uzly neurony

orientované větve synaptické váhy

Vícevrstvé neuronové síte

(Multilayer Neural Network - MLNN)

neurony (výkonné jednotky) sestavené do vrstev

sítě s dopředným šířením informace (feedforward)

Vrstevnatá struktura

vstupní vrstva (input layer)

skryté vrstvy (hidden layers)

výstupní vrstva (output layer)

Např.: 15 - 20 - 2

počet počet počet

vstupních skrytých výstupních

neuronů neuronů neuronů

rekurentní sítě (recurrent networks)

• informace se šíří v dopředném směru

• formou jednoduchých zpětných vazeb

• formou vícenásobných zpětných vazeb

Toto propojení zprostředkovávají synaptické váhy.

Neurony tvoří vrstvy: obvykle typ McCulloch-Pitt

Proces učení (trénink)

• modifikace synaptických vah a prahů podle

zvoleného algoritmu učení

• výběr charakteristických rysů a zkušeností

ze vstupních signálů

• nastavení parametrů UNS tak, aby odchylka

(v dané metrice) mezi požadovaným a

skutečným výstupem při odezvě na soubor

trénovacích vzorů byla minimální

Principy učení a jeho druhy

Topologie: cyklická (rekurentní)

aproximace nelineárních vztahů

acyklická (dopředná)

nelinární dynamické systémy

UNS jsou schopné analyzovat a rozpoznat určité

množství reálných vzorů. Reálná data jsou často

zašuměná. Není tedy možné klasifikovat správně

úplně všechny vzory.

Dělení způsobů učení (příklady)

I.

1. neasociativní - jednou nebo opakovaně je

předkládán síti vzor nebo

skupina vzorů bez uvažování

jejich vzájemných souvislostí

Cíl: uchování v paměti a vybavování

2. asociativní - cílem je extrakce vztahů mezi

jednotlivými vzory nebo

skupinami vzorů

II.

1. učení s učitelem - (supervised learning)

Perceptron, Adaline, Madaline,

metoda zpětného šíření chyby

2. učení bez učitele - (unsupervised learning)

spojité Hopfieldovy sítě, LVQ,

Kohonenovy samoorganizující

se mapy, asociativní paměti

III.

1. jednorázové učení

2. opakované učení

Proces opakovaného učení

A)

• daný počet opakovaného předkládání téhož vzoru

• otestování na velikost chyby

• proces je ukončen nebo pokračuje

B)

• daný počet opakovaného předkládání téhož vzoru

• otestování na velikost chyby

• systém je klasifikován a „odměněn“ nebo „trestán“

C)

posilované učení (reinforced learning)

D)

adaptivní upravování na základě výsledků

z předchozích kroků

Pravdivostní tabulka:

(pro konjunkci) Aktivita

x y výsledek

1 1 1

logický součin 0 1 0

1 0 0

0 0 0

v daném okamžiku musí být aktivní oba neurony

současně

w i j (t+1) = w i j (t) + α y i (t) x j (t)

Základní zákony učení

(learning rules, learning algorithms)

Hebbův zákon učení

(Hebbian learning)

základ všech současných modelů, odvozen z analogie

s učením biologických systémů, pro formální neuron

ij

ijxy

dt

dw

Jeden vstupní vektor x a požadovaný výstup tar

Neuron typu McCulloch-Pitt

Aktivační funkce: skoková (threshold, hardlimit)

Klasifikace pouze do dvou tříd

Modifikace vah: w (t+1) = w (t) + (tar – y) x (0 < <1/|k|) , k … je maximální modul

tréninkových vzorků

Minimalizace chyby: y = (tar – y) = 0

správný výstup y = (tar – y) = 1

wij se nemění

chybný výstup

modifikace wij

Zákon učení perceptronu

!

Učení konverguje pouze v případě tréninkových

vzorků z lineárně separabilního prostoru. !

Metoda nejmenších čtverců

Widrow - Hoffův zákon - LMS

Least Mean Square

účelové učení (performance learning) – hledá se soubor

vah, který odpovídá extrému účelové funkce

Vyjadřuje rozdíl naměřených a vypočtených hodnot.

mění váhy a prahy v souhlase s velikostí chyby

pro vrstevnaté sítě – minimalizuje chybu pro

všechny trénovací vzory

Pravidlo delta (Delta rule):

chyba je redukována postupně pro každý

vzor nebo skupinu vzorů - skupinová adaptace

(batch updating)

wij = wij (t + 1) – wij (t)

wij =

(k) je chyba, N je počet tréninkových vzorků,

xi (k) je vstup

N

k 1

(k)xδ(k) i

Inspirace: organizace mozku do oblastí – map,

podmnožiny podobných vektorů jsou

navzájem propojeny.

Praktické aplikace: sítě tvořené asi 1 000 neurony,

učení časově náročné, výkonné počítače

Použití: zejména pro analýzu velkého počtu

vstupních parametrů, např. při

technologických procesech (VLSI),

při rozpoznávání řeči – jen dílčí problémy,

pro identifikaci řečníka, v robotice (řízení

ramene robota v nepřístupném prostředí,

pohyb robota v labyrintu ). Problém

obchodního cestujícího. Při detekci poruch

řeči, při zpracování biologických signálů

(EEG, EKG, MEG)

magnetoencefalograf

Samoorganizující se neuronové sítě ( Self – Organizing Maps )

SOM

Neuronové sítě s učením bez učitele

(unsupervised learning)

Princip: učení je založeno na schopnosti NN

rozeznat ve vstupních vzorech stejné

nebo blízké vlastnosti a třídit přicházející

vektory podle nich. Podobné vektory

sdružuje do shluků (clusters)

měnící se vektory vah nejsou porovnávány

s požadovanými (target) hodnotami

Použití: tam, kde neznáme správné řešení,

pro shlukování, vizualizaci, pro abstrakci

nelze: pro rozpoznání statistických veličin

Pozn: při nesprávné volbě úlohy jsou výsledky trénování

špatné

Kritérium: výpočet vzdálenosti mezi vzory

a aktuálními hodnotami,

hledání extrémů minimální vzdálenost

maximální výstupní

hodnota

sekvence vzorků : x = x ( t ) Rn t … čas

množina referenčních vektorů:

w i ( t ) : w i Rn , i = 1, 2,… , k

w i ( 0 ) inicializace

Kompetitivní učení ( Competitive learning )

Zákon kompetice, soutěžní učení

lokální propojení, signál je šířen také k sousedním

neuronům, každý vstupní vektor vzorů je v každém

časovém okamžiku porovnáván s každým vektorem Wj

Míra porovnání : vzdálenost d (X, Wj )

Index j = c je index nejbližšího referenčního vektoru.

Pak vzdálenost

d (X, Wc )

je minimum všech vzdáleností.

Vektor Wc se nazývá vítěz v soutěži (kompetici)

(winner, centroid)

Pozn.: referenční vektory

bývají značeny také

jako mi

Míru naučenosti určujeme pomocí vzdálenosti

resp. blízkosti reprezentace vzorů.

Nejčastěji používané vzdálenosti:

• Euklidovská - pro pravoúhlý souřadnicový systém

• Hammingova – pro binární vektory ( 0, 1 )

Určuje jaké množství elementů dvou vektorů

je různé. Lze ji použít na porovnání jakýchkoliv množin

z diskrétních hodnot

• Minkowskiho – zobecnění Euklidovské vzdálenosti

Elementy vektorů jsou buď binární hodnoty (0, 1) nebo

písmena abecedy.

x = (1, 0, 1, 1, 1, 0) u = (p, a, t, t, e, r, n)

y = (1, 1, 0, 1, 0, 1) w = (w, e, s, t, e, r, n)

dH (x,y) = 4 dH (x,y) = 3

n

i ii

nn

yxyx

yxyxyx

1

2

22

11

)(),(

)()(),(

E

E

d

d

/1

1

),(

n

i

ii yxyxMd

Hodnoty signálu sousedící v prostoru nebo v čase

jsou představovány vzorky (patterns)

uspořádaná množina reálných čísel - vektor

Elementy vektoru X = (x1, x2 ,…, xn) představují

souřadnice v prostoru n-té dimenze

spatially temporally

Koncepce deterministická nebo stochastická

(přirozenější)

Hodnoty vzorků jsou pravděpodobností (samples),

mohou nabývat diskrétní nebo spojité hodnoty.

Jde o funkci rozložení pravděpodobnosti

Do dnešní doby bylo metodě SOM věnováno kolem 4000 článků,

speciální workshopy a samostatné sekce na všech velkých konferencích

Reprezentace dat

Na Internetu :

Kaski, S., Kangas, J., Kohonen, T.: Bibliography of self-

organizing map

(SOM) papers: 1981-1997. Neural Computing Surveys,

1(3&4):1-176, 1998

Knihy:

Kohonen, T.: Self-Organizing Maps. Berlin Heidelberg, 3-rd ed.

Springer Series in Information Sciences, Springer-Verlag, 2001,

ISBN 3-540-67921-9

Software: http://www.cis.hut.fi/research/software.shtml

SOM_PAK (UNIX)

http://www.cis.hut.fi/software.shtml

SOM Toolbox (Win NT)

http://www.mbnet.fi/~phodju/nenet/Nenet/General.html

Kde je možné najít literaturu?

Kohonenovo učení

základní myšlenka

prostorová reprezentace dat

komprese dat

transformace z n - rozměrného na m - rozměrný prostor

n > m

propojení mezi sousedními neurony

model neuronu McCulloch-Pitts

nepracuje se s aktivační funkcí, ale s funkcí okolí

(neighborhood function)

výpočet vzdáleností a jejich minimalizace

centroid (winner)

neuron patří do

okolí

neuron nepatří

do okolí

okolí

vstupní vektor x(t)

váhy w- referenční vektory

předem zvolená topologie mapy a okolí

– často čtvercová nebo hexagonální

způsob modifikace velikosti okolí

Kohonenův algoritmus učení ( Delta pravidlo)

pp. Euklideovská metrika

Obecně: mapa nejčastěji dvojdimenzionální

(principielně neexistuje omezení v počtu

dimenzí)

volba okolí (neighbourhood ) s předem

známou topologií

konvergence učení - závisí na mnoha parametrech

• inicializační hodnoty vstupních parametrů a vah

(hodnotách referenčních vektorů),

• počet neuronů a způsob jejich organizace v mapě,

• tvar a velikost sousedního okolí i-tého neuronu,

• rychlost učení

při učení nejsou jednotlivé neurony na sobě navzájem

závislé, sdružují vektory s podobnými vlastnostmi

je hledán vítězný neuron (winner)

cíl:

rozdělení vstupních dat na kategorie (třídy)

- klasifikace

shlukování (clustering)

Shluk (cluster) je tvořen určitým počtem vstupních

vektorů, které se sobě nejvíce podobají

(mají nejvíce společných nebo velmi blízkých vlastností.

Možný počet rozdělení P vzorků do K tříd:

KP / K! jen pro malý počet vzorů

Určení míry podobnosti (similarity measure)

resp. míry neshody

Nejčastěji vzdálenost

Je to oblast v N-dimenzionálním prostoru (data jsou

popsána N vlastnostmi – features) s relativně vysokou

hustotou bodů a je oddělena od ostatních oblastí s

relativně nízkou hustotou bodů.

Důležité: - rozmístění v mapě

- počet dominantních vlastností v rámci

jednoho tréninkového procesu

- posun ve vstupních datech a „přeřazení“

některé vlastnosti do jiné skupiny při

opakování procesu.

Problém: počet shluků

Poloměr okolí Nc je funkcí času, s rostoucím

časem se zmenšuje

Proces končí pro Nc = c

Okolí je totožné s vítězným neuronem

Kohonenův algoritmus přejde na jednoduché

kompetiční učení.

vítězný neuron: d(X, Wc ) = mini [d(X, Wi )]

dj (X, W) = , j=1,…,N

X = [x1, x2 ,…,xN ],

Wi = [wi1, wi2,…,wiN ]

2

1

)( ij

n

i

WX

Vektory blízké neuronu „c“ patří do jeho okolí, jejich váhy

jsou adaptovány v souhlase s algoritmem učení. Tvoří

jednotlivé shluky. Váhy neuronů ležících vně okolí „Nc“

se nemění.

Do okolí (neighbourhood) se klasifikují všechny vstupní

vektory nejvíce se podobající vítězi.

Vždy klasifikační úloha.

Topologie mapy (kompetitivní vrstvy) i okolí budoucího

vítěze jsou předem zvolené.

Příklady topologií Kohonenovy mapy

a okolí vítězného neuronu.

Váhové vektory v

KSOM:

a) rozložení při

inicializaci

b) po 20-ti

iteracích

c) po 40-ti

iteracích

d) po 100 iteracích

Vektory vah během trénování, 1-D mapa

Reprezentace 3-D funkce rozložení pomocí 2-D mapy