Vektorová kvantizace
Obecná formulace problému:
► Dána hustota pravděpodobnosti p(x) na vstupních vektorech x eKn.
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 Rn 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:
c = arg min
/=1
X - Wj
a poté minimalizujeme chybu
E =
x - wc
p{x)dx
Pozor! Zde c závisí na x
Vektorová kvantizace
V praxi často máme často k dispozici tréninkovou množinu
T = {xjelRn\j=-\,...,e}
z níž jsou vzory rovnoměrně vytahovány. Chyba potom odpovídá
E =
1 e
w.
Pokud byla množina T volena náhodně (dle rozložení p(x)) a £ je dost velké, pak
1 1
w.
x - wc
p(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ů
chytřejší kvantizace
Lloydův algoritmus
Přepodkládáme konečnou tréninkovou množinu:
{xj |xy-e JRn \j = \ ,...,t\
Algoritmus postupně posouvá reprezentanty k tréninkovým vzorům.
V kroku t vypočte w^\..., takto: ► pro každé k = \,...,h spočítej množinu T<< vektorů zT, které jsou nejblíže w[*~1^:
k = arg min \
-*(ŕ-l) X, - w. 1 i I
spočítej    ) jako těžiště množiny T/<:
4t} =
k
—r
X
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 t po předložení vstupu xt vypočteme takto: Jestliže je w£ř~1) nejblíže xř, tj. k = arg min/ xt - wf~^ pak
-+(r)     -+(M) , n  (^(ř-1)x
k ¥Vk
jinak wKkJ = wKk )
Parametr 0 < 6 < 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í...
Kohonenovo učeni - neuronová síť
Organizační dynamika: Jednovrstvá síť
Aktivní dynamika: Pro vstup xe~Rnak = '\,...,h
y k =
1   k = argmin/=1.....h x-Wj
0 jinak
Kohonenovo učení - neuronová síť
Adaptivní dynamika (online algoritmus, Kohonenovo učení):
V kroku t po předložení vstupu xt adaptujeme každé wk takto
Jestliže k = arg min/=1... h
pak
^r) = ^1) + 0(ř)-(x-^r-1))
k   ~ ¥'k
jinak tfW = tf(M>
Parametr 0 < 6 < 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.
8
Efektivita Kohonenova učení
► Funguje dobře pokud většina vstupů 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).
Čá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 /}, 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
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íť
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.
12
Kohonenova mapa - bio odbočka
posterior cortex (lobus occipitalis)
visual field of the right eye
0
center of the visual Held 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 = 1, ...,h
y k =
1 k = argminí=i,...,/, 0 jinak
X - Wj
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é sgN0 definujeme okolí neuronu c velikosti s takto: Ns(c) = [k | d{c,k) < s)
V kroku t po predložení vstupu xt adaptujeme každé wk takto
+ 0.(xř-^r"1)) keNs(c)
jinak
^(ř-1)
kde c = argmin/=1.....h
^(ř-1) xř - ;
a kde 6 e IR a s e N0 jsou
parametry, které se mohou v průběhu učení měnit.
Kohonenova mapa - adaptivní dynamika
Obecnější formulace adaptivní dynamiky:
^ = ^-1) + 0(c//c).(^-<-1))
kdec = argmin/=1/...//7 odpovídá
-*(M) xt-w) 1
. Předchozí případ potom
e(c,k) =
6 ke Ns(c) 0 jinak
Obvykle se používá plynulejší přechod mezi nenulovými a nulovými hodnotami, např.
Q(c,k) = 0O * ^p
-d{c,k)>
a'
kde 0O é ir určuje maximální míru změny vah a a e ir je šířka (oba parametry se mohou v průběhu měnit).
i 000
Vstupy jsou uniformně rozloženy ve čtverci.
Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996
Příklad 2
Vstupy jsou uniformně rozloženy v trojúhelníku.
Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996
Příklad 3
Vstupy jsou uniformně rozloženy v kvádru.
Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996
Příklad 4
Vstupy jsou uniformně rozloženy v kaktusu.
Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996
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í 6 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 a) 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
► 6 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í
J m (x) d x = h
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) oc p2/3(x)
22
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.
LVQ - 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 g {C-i,..., 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 xt 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 (xt,dt) kde
► Xjf g 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
LVQ - klasifikace pomocí Kohonenovy mapy
Využijeme vektorovou kvantizaci (Kohonenovu mapu) takto:
1. Natrénujeme mapu na vektorech vlastností xt kde
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 C,, 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.
25
Postupně projdi tréninkové vzory. Pro vzor (xt/dt) urči nejbližší neuron c
c = arg min
/=1
xt - Wj
Potom uprav váhy neuronu c takto:
W
w
= Vr
^+a(xt-w^) dt - a(xt - w^) dt±Vl
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??
Bayesovský
■ ■ *
Mějme pouze dvě třídy C0 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(C01 (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,1 x) > P(Ci_/1 x).
Označme Ro množinu všech x, která splňují P(C0 | x) > P(Ci | x) a fí1 = Rn \ R0.
Bayesovský klasifikátor minimalizuje pravděpodobnost chyby:
P(x gR0aCi) + P(xgRiA Co) Bayesovská hranice je hranicí mezi množinami R0 a .
27
Bayesovská hranice a LVQ1 - příklad
.->.;r,i>Si
t^^.l.' J-. |.-
I
Í2
n
Zdroj obrázku: The Self-Organizing Map, Teuvo Kohonen, IEEE, 1990
28
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 wf~^ a wíř~1^.
Jestliže jsou splněny následující dvě podmínky
► xt se nachází v okně okolo nadroviny umístěné ve středu spojnice w>   J awj   J 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ě):
Wj J = Wj   1 + a(xt - Wj J)
^(t)     -+(M)      (^ ^(ř)x
LVQ2
Okno je obvykle definováno takto: Řekneme, že xt se nachází v okně relativní šířky q mezi wy~^' a wr'^' pokud
di   dj\ \-q
kde dj =
xt - w) J
a dj =
-*(M)
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 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":
wy ; = wy 1 + a(xt - Wj J) ->(t)    -+(M)     ,-> -^(ř)x
pokud / a j je pár výstupních neuronů nejblíže k xř, Vj = dř, Vj ŕ dt a xt patří do okna mezi a
Navíc:
wy; = wrv   ; + £a(xř - w)J) pokud r g {/,;'} a v,- = v} = dř.
e se doporučuje nastavit dle šířky okna mezi 0.1 až 0.5 a nechat konstantní.