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