+ All Categories
Home > Documents > Kohonenovy mapy (struktura, geometrie,...

Kohonenovy mapy (struktura, geometrie,...

Date post: 27-Feb-2020
Category:
Upload: others
View: 3 times
Download: 0 times
Share this document with a friend
21
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)
Transcript
Page 1: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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)

Page 2: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 3: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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.

Page 4: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 5: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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ů

Page 6: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 7: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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. !

Page 8: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 9: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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)

Page 10: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 11: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 12: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 13: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 14: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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?

Page 15: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 16: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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í

Page 17: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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í.

Page 18: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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ů

Page 19: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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í.

Page 20: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

Page 21: Kohonenovy mapy (struktura, geometrie, architektura)amber.feld.cvut.cz/ssc/ssc-p/asnP2_16.pdfAlgoritmy a struktury neuropočítačů ASN - P2 • Topologie neuronových sítí, principy

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

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


Recommended