Umělé neuronové sítě a Support Vector Machines

transcript

Petr Schwraz

schwarzp@fit.vutbr.cz

Perceptron (1 neuron)

bxwfy i

Nxf() y

xi – vstupy neuronuwi – váhy jednotlivých vstupůb – aktivační práhf() – nelineární funkce

Co umí perceptron?

• Chceme klasifikovat mezi dvěmi třídami, řekněme, že:

pokud y>=0, vstupní vektor spadá do třídy 1.

pokud y<0, vstupní vektor spadá do třídy 2.• Pro zjednodušení náš vstupní vektor má pouze

dvě dimenze, předpokládejme f(a)=a• Kde je hranice mezi třídami?

bxwfy i

Co umí perceptron? II

• hranice mezi třídami je přímka => lze řešit pouze lineárně separovatelný problém

wx 0y =>

Transformační funkce f(a)• Nejprve bez ni: f(a) = a, w1=2, w2=4, b=5

Transformační funkce f(a) II

• Sigmoida

• Omezuje dynamický rozsah výstupu neuronu v místě, kde si je neuron jist

Třívrstvá dopředná neuronová síť

• je schopna aproximovat libovolnou nelineární funkci• první vrstva pouze kopíruje vstup, dvě vrstvy neuronů• M výstupních neuronů

vstupní

Co umí třívrstvá síť

• Neurony ve druhé vrstvě (skryté) mají přenosovou funkci Sigmoidu, výstupní neuron má lineární přenosovou funkci

Trénování síté

• Pro experiment je potřeba mít tři sady dat:

trénovací, krosvalidační, testovací• Sady obsahují vektory parametrů a požadované

výstupní vektory neuronové sítě (targets)• Je dobré data nejprve normalizovat• Je potřeba správně zvolit chybovou funkci • Je potřeba správně zvolit trénovací algoritmus

Normalizace dat

• z každého vektoru se odečte vektor středních hodnot odhadnutý na trénovací sadě a pak se vektor podělí vektorem směrodatných odchylek

• Dynamický rozsah hodnot se přizpůsobí dynamickému rozsahu vah

bez normalizace xx~

Kriteriální funkce• ; t je target (chtěná hodnota)

– nejmenší čtverce (minimum square error) – chybová funkce je citlivá na vyvážení dat setu pro

jednotlivé třídy– je citlivá na distribuci dat uvnitř tříd

target pro třídu 1

target pro třídu 2

iii ytE

Back propagation

1. Váhy a prahy sítě se nainicializují náhodně

2. Pošlou se data skrze síť

3. Vypočte se chyba

4. Chyba se pošle zpět sítí

5. Podle chyby se upraví jednotlivé váhy a prahy

Zpětné šíření chyby

Zjednodušení zápisu: w0=b, x0=1

Hledáme minimum chyby

kde yi je výstup i-tého neuronu výstupní vrstvy, ti je chtěná hodnota i-tého neuronu výstupní vrstvy, je váha z j-tého neuronu skryté vrstvy k i-tému neuronu výstupní vrstvy, je výstup z j-tého neuronu skryté vrstvy

iii xwftytE

2 ))(()(

iixwfy

Zpětné šíření chyby II

ohiioh

xxwFytw

)(')(20

Chyba váh mezi skrytou a výstupní vrstvou:

Chyby neuronů ve skryté vrstvě:

oh – output-hidden

Eij)('

Chyby vah mezi vstupní a skrytou vrstvou:

hi –hidden-input

Úprava vah

newij w

Úpravu vah lze dělat:

1. po předložení všech vektorů trénovací sady (chyby se akumulují)

´- nejsprávnější přístup, ale pomalý

2. po každém vektoru

- rychlé trénování

- riziko, že se síť natrénuje na posledních pár vektorů z trénovací sady

- nelze optimálně využít cache procesoru

3. po předložení několika vektorů

Ochrana proti přetrénování

• používá se krosvalidační sada

• algoritmus New Bob:

1. proved jednu iteraci trénovaní

2. zjisti úspěšnost NN na CV sadě

- pokud přírustek je menší než 0.5%, sniž rychlost trénování na ½ ( )

- pokud přírustek opětovně menší než 0.5%, zastav trénování

• jdi na 1.

Implementace NN

• Trénovací algoritmus a i dopředný průchod sítí lze zapsat maticově (viz. diplomová práce - Stanislav Kontár), používají se akcelerované knihovny pro maticový počet (BLAS, ATLAS)

• Optimální využití cache procesoru• Zarovnaní všech paměťových struktur na 16-ky

bytes pro SIMD instrukce procesoru (SSE)• Software: Matlab, QuickNet, SNet

Pravděpodobnostní interpretace výstupů neuronových sítí

• Ze statistiky: pravděpodobnost lze transformovat z intervalu 0÷1 do intervalu -∞÷∞ pomocí funkce logit, kde se dobře modeluje:

• a nazpět:

vzorec je již použitá Sigmoida

1log)logit(

SoftMax• Chceme aby součet všech výstupů NN byl 1:

• Lze zajistit SoftMaxem - nelineární funkcí na výstupu NN, která jednotlivé výstupy spojuje:

• SoftMax se většinou pojí s Cross-entropy chybovým kritériem:

- klade větší důraz na chyby z hlediska pravděpodobnosti – když je má být výstup 1, nikdy nemůže být 0

iiiii ytytE

)1log()1(log

Support Vector Machines

• SVM je perceptron (jeden neuron) s lineární výstupní funkcí

• Rozdíl a výhoda je v trénovacím algoritmu !!!• V základní verzi zvládne pouze lineárně

separovatelnou, a dvě nepřekrývající se třídy

bbxwy i

SVM – chybové kritérium• Maximalizuje mezeru (margin) mezi dvěmi

shluky dat

Jak hýbat s mezerou mezi shluky?

• Máme diskriminační linii, která je dána normálovým vektorem w (váhy)

• I když se mění délka w (označíme |w|), tak sklon linie zůstává stejný (offset je dán prahem b)

• Pokud se mění |w|, tak se linie posouvá• Tohoto můzeme využít!

Příklad ve 2D

• Rovnice diskriminační linie

• Pokud násobíme w libovolnou konstantou, směrnice přímky ( ) se nemění

• Přímka se vzdaluje od počátku nepřímo úměrně |w|.

Geometrická reprezentace

• Mámě dva body• Chceme aby pro jednu třídu dával klasifikátor hodnoty 1 a pro

druhou -1: <w.x+>+b=+1, <w.x->+b=-1• Hodnoty na výstupu klasifikátoru nemají odpovídající geometrický

vztah k datům, proto normalizujeme vektor w jeho délkou

Geometrická reprezentace II

Trénování SVM

• Minimalizujeme délku |w|, čímž roztahujeme mezeru mezi shluky, hledáme optimální b a zároveň zavádíme omezující podmínky, aby mezera „nešla“ do dat.

• Minimalizace |w| je problematická, protože obsahuje odmocninu, proto raději budeme minimalizovat w2

Trénování SVM II

• Minimalizujeme

• S podmínkami:

l je počet trénovacích vektorů

• K minimalizaci se používá metoda Lagrangeových násobitelů (Lagrange multipliers)

.min,b

1).( bxwy ii li 1

Trénování SVM III – zápis pomocí Lagrangianu

• Minimalizujeme• Podmínka• V místě řešení platí

• Lagrangian:

1).( bxwyg ii

)(.)( xgxf

iiii bxybL

]1).([,2

1),,( wwww

Důalní úloha

• Při minimalizaci se obvykle Lagrangian zderivuje, položí nule a najde minimum

• Při trénování SVM se ale přechází na „duální úlohu“ nebo „duální problém“, která zjednodušuje řešení a umožňuje použití skalárních součinů mezi daty (tzv. jader nebo kernels)

• Duální úloha má stejné řešení jako původní (primarní) úloha a existuje pro linearní nebo kvadratické úlohy.

Přechod na duální úlohu

iiiiyw

0 0),,(

bL αw

• Dosazením zpět do Lagrandgianu

jijijijii yybL

1),,( xxαw

Dostali jsme funkci jedné proměnné, kterou maximalizujem s podmínkami

• Řešením je vektor vah získaný váhováním trénovacích dat

• Tato reprezentace umožňuje zavedení skalárních součinů mezi daty (jader, kernels) i při klasifikaci

Řešení

.. xxxw

• Práh b nelze získat z duální úlohy, proto je nutné dosadit do podmínek primární úlohy.

Řešení II

.min.max 11 iyiy iibxwxw

Co jsou to Support Vectors?

• Jsou to vektory které leží na okraji prázdné oblasti a přímo ovlivňují řešení

• Pro ostatní vektory bude αi=0 a kdyby se vypustily z trénovacího setu, výsledek by se nezměnil

x2support vectors

Lineárně neseparovatelná úloha

• Může být řešena mapováním dat do prostoru s více dimenzemi

• Jádra mohou být počítána optimálně bez přímého mapování

Příklad jádra

• Bod x=(x1, x2)• Projekce do vícedimenzionárního prostoru

může být Φ(x)={x1, x2, x12, x2

2}• K(x, y) = <Φ(x). Φ(y)> = x1 y1+ x2 y2+ x1

y12+ x2

2 y22,což potřebuje 8 nasobení a 4

součty• Toto muže být přepsáno na

K(x, y) =x1 (y1+ x1 y12)+ x2 (y2+ x2) y2

2, což potřebuje 6 nasobení a 3 součty

Překrývající se třídy

• Pro překrývající třídy uvedene řešení selže.

• Zavádějí se promněnné (slack variables), které oslabí omezující podmínky

Překrývající se třídy II

• Minimalizujeme

• S podmínkami:

• První term maximalizuje mezeru mezi shluky dat a druhý minimalizuje takzvanou strukturální chybu

• C udává důležitost strukturální chyby• Pokud je C velké, SVM funguje podobne jako

perceptron

.min www

iii bxwy 1).( li 10i

Použití

• Výhodné při znalosti jednoho pozitivního vzoru a velkého množství negativních (rozbalancovaná data)

• Při velmi velkých dimenzích vstupních vektorů

• Při řídkých datech

Software

• Existuje velni dobrá knihovna LibSVM

http://www.csie.ntu.edu.tw/~cjlin/libsvm/

Závěr

• Důležité je vždy nejdříve důkladně zapřemýšlet nad úlohou a podle toho zvolit správný klasifikátor, než se snažit bezhlavě optimalizovat náhodně vybraný klasifikátor na pro něj nevhodnou úlohu.

Umělé neuronové sítě a Support Vector Machines

Documents