Vektorová kvantizace
Obecná formulace problému:
Dána hustota pravděpodobnosti p(x) na vstupních vektorech x e R".
Tj. předpokládáme, že „něco" náhodně generuje vstupní vektory podle rozložení s hustotou p(x).
► Cílem je aproximovat hustotu p(x) pomocí konečně mnoha reprezentantů w, e R" kde ;' = 1,...,h.
Velmi zhruba: v oblasti s větší hustotou by mělo být více reprezentantů, v oblastech s menší hustotou méně.
► Formálněji: danému vstupnímu vektoru x přiřadíme reprezentanta wc, který je mu nejblíže:
a poté minimalizujeme chybu
Pozor! Zde c závisí na x.
Vektorová kvantizace
V praxi často máme často k dispozici tréninkovou množinu
T = {itjeMn\j=J\,...,€}
z níž jsou vzory rovnoměrně vytahovány. Chyba potom odpovídá
y'=i
Pokud byla množina T volena náhodně (dle rozložení p(x)) a l je dost velké, pak
^ZjH^_^cI|2 ~ f II*- wc\\2p(x)dx
Příklad - komprese obrázků
► každý pixel má 256 stupňů šedi.
► každá dvojice sousedních pixelů je dvourozměrným vektorem z {0,...,255}x{0/.../255}
► komprese najde malou množinu reprezentantů, kteří budou kódovat stupně šedi dvojic pixelů (pro danou dvojici vezmeme nejbližšího reprezentanta)
► obrázek se potom zakóduje jednoduchým průchodem při němž se dvojice pixelů nahradí reprezentanty
3
Příklad - komprese obrázků
Lloydův algoritmus
Přepodkládáme konečnou tréninkovou množinu:
{)tj\)tjeMn\j= !,...,€}
Algoritmus postupně posouvá reprezentanty k tréninkovým vzorům.
V kroku ř vypočte takto: ► pro každé k = 1,..., h spočítej množinu T< vektorů z T, které jsou nejblíže w£ř~1^:
XjET
k = arq min
1=1.....h
Xj - Wj
(ř-1)
spočítej      jako těžiště množiny T \Tk\
w.
xeTk
Výpočet ukončíme např. ve chvíli, kdy je chyba E pro aktuální reprezentanty dostatečně malá.
Kohonenovo učení
Nevýhoda Lloydova algoritmu: není online! (mimo jiné ...)
Následující Kohonenův algoritmus je online (připouští obě verze vstupů: náhodně generované i dané tréninkovou množinou).
V kroku ř po předložení vstupu xt vypočteme takto:
Jestliže je     ^ nejblíže xt, tj. k = arg min,
i
(t-1)
pak
w,
(0
w,
(t-1)
+ 9 ■ (xt
w,
(ř-1)
jinak wl^ = w.
' k I
»,(f-1)
Parametr 0 < 9 < 1 určuje míru posunu reprezentanta ve směru ke vstupnímu vzoru. Na začátku učení se obvykle volí blízko 1 a postupně se zmenšuje.
Tento algoritmus lze snadno formulovat v jazyce neuronových sítí...
Kohone
ni - neuro
nová síť
Organizační dynamika: Jednovrstvá síť
Aktivní dynamika: Pro vstup x e R" ak = 1,..., h:
11 k = arg minf=1/..v/l ||x - vv,-| lO jinak
Kohonenovo učení - neuronová
Adaptivní dynamika (online algoritmus, Kohonenovo učení):
V kroku ř po předložení vstupu xt adaptujeme každé takto
Jestliže k
>,(0 _
argmin/=1.....h
xt - w
(ř-1)
pak
w,
(ř-1)
+ 0(ř)-(x-w[ř-1))
jinak vv^ = vv;
»,(f-i)
Parametr 0 < 9 < 1 určuje míru změny vah ve směru ke vstupnímu vzoru. Na začátku učení se obvykle volí blízko 1 a postupně se zmenšuje.
Efektivita Kohonenova učení
► Funguje dobře pokud většina vstupu zhruba rovnoměrně pokrývá jednu konvexní oblast.
► V případě dvou a více oddělených shluků nemusí hustota reprezentantů odpovídat hustotě rozložení:
► Př. dvě oddělené oblasti se stejnou hustotou.
► Předp., že vzory jsou iniciálně rozmístěny v jedné oblasti.
► Druhá potom přitáhne jednoho reprezentanta, který poté vždy vyhraje soutěž.
► Výsledek: jedna oblast bude reprezentována jedním reprezentantem, druhá zbytkem reprezentantů (hustota reprezentantů tedy neodpovídá hustotě pravděpodobnosti).
9
Částečná zlepšení Kohonenova učen'
Tyto nedostatky lze částečně odstranit např.
► přidáním šumu k tréninkovým vzorům - obvykle se přidávají náhodně generované vektory k tréninkovým vzorům, na počátku učení náhodné vektory převažují a postupně je jejich počet snižován
► radiální růst
► začínáme s váhovými vektory blízko 0
► všechny tréninkové vzory násobíme faktorem jS, který je na počátku blízko 0 a postupně roste
(váhy se musí postupně vzdalovat od 0)
► lokální paměť: Cílem je, aby pravděpodobnost vítězství každého z h neuronů (reprezentantů) byla zhruba 1 /h.
Každý neuron si udržuje přehled o tom kolikrát vyhrál v soutěži. Pokud je četnost výher příliš vysoká, na nějakou dobu vypadne ze soutěže.
10
Kohonenova mapa
Organizační dynamika: Jednovrstvá síť
yi y k y h
X^ X; xn
► Mezi neurony je navíc zavedena topologická struktura (tj. neurony tvoří uzly neorientovaného grafu).
► V drtivé většině případů je tato struktura buď jednorozměrná řada jednotek nebo dvojrozměrná mřížka.
Kohonenova mapa - ilustrace
Kohonenova mapa - bio odbočka
posterior cortex (lobjs occipitalis)
visual field of the right eye 0
center of the visual field and corresponding cortex region
visual field and corresponding cortex region
Fig. 15.2.  Mapping of the visual field on the cortex Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996
Kohonenova mapa
Aktivní dynamika: Pro vstup x e R" a k
fl k = argminf=1/..v/l ||x- w,|| lO jinak
\,...,h:
Adaptivní dynamika: V adaptivním režimu využijeme topologickou strukturu.
► Označme d(c,k) délku nejkratší cesty z neuronu c do neuronu k v topologické struktuře.
► Pro neuron c a dané s £ No definujeme okolí neuronu c velikosti s takto: Ns(c) = [k \ d{c,k) < s]
V kroku ř po předložení vstupu xt adaptujeme každé wk takto:
w,
(0
w,
w,
(t-1)
k
(f-1)
+ 0-(xř-4ř_1)) k£Ns(c)
kde c = arg min/=1/..v/l
xř -
.(t-1)
jinak
a kde 0 e R a s £ N0 jsou
parametry, které se mohou v průběhu učení měnit.
Kohonenova mapa - adaptivní dynamika
Obecnější formulace adaptivní dynamiky:
w,
(0
>(f-i)
wr ' + 0(c,/c)-(x-^ř-1))
kde c = arg min,-^..^ odpovídá
xt - w
(ř-i)
. Předchozí případ potom
e(c,/c)
\e keNs(c) lO jinak
Obvykle se používá plynulejší přechod mezi nenulovými a nulovými hodnotami, např.
®(c,k) = 6q ■ exp
-d{c,kf
kde 0O e K určuje maximální míru změny vah a o e R je šířka (oba parametry se mohou v průběhu měnit).
Příklad 1
Vstupy jsou uniformně rozloženy v trojúhelníku.
Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996
17
Příklad 3
Příklad 4
Příklad - defekt
Překroucená síť - topologický defekt.
Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996
Kohonenova mapa - parametry - pohled praktika
Iniciální váhy (prý) nejsou příliš důležité, pokud jsou různé. Učení se obvykle sestává ze dvou fází: hrubé učení:
► obvykle cca 1000 kroků
rychlost učení 9 by měla začít kolem 0.1 a postupně klesat k 0.01
► okolí každého neuronu (dané parametrem s nebo případně šířkou o) by mělo zpočátku obsahovat většinu neuronů a postupně se zmenšovat tak, aby ke konci této fáze obsahovalo nejvýše několik neuronů
dolaďování:
*■ počet kroků je obvykle volen jako 500 násobek počtu neuronů v síti
► 9 by se měla držet kolem 0.01 jinak hrozí topologický defekt (zmačkaná síť)
► okolí každého neuronů by mělo obsahovat jen pár dalších neuronů (nebo jen ten jeden)
Kohonenova mapa - pohled teoretika
Předpokládáme náhodně generované vstupy s hustotou pravděpodobnosti p(x). Platí Jp(x)dx = 1.
Definujeme hustotu bodů m(x) = #(x)/dx kde #(x) je počet neuronů jejichž váhové vektory leží v malém okolí dx bodu x ve vstupním prostoru. Platí
kde h je počet neuronů (reprezentantů).
Pokud je dimenze mapy rovna jedné (tj. mapa je řetězcem neuronů) pak po natrénování
m(x) cc p2/3(x)
Kohonenova mapa - pohled teoretika
► Konvergenci k uspořádanému stavu se podařilo dokázat pouze pro jednorozměrnou topologii a různá rozložení vstupů (první výsledky byly pro uniformní rozložení) a fixní okolí velikosti 1 a konstantní rychlost učení
Lze nalézt velice jednoduché protipříklady pokud tyto podmínky nejsou splněny.
► Ve vícerozměrném případě žádné obecné výsledky neexistují, konvergence do uspořádaného stavu je ovlivněna mnoha faktory:
► iniciální rozložení neuronů
► velikost okolí
► rychlost učení
► Jakou dimenzi topologie zvolit? Drtivá většina aplikací je založena najedno nebo dvoudimenzionální mapě. Experimenty prokázaly, že ideální dimenze topologie odpovídá (Haussdorfově) dimenzi dat.
23
LV
- klasifikace pomocí Kohonenovy mapy
Přepodkládejme, že máme náhodně generované vzory tvaru (xř/ dt) kde xt e Rn je vektor vlastností a dt e {d,..., Cq} určuje jednu z q tříd.
Cílem je klasifikovat vstupy do tříd na základě znalosti vlastností, tj. každému xř chceme přiřadit třídu tak, abychom minimalizovali pravděpodobnost chyby.
Př.: Po pásu jede náhodně „naházené" ovoce dvou druhů: jablka a meruňky. Námi sledovaná data budou (xř, dř) kde
► x( e R2, první vlastnost je hmotnost, druhá je průměr
► dt je buď J nebo M v závislosti na tom, jestli je daný kus jablko nebo meruňka
Připouštíme možnost, že se najdou dvě jablka se stejnými mírami. Cílem je třídit ovoce na základě hmotnosti a průměru.
24
LV
- klasifikace pomocí Kohonenovy mapy
Využijeme vektorovou kvantizaci (Kohonenovu mapu) takto:
1. Natrénujeme mapu na vektorech vlastností xt kde \ = \,...,l.
2. Jednotlivé neurony označíme třídami. Třídu vc neuronu c nalezneme takto:
Pro každý neuron c a třídu C, spočítáme četnost vzorů třídy Q, které jsou reprezentovány neuronem c.
Toto lze provést jedním průchodem přes vzory
Neuronu c přiřadíme třídu s maximální četností.
3. Doladíme síť pomocí algoritmu LVQ (viz. dále)
Klasifikaci pomocí natrénované sítě provádíme takto: Na vektor vlastností x aplikujeme natrénovanou síť v aktivním režimu. Právě jeden neuron, řekněme c, bude mít výstup 1. Potom vstup zařadíme do třídy vc.
LVQ1
Postupně projdi tréninkové vzory. Pro vzor (xtldt) urči nejbližší neuron c
c = arg min ||x(-vv/||
Parametr a by měl být od počátku malý (cca 0.01 - 0.02) a postupně klesnout k 0.
Hranice mezi třídami vytvořená pomocí LVQ1 je poměrně dobrou aproximací bayesovské rozhodovací hranice.
Co to je??
;=1,...,/!
Potom uprav váhy neuronu c takto:
dt = vc dt * v c
26
Bayesovský klasifikátor
Mějme pouze dvě třídy Co a Ci (např. J a M).
Nechť P(C, | x) je pravděpodobnost, že je vstup z třídy C, za přepodkladu, že má vlastnost x. (např. P(Co | (a,b)) vyjadřuje pravděpodobnost, že ovoce s hmotností a a průměrem b je jablko)
Bayesovský klasifikátor přiřadí vstupu s vektorem vlastností x třídu Q, která splňuje P(C, | x) > P(C^-j \ x). Označme fí0 množinu všech x, která splňují P(C0 | x) > P(Ci | x) a Pit = Rn \ Pi0-
Bayesovský klasifikátor minimalizuje pravděpodobnost chyby:
P(X £ Pio A d) + P(X £ Pit A C0)
Bayesovská hranice je hranicí mezi množinami R0 a Ri.
27
Bayesovská hranice a LVQ1 - příklad
Aproximaci bayesovské hranice je možné zlepšit následujícím způsobem:
Pro vzor (xř, dt) určíme dva nejbližší neurony, řekněme ; a j s aktuálními váhami vvíř~1^ a vvíř~1^.
Jestliže jsou splněny následující dvě podmínky
► xř se nachází v okně okolo nadroviny umístěné ve středu
■ ■     ->(f-l) -»(ř-i) spojnice wy   ' a vir 'a
jeden z neuronů ;' a j klasifikuje správně a druhý špatně
pak aktualizujeme váhy takto (bez újmy na obecnosti předpokládejme, že neuron ;' klasifikuje správně):
v5jt) = v5řt-1)+a(i?t-v5řt)) = wj^ - a(xt - ^)
29
LVQ2
Okno je obvykle definováno takto: Řekneme, že xt se nachází v okně relativní šířky q mezi wjl~^ a vv'ř~1^ pokud
d i   dj\ ^ 1 -q 1 +Q
kde d.
(ř-i)
a d,
xt - wj
(ř-1)
Obvykle se volí q mezi 0.1 až 0.3.
LVQ2 zlepšuje pozici rozhodovací hranice tím, že ji posunuje k bayesovské hranici, ale jen do určitého počtu kroků. Později se neurony začínají vzdalovat (typicky se používá kolem 10 000 iterací).
30
LVQ3
LVQ3 se snaží odstranit defekt LVQ2 tím, že dobře klasifikující dvojici nejbližších neuronů posunuje směrem k vzoru (LVQ2 v takovém případě nedělá nic):
Nejprve „LVQ2 část":
^ = ^-a{xt-wf))
pokud ;' a y je pár výstupních neuronů nejblíže k xt, v, = dt, Vj + dt a xt patří do okna mezi      a wjl\
Navíc:
= ^ + ea(xt - 4t]) pokud r e [i, j} a v,- = vs = dt.
e se doporučuje nastavit dle šířky okna mezi 0.1 až 0.5 a nechat konstantní.
31