ˇ CESK E VYSOK E U ˇ CEN I TECHNICK E Fakulta jadern a a fyzik alnˇe inˇzen yrsk a DIPLOMOV A PR ACE 2006 Jan Vachulka

ˇ ´ VYSOKE ´ UCEN ˇ Í TECHNICKE ´ CESK E Fakulta jaderná a fyzikálnˇe inˇzenýrská

´ PRACE ´ DIPLOMOVA

2006

Jan Vachulka

ˇ ´ VYSOKE ´ UCEN ˇ Í TECHNICKE ´ CESK E Fakulta jaderná a fyzikálnˇe inˇzenýrská Katedra Matematiky

Monitorov´ an´ı pr˚ ubˇ ehu uˇ cen´ı neuronov´ ych s´ıt´ı s pˇ rep´ınac´ımi jednotkami Diplomová práce

Jméno : Jan Vachulka ˇ Skolitel : Ing. Frantiˇsek Hakl, CSc. Ak. rok : 2005-2006

Prohláˇsen´ı: Prohlaˇsuji, ˇze jsem pˇredkládanou práci vypracoval samostatnˇe, veˇskerá pouˇzitá literatura je uvedena v citac´ıch.

Podpis:

Obsah ´ 1 Uvod 1.1 Zamˇeˇren´ı a c´ıle diplomové práce . . . . . . . . . . . . . . . . .

4 4

2 Z´ akladn´ı definice 6 2.1 Formulace problému klasifikace do dvou mnoˇzin . . . . . . . . 6 2.2 Neuronová s´ıt’ . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Uˇcen´ı neuronové s´ıtˇe . . . . . . . . . . . . . . . . . . . . . . . 11 3 Neuron s pˇ rep´ınac´ı jednotkou 3.1 Neuron s pˇrep´ınac´ı jednotkou . . . . . . . . . . . . . . 3.2 Pˇrep´ınac´ı jednotka . . . . . . . . . . . . . . . . . . . . 3.3 Výpoˇcetn´ı neurony . . . . . . . . . . . . . . . . . . . . 3.4 Determinismus uˇcen´ı . . . . . . . . . . . . . . . . . . . 3.5 Srovnán´ı metod pouˇzitých pro uˇcen´ı pˇrep´ınac´ı jednotky 3.6 Srovnán´ı v závislosti na poˇctu vzor˚ u . . . . . . . . . . 3.7 Srovnán´ı v závislosti na poˇctu shluk˚ u . . . . . . . . . . 3.8 Závˇery . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

14 14 16 17 18 20 21 22 22

. . . . . . .

29 29 30 31 32 33 34 37

5 Urˇ cen´ı kvality neuronov´ e s´ıtˇ e 5.1 Základn´ı principy a motivace . . . . . . . . . . . . . . . . . . . 5.2 Kritérium nejmenˇs´ıch ˇctverc˚ u . . . . . . . . . . . . . . . . . . 5.3 Cross-entropy . . . . . . . . . . . . . . . . . . . . . . . . . . .

44 44 45 46

4 Interpretace v´ ystup˚ u neuronov´ e s´ıtˇ e 4.1 Pouˇzit´ı prahu . . . . . . . . . . . . . . . . . . 4.2 Zobecnˇen´ı pouˇzit´ı prahu . . . . . . . . . . . . 4.3 Pˇrevod výstup˚ u na pravdˇepodobnosti . . . . . 4.4 Histogramový odhad . . . . . . . . . . . . . . 4.5 Odhad parametr˚ u smˇesi normáln´ıch rozdˇelen´ı ´ 4.6 Uprava rozhodován´ı . . . . . . . . . . . . . . . 4.7 Srovnán´ı rozhodovac´ıch pravidel . . . . . . . .

1

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

5.4 Dalˇs´ı ztrátové funkce . . . . . . . . . . . . . . . . . . . . . . . 48 6 Benchmarky pro klasifik´ atory ´ 6.1 Uvod . . . . . . . . . . . . . . . . . 6.2 Proben1 . . . . . . . . . . . . . . . 6.3 UCI Machine Learning Repository . 6.4 Delve . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 Anal´ yza neuronov´ ych s´ıt´ı s pˇ rep´ınac´ımi jednotkami ´ 7.1 Uvod a motivace . . . . . . . . . . . . . . . . . . . . . . 7.2 Základn´ı myˇslenky . . . . . . . . . . . . . . . . . . . . . 7.3 Analýza s´ıtˇe s jedn´ım neuronem . . . . . . . . . . . . . . 7.4 Závˇery z analýzy neuronové s´ıtˇe obsahuj´ıc´ı jeden neuron 7.5 Analýza ˇretˇezce . . . . . . . . . . . . . . . . . . . . . . . 7.6 Srovnán´ı kritéri´ı kvality . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . .

50 50 50 52 52

. . . . . .

53 53 54 54 61 61 67

8 Z´ avˇ er

70

A Metody shlukov´ e anal´ yzy ´ A.1 Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Iteraˇcn´ı metody . . . . . . . . . . . . . . . . . . . . . . . . . . A.2.1 Forgyho metoda . . . . . . . . . . . . . . . . . . . . . . A.2.2 Nalezen´ı poˇcáteˇcn´ıho rozkladu . . . . . . . . . . . . . . A.2.3 Deterministické metody pro nalezen´ı poˇcáteˇcn´ıho rozkladu . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Hierarchické metody . . . . . . . . . . . . . . . . . . . . . . . A.3.1 Metoda nejbliˇzˇs´ıho souseda (single linkage) . . . . . . . A.3.2 Metoda nejvzdálenˇejˇs´ıho souseda (complete linkage) . . A.3.3 Metoda pr˚ umˇerné nepodobnosti vzor˚ u (average linkage) A.3.4 Poznámky k implementaci hierarchických metod . . . .

71 71 72 72 73

B Metoda hlavn´ıch komponent

80

C Pouˇ zit´ e n´ astroje

82

2

73 77 77 78 78 78

Pouˇ zit´ e znaˇ cen´ı def

⇔

ekvivalence ve smyslu definice

def

= R R+ 0 N

rovnost ve smyslu definice mnoˇzina reálných ˇc´ısel [0; +∞) mnoˇzina pˇrirozených ˇcisel

n ˆ Rn Rn,m diag(α1 , . . . , αn ) AT x(i)

n ˆ = {i ∈ N|i ≤ n} vektorový prostor nad tˇelesem reálných ˇc´ısel dimenze n vektorový prostor reálných matic o n ˇrádc´ıch a m sloupc´ıch diagonáln´ı matice, jej´ıˇz diagonála je tvoˇrena ˇc´ısly α1 , . . . , αn transpozice matice A i-tá sloˇzka vektoru x ∈ Rn

2X |X| Dom(f ) Ran(f )

def

def

mnoˇzina vˇsech podmnoˇzin mnoˇziny X, 2X = {x|x ⊆ X} poˇcet prvk˚ u mnoˇziny X definiˇcn´ı obor funkce f obor hodnot funkce f

3

Kapitola 1 ´ Uvod 1.1

Zamˇ eˇ ren´ı a c´ıle diplomov´ e pr´ ace

Jak naznaˇcuje název diplomové práce, jej´ım hlavn´ım tématem je jeden z typ˚ u neuronových s´ıt´ı - neuronové s´ıtˇe s pˇrep´ınac´ımi jednotkami. Dále v textu, pokud nebude ˇreˇceno jinak, se neuronovou s´ıt´ı, nebo jen s´ıt´ı bude rozumˇet právˇe neuronová s´ıt’ s pˇrep´ınac´ımi jednotkami. Tento typ neuronových s´ıt´ı p˚ uvodnˇe vznikl za u ´ˇcelem rozliˇsen´ı signálu od pozad´ı pˇri ˇreˇsen´ı fyzikáln´ıch problém˚ u. Jedná se ale o nástroj, který lze obecnˇe pouˇz´ıt pro klasifikaci do dvou tˇr´ıd ˇci aproximaci funkce. Neuronové s´ıtˇe tohoto typu jiˇz byly aplikovány na nˇekolik problém˚ u (viz. napˇr. [HLA02]), nicménˇe o vlastnostech tˇechto s´ıt´ı z praktického hlediska stále existuje mnoho otázek. Hlavn´ım u ´ˇcelem práce tedy bylo systematické zmapován´ı vlastnost´ı tˇechto s´ıt´ı a vypozorován´ı závˇer˚ u, které by pomohly pˇri jejich aplikaci na reálné problémy. Pˇri ˇreˇsen´ı tohoto problému se postupovalo takto: 1. Byl vybrán soubor problém˚ u, které se budou pouˇz´ıvat pˇri zjiˇst’ován´ı vlastnost´ı s´ıt´ı, viz. kapitola 6. 2. Bylo nutné ˇreˇsit problém urˇcován´ı kvality nauˇcených s´ıt´ı, viz. kapitola 5. 3. Pˇredchoz´ı bod vyˇzadoval zodpovˇezen´ı otázky, jak interpretovat výstup neuronové s´ıtˇe, tento problém je ˇreˇsen v kapitole 4. 4. Bylo nutné zajistit determinismus uˇcen´ı neuronových s´ıt´ı, viz. kapitola 3.

4

5. Vˇse bylo zavrˇseno proveden´ım analýzy tˇechto s´ıt´ı, popsané v kapitole 7. 6. Nav´ıc bylo tˇreba pˇreformulovat terminologii týkaj´ıc´ı se tˇechto s´ıt´ı, viz. kapitola 2.

5

Kapitola 2 Z´ akladn´ı definice 2.1

Formulace probl´ emu klasifikace do dvou mnoˇ zin

Problém oznaˇcovaný jako klasifikace do dvou mnoˇzin, v rámci nˇehoˇz prob´ıhala analýza neuronových s´ıt´ı, lze popsat následovnˇe: Necht’ je dána mnoˇzina S ∈ Rn , n ∈ N libovolné a necht’ existuj´ı mnoˇziny S1 , S2 ⊆ S splˇ nuj´ıc´ı 1. S1 ∩ S2 = ∅ 2. S1 ∪ S2 = S Necht’ zobrazen´ı χ : S 7→ {−1; 1} je definováno takto 1 pro x ∈ S1 def χ(x) = −1 pro x ∈ S2 def Dále se bude symbolem T znaˇcit tˇr´ıda funkc´ı T = {f |f : S 7→ R}. Necht’ ˇ sen´ım u je dána funkce L : T × T 7→ R+ ´ lohy klasifikace do dvou tˇr´ıd se 0 . Reˇ bude dále rozumˇet nalezen´ı funkce g minimalizuj´ıc´ı výraz

L(g, χ) ´ celem je naj´ıt funkci g, která o kaˇzdém prvku mnoˇziny Pozn´ amka 2.1 Uˇ S rozhoduje, zda mu pˇr´ısluˇs´ı hodnota −1 nebo 1, neboli do které ze dvou moˇzných tˇr´ıd patˇr´ı. Správné hodnoty jsou pˇredstavovány funkc´ı χ. Funkce L nazývaná bˇeˇznˇe jako ztrátová funkce urˇcuje pˇri daných poˇzadovaných hodnotách ztrátu, pˇri volbˇe urˇcité funkce g jako ˇreˇsen´ı. 6

Pozn´ amka 2.2 Funkce g bude dále právˇe funkce realizovaná neuronovou s´ıt´ı. Funkce L bude nˇejaké kritérium, které urˇcuje kvalitu neuronové s´ıtˇe na základˇe prvk˚ u z mnoˇziny S. Pozn´ amka 2.3 Pro vzory nebo celé mnoˇziny vzor˚ u, kterým pˇr´ısluˇs´ı hodnota +1, se bude pouˇz´ıvat výraz signál, pro vzory pˇr´ısluˇsné k hodnotˇe −1 se bude pouˇz´ıvat výraz pozad´ı.

2.2

Neuronov´ a s´ıt’

P˚ uvodn´ı motivace pro pouˇzit´ı a podobu umˇelých neuronových s´ıt´ı vycház´ı z nervových systém˚ u ˇzivých organism˚ u, základn´ı princip pˇr´ırodn´ıch a tedy i umˇelých neuronových s´ıt´ı spoˇc´ıvá v rozdˇelen´ı celku na jednoduˇsˇs´ı jednotky nazývané neurony. Neurony jsou vzájemnˇe propojeny a pˇredávaj´ı si mezi sebou informace, d´ıky této kooperaci jednoduˇsˇs´ıch jednotek lze z´ıskat sloˇzitˇejˇs´ı a mocnˇejˇs´ı nástroj pro ˇreˇsen´ı nejr˚ uznˇejˇs´ıch u ´loh. Jelikoˇz je tento nástroj sloˇzen z jednoduˇsˇs´ıch ˇcást´ı, je snadnˇejˇs´ı nastavit parametry takového nástroje (jinými slovy nauˇcit danou neuronovou s´ıt’), neˇz nastavovat parametry komplexn´ıho a daleko sloˇzitˇejˇs´ıho systému. Následuje zaveden´ı pojm˚ u jako je neuron, neuronová s´ıt’ a uˇcen´ı neuronové s´ıtˇe v kontextu neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami. Definice 2.1 Necht’ je dána funkce f : Rn ×P ar 7→ Rm , kde mnoˇzina P ar je libovolná mnoˇzina objekt˚ u pˇredstavuj´ıc´ı parametry funkce f . Mnoˇzina Mf = n m {g|(g : R 7→ R ) ∧(∃α ∈ P ar)(∀(x, α) ∈ Dom(f ))(g(x) = f (x, α))} se bude nazývat model neuronu s pˇ rechodovou funkc´ı f . Pozn´ amka 2.4 Pod modelem neuronu se rozum´ı tˇr´ıda funkc´ı stejného tvaru, které se liˇs´ı hodnotou jejich parametru. Prvky urˇcitého modelu neuronu jsou konkrétn´ı funkce zobrazuj´ıc´ı prostor Rn do Rm . Definice 2.2 Modelem neuronu se bude nazývat mnoˇzina [ MN = Mf Mf je model neuronu s pˇrechodovou funkc´ı f

Pozn´ amka 2.5 Mnoˇzina MN je sjednocen´ım vˇsech model˚ u neuron˚ u a obsahuje veˇskeré objekty, které lze oznaˇcit jako neuron.

7

Definice 2.3 Necht’ Mf je model neuronu s pˇrechodovou funkc´ı f : Rn × P ar 7→ Rm , funkce q ∈ Mf se bude nazývat neuron. Dalˇs´ı pojmy souvisej´ıc´ı s pojmem neuron jsou • Dom(q) vstupn´ı prostor neuronu q • n vstupn´ı dimenze neuronu q ozn. indim(q) • Ran(q) výstupn´ı prostor neuronu q • m výstupn´ı dimenze neuronu q, ozn. outdim(q) Pozn´ amka 2.6 Neuron je definován jako funkce, podoba neuronou s urˇcitou pˇrechodovou funkc´ı je dána pˇr´ısluˇsným modelem neuronu (tedy tˇr´ıdou funkc´ı urˇcitého tvaru). Hodnota parametru α, který urˇcuje neuron, m˚ uˇze být k-tice reálných ˇc´ısel, m˚ uˇze vˇsak m´ıt i sloˇzitˇejˇs´ı stukturu. Definice 2.4 Pod pojmem topologie se bude rozumˇet orientovaný acyklický graf T = (V, E), který nav´ıc splˇ nuje vlastnosti (ozn. V = {vin } ∪ VH ∪ {vout }, vin 6= vout , vout 6∈ VH , vin ∈ / VH ): 1. |V | < +∞ 2. (∀v ∈ V )((u, vin ) ∈ / E) 3. (∀v ∈ V )((vout , v) ∈ / E) 4. (∀v ∈ VH ∪ {vout })(∃u ∈ V )((u, v) ∈ E) 5. (∀v ∈ VH ∪ {vin })(∃u ∈ V )((v, u) ∈ E) Pozn´ amka 2.7 Topologie je tedy acyklický orientovaný graf, který obsahuje právˇe jeden vrchol, ze kterého jiˇz nevede ˇzádná hrana (výstup), právˇe jeden vrchol, do kterého nevede ˇzádná hrana (vstup) a nˇekolik “skrytých” vrchol˚ u, pˇres které jsou propojeny vstup a výstup. Pozn´ amka 2.8 Na obrázku 2.1 je ilustrován pˇr´ıklad topologie. Jednotlivá koleˇcka reprezentuj´ı vrcholy, ˇsipky reprezentuj´ı orientované hrany mezi vrcholy, orientace ˇsipek je od rodiˇc˚ u smˇerem k dˇetem. Vstup (vin ) se bude znaˇcit koleˇckem vybarveným ˇcernˇe, výstup bude vˇzdy nejn´ıˇze zobrazený vrchol, ze kterého jiˇz nevede ˇzádná hrana. Z praktických d˚ uvod˚ u je vstup zobrazen pouze jedn´ım koleˇckem a nen´ı pro kaˇzdou sloˇzku vstupu zobrazen zvláˇstn´ı vstupn´ı neuron, poˇcty vstupn´ıch neuron˚ u by pak vˇetˇsinou pˇrevýˇsily poˇcet ostatn´ıch neuron˚ u. 8

Obrázek 2.1: Pˇr´ıklad topologie Definice 2.5 Necht’ je dána topologie T , mnoˇzina def MTN N = {NN = (T, N , g, id)|ψ(NN)} se bude nazývat model neuronov´ e s´ıtˇ e se vstupn´ı dimenz´ı d nad topologi´ı T , ψ je relace nad uspoˇrádanými ˇctveˇricemi (T, N , g, id) definovaná následovnˇe 1) def 2) (T, N , g, id) ∈ ψ ⇔ 3) 4)

N ⊆ MN g : N 7→ V je bijekce id : N 7→ n ˆ je bijekce, n = |V | vstupn´ı dimenze neuronu q = g −1 (vin ) je rovna d

Pozn´ amka 2.9 V oznaˇcen´ı modelu neuronové s´ıtˇe se nevyskytuje vstupn´ı dimenze, ta bude vˇsak vˇzdy zˇrejmá z kontextu. Definice 2.6 Modelem neuronov´ e s´ıtˇ e se bude nazývat mnoˇzina [ M NN = MTN N T je topologie Definice 2.7 Prvek NN ∈ MTN N modelu neuronové s´ıtˇe se vstupn´ı dimenz´ı d nad topologi´ı T se bude nazývat Neuronov´ a s´ıt’ se vstupn´ı dimenz´ı d nad topologi´ı T . Necht’ NN = (T, N , g, id) ∈ MTN N , T = (V, E), následuje nˇekolik pojm˚ u týkaj´ıc´ıch se konkrétn´ı NN. Necht’ m = |N |, q ∈ N libovolný, def

• parents(q) = {q ′ ∈ N |(g(q ′), g(q)) ∈ E} def

• children(q) = {q ′ ∈ N |(g(q), g(q ′)) ∈ E} 9

def

• qin = g −1 (vin ) vstupn´ı neuron NN def

• qout = g −1(vout ) výstupn´ı neuron NN def

• indim(NN) = d vstupn´ı dimenze NN Pozn´ amka 2.10 Neuronová s´ıt’ NN = (T, N , g, id) je objekt, který se skládá z neuron˚ u a jehoˇz struktura je dána jeho topologi´ı. Jednotlivé neurony jsou oˇc´ıslovány funkc´ı id. Smysl tohoto oˇc´ıslován´ı spoˇc´ıvá hlavnˇe v uchopitelnosti jednotlivých neuron˚ u pˇri definován´ı pˇrechodové funkce realizované celou neuronovou s´ıt´ı a algoritmu uˇcen´ı neuronové s´ıtˇe. Pozn´ amka 2.11 Pokud na topologii nebo dimenzi neuronové s´ıtˇe nebude záleˇzet, bude se informace o topologii, ˇci vstupn´ı dimenzi vypouˇstˇet. Definice 2.8 Necht’ NN = (T, N , g, id) je neuronová s´ıt’ se vstupn´ı dimenz´ı d, q ∈ N , m = indim(q), o = outdim(q). Funkce q r : Rd 7→ Rm a q p : Rd 7→ Ro jsou definovány následovnˇe. Necht’ • n = |parents(q)| • (q1 , . . . , qn ) je uspoˇrádaná n-tice, pro niˇz plat´ı – (∀i ∈ n ˆ )(qi ∈ parents(q))

– (∀i, j ∈ n ˆ )(i < j ⇔ id(qi ) < id(qj )) a koneˇcnˇe

def

q p (x) = (q1r (x), . . . , qnr (x)) q(q p (x)) pro n>0 def r q (x) = q(x) jinak Pozn´ amka 2.12 Funkce q p vezme výstupy rodiˇc˚ u neuronu q a pˇrevede je na podobu jediného vektoru, který je teprve zpracován neuronem q. Funkce q p i q r jsou definovány rekurzivnˇe a slouˇz´ı k popsán´ı toku dat uvnitˇr neuronové s´ıtˇe, narozd´ıl od funkce q maj´ı vstupn´ı prostor totoˇzný se vstupn´ım prostorem celé neuronové s´ıtˇe a vracej´ı výstup z urˇcitého m´ısta v s´ıti. Definice 2.9 Neuronová s´ıt’ NN = (T, N , g, id) se bude nazývat korektn´ı, pokud plat´ı podm´ınka (∀q ∈ N )(dim(Ran(q p )) = indim(q)) 10

(2.1)

Pozn´ amka 2.13 Definice 2.9 zavád´ı pˇrirozenou podm´ınku pro tok dat uvnitˇr neuronové s´ıtˇe, nemˇelo by se stát, ˇze neuronu by ke zpracován´ı dostal vstup, který nepocház´ı ze vstupn´ıho prostoru daného neuronu. Jelikoˇz nemá smysl se zabývat neuronovými s´ıtˇemi, které nejsou korektn´ı, bude se vˇsude dále pod pojmem neuronová s´ıt’ uvaˇzovat neuronová s´ıt’, která je korektn´ı. r Definice 2.10 Necht’ NN = (T, N , g, id) ∈ M N N , funkce qout se bude nazývat funkce realizovaná neuronovou s´ıt´ı NN.

Pozn´ amka 2.14 Pomoc´ı neuronové s´ıtˇe je definována jistá funkce f : Rd 7→ Rn , dále se bude ˇcasto neuronová s´ıt’ ztotoˇzn ˇ ovat s funkc´ı kterou reprezentuje, tato funkce se bude znaˇcit NN, tedy NN(x) bude dále reprezentovat funkˇcn´ı hodnotu funkce realizované neuronovou s´ıt´ı NN. Jelikoˇz hodnota NN(x) je definována pomoc´ı hodnoty pˇrechodové funkce výstupn´ıho neuronu, je výstupn´ı dimenze celé neuronové s´ıtˇe totoˇzná s výstupn´ı dimenz´ı výstupn´ıho neuronu, vˇsude dále se budou uvaˇzovat pouze neuronové s´ıtˇe, jejich výstupn´ı dimenze je rovna jedné.

2.3

Uˇ cen´ı neuronov´ e s´ıtˇ e

Definice 2.11 Mnoˇzina X = {(x, t, i)|(x, t, i) ∈ Rm × {−1, +1} × N} s vlastnostmi • n = |X| < +∞ • m∈N • (∀(x, t, i) ∈ X)(i ∈ n ˆ) • (∀(x1 , t1 , i1 ), (x2 , t2 , i2 ) ∈ X)((x1 = x2 ∧ t1 = t2) ⇔ (i1 = i2 )) se bude nazývat mnoˇzina vzor˚ u dimenze m, nebo jen mnoˇzina vzor˚ u. Velikost´ı X se bude rozumˇet ˇc´ıslo n. Dále necht’ (x, t, i) ∈ X • x se bude nazývat vzor a znaˇcit xi • t se bude nazývat poˇzadovaná hodnota a znaˇcit ti • i se bude nazývat index vzoru • dvojice (x, t) se bude znaˇcit wi • mnoˇzina {x ∈ Rm |(∃(x′ , t′ , i′ ) ∈ X)(x = x′ )} se bude znaˇcit Xx 11

• mnoˇzina {t ∈ {−1; 1}|(∃(x′ , t′ , i′ ) ∈ X)(t = t′ )} se bude znaˇcit Xt Definice 2.12 Necht’ X je mnoˇzina vzor˚ u dimenze m a velikosti n, X se bude nazývat uˇ c´ıc´ı mnoˇ zina dimenze m s n vzory a znaˇcit DL (n, m). Pozn´ amka 2.15 Definice uˇc´ıc´ı mnoˇziny je pouze jiné pojmenován´ı pro mnoˇzinu vzor˚ u, jej´ı smysl je pouze ve zvýraznˇen´ı u ´ˇcelu, ke kterému je daná mnoˇzina vzor˚ u pouˇzita. Definice 2.13 Mnoˇzina def DL = {DL (n, m)|DL (n, m) je uˇc´ıc´ı mnoˇzina dimenze m s n vzory, kde n, m ∈ N} se bude nazývat mnoˇzina uˇc´ıc´ıch mnoˇzin. Pozn´ amka 2.16 Symbolem DL se nˇekdy bude oznaˇcovat bl´ıˇze nespecifikovaná uˇc´ıc´ı mnoˇzina, z kontextu vˇsak bude vˇzdy zˇrejmé, zda se jedná o jednu uˇc´ıc´ı mnoˇzinu, ˇci výˇse definovanou mnoˇzinu uˇc´ıc´ıch mnoˇzin. Definice 2.14 Necht’ Mf je model neuronu s pˇrechodovou funkc´ı f , funkce u : DL 7→ Mf se bude nazývat nenauˇ cen´ y neuron s pˇ rechodovou funkc´ı f. Definice 2.15 Necht’ NN U = (T, U, g u , idu ) je uspoˇrádaná ˇctveˇrice, kde • T = (V, E) je topologie • U je mnoˇzina nenauˇcených neuron˚ u • g u : U 7→ V je bijekce • idu : U 7→ vˆ je bijekce, v = |V | NN U se bude nazývat nenauˇcená neuronová s´ıt’ nad topologi´ı T . Definice 2.16 Mnoˇzina def

NNT,U = {NNU | NNU je nenauˇcená neuronová s´ıt’ nad topologi´ı T } se bude nazývat mnoˇzina nenauˇcených neuronových s´ıt´ı nad topologi´ı T . Definice 2.17 Mnoˇzina def

MUN N =

[

NNT,U

T je topologie se bude nazývat mnoˇzina nenauˇcených neuronových s´ıt´ı. 12

Definice 2.18 Uˇc´ıc´ı metodou neuronové s´ıtˇe se bude nazývat funkce LM : LD × MUN N 7→ M N N , která je definována následovnˇe. Necht’ l ∈ LD , NNU ∈ MUN N , NNU = (T ′ , U, Gu , idu ), T ′ = (V ′ , E ′ ). def

LM (l, NNU ) = NN = (T, N , g, id) kde pro NN plat´ı • T = T′ • (∀q ∈ N )(∀u ∈ U)(id(q) = id(u) ⇒ ((q = u(lq )) ∧ (g(q) = g u (u)))) def

kde lq = {(x′ , t′ , i′ )|(∃(x, t, i) ∈ l)((x′ , t′ , i′ ) = (q p (x), t, i))}

Pozn´ amka 2.17 Uˇc´ıc´ı metoda byla definována za pouˇzit´ı sady podm´ınek, které plat´ı pro funkˇcn´ı hodnotu za daných vstupn´ıch hodnot. Je samozˇrejmˇe moˇzná i konstruktivn´ı definice této funkce, taková definice by vˇsak byla velice nepˇrehledná, proto byl preferován pouˇzitý pˇr´ıstup. Pozn´ amka 2.18 Uˇc´ıc´ı metoda pˇriˇrazuje uˇc´ıc´ı mnoˇzinˇe a nenauˇcené neuronové s´ıti konkrétn´ı neuronovou s´ıt’. Z toho, jak byla uˇc´ıc´ı metoda definovaná je vidˇet, ˇze jiˇz pˇredem je nutné zadat topologii neuronové s´ıtˇe a definovat funkce, pomoc´ı kterých se uˇc´ı jednotlivé neurony. Proces uˇcen´ı tedy optimalizuje pouze parametry jednotlivých neuron˚ u. Propojen´ı mezi neurony, pˇrechodové funkce neuron˚ u a zp˚ usoby uˇcen´ı jednotlivých neuron˚ u jsou jiˇz ’ pˇredem dány a zakódovány v nenauˇcené neuronové s´ıt i. Nenauˇcená neuronová s´ıt’ je vlastnˇe pˇredpis, jak za vyuˇzit´ı uˇc´ıc´ı mnoˇziny zkonstuovat neuronovou s´ıt’. Z definice mnoˇzin lq je zˇrejmé, ˇze se jedná o mnoˇzinu vzor˚ u, nav´ıc je tato p mnoˇzina definována pomoc´ı rekurzivnˇe definované funkce q z ˇcehoˇz plyne, ˇze neurony mus´ı být pˇri uˇcen´ı brány v urˇcitém poˇrad´ı. Nauˇcen´ı neuronu mus´ı pˇredcházet nauˇcen´ı jeho rodiˇc˚ u. Z definice lq je také vidˇet, ˇze pro uˇcen´ı kaˇzdého neuronu jsou pouˇzity stejné poˇzadované hodnoty. Definice 2.18 zavád´ı zp˚ usob nauˇcen´ı libovolné neuronové s´ıtˇe s pˇrep´ınac´ımi jednotkami. Pozn´ amka 2.19 Dalˇs´ı vlastnosti uˇc´ıc´ı metody plynouc´ı z definice 2.18 jsou: • Uˇc´ıc´ı proces neuronové s´ıtˇe nen´ı iteraˇcn´ı (pˇri uˇcen´ı jednotlivých neuron˚ u se vˇsak iteraˇcn´ı metody pouˇz´ıvaj´ı, viz. následuj´ıc´ı kapitola). • Pˇri uˇcen´ı kaˇzdého neuronu je pouˇzitá celá uˇc´ıc´ı mnoˇzina naráz. • Pro nauˇcen´ı neuronu q je tˇreba m´ıt k dispozici uˇc´ıc´ı mnoˇzinu sloˇzenou z výstup˚ u rodiˇc˚ u q. 13

Kapitola 3 Neuron s pˇ rep´ınac´ı jednotkou Neuronové s´ıtˇe s pˇrep´ınac´ımi jednotkami, jak název napov´ıdá, obsahuj´ı pˇrep´ınac´ı jednotky. Tyto jednotky se v neuronové s´ıti neobjevuj´ı samostatnˇe, ale vˇzdy jako souˇcást neuronu s pˇrep´ınac´ı jednotkou (d˚ uvody lze naj´ıt v [HLA01, HLA02]). Nejprve je uveden popis neuronu s pˇrep´ınac´ı jednotkou a jeho funkcionality, následuj´ı detailnˇejˇs´ı popisy jeho jednotlivých ˇcást´ı.

3.1

Neuron s pˇ rep´ınac´ı jednotkou

Na neuron s pˇrep´ınac´ı jednotkou (NSU) se lze d´ıvat jako na strukturu, která se skládá z právˇe jedné pˇrep´ınac´ı jednotky a nˇekolika výpoˇcetn´ıch jednotek (neuron˚ u), schéma neuronu s pˇrep´ınac´ı jednotkou je na obrázku 3.1. Zpracován´ı vstupu neuronem s pˇrep´ınac´ı jednotkou lze popsat slovy následovnˇe:

Obrázek 3.1: Schéma neuronu s pˇrep´ınac´ı jednotkou

14

1. pˇrep´ınac´ı jednotka pˇri zpracován´ı vstupu x rozhodne, který výpoˇcetn´ı neuron vstup x zpracuje 2. výpoˇcetn´ı neuron, který dostane pˇridˇelen vstup x ke zpracován´ı, na x aplikuje svoji pˇrechodovou funkci, t´ım se z´ıská výstup y 3. výstup y výpoˇcetn´ıho neuronu se vezme jako výstup neuronu s pˇrep´ınac´ı jednotkou Formálnˇe lze funkci realizovanou neuronem s pˇrep´ınac´ı jednotkou popsat následovnˇe: Definice 3.1 Necht’ • k∈N • Mf je model neuronu s pˇrechodovou funkc´ı f ˆ • q1 , . . . , qk jsou neurony, qi ∈ Mf , qi : Rn 7→ Rm pro ∀i ∈ k, • h : Rn 7→ kˆ • x ∈ Rn • j = h(x) def

NSU(x) = fj (x)

(3.1)

• funkce NSU : Rn 7→ Rm se bude nazývat neuron s pˇrep´ınac´ı jednotkou • k se bude nazývat poˇcet výpoˇcetn´ıch neuron˚ u • h se bude nazývat pˇrep´ınac´ı jednotka Pozn´ amka 3.1 V pˇredchoz´ı definici tedy funkce h pˇredstavuje pˇrep´ınac´ı jednotku a funkce q1 , . . . , qk jsou výpoˇcetn´ı neurony. Je ponˇekud problematické, jak odliˇsit výpoˇcetn´ı neurony a neurony s výpoˇcetn´ı jednotkou pouze pomoc´ı pˇrechodové funkce, nebo jej´ım tvarem. To, ˇze NSU má po ˇcástech definovanou pˇrechodovou funkci, jistˇe nen´ı dostateˇcné kritérium. Dále se vˇsude bude intuitivnˇe pˇredpokládat, ˇze neuron s pˇrep´ınac´ı jednotkou se skládá z pˇrep´ınac´ı jednotky a výpoˇcetn´ıch neuron˚ u, které maj´ı jiˇz lineárn´ı pˇrechodovou funkci a nemaj´ı ˇzádnou vnitˇrn´ı strukturu. Dále budou popsány konkrétn´ı NSU a bude vidˇet, ˇze v´ıceménˇe pˇredstavuj´ı po ˇcástech lineárn´ı funkce. 15

Uˇcen´ı NSU s k výpoˇcetn´ımi neurony lze popsat následovnˇe: 1. pomoc´ı uˇc´ıc´ı mnoˇziny je nauˇcena pˇrep´ınac´ı jednotka 2. uˇc´ıc´ı mnoˇzina je rozdˇelena na k podmnoˇzin pomoc´ı jiˇz nauˇcené pˇrep´ınac´ı jednotky 3. i-tá podmnoˇzina uˇc´ıc´ı mnoˇziny je pouˇzita k nauˇcen´ı i-tého výpoˇcetn´ıho neuronu

3.2

Pˇ rep´ınac´ı jednotka

Pˇrep´ınac´ı jednotka, jak je zˇrejmé z popisu neuronu s pˇrep´ınac´ı jednotkou, ˆ kde n je vstupn´ı dimenze neuronu a k je poˇcet realizuje funkci h : Rn 7→ k, výpoˇcetn´ıch neuron˚ u. Pro libovolný vstup x tedy rozhodne, který výpoˇcetn´ı neuron by mˇel daný vstup zpracovat. Pro takové rozhodnut´ı mus´ı být vstupn´ı prostor nˇejak popsán. K popisu vstupn´ıho prostoru se pouˇz´ıvá následuj´ıc´ı postup. Ve vstupn´ım prostoru je um´ıstˇeno k bod˚ u, kaˇzdý z tˇechto bod˚ u je asociován s jedn´ım výpoˇcetn´ım neuronem. Pˇri rozhodován´ı, který výpoˇcetn´ı neuron by mˇel zpracovat vstup x se zvol´ı ten, jemuˇz pˇr´ısluˇsej´ıc´ı bod je nejbl´ıˇze danému vstupu. Pokud by byla tato vzdálenost stejná pro v´ıce bod˚ u, vybere se výpoˇcetn´ı neuron s nejniˇzˇs´ım indexem. Detailnˇeji lze pˇrep´ınac´ı jednotku definovat následovnˇe: Definice 3.2 Necht’ • NSU je neuron s pˇrep´ınac´ı jednotkou • k je poˇcet výpoˇcetn´ıch neuron˚ u NSU • n = indim(NSU) • h : Rn 7→ kˆ • x ∈ Rn • µ 1 , . . . , µ k ∈ Rn • d : Rn × Rn 7→ R0+ ˆ • dmin = min{d(x, µi )|i ∈ k}

16

def

ˆ min = d(x, µi )} h(x) = min{i ∈ k|d

(3.2)

Funkce h se bude nazývat pˇrep´ınac´ı jednotkou neuronu NSU Pozn´ amka 3.2 Funkce d v definici pˇrep´ınac´ı jednotky slouˇz´ı k urˇcován´ı vzdálenost´ı mezi body ze vstupn´ıho prostoru. Definice 3.3 Necht’ x, y ∈ Rn v u n X def u de = t (x(i) − y (i) )2

(3.3)

dabs

(3.4)

i=1

v u n X def u = t |x(i) − y (i) | i=1

def

dsum = |

n X i=1

x(i) −

n X i=1

y (i) |

(3.5)

K uˇcen´ı pˇrep´ınac´ı jednotky se pouˇz´ıvaj´ı metody shlukové analýzy, viz. dodatek A. Jako vstup pro shlukován´ı se pouˇz´ıvá mnoˇzina vzor˚ u z uˇc´ıc´ı mnoˇziny, která neobsahuje poˇzadované hodnoty. V principu se pak dˇeje toto: 1. shlukovac´ı metoda rozdˇel´ı uˇc´ıc´ı vzory z uˇc´ıc´ı mnoˇziny na disjunktn´ı podmnoˇziny 2. u kaˇzdé podmnoˇziny se urˇc´ı tˇeˇziˇstˇe 3. ke kaˇzdému (zat´ım nenauˇcenému) výpoˇcetn´ımu neuronu se pˇriˇrad´ı jedno tˇeˇziˇstˇe jako bod µ Na obrázku 3.2 je pˇr´ıklad rozdˇelen´ı dvojrozmˇerného vstupn´ıho prostoru neuronu pˇri daných uˇc´ıc´ıch vzorech.

3.3

V´ ypoˇ cetn´ı neurony

Jako výpoˇcetn´ıch neuron˚ u uvnitˇr neuron˚ u s pˇrep´ınac´ı jednotkou se pouˇz´ıvaj´ı dva typy neuron˚ u, tyto neurony se uˇc´ı stejným zp˚ usobem, liˇs´ı se vˇsak jejich pˇrechodová funkce.

17

Obrázek 3.2: Pˇr´ıklad rozdˇelen´ı dvourozmˇerného vstupn´ıho prostoru do tˇr´ı ˇcást´ı, ˇcerné body reprezentuj´ı vzory z uˇc´ıc´ı mnoˇziny Definice 3.4 Neuronem typu I se bude nazývat neuron s pˇrechodovou funkc´ı f : Rn 7→ Rn+1 , n ∈ N x f (x) = diag(α1 , . . . , αn , αn+1 ) 1 Definice 3.5 Neuronem typu II se bude nazývat neuron s pˇrechodovou funkc´ı f : Rn 7→ R, n ∈ N x f (x) = (α1 , . . . , αn+1 ) 1 Parametry neuron˚ u typu I i II jsou nastavovány pomoc´ı metody nejmenˇs´ıch ˇctverc˚ u, jej´ıˇz popis lze naj´ıt napˇr. v [VIS98, AND85].

3.4

Determinismus uˇ cen´ı

Pro srovnán´ı uˇcen´ı neuronových s´ıt´ı s r˚ uznými parametry je tˇreba, aby uˇcen´ı bylo deterministické a to hlavnˇe z následuj´ıc´ıch d˚ uvod˚ u: • Pokud by uˇcen´ı nebylo deterministické a pˇri uˇcen´ı neuronové s´ıtˇe by se sledovala napˇr. veliˇcina X. Pozdˇeji by se mohlo zjistit, ˇze je tˇreba sledovat i veliˇcinu Y , t´ım by se staly veˇskeré jiˇz napoˇctené výsledky nepouˇzitelné, protoˇze pro z´ıskán´ı hodnot veliˇciny Y by bylo tˇreba znovu z´ıskat hodnoty jiˇz dˇr´ıve namˇeˇrené, které by odpov´ıdaly pr˚ ubˇehu uˇcen´ı, pˇri kterém bylo provedeno nové mˇeˇren´ı. • Pˇri drobné zmˇenˇe uˇc´ıc´ıch dat by uˇcen´ı mˇelo prob´ıhat podobnˇe, jako pˇri uˇcen´ı p˚ uvodn´ıch dat. Pokud se neuronová s´ıt’ nauˇc´ı za pouˇzit´ı uˇc´ıc´ı 18

mnoˇziny X, která se pozdˇeji napˇr´ıklad rozˇs´ıˇr´ı, mˇelo by uˇcen´ı prob´ıhat alespoˇ n podobnˇe, jako s p˚ uvodn´ı uˇc´ıc´ı mnoˇzinou, oˇcekávalo by se také, ˇze výsledná s´ıt’ bude kvalitn´ı. Tento poˇzadavek je trochu naivn´ı, ale rozhodnˇe ho lze lépe splnit v pˇr´ıpadˇe deterministického uˇcen´ı. K uˇcen´ı výpoˇcetn´ıch neuron˚ u se pouˇz´ıvá metoda nejmenˇs´ıch ˇctverc˚ u, která je deterministická, procházen´ı celé neuronové s´ıtˇe pˇri uˇcen´ı je také deterministické. Jediný prvek, kde se vyuˇz´ıvala náhoda, je uˇcen´ı pˇrep´ınac´ı jednotky. Nˇekteré metody pro uˇcen´ı pˇrep´ınac´ı jednotky jsou iteraˇcn´ı a na poˇcátku jiˇz vyˇzaduj´ı odhad ˇreˇsen´ı, tento odhad se z´ıskával náhodným generován´ım. V kapitole o pouˇzitých metodách shlukové analýzy jsou uvedeny výsledky nˇekterých experiment˚ u, které ilustruj´ı cilivost iteraˇcn´ıch metod na koneˇcném výsledku. Daly by se pouˇz´ıt i neiteraˇcn´ı metody, ze srovnán´ı výpoˇcetn´ı nároˇcnosti metod shlukové analýzy vˇsak vyplývá, ˇze tyto metody jsou od jisté velikosti uˇc´ıc´ı mnoˇziny velice nároˇcné pro pouˇzit´ı. Je nutné si uvˇedomit, ˇze pro nauˇcen´ı neuronové s´ıtˇe m˚ uˇze být nutné nauˇcit mnoho pˇrep´ınac´ıch jednotek a to by mohlo trvat delˇs´ı ˇcas. Citlivost iteraˇcn´ıch metod na poˇcáteˇcn´ı ˇreˇsen´ı by nemusela být aˇz tak tragická, kdyby se ukázalo, ˇze na celkové uˇcen´ı neuronové s´ıtˇe to nemá pˇr´ıliˇs významný dopad. Bohuˇzel z praktických výsledk˚ u se ukázalo, ˇze opak je pravdou. Pro ilustraci tohoto jevu jsou uvedeny výsledky, na nichˇz je ukázáno, jak se liˇs´ı výsledky tˇechto s´ıt´ı pˇri opakovaném uˇcen´ı. Tento experiment vycház´ı z jednoduché pˇredstavy, ˇze pokud maj´ı dvˇe s´ıté r˚ uznou kvalitu, mus´ı se liˇsit i jejich parametry. Pro nˇekolik r˚ uzných s´ıt´ı byl proveden tis´ıckrát následuj´ıc´ı experiment: 1. neuronová s´ıt’ byla nauˇcena (jako uˇc´ıc´ı mnoˇzina byla pouˇzita mnoˇzina vzor˚ u, která je oznaˇcena v kapitole 6 jako heart 2. byly spoˇcteny výstupy neuronové s´ıtˇe, kde jako vstupy byly pouˇzity vzory z uˇc´ıc´ı mnoˇziny 3. byla spoˇctena chyba klasifikace danou s´ıt´ı (pomˇer ˇspatnˇe klasifikovaných vzor˚ u ku poˇctu vˇsech vzor˚ u, kde za ˇspatnˇe ohodnocený vzor byl povaˇzovaný vzor, u nˇehoˇz byla s´ıt’ uˇcena na hodnotu +1 resp. -1, ale s´ıt’ ho pozdˇeji zaˇradila bl´ıˇze -1 resp. +1) 4. uloˇzen´ı kvality Na obrázc´ıch 3.3, 3.4 a 3.5 je vˇzdy vlevo uveden historgram chyb neuronové s´ıtˇe, vpravo je uvedena topologie neuronové s´ıtˇe, které odpov´ıdá 19

daný histogram. Z uvedených histogram˚ u lze usoudit, ˇze kvality neuronových s´ıt´ı, které byly uˇceny pomoc´ı stejné nenauˇcené neuronové s´ıtˇe a stejné uˇc´ıc´ı mnoˇziny, se liˇs´ı, z toho plyne, ˇze i odpov´ıdaj´ıc´ı neuronové s´ıtˇe se liˇs´ı. Náhodný poˇcáteˇcn´ı rozklad tedy ovlivˇ nuje uˇcen´ı s´ıt´ı.

150 100 50 0

Frekvence

200

250

Histogram chyby naučené neuronové sítě

0.06

0.08

0.10

0.12

0.14

Chyba

Obrázek 3.3: Histogram chyby klasifikace a topologie odpov´ıdaj´ıc´ı neuronové s´ıtˇe

3.5

Srovn´ an´ı metod pouˇ zit´ ych pro uˇ cen´ı pˇ rep´ınac´ı jednotky

Pro uˇcen´ı pˇrep´ınac´ı jednotky byly pouˇz´ıvány následuj´ıc´ı metody shlukové analýzy. • Iteraˇcn´ı metody – Forgy rand – Forgy PCA – Forgy LA • Hierarchické metody – Nejbliˇzˇs´ı soused – Nejvzálenˇejˇs´ı soused 20

0

50

100

Frekvence

150

200

250

300


0.00

0.05

0.10

0.15

0.20

Chyba

Obrázek 3.4: Histogram chyby klasifikace a topologie odpov´ıdaj´ıc´ı neuronové s´ıtˇe – Pr˚ umˇerná nepodobnost Z iteraˇcn´ıch metod jsou pouˇzity r˚ uzné varianty Forgyho metody, tyto varianty se liˇs´ı ve zp˚ usobu urˇcen´ı poˇcáteˇcn´ıho ˇreˇsen´ı, které se dále iteraˇcnˇe zlepˇsuje. Varianta Forgy rand vybere náhodnˇe k bod˚ u a ostatn´ı body jsou zaˇrazeny do shluku k nejbliˇzˇs´ımu bodu, varianty Forgy PCA a Forgy LA pouˇz´ıvaj´ı metodu PCA Part a jej´ı variantu LA ( viz. odstavec A.2.3) k nalezen´ı poˇcáteˇcn´ıho rozkladu. Tyto jednotlivé metody pracuj´ı na r˚ uzných principech a minimalizuj´ı i r˚ uzná kritéria pro rozdˇelen´ı vzor˚ u do shluk˚ u. To je d˚ uvod, proˇc tyto metody nebyly srovnávány pˇr´ımo v rámci shlukové analýzy. Srovnána byla výpoˇcetn´ı nároˇcnost tˇechto algoritm˚ u, v kapitole 7 jsou uvedeny výsledky, které byly z´ıskány pˇri zjiˇst’ován´ı vlivu jednotlivých metod na celkové uˇcen´ı neuronových s´ıt´ı. Hlavn´ı parametry ovlivˇ nuj´ıc´ı metody shlukové analýzy jsou poˇcet vzor˚ u urˇcených ke shlukován´ı, jejich dimenze a zp˚ usob urˇcován´ı vzdálenosti mezi vzory. Uvedené výsledky byly z´ıskány pˇri pouˇzit´ı euklidovské vzdálenosti.

3.6

Srovn´ an´ı v z´ avislosti na poˇ ctu vzor˚ u

Na obrázku 3.6 je vidˇet závislost doby výpoˇctu na velikosti uˇc´ıc´ı mnoˇziny (pro výpoˇcet bylo vˇzdy vzato prvn´ıch n vzor˚ u) pro veˇskeré uvedené metody 21

60 40 20 0

Frekvence

80

100


0.08

0.09

0.10

0.11

0.12

0.13

Chyba

Obrázek 3.5: Histogram chyby klasifikace a topologie odpov´ıdaj´ıc´ı neuronové s´ıtˇe najednou. Z tohoto obrázku je zˇrejmé, ˇze výpoˇcetn´ı nároˇcnost hierarchických metod je znaˇcnˇe vyˇsˇs´ı neˇz nároˇcnost Forgyho metody. To vyplývá ze sloˇzitosti uvedených metod (viz dodatek A). Veˇskeré shlukován´ı bylo provedeno pro deset shluk˚ u. Na obrázc´ıch 3.7 aˇz 3.12 jsou uvedeny zvláˇst’ hierarchické metody a varianty Forgyho metody pro r˚ uzné dimenze vstupn´ıch dat (pro vzory bylo pouˇzito vˇzdy prvn´ıch k hodnot z uˇc´ıc´ı mnoˇziny mushroom1-lrn) Na obrázku je uvedeno srovnán´ı pro uˇc´ıc´ı mnoˇzinu heart1-lrn. Tato mnoˇzina dat obsahuje ménˇe vzor˚ u, neˇz mushroom1-lrn. Je vidˇet, ˇze pˇri niˇzˇs´ı velikosti uˇc´ıc´ı mnoˇziny (≤ 500) je rozd´ıl v ˇcásové nároˇcnosti malý, hierarchické metody jsou v tomto pˇr´ıpadˇe dokonce rychlejˇs´ı neˇz Forgy PCA.

3.7

Srovn´ an´ı v z´ avislosti na poˇ ctu shluk˚ u

Kromˇe poˇctu vzor˚ u v uˇc´ıc´ı mnoˇzinˇe, je dalˇs´ım parametrem poˇcet hledaných shluk˚ u. Na obrázc´ıch 3.15 a 3.15 jsou zobrazeny závislosti doby potˇrebné pro shlukován´ı v závislosti na poˇctu shluk˚ u pˇri konstantn´ı velikosti uˇc´ıc´ı mnoˇziny.

3.8

Z´ avˇ ery

Ze srovnán´ı vedených metod lze doj´ıt k následuj´ıc´ım závˇer˚ um: 22

Používané metody

10 0

5

Čas výpočtu[s]

15

Forgy LA Forgy PCA Forgy rand Nejbližší soused Průměrná nepodobnost nejvzdálenější soused

0

1000

2000

3000

4000

Počet prvků v datové množině

Obrázek 3.6: Závislost doby výpoˇctu pouˇzitých metod na poˇctu prvk˚ u ve vstupn´ı mnoˇzinˇe, data mushroom1-lrn (dim=125) • hierarchické metody jsou od urˇcité hranice daleko nároˇcnˇejˇs´ı na výpoˇcetn´ı ˇcas neˇz iteraˇcn´ı metody • pro uˇc´ıc´ı mnoˇziny s menˇs´ım poˇctem vzor˚ u (≤ 700) je výpoˇcetn´ı nároˇcnost hierarchických a iteraˇcn´ıch metod podobná, dokonce jsou hierarchické metody ménˇe nároˇcné neˇz iteraˇcn´ı metoda Forgy PCA • uvedené hierarchické metody maj´ı pˇribliˇznˇe stejné nároky na výpoˇcetn´ı ˇcas, nejsou citlivé na poˇcet shluk˚ u • Forgy PCA je významnˇe nároˇcnˇejˇs´ı, neˇz dalˇs´ı varianty Forgyho metody, pˇriˇcemˇz nároˇcnost tˇechto metod je ovlivnˇena poˇctem shluk˚ u Pozn´ amka 3.3 Z deterministických variant Forgyho metody je varianta Forgy LA výraznˇe ménˇe nároˇcná na výpoˇcetn´ı ˇcas, bylo by pozitivn´ı zjiˇstˇen´ı, ˇze výsledky celých neuronových s´ıt´ı jsou pˇri pouˇzit´ı jednotlivých variant srovnatelné.

23

Hierarchické metody

10 0

5

Čas výpočtu[s]

15

Nejbližší soused Průměrná nepodobnost nejvzdálenější soused

0

1000

2000

3000

4000


Obrázek 3.7: Závislost doby výpoˇctu hierarchických metod na poˇctu prvk˚ u ve vstupn´ı mnoˇzinˇe (dim=125)

Iterační metody

2.0 1.5 0.0

0.5

1.0

Čas výpočtu[s]

2.5

3.0

3.5

Forgy LA Forgy PCA Forgy rand

0

1000

2000

3000

4000


Obrázek 3.8: Závislost doby výpoˇctu iteraˇcn´ıch metod na poˇctu prvk˚ u ve vstupn´ı mnoˇzinˇe (dim=125) 24


4 3 0

1

2

Čas výpočtu[s]

5

6

7


0

1000

2000

3000

4000



Iterační metody

0.4 0.3 0.0

0.1

0.2

Čas výpočtu[s]

0.5

0.6

0.7


0

1000

2000

3000

4000




1.5 1.0 0.0

0.5

Čas výpočtu[s]

2.0

2.5


0

1000

2000

3000

4000



Iterační metody

0.04 0.00

0.02

Čas výpočtu[s]

0.06

0.08


0

1000

2000

3000

4000



Používané metody

0.010 0.000

0.005

Čas výpočtu[s]

0.015

0.020


100

200

300

400


Obrázek 3.13: Závislost doby výpoˇctu na poˇctu prvk˚ u ve vstupn´ı mnoˇzinˇe, data heart1-lrn (dim=35)

Používané metody

10 0

5

Čas výpočtu[s]

15


0

20

40

60

80

100

Počet shluků

Obrázek 3.14: Výsledky pro data muhroom1-lrn (dimenze 125, poˇcet vzor˚ u 4062) 27

0.20

Používané metody

0.10 0.00

0.05

Čas výpočtu[s]

0.15


0

20

40

60

80

100

Počet shluků

Obrázek 3.15: Výsledky pro data heart1-lrn (dimenze 35, poˇcet vzor˚ u 460

28

Kapitola 4 Interpretace v´ ystup˚ u neuronov´ e s´ıtˇ e Jedna z otázek ohlednˇe výstup˚ u neuronových s´ıt´ı se týkala rozhodnut´ı, kam vlastnˇe zaˇradit vstup x, pˇri urˇcité hodnotˇe výstupu y = NN(x). Neuronové s´ıtˇe jsou uˇceny na poˇzadované hodnoty −1 a +1, pˇriˇcemˇz výstup y neuronové s´ıtˇe m˚ uˇze být libovolné reálné ˇc´ıslo. Intuitivnˇe lze prohlásit, ˇze pokud y je dostateˇcnˇe bl´ızko +1, lze vstup x oznaˇcit jako signál a v opaˇcném pˇr´ıpadˇe oznaˇcit x jako pozad´ı. Toto ˇreˇsen´ı jistˇe nen´ı pˇr´ıliˇs uspokojivé, a proto je tˇreba ho trochu formalizovat. Mˇejme tedy neuronovou s´ıt’ NN, nauˇcenou pomoc´ı uˇc´ıc´ı mnoˇziny DL , je tˇreba naj´ıt vhodnou funkci c : R 7→ DS , která o výstupu neuronové s´ıtˇe rozhodne, zda se jedná o signál ˇci pozad´ı. Symbolem DS byla oznaˇcena mnoˇzina DS = {s, b}, kde s oznaˇcuje signál, b pozad´ı.

4.1

Pouˇ zit´ı prahu

Nejjednoduˇsˇs´ı zp˚ usob, jak ˇreˇsit tento problém je zavést funkci c takto s pro y ≥ 0 c(y) = (4.1) b pro y < 0 Nicménˇe problém s takto definovanou funkc´ı c je, ˇze c(10−10 ) = c(1) a je na prvn´ı pohled vidˇet, ˇze pro hodnotu x = 10−10 nen´ı zrovna moc jisté, zda y oznaˇcit jako signál ˇci pozad´ı. Dalˇs´ı problém spoˇc´ıvá v tom, ˇze c(1010 ) = c(1) a pˇrestoˇze neuronová s´ıt’ byla uˇcena na výstupn´ı hodnoty −1 a +1, zaˇrad´ı se bez nejmenˇs´ıch problém˚ u i hodnoty, které jsou velice vzdálené poˇzadovaným výstup˚ um s´ıtˇe, do nˇekteré ze tˇr´ıd. 29

Pˇrirozenˇe se tedy nab´ız´ı zavést kromˇe moˇzných rozhodnut´ı signál/pozad´ı jeˇstˇe hodnotu nev´ım. Tyto hodnoty se budou znaˇcit následovnˇe: signál s pozad´ı b nev´ım u a zobecnˇen´ı funkce c je nyn´ı funkce c : R 7→ D, kde D = {s, b, u}. Definice 4.1 Rozhodovac´ım pravidlem se bude nazývat libovolná funkce c : R 7→ D Definice 4.2 Necht’ c je rozhodovac´ı pravidlo, • mnoˇzina As = {y ∈ Real|c(y) = s} se bude nazývat oblast pˇrijet´ı signálu • mnoˇzina Ab = {y ∈ Real|c(y) = b} se bude nazývat oblast pˇrijet´ı pozad´ı • mnoˇzina Au = R \ (As ∪ Ab ) se bude nazývat oblast nepˇrijet´ı Definice 4.3 Rozhodovac´ı pravidlo tvaru 4.1 se bude nazývat prahové pravidlo a znaˇcit R0 . Nyn´ı zbývá naj´ıt obecnˇejˇs´ı postup, jak rozdˇelit R na oblasti pˇr´ısluˇsej´ıc´ı jednotlivým hodnotám s, b nebo u.

4.2

Zobecnˇ en´ı pouˇ zit´ı prahu

Jednou z moˇznost´ı, jak volit funkci c   s b c(y) =  u

je následuj´ıc´ı: pro y ∈ [a, b) pro y ∈ [c, d) jinak

(4.2)

Kde interval HS = [a, b) (resp. HB = [c, d)) je vhodné okol´ı bodu +1 (resp. −1). Nicménˇe je stále problematické, jak volit optimálnˇe tyto intervaly (jednou z moˇznost´ı by bylo volit tyto intervaly tak, aby chyba klasifikace pro vzory z uˇc´ıc´ı mnoˇziny byla v tˇechto intervalech menˇs´ı nebo rovna poˇzadované hodnotˇe, pro ˇreˇsen´ı problému vˇsak byla nakonec zvolena jiná cesta). Necht’ C je náhodná veliˇcina, která m˚ uˇze nabývat hodnot s a b, Y je náhodná veliˇcina nabývaj´ıc´ı hodnoty z R, která nabývá hodnoty výstup˚ u 30

neuronové s´ıtˇe NN. Pro vzory y ∈ HS (resp. y ∈ HB ) by jistˇe mˇelo platit p(C = s|Y = y) > p(C = b|Y = y)(resp. (p(C = b|Y = y) > p(C = s|Y = y)). Coˇz vede na myˇslenku, ˇze optimáln´ı by bylo z´ıskat pravdˇepodobnosti p(C = s|Y = y) a p(C = b|Y = y) pro ∀y ∈ R a pˇri rozhodován´ı o pˇr´ısluˇsnosti vstupu neuronové s´ıtˇe pouˇz´ıt tˇechto funkc´ı. V takovém pˇr´ıpadˇe by tedy funkce c vypadala takto:   s pro p(C = s|Y = y) > t b pro p(C = b|Y = y) > t (4.3) c(y) =  u jinak kde t ∈ (0, 5; 1) je poˇzadovaná u ´ roveˇ n pro urˇcen´ı pˇr´ısluˇsnosti vzoru.

4.3

Pˇ revod v´ ystup˚ u na pravdˇ epodobnosti

Pˇredchoz´ı text obsahoval motivaci, proˇc má smysl se pokusit pˇrevést výstupy neuronové s´ıtˇe na pravdˇepodobnosti. Jsou tedy dány uˇc´ıc´ı mnoˇzina a nenauˇcená neuronová s´ıt’. K z´ıskán´ı nauˇcené neuronové s´ıtˇe NN je pouˇzita uˇc´ıc´ı metoda. Následnˇe jsou pro veˇskeré vzory z uˇc´ıc´ı mnoˇziny spoˇcteny odpov´ıdaj´ıc´ı výstupy. Tyto výstupy jsou jiˇz jednorozmˇerné a o kaˇzdém z nich je známa pˇr´ısluˇsnost do jedné z klasifikaˇcn´ıch tˇr´ıd. S pomoc´ı tˇechto výstup˚ u lze tedy jeˇstˇe z´ıskat informaci, kterou uˇc´ıc´ı metoda nemusela vyuˇz´ıt. Intuitivnˇe je pˇredstava, ˇze uˇc´ıc´ı metoda vlastnˇe pˇrevád´ı uˇc´ıc´ı mnoˇzinu do tvaru (tedy na neuronovou s´ıt’), ve kterém lze tuto mnoˇzinu pozdˇeji pouˇz´ıt ke klasifikaci mnoˇziny, o n´ıˇz nic nev´ıme, dalˇs´ı zpracován´ı výstup˚ u tedy pouze rozˇsiˇruje uˇc´ıc´ı metodu, v d˚ usledku se vlastnˇe kombinuj´ı dvˇe metody a je i moˇzné, ˇze se tak dostane lepˇs´ıch výsledk˚ u. Na výstupy neuronové s´ıtˇe se lze d´ıvat jako na realizace náhodné veliˇciny Y ∈ R a pokusit se odhadnout pravdˇepodobnosti p(C = s|Y = y) a p(C = b|Y = y) kde y ∈ R. S výhodou lze vyuˇz´ıt faktu, ˇze výstupy NN jsou jiˇz jen jednorozmˇerné. Pravdˇepodobnosti p(C = s|Y = y), p(C = b|Y = y) lze odhadnot pomoc´ı následuj´ıc´ıho postupu: 1. odhadnou se hustoty pravdˇepodobnosti f (y|C = s), f (y|C = b), f (y) 2. pro výpoˇcet p(C = s|Y = y), p(C = b|Y = y) se pouˇzije následuj´ıc´ıch výraz˚ u f (y|C = s)p(C = s) p(C = s|Y = y) = f (y) 31

p(C = b|Y = y) =

f (y|C = b)p(C = b) f (y)

Pˇri tomto postupu je nutné vyˇreˇsit nˇekolik problém˚ u. Nejsou známy p(C) a f (y), dále se bude pˇredpokládat, ˇze p(C = s) = p(C = b) = 0, 5. Hustota pravdˇepodobnosti f (y) se odhaduje pomoc´ı vztahu f (y) = f (y|C = s)p(C = s) + f (y|C = b)p(C = b). Je také nutné zvolit vhodnou metodu pro odhad p(Y |C), v tomto pˇr´ıpadˇe je tvar hustory rozdˇelen´ı neznámý a je tˇreba pouˇz´ıt nˇekterou z neparametrických metod odhadu hustoty pravdˇepodobnosti. Nejprve byl pro svou jednoduchost zvolen histogramový odhad. Pozdˇeji byla hledaná hustota pravdˇepodobnosti také modelována jako smˇes normáln´ıch rozdˇelen´ı.

4.4

Histogramov´ y odhad

Pro odhad f (y|C = s) a f (y|C = b) se nejprve vhodnˇe zvolil interval I ⊆ R tak, aby obsahoval vˇeS tˇsinu realizac´ı Y . Tento interval se dále rozdˇelil na stejnˇe velké d´ılky Ij , I = Ij , Ii ∩ Ij = ∅ pro i 6= j, jejichˇz poˇcet byl odvozen z j∈m ˆ

poˇctu dat. Pro kaˇzdý d´ılek(ozn. j) se pak odhadly hodnoty 1 Nsj h Ns 1 Nbj p(j|C = b) = h Nb

p(j|C = s) =

kde h je velikost jednoho d´ılku, Nsj (resp. Nbj ) je poˇcet realizac´ı Y , které patˇr´ı do signálu (resp. pozad´ı) v j-tém d´ılku, Ns (resp. Nb ) je celkový poˇcet zástupc˚ u signálu (resp. pozad´ı) . T´ım se dostala po ˇca´stech konstantn´ı funkce   0 pro y ∈ I<     p(1|C) pro y ∈ I1    p(2|C) pro y ∈ I2 (4.4) f (y|C) = ..  .     p(n|C) pro y ∈ Im    0 pro y ∈ I >

kde m je poˇcet d´ılk˚ u def

I< = {y ∈ R|y 6∈ I ∧ (∀x ∈ I)(y < x)} def

I> = {y ∈ R|y 6∈ I ∧ (∀x ∈ I)(y > x)} 32

Pozn´ amka 4.1 Mnoˇziny I< a I> byly pˇridány proto, aby se pokryla celá mnoˇzina R, pokud výstup neuronové s´ıtˇe padne do jednoho z tˇechto interval˚ u, definuje se pravdˇepodobnost, ˇze takový vstup je signál nebo pozad´ı, nulová. Pozn´ amka 4.2 Interval I a jednotlivé d´ılky Ij byly nastavovány za pouˇzit´ı následuj´ıc´ıho postupu. Necht’ n je velikost uˇc´ıc´ı mnoˇziny. def

def

1. a = −2; b = 2 def

2. I = [a; b] (pro tento interval budou tedy pravdˇepodobnosti nenulové) def

n (tedy nastavit poˇcet d´ılk˚ u tak, aby v kaˇzdém bylo pr˚ umˇernˇe 30 3. m = 30 realizac´ı) def

4. pokud m < 30 tak m = min(30, n) (oˇsetˇren´ı, aby byl d´ılk˚ u urˇcitý minimáln´ı poˇcet) def b−a m

5. h =

Pozn´ amka 4.3 Nevýhodou tohoto typu odhadu hustoty pravdˇepodobnosti je závislost na volbˇe poˇctu a velikostech jednotlivých d´ılk˚ u, nav´ıc je takto z´ıskaná funkce nespojitá.

4.5

Odhad parametr˚ u smˇ esi norm´ aln´ıch rozdˇ elen´ı

Modelován´ı hustoty pravdˇepodobnosti pomoc´ı smˇesi pravdˇepodobnostn´ıch rozdˇelen´ı je nˇekde na p˚ ul cesty mezi parametrickými a neparametrickými odhady. Smˇesi rozdˇelen´ı maj´ı dostateˇcnou flexibilitu pro aproximaci hustot pravdˇepodobnosti. Vyuˇzit´ı tohoto pˇr´ıstupu v aplikaci na problém odhadu pravdˇepodobnost´ı f (y|C) bylo zvoleno z následuj´ıc´ıch d˚ uvod˚ u. • v ideáln´ım pˇr´ıpadˇe by f (y|C = s) a f (y|C = b) mˇely podobu delta distribuc´ı, nebo alespoˇ n hustot pravdˇepodobnosti, které se podobaj´ı normáln´ımu rozdˇelen´ı se stˇredn´ımi hodnotami v bodech −1 a +1. V praxi to samozˇrejmˇe vycház´ı h˚ uˇre, nicménˇe se smˇes normáln´ıch rozdˇelen´ı zdá být vhodným nástrojem • výsledkem je hustota pravdˇepodobnosti, která je spojitá a definovaná na celém R • parametry výsledné smˇesi lze snadno uchovávat 33

• pouˇzit´ı je snadnˇejˇs´ı neˇz pˇri pouˇzit´ı napˇr´ıklad jádrových odhad˚ u, odpadá problém se vzorkován´ım a interpolac´ı bod˚ u Tvar smˇesi normáln´ıch rozdˇelen´ı lze zapsat takto f (y|C) =

k X

αi pi (y|C)

(4.5)

i=1

kde

2

pi (y|C) = √ 1

2πσi2

k P

i) exp(− (y−µ ) 2σ2 i

αi = 1

i=1

Pozn´ amka 4.4 Z výrazu 4.5 je vidˇet, ˇze parametrem tohoto modelu je poˇcet komponent smˇesi oznaˇcený jako k. Optimáln´ı nastaven´ı tohoto parametru lze ˇreˇsit r˚ uznˇe a záleˇz´ı i na aplikac´ıch. K urˇcen´ı k byl pouˇzit tento postup • nauˇc´ı se smˇesi pro hodnoty k ∈ {1, . . . , kmax } • výsledná nauˇcená smˇes je ta, která maximalizuje výraz 3 log(p(Y|Mk )) − k log(n) 2 kde Y jsou data pouˇzitá pro uˇcen´ı smˇesi, Mk reprezentuje nauˇcenou smˇes s k komponentami. V´ıce lze naj´ıt napˇr. v [FF02]. Pro nalezen´ı parametr˚ u smˇesi normáln´ıch rozdˇelen´ı s k komponentami byl pouˇzit EM algoritmus (viz. napˇr. [BIS97, BIL98]).

4.6

´ Uprava rozhodov´ an´ı

Pouˇzit´ı odhad˚ u hustoty pravdˇepodobnosti s sebou pˇrináˇs´ı nˇekolik problém˚ u. Pokud jsou f (y|C = s) i f (y|C = b) nulové, je otázkou jak volit p(C = s|Y = y) a p(C = b|Y = y), v takových pˇr´ıpadech je pˇrijatelné ˇreˇsen´ı definovat pravdˇepodobnosti p(C = s|Y = y) a p(C = b|Y = y) jako nulové, jiˇz vˇsak neplat´ı rovnost p(C = s|Y = y) + p(C = b|Y = y) = 1. Horˇs´ı je pˇr´ıpad, kdy jsou f (y|C = s) i f (y|C = b) bl´ızké nule. V takovém pˇr´ıpadˇe by vyˇsly pravdˇepodobnosti p(C = s|Y = y) i p(C = b|Y = y) dost vysoké na to, aby se pouˇzily pro rozhodnut´ı, zda se jedná o signál nebo

34

400 300 x2 200 100 0

0

50

100

150

200

250

x1

Obrázek 4.1: Rozhodovac´ı oblasti pro signál a pozad´ı - pouˇzit´ı prahu pozad´ı. Napˇr´ıklad necht’ f (y|C = s) = 10−3 a f (y|C = b) = 10−5 v takovém pˇr´ıpadˇe 1 f (y) = (p(y|s) + p(y|b)) = 0.000505 2 p(C = s|Y = y) = 0.99 p(C = b|Y = y) = 0.01 A výsledkem by bylo, ˇze daný vzor by byl jednoznaˇcnˇe oznaˇcen jako signál, pˇrestoˇze pocház´ı z ˇcásti vstupn´ıho prostoru neuronové s´ıtˇe, ze kterého nepocházelo pˇr´ıliˇs bod˚ u z uˇc´ıc´ı mnoˇziny. Tvar rozhodovac´ıch oblast´ı pro signál a pozad´ı ve vstupn´ım prostoru neuronové s´ıtˇe jsou si pˇri pouˇzit´ı prahu nebo odhadu hustoty pravdˇepodobnosti velice podobné. To je patrné i z obrázk˚ u 4.1 a 4.2, na kterých jsou zobrazeny oblasti, odkud se vzory oznaˇcuj´ı jako signál nebo pozad´ı. Uvedené výsledky byly z´ıskány neuronovou s´ıt´ı n´ıˇze oznaˇcenou jako NN3. To je sice z jistého pohledu zlepˇsen´ı, ale stále nejsou dobˇre vymezeny oblasti, odkud byly vzory z uˇc´ıc´ı mnoˇziny. Pro ostˇrejˇs´ı vymezen´ı tˇechto oblast´ı bylo pouˇzita informace, kterou poskytuje odhad f (y) (pro ilustraci je odhad f (y) pro s´ıt’ NN3 nauˇcenou na uvedených dvojrozmˇerných datech zobrazen na obrázku 4.4).

35

400 300 x2 200 100 0

0

50

100

150

200

250

x1

Obrázek 4.2: Rozhodovac´ı oblasti pro signál a pozad´ı - pouˇzit´ı smˇesi normáln´ıch rozdˇelen´ı, pmin = 0 Výsledná podoba rozhodovac´ıho pravidla je tedy zobecnˇen´ım 4.3   s pro p(C = s|Y = y) > t ∧ f (y) ≥ pmin b pro p(C = b|Y = y) > t ∧ f (y) ≥ pmin c(x) =  u jinak

(4.6)

Definice 4.4 Necht’ rozhodovac´ı pravidlo c je tvaru 4.6, hodnoty p(C = s|Y = y), p(C = b|Y = y) a f (y) byly spoˇcteny z mnoˇziny Y ⊆ R pomoc´ı histogramového odhadu popsaného v 4.4 a hodnota pmin necht’ je rovna ˇc´ıslu α. Takové rozhodovac´ı pravidlo se bude nazývat pravidlo histogramu na u ´ rovni α a znaˇcit RHIST (α). Definice 4.5 Necht’ rozhodovac´ı pravidlo c je tvaru 4.6, hodnoty p(C = s|Y = y), p(C = b|Y = y) a f (y) byly spoˇcteny z mnoˇziny Y ⊆ R pomoc´ı odhadu smˇesi normáln´ıch rozdˇelen´ı popsaného v 4.5, hodnota pmin necht’ je rovna ˇc´ıslu α. Takové rozhodovac´ı pravidlo se bude nazývat pravidlo smˇesi na u ´ rovni α a znaˇcit RGM (α). Pˇri rozhodován´ı o oznaˇcen´ı vstupu jako signál nebo pozad´ı jsou nyn´ı pouˇzity pouze vstupy, jejichˇz výstupy pocházej´ı z podmnoˇziny R pro nˇeˇz je odhad pravdˇepodobnosti, ˇze do nich padl vzor z uˇc´ıc´ı mnoˇziny, vyˇsˇs´ı neˇz urˇcitá hranice. T´ımto zp˚ usobem lze ovlivnit vlastnost generalizace neuronové s´ıtˇe, a v d˚ usledku oznaˇcovat jako signál/pozad´ı pouze vzory, které jsou bl´ızké vzor˚ um z uˇc´ıc´ı mnoˇziny. 36

0

100

200

300

400

Pro pmin rovno nule toto pravidlo pˇrecház´ı na pravidlo 4.3, pˇri zvyˇsován´ı pmin se zmenˇsuj´ı oblasti vstupn´ıho prostoru neuronové s´ıtˇe, ze kterých pocházej´ı vzory, které by byly urˇceny jako signál nebo pozad´ı. U tohoto pravidla se jiˇz z˚ ustalo, jako hodnota pmin se volila nejˇcastˇeji hodnota 0.1.

0

50

100

150

200

250

Obrázek 4.3: Odhad hustoty pravdˇepodobnosti f (y) z´ıskaný pomoc´ı smˇesi normáln´ıch rozdˇelen´ı pro odpov´ıdaj´ıc´ı vstupy z R2 , zobrazeno pomoc´ı izoˇcar.

4.7

Srovn´ an´ı rozhodovac´ıch pravidel

Srovnán´ı bylo provedeno následovnˇe 1. byly vytvoˇreny sloˇzitˇejˇs´ı dvourozmˇerná uˇc´ıc´ı data, viz. obr. 4.5 2. nˇekolik neuronových s´ıt´ı bylo nauˇceno pro rozpoznáván´ı tˇechto dat 3. byly spoˇcteny výstupy pro vzory z uˇc´ıc´ı mnoˇziny 4. tyto výstupy byly pouˇzity k z´ıskán´ı odhadu hustoty pravdˇepodobnosti 5. byl navzorkován prostor R2 tak, aby obsahoval veˇskeré vzory z uˇc´ıc´ı mnoˇziny, t´ım vznikla mnoˇzina vzor˚ uS 6. na S byly aplikovány neuronové s´ıtˇe 37

x2

(y)

ad p Odh x1

Obrázek 4.4: Odhad hustoty pravdˇepodobnosti f (y) z´ıskaný pomoc´ı smˇesi normáln´ıch rozdˇelen´ı pro odpov´ıdaj´ıc´ı vstupy z R2 , zobrazen 3D graf (body urˇcuj´ıc´ı mˇr´ıˇzku jsou jednoduˇse spojeny u ´ seˇckami). 7. na výstupy neuronových s´ıt´ı se pouˇzily odhady hustoty pravdˇepodobnosti 8. byly zobrazeny oblasti,ve kterých se jednotlivé body povaˇzuj´ı za signál, pozad´ı nebo nev´ım Rozhodovac´ı oblasti jsou zobrazeny následovnˇe. Vstupn´ı prostor neuronových s´ıt´ı je dvourozmˇerný a kaˇzdému bodu z tohoto prostoru je rozhodovac´ım algoritmem pˇriˇrazena hodnota z mnoˇziny {s, b, u}. Pro zobrazen´ı rozhodovac´ıch oblast´ı bylo zvoleno zobrazit hranice oblast´ı pro pˇrijet´ı bod˚ u jako signál ˇci pozad´ı v pˇr´ısluˇsných barvách, jelikoˇz tyto hranice vˇetˇsinou omezuj´ı uzavˇrené oblasti, lze snadno poznat, kde je oblast pro signál a kde pro pozad´ı. Pro vˇetˇs´ı pˇrehlednost jsou nav´ıc zobrazeny i body z uˇc´ıc´ı mnoˇziny. Na obrázku 4.6 jsou zobrazeny topologie vybraných neuronových s´ıt´ı, pro nˇeˇz jsou n´ıˇze zobrazeny rozhodovac´ı oblasti pro signál, pozad´ı nebo nev´ım. Tyto neuronové s´ıtˇe byly z´ıskány následuj´ıc´ım zp˚ usobem: NN1 obsahuje pouze jeden neuron s pˇrep´ınac´ı jednoutkou a deseti výpoˇcetn´ımi neurony, byla zkonstruována ruˇcnˇe

38

NN2 byla z´ıskána takto, náhodnˇe se vygenerovalo 100 neuronových s´ıt´ı, ty byly nauˇceny a byla pro nˇe vyhodnocena chyba E0 (viz. 5.4), neuronové s´ıti NN2 odpov´ıdala nejniˇzˇs´ı hodnota E0 NN3 vznikla odebrán´ım nˇekolika neuron˚ u z NN2 Pro kaˇzdou s´ıt’ jsou zobrazeny oblasti pˇri pouˇzit´ı pravidel RT , RGM (0, 1) a RHIST (0, 1) Z výsledk˚ u z´ıskaných pro uvedenou dvojrozmˇernou uˇc´ıc´ı mnoˇzinu vyplynulo, ˇze popsaný pˇr´ıstup je pouˇzitelný. Tento výsledek byl nicménˇe prozat´ım z´ıskán pouze pro jednu jednoduˇsˇs´ı u ´ lohu, Dalˇs´ı ovˇeˇren´ı tohoto pˇr´ıstupu bylo provedeno zároveˇ n s analýzou neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami.

100

200

x2

300

400

signál pozadí

50

100

150

200

x1

Obrázek 4.5: Netriviáln´ı dvourozmˇerná uˇc´ıc´ı mnoˇzina, tato mnoˇzina obsahuje body ze dvou tˇr´ıd

39

Obrázek 4.6: Srovnávané neuronové s´ıtˇe, zleva NN1, NN2, NN3

40

400 300 x2 200 100 0

0

50

100

150

200

250

150

200

250

150

200

250

0

100

200

x2

300

400

x1

0

50

100

0

100

200

x2

300

400

x1

0

50

100 x1

41

Obrázek 4.7: NN1: Hranice rozhodovac´ıch oblast´ı, pˇri pouˇzit´ı r˚ uzn´ ych rozhodovac´ıch pravidel. Zhora: R0 , RHIST (0, 1), RGM (0, 1).

400 300 x2 200 100 0

0

50

100

150

200

250

150

200

250

150

200

250

0

100

200

x2

300

400

x1

0

50

100

0

100

200

x2

300

400

x1

0

50

100 x1

42


400 300 x2 200 100 0

0

50

100

150

200

250

150

200

250

150

200

250

0

100

200

x2

300

400

x1

0

50

100

0

100

200

x2

300

400

x1

0

50

100 x1

43


Kapitola 5 Urˇ cen´ı kvality neuronov´ e s´ıtˇ e 5.1

Z´ akladn´ı principy a motivace

Jako vstup pro uˇc´ıc´ı metodu slouˇz´ı nenauˇcená neuronová s´ıt’ NN U a uˇc´ıc´ı mnoˇzina DL (n, m). Výsledná neuronová s´ıt’ pˇredstavuje zobrazen´ı, které by mˇelo slouˇzit pro zaˇrazován´ı vzor˚ u ze vstupn´ıho prostoru do klasifikaˇcn´ıch tˇr´ıd. Pro takovou neuronovou s´ıt’ vˇsak nen´ı zaruˇceno, ˇze dokáˇze dostateˇcnˇe dobˇre ˇreˇsit problém, k jehoˇz ˇreˇsen´ı byla urˇcena. Proces uˇcen´ı neuronové s´ıtˇe obsahuje nˇekolik u ´ skal´ı, mimo jiné napˇr.: • daný problém nelze z principu ˇreˇsit • uˇc´ıc´ı mnoˇzina je nekvalitn´ı • nenauˇcená neuronová s´ıt’ slouˇz´ıc´ı jako vstup uˇc´ıc´ı metody je ˇspatnˇe zvolena Je proto d˚ uleˇzité m´ıt k dispozici nˇejaký nástroj, který by pomohl urˇcit, zda je urˇcitá neuronová s´ıt’ pouˇzitelná, ˇci vybrat z mnoˇziny nauˇcených neuronových s´ıt´ı tu nejvhodnˇejˇs´ı. K tomu, aby se dala zmˇeˇrit kvalita neuronové s´ıtˇe by bylo optimáln´ı znát správnou hodnotu pro libovolný vzor ze vstupn´ıho prostoru, potom by bylo tˇreba moˇzné spoˇc´ıtat chybu pro kaˇzdý vzor a z toho odvodit celkovou chybu. Nˇeco takového je vˇsak nemoˇzné, nav´ıc, kdyby byla sch˚ udná cesta, jak z´ıskat správnou hodnotu pro libovolný vzor ze vstupn´ıho prostoru, nebylo by tˇreba uˇcit neuronovou s´ıt’. Bˇeˇznˇe je k dispozici mnoˇzina vzor˚ u X, ke kaˇzdému vzoru je známa poˇzadovaná hodnota a neuronová s´ıt’ je uˇcena co nejlépe vzhledem k nˇejakému kritériu klasifikovat dané vzory. Nakonec je moˇzné vyhodnotit hodnotu daného kritéria pro známé vzory a tuto hodnotu pouˇz´ıt jako kvalitu nauˇcen´ı. Tento 44

pˇr´ıstup vˇsak skrývá problém nazývaný pˇreuˇcen´ı. Vˇetˇsina kritéri´ı, které se minimalizuj´ı pˇri uˇcen´ı neuronových s´ıt´ı (vˇcetnˇe neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami) je zamˇeˇreno jen na body z uˇc´ıc´ı mnoˇziny. Nástává problém, ˇze neuronová s´ıt’ se m˚ uˇze skvˇele nauˇcit klasifikovat vzory z uˇc´ıc´ı mnoˇziny, ale pˇri klasifikaci vzor˚ u, které jiˇz nebyly v uˇc´ıc´ı mnoˇzinˇe, m˚ uˇze naprosto selhat a vracet nesmyslné hodnoty. Tento problém se bˇeˇznˇe ˇreˇs´ı tak, ˇze se mnoˇzina vzor˚ u, která je k dispozici, rozdˇel´ı na dvˇe ˇci v´ıce podmnoˇzin, které se teprve oznaˇcuj´ı jako uˇc´ıc´ı mnoˇzina a testovac´ı mnoˇzina. Uˇc´ıc´ı mnoˇzina se pouˇzije pro nauˇcen´ı a testovac´ı mnoˇzina se následnˇe pouˇzije pro vyhodnocen´ı minimalizovaného kritéria. Takto lze kvalitu neuronové s´ıtˇe mˇeˇrit nejen pomoc´ı vzor˚ u, které byly pouˇzity k jej´ımu nauˇcen´ı, ale i pomoc´ı vzor˚ u, které do té doby s´ıt’ nemˇela k dispozici. V nejlepˇs´ım pˇr´ıpadˇe by hodnoty vyhodnocovaného kritéria byly pro uˇc´ıc´ı i testovac´ı mnoˇzinu velice podobné. Definice 5.1 Necht’ X je mnoˇzina vzor˚ u dimenze m a velikosti n, X se bude nazývat testovac´ı mnoˇ zina dimenze m s n vzory a znaˇcit DT (n, m). Pozn´ amka 5.1 Definice testovac´ıch i uˇc´ıc´ıch mnoˇzin vlastnˇe pouze jinak pojmenováváj´ı mnoˇzinu vzor˚ u za u ´ˇcelem zd˚ uraznˇen´ı u ´ˇcelu, pro který jsou pouˇzity. Nˇekdy se pro testovac´ı kritérium m˚ uˇze pouˇz´ıt i jiné kritérium, neˇz které bylo minimalizováno pˇri uˇcen´ı. Toto plyne z toho, ˇze nˇekterá kritéria je velice obt´ıˇzné minimalizovat a je výhodnˇejˇs´ı pouˇz´ıt uˇc´ıc´ı metody ménˇe nároˇcné na výpoˇcetn´ı prostˇredky pro uˇcen´ı v´ıce s´ıt´ı a posléze vybrat s´ıt’, která minimalizuje jiné, opravdu poˇzadované kritérim. Toto je i pˇr´ıpad pˇri uˇcen´ı neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami. N´ıˇze v textu je popsáno nˇekolik kritéri´ı, které byly implementovány a pouˇz´ıvany pˇri srovnáván´ı výsledk˚ u pro r˚ uzné neuronové s´ıtˇe. Srovnán´ı jednotlivých kritéri´ı samo o sobˇe nen´ı moˇzné, proto byla tyto kritéria srovnávána pr˚ ubˇeˇznˇe bˇehem analýzy vlastnost´ı neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami viz. kapitola 7

5.2

Krit´ erium nejmenˇs´ıch ˇ ctverc˚ u

ˇ Casto pouˇz´ıvané kritérium pro minimalizaci i vyhodnocován´ı kvality neuronových s´ıt´ı je souˇcet kvadrát˚ u odchylek. Tato ztrátová funkce je pouˇz´ıvána hlavnˇe pro jednoduchost, lze ji totiˇz minimalizovat snadnˇeji neˇz jiné ztrátové

45

funkce, podrobnˇejˇs´ı diskuse lze naj´ıt napˇr. v [BIS97, VIS98]. Toto kritérium má podobu n X ESSE = (yi − ti )2 (5.1) i=1

hodnota tohoto kritéria je závislá na poˇctu dat, proto se pro vyhodnocen´ı kvality ˇcastˇeji pouˇz´ıvá stˇredn´ı hodnota kvadrátu odchylek n

EM SE nebo výraz

1X = (yi − ti )2 n i=1 n P

(yi − ti )2

ERSE = i=1 n P

(5.2)

(5.3)

(yi − t¯)2

i=1

kde t¯ =

n P

ti .

i=1

Tyto ztrátové funkce jiˇz nejsou závislé na poˇctu dat a usnadˇ nuj´ı tak srovnán´ı pro r˚ uzná testovac´ı data. Hodnota tˇechto kritéri´ı sice klesá s t´ım, jak se výstupn´ı hodnoty vzor˚ u z testovac´ı mnoˇziny bl´ıˇz´ı k poˇzadovaným výstup˚ um, nicménˇe toto kritérium se odvozuje za pˇredpokladu, ˇze poˇzadované hodnoty obsahuj´ı chybovou sloˇzku, která má normáln´ı rozdˇelen´ı. To v pˇr´ıpadˇe klasifikace do dvou skupin, kde poˇzadované hodnoty mohou být bud’ −1 nebo +1, nen´ı pˇr´ıliˇs opodstatnˇené, v´ıce lze na toto téma naj´ıt napˇr. v [BIS97]. Tyto d˚ uvody vedou k pouˇzit´ı jiných ztrátových funkc´ı.

5.3

Cross-entropy

Ztrátovou funkci, která je pro u ´ˇcely klasifikace vhodnˇejˇs´ı neˇz kritérium souˇctu kvadrát˚ u odchylek ESSE , lze odvodit následuj´ıc´ı u ´ vahou, jedná se o pouˇzit´ı principu maximáln´ı vˇerohodnosti. Necht’ vzory urˇcené pro klasifikaci pocházej´ı z prostoru Rn . Necht’ funkce f : Rn 7→ R kaˇzdému vzoru x z Rn pˇriˇrazuje pravdˇepodobnost, ˇze daný vzor je signál, tedy p(C = s|x). Dále necht’ X je mnoˇzina vzor˚ u. Definice 5.2 Funkce t01 : {−1, 1} 7→ {0, 1} je definována následovnˇe 0 pro t = −1 def t01 (t) = (5.4) 1 pro t = 1 46

Pro vˇetˇs´ı pˇrehlednost se bude m´ısto poˇzadovaných hodnot ti odpov´ıdaj´ıc´ım def vzor˚ um xi pouˇz´ıvat t′i = t01 (ti ). Za pˇredpokladu, ˇze dvojice (xi , ti ) oznaˇcované jako wi jsou realizace navzájem nezávislých náhodných veliˇcin Wi , lze pro pravdˇepodobnost mnoˇziny vzor˚ u p(X) napsat n Y p(X) = p(Wi = wi) (5.5) i=1

pro pravdˇepodobnosti p(Wi ) plat´ı (pˇredpokládá se, ˇze p(Wi = (X, T )) nezávis´ı na T ) p(Wi = (xi , +1)) = f (xi ) p(Wi = (xi , −1)) = 1 − f (xi )

(5.6) (5.7)

coˇz lze zapsat jako ′

′

p(Wi = (xi , ti )) = f (xi )ti (1 − f (xi ))1−ti

(5.8)

po dosazen´ı do 5.5 p(X) =

n Y

p(Wi = wi ) =

i=1

n Y i=1

′

′

f (xi )ti (1 − f (xi ))1−ti

(5.9)

ˇ ım je P (X) vˇetˇs´ı, t´ım v´ıce vzory z X odpov´ıdaj´ıc´ı pravdˇepodobnostem C´ daným funkc´ı f , toto lze obrátit, upevnit mnoˇzinu vzor˚ u a hledat funkci f , která nejlépe popisuje dané vzory. Optimáln´ı taková funkce by tedy maximalizovala 5.5. Tento výraz by jiˇz jako takový pro urˇcován´ı kvality postaˇcoval, nˇekolika u ´ pravami ho lze pˇrevést na ztrátovou funkci. Pˇri urˇcován´ı kvality jde hlavnˇe o srovnáván´ı funkc´ı f a nejde jiˇz tolik o opravdové hodnoty, lze proto dále upravovat zápornˇe vzatý logarimus p(X), t´ım se obrát´ı smysl a optimáln´ı funkce bude minimalizovat tento upravený výraz.

− log p(X) = − log{

=−

i=1

n X

i=1

′

′

f (xi )ti (1 − f (xi ))1−ti } = ′

′

log(f (xi )ti (1 − f (xi ))1−ti ) =

(5.10)

t′i log(f (xi )) + (1 − t′i ) log(1 − f (xi ))

(5.11)

=− n X

n Y

i=1

47

výraz 5.11 pˇredstavuje koneˇcnou podobu ztrátové funkce, která se bude znaˇcit ECE . Tato ztrátová funkce se v anglické literatuˇre nazývá cross-entropy. V´ıce lze o vlastnostech a pouˇzit´ı tohoto kritéria nalézt napˇr. v [BIS97] Pro vyhodnocen´ı ECE je tˇreba m´ıt k dispozici funkci vracej´ıc´ı odpov´ıdaj´ıc´ı pravdˇepodobnosti. Toto výstupy neuronové s´ıtˇe s pˇrep´ınac´ımi jednotkami nesplˇ nuj´ı, jiˇz to vˇsak splˇ nuje sloˇzen´ı funkc´ı, z nichˇz vnitˇrn´ı pˇredstavuje funkci reprezentovanou neuronovou s´ıt´ı a vnˇejˇs´ı, která výstupy neuronové s´ıtˇe pˇrevád´ı na pravdˇepodobnosti. Implementována a vyzkouˇsena byla kombinace, kdy pro odhad pravdˇepodobnost´ı byla pouˇzita smˇes normáln´ıch rozdˇelen´ı, která slouˇzila jako postprocessor na výstupy neuronové s´ıtˇe. Takto z´ıskané kritérium se bude znaˇcit ECEGM Pozn´ amka 5.2 Nyn´ı je vidˇet dalˇs´ı d˚ uvod, proˇc se snaˇzit interpretovat výstupy neuronové s´ıtˇe jako pravdˇepodobnosti. Pokud by neuronová s´ıt’ vracela pravdˇepodobnosti, ˇze daný vzor je signál, lze pouˇz´ıt kritérium ECE k srovnáván´ı r˚ uzných neuronových s´ıt´ı a výbˇeru té, která nabývá niˇzˇs´ı hodnoty tohoto kritéria. Jeˇstˇe lepˇs´ı by bylo pˇr´ımo toto kritérium minimalizovat pˇri uˇcen´ı, uˇc´ıc´ı proces neuronové s´ıtˇe s pˇrep´ınac´ımi jednotkami je vˇsak pevnˇe nastaven a taková u ´prava by byla tˇeˇzko proveditelná.

5.4

Dalˇs´ı ztr´ atov´ e funkce

Pˇrirozenou volbou, jak volit kvalitu nauˇcen´ı neuronové s´ıtˇe je pomˇer ˇspatnˇe klasifikovaných vzor˚ u z testovac´ı mnoˇziny ku vˇsem vzor˚ um z testovac´ı mnoˇziny. Pˇri takto formulovaném kritériu záleˇz´ı, jakým zp˚ usobem se rozhoduje o pˇr´ısluˇsnostech jednotlivých vzor˚ u viz. kapitola 4. Jako ztrátové funkce lze definovat následuj´ıc´ı výrazy, necht’ je dáná testovac´ı mnoˇzina LT (n, m). n0 (5.12) n kde n0 je poˇcet ˇspatnˇe urˇcených vzor˚ u z testovac´ı mnoˇziny pˇri pouˇzit´ı rozhodovac´ıho pravidla R0 . def

E0 =

nHIST (5.13) n kde nHIST je poˇcet ˇspatnˇe urˇcených vzor˚ u z testovac´ı mnoˇziny pˇri pouˇzit´ı rozhodovac´ıho pravidla RHIST (α). def

EHIST (α) =

def

EGM (α) =

48

nGM n

(5.14)

kde nGM je poˇcet ˇspatnˇe urˇcených vzor˚ u z testovac´ı mnoˇziny pˇri pouˇzit´ı rozhodovac´ıho pravidla RGM (α). jako posledn´ı ztrátová funkce byla zkouˇsena modifikace kritéria ECEGM následuj´ıc´ım zp˚ usobem: n

def

SGM =

1X ′ ′ f (xi )ti + (1 − f (xi ))1−ti n i=1 def

ESGM = 1 − SGM

49

(5.15)

(5.16)

Kapitola 6 Benchmarky pro klasifik´ atory 6.1

´ Uvod

Nˇekdy je potˇreba srovnávat dvˇe a v´ıce metod pro ilustraci jejich schopnost´ı, také pˇri vývoji nových metod je nutné srovnávat nové metody s výsledky jiných, jiˇz existuj´ıc´ıch metod. Pro tyto u ´ˇcely existuj´ı v r˚ uzných vˇedeckých oblastech referenˇcn´ı soubory problém˚ u, které usnadˇ nuj´ı porovnán´ı výsledk˚ u aniˇz by bylo nutné neustále pˇrepoˇc´ıtávat výsledky pro r˚ uzná data. Dalˇs´ı výhodou je fakt, ˇze tyto referenˇcn´ı soubory jiˇz obsahuj´ı data pˇripravená ve formˇe, aby se dala snadno pouˇz´ıt. Jako souˇcást tˇechto soubor˚ u problém˚ u jsou i pravidla, jak by se mˇelo postupovat pro správnou aplikaci srovnávané metody a následné umoˇznˇen´ı srovnán´ı výsledk˚ u s jinými, jelikoˇz pro korektn´ı porovnán´ı výsledk˚ u nestaˇc´ı jen ˇreˇsit stejný problém, ale je nutné dodrˇzovat i jistá pravidla. Pro srovnán´ı klasifikaˇcn´ıch metod nebo pˇr´ımo variant neuronových s´ıt´ı lze na internetu nalézt nˇekolik takových soubor˚ u.

6.2

Proben1

Proben1 je soubor problém˚ u pˇr´ımo pro srovnán´ı výkonu neuronových s´ıt´ı. Aˇz na nˇekolik vyj´ımek se jedná o reálné a nikoliv umˇele vytvoˇrené problémy. Velký pˇr´ınos tohoto souboru problému a hlavn´ı d˚ uvod, proˇc byl nakonec vybrán pro pouˇzit´ı, je snadnost pouˇzit´ı. Veˇskeré datové soubory jsou ve stejném formátu a jiˇz pˇredzpracovány pˇr´ımo pro uˇcen´ı. Obvykle reálná data obsahuj´ı chybˇej´ıc´ı hodnoty nebo odlehlá pozorován´ı, dalˇs´ım problémem m˚ uˇze být povaha dat, namˇeˇrené veliˇciny mohou být napˇr´ıklad diskrétn´ı, spojité, celoˇc´ıselné nebo dokonce kategoriáln´ı. Datové soubory v Proben1 jiˇz byly upraveny tak, aby se daly rovnou pouˇz´ıt a nebylo tˇreba 50

ˇreˇsit jejich zpracován´ı. V Proben1 jsou data upravena takto • za chybˇej´ıc´ı hodnoty jsou dosazeny stˇredn´ı hodnoty odpov´ıdaj´ıc´ıch veliˇcin • kategoriáln´ı promˇenné jsou zakódovány do binárn´ı podoby Necht’ veliˇcina X je kategoriáln´ı a m˚ uˇze nabývat hodnot z mnoˇziny M = {1, . . . , n}, m = |M|, konkrétn´ı hodnota x veliˇciny X je nahrazena vektorem y = (y1 , . . . , ym ), kde 1 pro x = i (6.1) yi = 0 jinak Pro potˇreby uˇcen´ı neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami bylo sice nutné uˇc´ıc´ı a testovac´ı datové soubory pˇrevést do odliˇsného formátu, ale to jiˇz nen´ı tak nároˇcný problém, jako pˇripravit reálnˇe namˇeˇrená data. Proben1 obsahuje jak klasifikaˇcn´ı, tak aproximaˇcn´ı problémy. Pouˇzita byla data z n´ıˇze popsaných problém˚ u, které jsou formulovány jako klasifikace do dvou tˇr´ıd. Cancer rozhodován´ı, zda má pacient rakovinu Dimenze uˇc´ıc´ı mnoˇziny: 9 Poˇcet objekt˚ u v uˇc´ıc´ı mnoˇzinˇe: 350 Pouˇzit´ı tˇechto dat vyˇzaduje uvést p˚ uvodn´ı origináln´ı zdroj tˇechto dat. ˇ ast namˇeˇrených dat bylo z´ıskáno z University Medical Centre, InstiC´ tute of Oncology, Ljublana, Slovinsko. Card rozhodován´ı, zda klientovi banky má být pˇridˇelena kreditn´ı karta Dimenze uˇc´ıc´ı mnoˇziny: 51 Poˇcet objekt˚ u v uˇc´ıc´ı mnoˇzinˇe: 345 Diabetes rozhodován´ı, zda má pacient cukrovku Dimenze uˇc´ıc´ı mnoˇziny: 8 Poˇcet objekt˚ u v uˇc´ıc´ı mnoˇzinˇe: 384 Heart rozhodován´ı, zda má pacient srdeˇcn´ı chorobu Dimenze uˇc´ıc´ı mnoˇziny: 35 Poˇcet objekt˚ u v uˇc´ıc´ı mnoˇzinˇe: 460

51

Mushroom rozhodován´ı, zda je daná houba jedlá, toto je jediný problém, kdy uˇc´ıc´ı mnoˇzina nebyla z´ıskaná mˇeˇren´ım hodnot, ale byla vytvoˇrena zadán´ım hodnot z knihy obsahuj´ıc´ı popis r˚ uzných druh˚ u hub Dimenze uˇc´ıc´ı mnoˇziny: 125 Poˇcet objekt˚ u v uˇc´ıc´ı mnoˇzinˇe: 4062

Bal´ık proben1 je volnˇe k dispozici pˇres ftp protokol na adrese ftp.cs.cmu.edu, adresáˇr /afs/cs/project/connect/bench/contrib/prechelt.

6.3

UCI Machine Learning Repository

UCI Machine learning repository je zˇrejmˇe nejrozsáhlejˇs´ı sb´ırka r˚ uzných problém˚ u, dalˇs´ı podobnˇe zamˇeˇrené referenˇcn´ı soubory problém˚ u vˇcetnˇe proben1 a delve obsahuj´ı ˇcást dat právˇe z tohoto zdroje. Tato sb´ırka problém˚ u obsahuje u ´ lohy jak aproximaˇcn´ıho, tak klasifikaˇcn´ıho typu (klasifikace jen do dvou i do v´ıce klasifikaˇcn´ıch tˇr´ıd). Veˇskeré datové soubory vˇcetnˇe dokumentace, lze volnˇe z´ıskat z internetové adresy http://www.ics.uci.edu/∼mlearn/ MLRepository.html.

6.4

Delve

Jedná se o nepˇr´ıliˇs rozsáhlý soubor, jehoˇz ˇcást obsahu se kryje s obsahem UCI Machine learning repository. Jeho positivem je rozdˇelen´ı problém˚ u na dvˇe skupiny, pˇriˇcemˇz jedna skupina by mˇela slouˇzit pro pouˇzit´ı pˇri vylepˇsován´ı metod, pˇriˇcemˇz se pˇredpokládá, ˇze protoˇze se daná metoda vylepˇsovala tak, aby se výsledky zlepˇsovaly na urˇcitých datech, nemˇela by tato data slouˇzit pro srovnán´ı s jinými metodami, druhá skupina slouˇz´ı opravdu k regulérn´ımu srovnáván´ı metod. Datové soubory a dokumetaci týkaj´ıc´ı se Delve lze volnˇe z´ıskat na internetové adrese http://www.cs.toronto.edu/∼delve/.

52

Kapitola 7 Anal´ yza neuronov´ ych s´ıt´ı s pˇ rep´ınac´ımi jednotkami 7.1

´ Uvod a motivace

Pro nauˇcen´ı neuronové s´ıtˇe je tˇreba m´ıt k dispozici uˇc´ıc´ı mnoˇzinu LD (n, m) a nenauˇcenou neuronovou s´ıt’ NN U , aplikován´ım uˇc´ıc´ı metody na dvojici (LD (n, m), NN U ) jsou nastaveny parametry jednotlivých neuron˚ u tvoˇr´ıc´ıch výslednou neuronovou s´ıt’. Nenauˇcená neuronová s´ıt’ obsahuje informaci o topologii a zp˚ usobu uˇcen´ı jednotlivých neuron˚ u. Na volbˇe nenauˇcené neuronové s´ıtˇe silnˇe závis´ı kvalita výsledné neuronové s´ıtˇe pro urˇcitá uˇc´ıc´ı data. Neuˇc´ı se tedy pouze jediná s´ıt’, ale pro nalezen´ı optimáln´ı neuronové s´ıtˇe se jich bˇeˇznˇe uˇc´ı vyˇsˇs´ı poˇcet. Pˇri takovémto zp˚ usobu uˇcen´ı, kdy se zkouˇs´ı r˚ uzné nenauˇcené neuronové s´ıtˇe, by velice pomohl nástroj, který by naznaˇcil, jaké vlastnosti by mˇeli splˇ novat nenauˇcené neuronové s´ıtˇe vhodné k ˇreˇsen´ı daného problému. Takových nástroj˚ u by mohlo být v´ıce, kaˇzdý optimalizuj´ıc´ı vybranou tˇr´ıdu parametr˚ u. Pro optimalizaci topologie a nˇekterých parametr˚ u nenauˇcené neuronové s´ıtˇe lze jiˇz nyn´ı pouˇz´ıt genetického algoritmu viz. [KAL02]. Genetický algoritmus vˇsak neoptimalizuje veˇskeré parametry a jeho ˇcasová nároˇcnost je zpravidla vysoká, proto je málokdy moˇzné vyzkouˇset genetický algoritmus pro r˚ uzná nastaven´ı, která j´ım nejsou optimalizovány. Pomohla by existence postupu, pomoc´ı nˇehoˇz by se v pˇrijatelnˇe krátkém ˇcase dalo odhadnout, které nastaven´ı pouˇz´ıt pro uˇcen´ı. Základn´ı myˇslenka je snaˇzit se vyˇreˇsit jednoduˇsˇs´ı u ´ lohu, to znamená vz´ıt nˇekolik jednoduˇsˇs´ıch s´ıt´ı a ukázat, ˇze pokud urˇcité parametry dávaj´ı na tˇechto jednoduˇsˇs´ıch s´ıt´ıch lepˇs´ı výsledky, budou pˇri pouˇzit´ı tˇechto parametr˚ u dávat lepˇs´ı výsledky i sloˇzitˇejˇs´ı s´ıtˇe.

53

Zp˚ usob pouˇzit´ı by pak vypadal následovnˇe: pˇred spuˇstˇen´ım genetického algoritmu by se nejprve spustila analýza uˇc´ıc´ıch dat, tato analýza by posléze doporuˇcila urˇcité nastaven´ı, které by se pak pouˇzilo pˇri spuˇstˇen´ı hlavn´ıho uˇc´ıc´ıho procesu. Daná analýza by mˇela m´ıt nˇekolik vlastnost´ı: • bˇeh analýzy by mˇel trvat ˇrádovˇe kratˇs´ı dobu, neˇz bˇeh následného uˇcen´ı • poˇcet parametr˚ u této analýzy by mˇel být minimáln´ı (v nejlépˇs´ım pˇr´ıpadˇe by jediným parametrem této analýzy byla pouze uˇc´ıc´ı mnoˇzina) • analýza by mˇela dávat rozumné výsledky pro co nejˇsirˇs´ı tˇr´ıdu uˇc´ıc´ıch mnoˇzin Výsledk˚ u hledán´ı takové analýzy m˚ uˇze být nˇekolik: • najde se postup, jak urˇcit vhodné parametry, které se mohou liˇsit podle typu dat • zjist´ı se, ˇze urˇcité nastaven´ı je nejvhodnˇejˇs´ı ve vˇsech pˇr´ıpadech • nepodaˇr´ı se naj´ıt postup, jak v rozumnˇe krátkém ˇcase odhadnout nejvhodnˇejˇs´ı parametry

7.2

Z´ akladn´ı myˇslenky

Ve snaze naj´ıt takovou analýzu je tˇreba se nejprve zamyslet, jak by mˇela pracovat a hodnoty kterých parametr˚ u by se mˇela snaˇzit odhadnout. Zaˇc´ıt by se mˇelo s nejjednoduˇsˇs´ımi s´ıtˇemi a v závislosti na dosaˇzených výsledc´ıch postupovat systematicky dále. Nejjednoduˇsˇs´ı neuronová s´ıt’ s pˇrep´ınac´ımi jednotkami obsahuje pouze vstupn´ı neuron a jeden neuron s pˇrep´ınac´ı jednotkou, proto byly nejprve vyhodnoceny výsledky pro takovéto triviáln´ı s´ıtˇe.

7.3

Anal´ yza s´ıtˇ e s jedn´ım neuronem

V pˇr´ıpadˇe neuronové s´ıtˇe obsahuj´ıc´ı pouze vstupn´ı neuron a jeden neuron s pˇrep´ınac´ı jednotkou jsou parametry neuronové s´ıtˇe shodné s parametry jediného NSU: • poˇcet výpoˇcetn´ıch neuron˚ u • typ výpoˇcetn´ıch neuron˚ u 54

• zp˚ usob nauˇcen´ı výpoˇcetn´ıch neuron˚ u • zp˚ usob nauˇcen´ı pˇrep´ınac´ı jednotky, jedná se pˇredevˇs´ım o výbˇer metody shlukové analýzy a jej´ıch parametr˚ u Jelikoˇz jediný NSU je zároveˇ n výstupn´ı neuron, mus´ı být výstupn´ı dimenze tohoto neuronu jednorozmˇerná, toto splˇ nuje pouze NSU s výpoˇcetn´ımi neurony typu I, ostatn´ı parametry jsou jiˇz libovolné. Nejv´ıce variabiln´ı je parametr udávaj´ıc´ı poˇcet výpoˇcetn´ıch neuron˚ u. Ostatn´ı parametry mohou nabývat koneˇcný poˇcet hodnot z relativnˇe malého rozmez´ı (pˇresto je vˇsak poˇcet kombinac´ı znaˇcný). Rozhodlo se tedy, ˇze se vˇzdy upevn´ı parametry pˇrep´ınac´ı jednotky ozn. P JP a neuronová s´ıt’ se bude uˇcit pro r˚ uzné hodnoty poˇctu výpoˇcetn´ıch neuron˚ u k. Za dostateˇcný rozsah hodnot poˇctu výpoˇcetn´ıch neuron˚ u byla zvolena mnoˇzina { i | 1 < i ≤ 100 }. Takto definované nenauˇcené neuronové s´ıtˇe byly nauˇceny uˇc´ıc´ı metodou spolu s daty z proben1 popsaného v kapitole 6. Pro kaˇzdou uˇc´ıc´ı mnoˇzinu DL (n, m) a parametry dané hodnotou P JP takto vznikl celý soubor neuronových s´ıt´ı pro r˚ uzné hodnoty poˇctu výpoˇcetn´ıch neuron˚ u. Tyto s´ıtˇe byly srovnány pomoc´ı kritéri´ı z mnoˇziny def

SE = {EM SE , E0 , EHIST (0, 1), EGM (0, 1), ECEGM , ESGM }

(7.1)

to zároveˇ n umoˇznilo i srovnán´ı uvedených kritéri´ı kvality. V potaz se musela vz´ıt jeˇstˇe otázka výpoˇcetn´ı nároˇcnosti. Uˇcen´ı výpoˇcetn´ıch neuron˚ u je v porovnán´ı se shlukovac´ımi algoritmy rychlé, z výsledk˚ u porovnán´ı ˇcasové nároˇcnosti metod shlukové analýzy nav´ıc plyne, ˇze vzhledem k velikostem pouˇzitých uˇc´ıc´ıch mnoˇzin (kromˇe problému oznaˇceného jako mushroom jsou velikosti uˇc´ıc´ıch mnoˇzin < 500 - viz. kapitola 6) jsou pro nauˇcen´ı pˇrep´ınac´ı jednotky pouˇzitelné veˇskeré popsané metody shlukové analýzy. Jelikoˇz pouˇzit´ı celé sady kritéri´ı kvality pro mnoho r˚ uzných pˇr´ıpad˚ u vedlo k vytvoˇren´ı pomˇernˇe vysokého poˇctu hodnot, byly výsledky pro jednotlivé kombinace DL (n, m) a P JP jeˇstˇe dále zpracovány. Za koneˇcné výsledky pro kaˇzdé kritérium urˇcen´ı kvality se povaˇzovaly následuj´ıc´ı statistiky: E stˇredn´ı hodnota med medián min minimáln´ı hodnota max maximáln´ı hodnota 55

NCN poˇcet výpoˇcetn´ıch neuron˚ u, pˇri nichˇz bylo dosaˇzeno minima odpov´ıdaj´ıc´ıho kritéria (pokud bylo minima kritéria nabýváno na v´ıce s´ıt´ıch, výsledkem bylo nejniˇzˇs´ı z nich) Hodnoty r˚ uzných kritéri´ı kvality byly poˇc´ıtány jak pro uˇc´ıc´ı, tak pro testovac´ı mnoˇzinu. Jako testovac´ı mnoˇzina se pouˇz´ıvala mnoˇzina vzor˚ u, která je v souboru proben1 oznaˇcována jako validaˇcn´ı (ke kaˇzdému problému obsahuje proben1 uˇc´ıc´ı mnoˇzinu a dvˇe r˚ uzné mnoˇziny vzor˚ u urˇcené pro vyhodnocen´ı kvality, v´ıce lze naj´ıt v [PRE94]), nav´ıc ke kaˇzdému problému existuj´ı tˇri r˚ uzné uˇc´ıc´ı, tˇri r˚ uzné validaˇcn´ı a tˇri r˚ uzné testovac´ı mnoˇziny. Napˇr´ıklad pro problém heart existuje uˇc´ıc´ı mnoˇzina 1, uˇc´ıc´ı mnoˇzina 2 a uˇc´ıc´ı mnoˇzina 3. To samé plat´ı pro validaˇcn´ı a testovac´ı mnoˇziny. Ve vˇsech pˇr´ıpadech byly pouˇzity mnoˇziny oznaˇcené ˇc´ıslem 1. Pro uˇcen´ı pˇrep´ınac´ı jednotky bylo pouˇzito pouze deterministických metod, to umoˇznilo pozdˇejˇs´ı vyhodnocen´ı dalˇs´ıch kritéri´ı, bez nutnosti pˇrepoˇc´ıtán´ı jiˇz dˇr´ıve z´ıskaných hodnot. Pozn´ amka 7.1 Pro u ´plnost bylo vyzkouˇseno i kritérium souˇctu odchylek v absolutn´ı hodnotˇe n X def ESAE = |f (xi ) − ti | (7.2) i=1

Podle oˇcekáván´ı vˇsak odpov´ıdaly hodnoty tohoto kritéria hodnotám z´ıskaných pomoc´ı kritéria ESSE a upustilo se od napoˇc´ıtáván´ı obou kritéri´ı najednou. ESSE (pˇresnˇeji jeho varianta EM SE ) bylo preferováno, jelikoˇz se pˇri uˇcen´ı výpoˇcetn´ıch neuron˚ u minimalizuje právˇe toto kritérium. Tabulky výsledných hodnot jsou vˇzdy uvedeny dvˇe, jedna s výsledky na uˇc´ıc´ı mnoˇzinˇe a jedna s výsledky na testovac´ı mnoˇzinˇe. Je také nutné si uvˇedomit, ˇze se sice porovnávaj´ı neuronové s´ıtˇe se stejnou topologi´ı, ale tyto s´ıtˇe maj´ı r˚ uznou s´ılu. Se zvyˇsuj´ıc´ım poˇctem výpoˇcetn´ıch neuron˚ u uvnitˇr neuronu s pˇrep´ınac´ı jednotkou roste poˇcet parametr˚ u popisu’ ’ j´ıc´ıch výslednou neuronovou s´ıt . Necht vstupn´ı dimenze neuronou s pˇrep´ınac´ı jednotkou je d, poˇcet parametr˚ u pro kaˇzdý výpoˇcetn´ı neuron je d + 1 (pokud se uvaˇzuj´ı pouze pˇrechodové funkce typu I a II) a dalˇs´ıch d parametr˚ u pˇredstavuje bod ze vstupn´ıho prostoru, pomoc´ı nˇehoˇz jsou vstupy distribuovány mezi jednotlivé výpoˇcetn´ı neurony. Celkový poˇcet parametr˚ u neuronu s pˇrep´ınac´ı jednotkou a k výpoˇcetn´ımi neurony je roven výrazu k(2d + 1). S rostouc´ım poˇctem výpoˇcetn´ıch neuron˚ u by se tedy mˇela sniˇzovat chyba na uˇc´ıc´ı mnoˇzinˇe a r˚ ust chyba na testovac´ı mnoˇzinˇe, jelikoˇz s´ıt’ se bude stávat pˇr´ıliˇs specializovaná na uˇc´ıc´ı mnoˇzinu.

56

E med min max stddev NCN

EM SE 0,259 0,228 0,101 0,639 0,099 35

E0 0,094 0,087 0,038 0,246 0,034 35

Card : Uˇ c´ıc´ı data EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,110 0,112 5,190 1,158 0,107 0,099 5,251 1,133 0,035 0,061 1,438 1,079 0,246 0,380 15,119 1,580 0,035 0,043 2,246 0,075 35 96 2 96

Tabulka 7.1: Pro uˇcen´ı pˇrep´ınac´ı jednotky byla pouˇzita následuj´ıc´ı kombinace: Forgyho metoda, poˇcáteˇcn´ı shluky nalezeny pomoc´ı LA, pˇri shlukován´ı pouˇzita euklidovská vzdálenost.


EM SE 3,713 1,828 0,538 30,317 5,125 3

Card : Testovac´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,210 0,419 0,452 2,149 1,983 0,209 0,430 0,465 2,148 1,957 0,122 0,198 0,209 0,898 1,328 0,279 0,576 0,674 4,515 3,344 0,028 0,099 0,099 0,612 0,355 4 4 4 6 4



EM SE 0,251 0,221 0,126 0,541 0,089 99

E0 0,092 0,081 0,046 0,206 0,031 99


Tabulka 7.3: Pro uˇcen´ı pˇrep´ınac´ı jednotky byla pouˇzita následuj´ıc´ı kombinace: Forgyho metoda, poˇcáteˇcn´ı shluky byly nalezeny pomoc´ı PCA, pˇri shlukován´ı pouˇzita euklidovská vzdálenost.

57


EM SE 3,088 2,031 0,492 17,186 3,049 2


Tabulka 7.4: Pro uˇcen´ı pˇrep´ınac´ı jednotky byla pouˇzita následuj´ıc´ı kombinace: Forgyho metoda, poˇcáteˇcn´ı shluky byly nalezeny pomoc´ı PCA, pˇri shlukován´ı pouˇzita euklidovská vzdálenost.


EM SE 0,260 0,258 0,131 0,982 0,097 93

E0 0,083 0,081 0,041 0,438 0,041 93


Tabulka 7.5: Pro uˇcen´ı pˇrep´ınac´ı jednotky byla pouˇzita následuj´ıc´ı kombinace: metoda nejbliˇzˇs´ıho souseda, pˇri shlukován´ı pouˇzita euklidovská vzdálenost.


EM SE 5,572 4,750 0,386 51,676 8,530 3


Tabulka 7.6: Pro uˇcen´ı pˇrep´ınac´ı jednotky byla pouˇzita následuj´ıc´ı kombinace: metoda nejbliˇzˇs´ıho souseda, pˇri shlukován´ı pouˇzita euklidovská vzdálenost. 58


EM SE 0,217 0,170 0,114 0,770 0,117 72

E0 0,081 0,064 0,043 0,330 0,048 38


Tabulka 7.7: Pro uˇcen´ı pˇrep´ınac´ı jednotky byla pouˇzita následuj´ıc´ı kombinace: metoda nejvzdálenˇejˇs´ıho souseda, pˇri shlukován´ı pouˇzita euklidovská vzdálenost.


EM SE 1,345 1,371 0,488 3,761 0,477 4


Tabulka 7.8: Pro uˇcen´ı pˇrep´ınac´ı jednotky byla pouˇzita následuj´ıc´ı kombinace: metoda nejvzdálenˇejˇs´ıho souseda, pˇri shlukován´ı pouˇzita euklidovská vzdálenost.


EM SE 0,284 0,280 0,205 0,482 0,042 16

Heart : Uˇ c´ıc´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,100 0,109 0,115 109,637 0,147 0,098 0,109 0,115 107,222 0,148 0,052 0,052 0,074 64,765 0,102 0,159 0,163 0,183 206,599 0,233 0,016 0,024 0,016 20,263 0,020 16 16 16 16 16


59


EM SE 2,538 1,670 0,539 21,704 2,910 2

Heart : Testovac´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,244 0,327 0,336 175,741 0,365 0,243 0,322 0,339 174,672 0,363 0,196 0,209 0,230 93,786 0,274 0,309 0,435 0,417 336,682 0,444 0,025 0,048 0,039 35,665 0,037 2 2 2 2 6



EM SE 0,018 0,010 0,000 0,152 0,027 8

Mushroom : Uˇ c´ıc´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,006 0,006 0,265 141,493 0,265 0,001 0,001 0,020 0,000 0,020 0,000 0,000 0,001 0,000 0,001 0,042 0,042 1,000 4041,731 1,000 0,009 0,009 0,404 473,343 0,404 8 8 2 3 2



EM SE 0,018 0,010 0,000 0,140 0,025 8

Mushroom : Testovac´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,006 0,007 0,265 69,005 0,265 0,001 0,003 0,019 0,000 0,019 0,000 0,000 0,000 0,000 0,000 0,038 0,038 1,000 1974,677 1,000 0,008 0,008 0,404 232,949 0,404 8 8 2 3 2


60

7.4

Z´ avˇ ery z anal´ yzy neuronov´ e s´ıtˇ e obsahuj´ıc´ı jeden neuron

Z výsledk˚ u z´ıskaných pro nejjednoduˇsˇs´ı moˇzné s´ıtˇe lze udˇelat nˇekolik závˇer˚ u: • výsledky se pro r˚ uzná nastaven´ı vskutku liˇs´ı a tedy záleˇz´ı na volbˇe nenauˇcené neuronové s´ıtˇe • ukázalo se, ˇze výsledky na uˇc´ıc´ı mnoˇzinˇe se opravdu zlepˇsuj´ı se zvyˇsuj´ıc´ım se poˇctem shluk˚ u, to je vidˇet i na uvedených výsledc´ıch, z kterých je patrné, ˇze nejlepˇs´ım s´ıt´ım odpov´ıdaly vysoké poˇcty výpoˇcetn´ıch neuron˚ u v NSU, vˇzdy vˇsak neplat´ı, ˇze vyˇsˇs´ı poˇcet shluk˚ u znamená lepˇs´ı ohodnocen´ı na uˇc´ıc´ıch datech • nejlepˇs´ı s´ıtˇe vzhledem k testovac´ı mnoˇzinˇe mˇely n´ızké poˇcty výpoˇcetn´ıch neuron˚ u, vˇetˇsinou ménˇe neˇz deset (pr˚ umˇerný poˇcet pro jednotlivé problémy se liˇsil, a to i pro r˚ uzné volby uˇcen´ı pˇrep´ınac´ı jednotky) z tohoto plyne, ˇze poˇcty shluk˚ u se nemus´ı volit nijak vysoké • problém oznaˇcovaný jako mushroom je zˇrejmˇe pˇr´ıliˇs jednoduchý - uˇz jediný neuron dokázal bezchybnˇe klasifikovat vzory z uˇc´ıc´ı i testovac´ı mnoˇziny (viz. tabulky 7.11 a 7.12), z tohoto d˚ uvod˚ u nemˇelo smysl se t´ımto problémem dále zabývat Nyn´ı je k dipozici urˇcitý základn´ı soubor napoˇctených hodnot pro r˚ uzná kritéria a lze pˇrej´ıt ke sloˇzitˇejˇs´ım neuronovým s´ıt´ı.

7.5

Anal´ yza ˇ retˇ ezce

Neuronové s´ıtˇe s pˇrep´ınac´ımi jednotkami se konstruuj´ı v podobˇe blok˚ u, tyto bloky jsou tvoˇreny libovolnˇe dlouhými ˇretˇezci neuron˚ u s pˇrep´ınac´ımi jednotkami, viz. pˇr´ıklad na obrázku 7.1. Obecná neuronová sit’ s pˇrep´ınac´ımi jednotkami obsahuje jako neurony pravˇe celé takové bloky. Nyn´ı lze srovnat oprávnˇenost pouˇzit´ı tˇechto ˇretˇezc˚ u srovnán´ım výsledk˚ u oproti neuronovým s´ıt´ım obsahuj´ıc´ım pouze jeden neuron s pˇrep´ınac´ı jednotkou. Toto srovnán´ı m˚ uˇze prokázat, ˇze pouˇzit´ım ˇretezc˚ u lze z´ıskat kvalitnˇejˇs´ı výsledky. Dalˇs´ımi moˇznými závˇery m˚ uˇze být zjiˇstˇen´ı, ˇze pouˇzit´ı ˇretˇezce vede s vˇetˇs´ı pravdˇepodobnost´ı k lepˇs´ımu výsledku (zde je tˇreba m´ıt na pamˇeti pomˇer poˇctu parametr˚ u jednoho neuronu a ˇretˇezce), také se m˚ uˇze doj´ıt k závˇeru, ˇze ˇretˇezce maj´ı výsledky horˇs´ı.

61

Obrázek 7.1: Pˇr´ıklad neuronové s´ıtˇe s topologi´ı ˇretˇezec obsahuj´ıc´ı tˇri výpoˇcetn´ımi neurony. Pokud je ˇretˇezec pouze blokem v rozsáhlejˇs´ı neuronové s´ıti, neobsahuje vstupn´ı neuron Pˇri pouˇzit´ı topologie ˇretˇezec rázem nar˚ ustá poˇcet kombinac´ı parametr˚ u urˇcuj´ıc´ıch, jakým zp˚ usobem uˇcit neurony tvoˇr´ıc´ı ˇretˇezec. V rámci ˇretˇezc˚ u se bude pouˇz´ıvat tato terminologie: • skryté neurony se budou nazývat NSU, jejichˇz rodiˇc i syn je NSU • prvn´ı neuron, se bude nazývat NSU, jehoˇz syn je NSU, ale jeho rodiˇc nen´ı • posledn´ı neuron se bude nazývat neuron, jehoˇz dˇeti nepocházej´ı z daného ˇretˇezce Pro sn´ıˇzen´ı poˇctu kombinac´ı se parametry pro skryté neurony vol´ı stejné, zláˇst’ se vol´ı parametry prvn´ıho a posledn´ıho neuronu. Pro dalˇs´ı sn´ıˇzen´ı poˇctu kombinac´ı se pro prvn´ı neuron a skryté neurony pouˇz´ıvala pouze pˇrechodová funkce typu I, pro posledn´ı neuron se pouˇz´ıvala pˇrechodová funkce typu II, ostatn´ı parametry posledn´ıho neuronu se od parametr˚ u skrytých neuron˚ u neliˇsily. Kromˇe parametr˚ u neuron˚ u je zde nav´ıc parametr urˇcuj´ıc´ı délku ˇretˇezce. Pro analýzu ˇretˇezc˚ u se pouˇzilo rozˇs´ıˇreného postupu analýzy s´ıtˇe s jedn´ım neuronem. Po nastaven´ı délky ˇretˇezce se jednotlivým nenauˇceným neuron˚ um pˇriˇradily veˇskeré potˇrebné parametry definuj´ıc´ı uˇcen´ı mimo poˇcet výpoˇcetn´ıch neuron˚ u, jedna taková ne´ uplná nenauˇcená neuronová s´ıt’ se bude znaˇcit Cf g a nazývat konfigurace, následnˇe se ˇretˇezec uˇcil pro r˚ uzné kombinace poˇct˚ u výpoˇcetn´ıch neuron˚ u. Poˇcty výpoˇcetn´ıch neuron˚ u byly vyb´ırány systematicky z mnoˇziny {2,. . . ,10}, toto vyplynulo z výsledk˚ u analýzy pro jeden neuron i ze zváˇzen´ı poˇctu kombinac´ı, které je moˇzné vyzkouˇset v rozumném ˇcase. Pro ˇretˇezec délky n a pˇri minimáln´ıch a maximáln´ıch poˇctech shluk˚ u kmin a kmax je totiˇz poˇcet nutných ˇretˇezc˚ u pˇri upevnˇených ostatn´ıch parametrech uˇcen´ı roven výrazu (kmax −kmin + 1)n , coˇz by pˇri vyˇsˇs´ıch hodnotách n kladlo pˇr´ıliˇs vysoké 62

nároky na výpoˇcetn´ı ˇcas. Pro maximáln´ı delku ˇretˇezce byla zvolena hodnota 3. Jednotlivé ˇretˇezce byly uˇceny za pouˇzit´ı stejných uˇc´ıc´ıch mnoˇzin, jako s´ıtˇe s jedn´ım neuronem (vynechán byl jiˇz problém mushroom), pouˇzitá kritéria kvality a vˇetˇsina poˇc´ıtaných statistik byla stejná, lze tedy snadno srovnat výsledky ˇretˇezc˚ u a s´ıt´ı obsahuj´ıc´ıch pouze jeden neuron. Pˇri analýze ˇretˇezc˚ u byly pro hodnoty kaˇzdého kritéria sledovány tyto statistiky: E stˇredn´ı hodnota med medián min minimáln´ı hodnota max maximáln´ı hodnota NCNS poˇcty výpoˇcetn´ıch neuron˚ u pro jednotlivé neurony ˇretˇezce, 2-3 tedy odpov´ıdá ˇrezˇezci, kde prvn´ım neuron je NSU se dvˇema výpoˇcetn´ımi neurony, a posledn´ı neuron je NSU se tˇremi výpoˇcetn´ımi neurony Zpracován´ı neuronových s´ıt´ı obsahuj´ıc´ı pouze jeden NSU bylo jeˇstˇe celkem proveditelné ruˇcnˇe. Pˇri analýze ˇretˇezc˚ u bylo vˇsak tˇreba zpracovat mnohem v´ıce dat. A nav´ıc tyto výsledky srovnat s pˇredchoz´ımi výsledky. Problémem tedy bylo porovnat konfigurace, a to jak mezi sebou pro stejná data, tak globálnˇe pro veˇskerá data. Pokud se ale maj´ı porovnávat nˇejaké objekty, je k tomu tˇreba relace, pomoc´ı které lze urˇcit, který z objekt˚ u je menˇs´ı. Pro srovnán´ı konfigurac´ı bylo vyuˇzito napoˇctených hodnot kritéri´ı kvality. Protoˇze pro kaˇzdou konfiguraci bylo nauˇceno mnoho s´ıt´ı s r˚ uznými kombinacemi poˇct˚ u výpoˇcetn´ıch neuron˚ u, nepouˇz´ıvali se pˇr´ımo napoˇc´ıtané hodnoty, ale vybrané sledované statistiky. Definice 7.1 Necht’ • Cf g1 a Cf g2 jsou r˚ uzné konfigurace • f1 , f2 ∈ Rn (i)

(i)

(i)

(i)

• n1 = |{i ∈ n ˆ |f1 < f2 }| • n2 = |{i ∈ n ˆ |f1 > f2 }| def

RCf g (C1 , C2 ) ⇔ n1 > n2 pokud plat´ı RCf g (C1 , C2 ), bude se ˇr´ıkat, ˇze C1 je menˇs´ı neˇz C2 . 63

(7.3)

E med min max stddev NCNS

EM SE 0,384 0,333 0,222 0,982 0,161 10-6

E0 0,139 0,119 0,067 0,438 0,077 4-10

Card : Uˇ c´ıc´ı data EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,136 0,161 113,245 0,187 0,119 0,125 99,191 0,157 0,061 0,084 0,000 0,101 0,438 0,771 282,751 0,771 0,079 0,126 58,282 0,116 4-10 4-10 2-2 10-10

Tabulka 7.13: Výsledky pro ˇretˇezec délky 2, nastaven´ı: 1. neuron: pˇrep´ınac´ı jednotka uˇcena metodou nejbliˇzˇs´ıho souseda, pouˇzita euklidovská vzdálenost, 2. neuron: pˇrep´ınac´ı jednotka uˇcena metodou nejbliˇzˇs´ıho souseda, vzdálenost urˇcována pomoc´ı dsum Pro srovnán´ı dvou konfigurac´ı lze pouˇz´ıt relaci 7.3, ta vyuˇz´ıvá ke srovnán´ı dvou konfigurac´ı vektor˚ u z Rn , pˇriˇcemˇz je tˇreba doplnit, co se skrývá za vektory f1 a f2 . Pro konfiguraci Cf g byly nakonec jako hodnoty vektoru f pouˇzity hodnoty minim a medián˚ u pro veˇskerá pouˇzité kritéria kvality. Jedna konfigurace je podle relace 7.3 menˇs´ı neˇz druhá pokud má na v´ıce m´ıstech niˇzˇs´ı hodnoty uvedených statistik. Dalˇs´ı zpracován´ı pak prob´ıhalo tak, ˇze se tˇr´ıdila kritéria pomoc´ı relace 7.3 a sledovalo se, které konfigurace vedou ˇcastˇeji k lepˇs´ım výsledk˚ u, neboli, které konfigurace jsou ˇcasto malé v porovnán´ı s jinými. V tˇechto srovnán´ıch v´ıtˇezila nejˇcestˇeji metody nejvzdálenˇejˇs´ıho souseda a metoda pr˚ umˇerné nepodobnosti, za nimi následovali varianty Forgyho metody. Výsledky hierarchické metody nejbliˇzˇs´ıho souseda nedosahovala tak dobrých výsledk˚ u, jako ostatn´ı hierarchické metody. V tabulkách 7.13 - 7.18 jsou uvedeny nejlepˇs´ı výsledky pro jednotlivé délky ˇretˇezc˚ u dva a tˇri spoˇctené pro problém card. Nyn´ı zbývalo ovˇeˇrit, zda pˇri pouˇzit´ı konfigurace, dávaj´ıc´ı lepˇs´ı výsledky na ˇretˇezc´ıch, se dostanou lepˇs´ı výsledky na obecných s´ıt´ıch. Toto jiˇz bylo zkouˇseno jen pro kritérium kvality E0 , vzhledem k výsledk˚ um sekce 7.6, to nijak neub´ırá na vypov´ıdaj´ıc´ı hodnotˇe. Toto se zjiˇst’ovalo takto: 1. vybrala se konfigurace vedouc´ı k lepˇs´ım výsledk˚ um pro ˇretˇezce 2. vygenerovalo a nauˇcilo se za pouˇzit´ı této konfigurace 1000 s´ıt´ı 3. vybrala se konfigurace vedouc´ı k horˇs´ım výsledk˚ um pro ˇretˇezce 4. vygenerovalo a nauˇcilo se za pouˇzit´ı této horˇs´ı konfigurace 1000 s´ıt´ı 64


EM SE 225,474 2,386 0,343 661,604 271,898 2-4

Card : Testovac´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,158 0,200 0,224 80,044 0,249 0,128 0,192 0,192 78,456 0,221 0,099 0,122 0,122 0,000 0,148 0,436 0,436 0,715 206,031 0,715 0,072 0,066 0,111 36,727 0,100 6-2 2-2 3-4 2-2 3-9

Tabulka 7.14: Výsledky pro ˇretˇezec délky 2, nastaven´ı: 1. neuron: pˇrep´ınac´ı jednotka uˇcena metodou nejbliˇzˇs´ıho souseda, pouˇzita euklidovská vzdálenost, 2. neuron: pˇrep´ınac´ı jednotka uˇcena metodou nejbliˇzˇs´ıho souseda, vzdálenost urˇcována pomoc´ı dsum


EM SE 0,352 0,337 0,208 0,984 0,088 6-10-10

Card : Uˇ c´ıc´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,112 0,115 0,133 106,965 0,170 0,104 0,107 0,122 93,901 0,161 0,055 0,055 0,067 0,000 0,093 0,441 0,441 0,464 412,847 0,492 0,043 0,044 0,050 40,942 0,046 6-10-10 6-10-10 6-10-10 4-8-2 6-10-10

Tabulka 7.15: Výsledky pro nejlepˇs´ı ˇretˇezec délky 3, nastaven´ı: 1. neuron: pˇrep´ınac´ı jednotka uˇcena metodou pr˚ umˇerné nepodobnosti, pouˇzita euklidovská vzdálenost, dalˇs´ı neurony: pˇrep´ınac´ı jednotka uˇcena metodou pr˚ umˇerné nepodobnosti, pouˇzita euklidovská vzdálenost


EM SE 1,496 0,575 0,395 591,127 21,884 3-9-6

Card : Testovac´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,154 0,199 0,231 88,982 0,266 0,145 0,192 0,221 78,139 0,261 0,105 0,128 0,134 0,000 0,169 0,436 0,448 0,535 294,510 0,491 0,043 0,047 0,052 32,475 0,044 7-3-6 2-7-4 2-10-8 4-8-2 2-5-9

Tabulka 7.16: Výsledky pro nejlepˇs´ı ˇretˇezec délky 3, nastaven´ı: 1. neuron: pˇrep´ınac´ı jednotka uˇcena metodou pr˚ umˇerné nepodobnosti, pouˇzita euklidovská vzdálenost, 2. neuron: pˇrep´ınac´ı jednotka uˇcena metodou pr˚ umˇerné nepodobnosti, pouˇzita euklidovská vzdálenost 65


EM SE 0,402 0,381 0,171 0,972 0,134 4-6-8

E0 0,139 0,125 0,041 0,426 0,063 4-6-5

Card : Uˇ c´ıc´ı data EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,140 0,171 157,185 0,198 0,128 0,157 135,366 0,185 0,029 0,049 41,122 0,066 0,435 0,629 3091,953 0,567 0,064 0,080 163,629 0,076 4-6-8 4-5-10 3-9-9 4-6-8

Tabulka 7.17: Výsledky pro nejhorˇs´ı ˇretˇezec délky 3, nastaven´ı: 1. neuron: pˇrep´ınac´ı jednotka uˇcena metodou Forgy LA, pouˇzita euklidovská vzdálenost, dalˇs´ı neurony: pˇrep´ınac´ı jednotka uˇcena metodou Forgy PCA, pouˇzita euklidovská vzdálenost


EM SE 33,950 0,859 0,430 5943,301 389,540 4-9-4

Card : Testovac´ı data E0 EHIST (0, 1) EGM (0, 1) ECEGM ESGM 0,204 0,296 0,334 131,539 0,359 0,186 0,291 0,320 113,243 0,353 0,116 0,134 0,163 49,520 0,189 0,448 0,663 0,669 1828,447 0,574 0,057 0,066 0,076 92,856 0,067 3-4-2 4-4-7 4-5-9 7-3-9 7-8-6

Tabulka 7.18: Výsledky pro nejhorˇs´ı ˇretˇezec délky 3, nastaven´ı: 1. neuron: pˇrep´ınac´ı jednotka uˇcena metodou Forgy LA, pouˇzita euklidovská vzdálenost, 2. neuron: pˇrep´ınac´ı jednotka uˇcena metodou Forgy PCA, pouˇzita euklidovská vzdálenost

66

veliˇcina E med min max stddev

lepˇs´ı konfigurace 0,140 0,134 0,093 0,448 0,035

horˇs´ı konfigurace 0,184 0,169 0,116 0,471 0,053

Tabulka 7.19: Srovnán´ı hodnot výhodnocených z výsledk˚ u náhodných s´ıt´ı, pouˇzito kritérium kvality E0 na testovac´ıch datech 5. výsledky se porovnaly V tabulce 7.19 jsou uvedeny výsledky pro problém card, porovnán´ı takto dosaˇzený výsledk˚ u odpov´ıdalo výsledk˚ um na ˇretˇezc´ıch. Bohuˇzel experiment˚ u tohoto typu nebylo provedeno dostateˇcné mnoˇzstv´ı na to, aby se dalo s vˇetˇs´ı zodpovˇednost´ı prohlásit, ˇze tento postup povede pro ˇsirokou tˇr´ıdu dat k výsledk˚ um, které zlepˇs´ı uˇcic´ı proces. Z experiment˚ u ale vycház´ı, ˇze výsledky by mohli být slibné. Dále lze ˇr´ıci: • ˇretˇezce vˇetˇsinou dosahovali na testovac´ı mnoˇzinˇe lepˇs´ıch výsledk˚ u, neˇz s´ıtˇe s jedn´ım neuronem, toto platilo jak pro minimáln´ı hodnoty kritéri´ı, tak pro stˇredn´ı hodnotu a medián • z výsledk˚ u vycházelo, ˇze pouˇzit´ı hierarchický metod, hlavnˇe metody pr˚ umˇerné nepodobnosti, vede k lepˇs´ım výsledk˚ um

7.6

Srovn´ an´ı krit´ eri´ı kvality

Bˇehem analýzy ˇretˇezc˚ u bylo zároveˇ n provedeno srovnán´ı kritéri´ı kvality, v takovémto srovnán´ı nemá smysl nˇejaké tˇr´ıdˇen´ı a urˇcován´ı nejlepˇs´ıho kritéria, jelikoˇz nelze ˇr´ıci, které kritérium je lepˇs´ı neˇz jiné, to je dáno konkrétn´ı ´ celem bylo sp´ıˇse zjistit, jak si navzájem hodnoty tˇechto kritéri´ı aplikac´ı. Uˇ odpov´ıdaj´ı a jetli nˇekterá z nich nejsou zbyteˇcná. Jinými slovy je c´ılem zjistit, která kritéria jsou nejpodobnˇejˇs´ı/nejvzdálenˇejˇs´ı, nebo rovnou z´ıskat nˇejakou hierarchii, která by je zaˇradila do skupin ˇci systému. Jedná se vlastnˇe o mˇeˇren´ı vzdálenost´ı funkc´ı, pˇriˇcemˇz jsou k dispozici pouze funkˇcn´ı hodnoty v urˇcitých bodech (nauˇcených neuronových s´ıt´ıch). Pro mˇeˇren´ı vzdálenosti mezi kritérii bylo pouˇzito koeficientu korelace spoˇcteného z hodnot kritéri´ı pro nauˇcené neuronové s´ıtˇe. Dále se na výsledky 67

napoˇctených vzdálenost´ı aplikovala hierarchická metoda nejbliˇzˇs´ıho souseda. Pro potˇreby shlukovac´ı metody nebyl pouˇzit pˇr´ımo koeficinet korelace, ale výraz ??, který nabývá hodnot mezi nulou a jedniˇckou, pˇriˇcemˇz n´ızké hodnoty znaˇc´ı vˇetˇs´ı podobnost mezi kritérii. Vzdálenost dvou kritéri´ı byla poˇc´ıtána takto: Definice 7.2 Necht’ E1 a E2 jsou krititéria kvality def

dr (E1 , E2 ) =

1−R 2

(7.4)

kde R je koeficient korelace odpov´ıdaj´ıc´ı hodnotám kritéri´ı kvality. Tedy pokud by dvˇe kritéria dávala totoˇzný výsledek, bylo by toto kritérium rovno nule, v pˇr´ıpadˇe r˚ ustu jednoho a klesán´ı druhého kritéria by se jeho hodnota bl´ıˇzila jedné. Takto lze dokonce mˇeˇrit vzdálenost toho samého kritéria samo od sebe v pˇripadˇe, ˇze bylo aplikováno na uˇc´ıc´ı a testovac´ı mnoˇzinu. Kdyˇz jsou k dispozici hodnoty vzdálenost´ı, lze je pouˇz´ıt k srovnán´ı kritéri´ı. Pro takovéto u ´ˇcely lze s výhodou vyuˇz´ıt hierarchické metody shlukován´ı. Tyto metody (popsány v kapitole A) vrac´ı celou hierarchii shlukovaných vzor˚ u. Kritérium je ted’ vlastnˇe vzor. takovouto hierarchii lze pak zobrazit pomoc´ı stromu, který se nazývá dendrogram. Na obrázku 7.2 je zobrazen dendrogram pro kritéria kvality, koeficient korelace byl poˇc´ıtán pro hodnoty odpov´ıdaj´ıc´ı ˇretˇezc˚ um délky 3, byly pouˇzity ˇ ıslice na ose x urˇcuj´ı kód kritéria viz. výsledky pro veˇskeré data najednou. C´ (tabulka 7.20), hodnoty na ose y odpov´ıdaj´ı u ´ rovn´ım mezishlukové vzdálenosti, na kterých doˇslo ke slouˇcen´ı shluk˚ u, pouˇzita byla metoda nejbliˇzˇs´ıho souseda. Obdobnˇe jako na obázku 7.2 dopadly i dendrogramy pro kritéria na jednotlivé data zvláˇst’. Z uvedeného dendrogramu je patrné, ˇze v´ıce neˇz na typu kritéria záleˇz´ı na tom, zda bylo vyhodnoceno na uˇc´ıc´ı nebo testovac´ı mnoˇzinˇe. Výj´ımkou je pouze kritérium ECEGM , u nˇehoˇz byla vzdálenost hodnot pˇr´ısluˇsná uˇc´ıc´ım a testovac´ım mnoˇzinám bliˇzˇs´ı neˇz k ostatn´ım kritéri´ım, nicmenˇe ostatn´ı kritéria (kromˇe EM SE mˇeli vzdálenost mezi hodnotami na uˇc´ıc´ı a testovac´ı mnoˇzinˇe výraznˇe niˇzˇs´ı), nejv´ıce se výsledek na uˇc´ıc´ı a testovac´ı mnoˇzinˇe liˇsil pro kritérium EM SE , to je dáno t´ım, ˇze toto kritérium na rozd´ıl od kritéri´ı, které vyhodnocuj´ı pomˇer ˇspatnˇe zaˇrazených vzor˚ u ku vˇsem, je poˇc´ıtáno pˇr´ımo z výstup˚ u neuronové s´ıtˇe a je ovlivnˇeno hodnotami, které padnou daleko od oˇcekávaných hodnot {−1; +1}. Závˇer je tedy ten, ˇze pro urˇcen´ı kvality neuronové s´ıtˇe se zdá být nejlepˇs´ı kritérium E0 , které je nejrychlejˇs´ı a nejjednoduˇsˇs´ı. Z tohoto pohledu se zdá, ˇze pouˇzit´ı vˇetˇsiny kritéri´ı bylo zbyteˇcné. Otázka proˇc se hodnoty pro ECEGM odliˇsovali od ostatn´ıch vyˇzaduje dalˇs´ı, podrobnˇejˇs´ı analýzu, která zat´ım nebyla provedena. 68

0.3 0.2

10

9

6

4

12

8

5

3

1

11

7

2

0.0

0.1

Úroveň, na které byla kritéria sloučena

0.4

0.5

Dendrogram kritérií kvality

Číselné kódy pro jednotlivá kritéria

Obrázek 7.2: Dendrogram pro kritéria kvality pˇri urˇcen´ı vzdálenosti pomoc´ı koeficientu korelace. Pro vyhodnocen´ı pouˇzity hodnoty kritéri´ı z´ıskaných pro ˇretˇezce délky 3, na datech k problém˚ um heart, card, cancer a diabetes. Liché ˇc´ıslice odpov´ıdaj´ı kritéri´ım spoˇctených na uˇc´ıc´ıch datech, sudé ˇc´ıslice odpov´ıdaj´ı kritéri´ım spoˇctených na testovac´ıch datech. ˇ ıslice v dendrogramu C´ 1 2 3 4 5 6 7 8 9 10 11 12

odpov´ıdaj´ıc´ı kritérium kvality EM SE pro uˇc´ıc´ı data EM SE pro testovac´ı data E0 pro uˇc´ıc´ı data E0 pro testovac´ı data EHIST (0, 1) pro uˇc´ıc´ı data EHIST (0, 1) pro testovac´ı data EGM (0, 1) pro uˇc´ıc´ı data EGM (0, 1) pro testovac´ı data ECEGM pro uˇc´ıc´ı data ECEGM pro testovac´ı data ESGM pro uˇc´ıc´ı data ESGM pro testovac´ı data

Tabulka 7.20: Význam ˇc´ıslic v dendrogramu. 69

Kapitola 8 Z´ avˇ er V pr˚ ubˇehu práce bylo zpracováno veliké mnoˇzstv´ı informac´ı týkaj´ıc´ı se neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami a upravena terminologie tˇechto neuronových s´ıt´ı. Byly zmapovány nˇekteré vlastnosti pouˇzitých shlukovac´ıch metod a jejich dopad na proces uˇcen´ı, nav´ıc byly implementovány dvˇe metody umoˇzn ˇ uj´ıc´ı deterministické vyuˇzit´ı Forgyho shlukovac´ı metody. Byl navrˇzen a vyzkouˇsen zp˚ usob, jak interpretovat výstupy neuronové s´ıtˇe. Interpretace výstup˚ u neuronové s´ıtˇe byla posléze vyuˇzita pro definován´ı rozhodovac´ıch pravidel pˇri klasifikaci a pˇri urˇcován´ı kvality nauˇcených neuronových s´ıt´ı. Pˇri srovnán´ı kritéri´ı kvality se vˇsak ukázalo, ˇze tento pˇr´ıstup nebyl alespoˇ n v rámci provedených experiment˚ u pˇr´ınosný. Bˇehem experiment˚ u bylo nauˇceno mnoho neuronových s´ıt´ı pˇri pouˇzit´ı datových soubor˚ u z proben1. Tyto výsledky mohou slouˇzit jako referenˇcn´ı hodnoty pˇri dalˇs´ım vývoji neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami. Výsledky nezahrnuj´ı pouze ˇc´ıselné hodnoty, ale i pomocné programy v programovac´ıch jazyc´ıch c++ a R, které lze pˇr´ıpadnˇe pozmˇenˇené pouˇz´ıt. Na nˇekolika problémech byly srovnány výsledky neuronových s´ıt´ı nad topologi´ı ˇretˇezec. Zároveˇ n byly srovnány i kritéria urˇcován´ı kvality. Ukázalo se, ˇze neuronové s´ıtˇe dosahuj´ı lepˇs´ıch výsledk˚ u pˇri pouˇzit´ı hierarchických metod a to konkrétnˇe metody nejvzdálenˇejˇs´ıho souseda a metody pr˚ umˇerné nepodobnosti, je nepˇr´ıjemné, ˇze tyto hierarchické metody jsou nároˇcnˇejˇs´ı na výpoˇcetn´ı ˇcas, neˇz metody iteraˇcn´ı. Byl navrˇzen a implementován systém snaˇz´ıc´ı se doporuˇcit vhodné parametry uˇcen´ı pro ˇreˇsenou u ´ lohu.

70

Dodatek A Metody shlukov´ e anal´ yzy A.1

´ Uvod

Pod pojmem shluková analýza se rozum´ı soubor statistických metod, které ´ redn´ım pojmem shlukové analýzy pomáhaj´ı pˇri analýze struktury dat. Ustˇ je pojem shluk, tento pojem nelze pˇresnˇe definovat a záleˇz´ı na konkrétn´ım problému. Intuitivnˇe jsou shluky tvoˇreny objekty (coˇz mohou být napˇr. n-tice reálných ˇc´ısel), které jsou si navzájem podobné, pˇriˇcemˇz objekty z r˚ uzných shluk˚ u jsou si navzájem podobné co nejménˇe. C´ılem metody shlukové analýzy je tedy naj´ıt shluky v neznámých datech. Z výsledk˚ u shlukován´ı lze pak vycházet pˇri zkoumán´ı struktury dat, vyuˇz´ıvat je pro klasifikaci a k mnoha dalˇs´ım aplikac´ım. Metody shlukové analýzy se dˇel´ı na dvˇe skupiny. Iteraˇcn´ı Metody vyˇzaduj´ı na poˇcátku jiˇz objekty rozdˇelené do k shluk˚ u a následnˇe berou postupnˇe jednotlivé objekty a pˇresouvaj´ı je mezi shluky tak, aby pˇr´ısluˇsnosti objekt˚ u do shluk˚ u co nejlépe splˇ novaly urˇcité kritérium. Toto se dˇeje dokud se napˇr´ıklad jiˇz nemˇen´ı pˇr´ısluˇsnoti objekt˚ u do jednotlivých shluk˚ u, nebo pokud jiˇz byl vykonán urˇcitý poˇcet iterac´ı. Hierarchické metody naopak nevyˇzaduj´ı poˇcáteˇcn´ı zaˇrazen´ı objekt˚ u do tˇr´ıd. Pracuj´ı s pojmem podobnosti/odliˇsnosti celých shluk˚ u a v kaˇzdém kroku jsou slouˇceny dva nejpodobnˇejˇs´ı shluky. Existuj´ı i hierarchické metody, které v kaˇzdém kroku vyberou podle urˇcitého kritéria shluk, který pak rozdˇel´ı na dva nové. Metody tohoto typu skonˇc´ı, aˇz kdyˇz je v kaˇzdém shluku právˇe jeden objekt. Pˇri popisu pouˇzitých metod bude pouˇzito následuj´ıc´ı pojmy. Definice A.1 Necht’ X ⊆ T je mnoˇzina vzor˚ u. Rozkladem mnoˇziny X do k shluk˚ u se rozum´ı mnoˇzina A = {S1 , . . . , Sk }, Si ⊆ X s vlastnostmi: ˆ i 6= ∅); 1. (∀i ∈ k)(S 71

ˆ i 6= j)(Si ∩ Sj = ∅) 2. (∀i, j ∈ k, 3.

k S

Si = X

i=1

Definice A.2 Tˇeˇziˇstˇem shluku Si ∈ A se rozum´ı výraz T (Si ) =

A.2

1 |Si |

P

x

x∈Si

Iteraˇ cn´ı metody

Jako implementace pˇrep´ınac´ı jednotky byly z iteraˇcn´ıch metod pouˇzita Forgyho metoda, jedná se o jednu z variant metody bˇeˇznˇe oznaˇcované jako kmeans. Jiˇz dˇr´ıve byla vyzkouˇsena MacQeenova varianta, ta je ale závislá na poˇrad´ı vzor˚ u, v jakém se pouˇz´ıvaj´ı pˇri shlukovan´ı, proto byla preferována Forgyho varianta.

A.2.1

Forgyho metoda

Necht’ X je mnoˇzina vˇsech vzor˚ u, A = {S1 , . . . , Sk } je libovolný rozklad X a P = {p1 , . . . , pk } je mnoˇzina vzorových bod˚ u (pomoc´ı tˇechto bod˚ u - tˇeˇziˇst’ shluk˚ u, jsou zaˇrazovány objekty do shluk˚ u). 1. ∀i ∈ kˆ : pi = T (Si). 2. ∀x ∈ X proved’: (necht’ x ∈ Si ) I Urˇc´ı se Sj : d(pj , x) = min{d(p, x)|p ∈ P }

II Pokud Si 6= Sj pˇresune se x z Si do Sj

III konec cyklu pro dané x 3. pj = T (Sj ) ∀j ∈ kˆ

4. Pokud v bodˇe 2 doˇslo k pˇresunut´ı nˇejakého vzoru mezi shluky, jde se na bod 2, jinak konec. Sloˇ zitost iteraˇ cn´ıch metod Necht’ poˇcet vˇsech je objekt˚ u je n, necht’ k je poˇcet hledaných shluk˚ u. Sloˇzitost tˇechto metod lze z´ıskat následuj´ıc´ı u ´ vahou: Pro urˇcen´ı pˇr´ısluˇsnosti jednoho vzoru je tˇreba pro kaˇzdý shluk vyhodnotit kritérium vhodnosti pˇresunu objektu, to pˇredstavuje k operac´ı závisej´ıc´ıch na dimenzi prostoru (oznaˇcme ho d). Toto je v jedné iteraci nutné provést pro kaˇzdý vzor. Necht’ h je celkový 72

poˇcet iterac´ı metody nutný pro nalezen´ı stabiln´ıho rozkladu (za pˇredpokladu, ˇze takový rozklad bude nalezen). Koneˇcná sloˇzitost je dána výrazem kdhn. Poˇcet iterac´ı h samozˇrejmˇe závis´ı na datech, ale v praxi se ukazuje, ˇze jeho vliv na celkovou sloˇzitost nen´ı pˇr´ıliˇs velký.

A.2.2

Nalezen´ı poˇ c´ ateˇ cn´ıho rozkladu

Popis metody k − means zaˇc´ıná t´ım, ˇze je jiˇz k dispozici poˇcáteˇcn´ı rozklad a v dalˇs´ıch iterac´ıch se tento poˇcáteˇcn´ı rozklad upravuje tak, aby se zlepˇsovala hodnota minimalizovaného kritéria (souˇctu kvadrát˚ u odchylek bod˚ u od odpov´ıdaj´ıc´ıch tˇeˇziˇst’ shluk˚ u). Z praktických experiment˚ u se ukazuje, ˇze poˇcáteˇcn´ı rozklad má na koneˇcný výsledek metody velký vliv. Na obrázc´ıch A.1 a A.2 jsou ilustrovnány výsledky pˇri zjiˇst’ován´ı citlivosti výsledku shlukován´ı na náhodném poˇcáteˇcn´ım rozkladu. Zopakován´ı experiment˚ u, které by závisely na výsledc´ıch shlukován´ı s poˇcáteˇcn´ım rozkladem urˇceným náhodnˇe, by tedy bylo velice obt´ıˇzné. Bylo proto ˇzádouc´ı poˇcáteˇcn´ı rozklad urˇcovat deterministicky. Prvn´ı a nejjednoduˇsˇs´ı moˇznost je pouˇz´ıt prvn´ıch k vzor˚ u v datech jako centra shluk˚ u a dalˇs´ı vzory postupnˇe pˇriˇradit k nejbliˇzˇs´ımu shluku. Tento postup je zˇrejmˇe rychlý, nicménˇe výsledek shlukován´ı by závisel na poˇrád´ı vstupn´ıch dat a proto byl zavrhnut. Dalˇs´ı moˇznost je pouˇzit´ı hierarchických metod, které nezávis´ı na náhodˇe. Problém v tomto pˇr´ıstupu spoˇc´ıvá ve výpoˇcetn´ı nároˇcnosti bˇeˇzných hierarchických metod viz. srovnán´ı ˇcas˚ u nutných pro proveden´ı shlukován´ı pro r˚ uzné metody shlukován´ı. Pro poˇcáteˇcn´ı rozklad je vˇsak moˇzné pouˇz´ıt hierarchickou metodu zvanou PCA Part, tato hierarchická metoda byla pˇr´ımo vyvinuta pro hledán´ı rozkladu, který má slouˇzit jako výchoz´ıho ˇreˇsen´ı pro iteraˇcn´ı metody, detailnˇejˇs´ı popis a motivaci této metody lze naj´ıt v [TD04].

A.2.3

Deterministick´ e metody pro nalezen´ı poˇ c´ ateˇ cn´ıho rozkladu

PCA Part PCA Part je hierarchický algoritmus, který je v porovnán´ı s klasickými hierarchickými ménˇe výpoˇcetnˇe nároˇcný za cenu z´ıskán´ı horˇs´ıho rozkladu. Na rozd´ıl od klasických metod, jako je napˇr. metoda nejbliˇzˇs´ıho souseda, se záˇc´ıná rozkladem tvoˇreným pouze jedn´ım shlukem obsahuj´ıc´ım veˇskeré objekty a konˇc´ı se po dosaˇzen´ı pˇredem daného poˇctu shluk˚ u. Struˇcnˇe lze tuto metodu popsat následovnˇe: 1. na poˇcátku rozklad obsahuje pouze jeden shluk se vˇsemi vzory 73

800 600 400

Frekvence

200 0

850

900

950

1000

1050

SSE

Obrázek A.1: Histogram veliˇciny SSE z´ıskaný Forgyho metodou pro 10000 opakovnán´ı pˇri náhodném poˇcáteˇcn´ım rozkladu, pouˇzita data heart1-lrn, data neobsahovaly informace o poˇzadovaných výstupech. 2. vybere se jeden ze shluk˚ u v rozkladu 3. vybraný shluk se rozdˇel´ı podle urˇcitého pravidla na dva 4. pokud je rozklad tvoˇren ménˇe shluky, neˇz je poˇzadováno, jde se zpˇet na bod 2 5. vrát´ı se výsledný rozklad Definice A.3 Necht’ X ⊆ Rn , |X| < +∞, X def SSE(X) = (x − T (X))2

(A.1)

x∈X

Pozn´ amka A.1 Výraz SSE(X) pˇredstavuje kritérium, které se snaˇz´ı minimalizovat nˇekteré iteraˇcn´ı metody vˇcetnˇe Forgyho varianty k-means. Definice A.4 Necht’ X ⊆ Rn , |X| < +∞, X def ssei (X) = (x(i) − T (X)(i) )2 x∈X

74

(A.2)

1200 1000 800 600

Frekvence

400 200 0

700

750

800

850

SSE

Obrázek A.2: Histogram pro SSE z´ıskaný Forgyho metodou pro 10000 opakovnán´ı pˇri náhodném poˇcáteˇcn´ım rozkladu, pouˇzita data card1-lrn, data neobsahovaly informace o poˇzadovaných výstupech. Pozn´ amka A.2 Výraz ssei je obdoba SSE, berou se ale v u ´vahu pouze i-té sloˇzky vzor˚ u. Definice A.5 Necht’ • X ⊆ Rn , |X| < +∞ (mnoˇzina shlukovaných vzor˚ u) • k ∈ N (výsledný poˇcet shluk˚ u v rozkladu) • |X| ≥ k • FT : 2X 7→ Rn,n • A1 , . . . , Ak jsou rozklady X pro které plat´ı pro A1

A1 = {A11 }, kde A11 = X

pro Ai , i > 1

75

(A.3)

|Ai | = i 1 {Ai , . . . , Aii }

(A.4) (A.5)

j0 = min{j|SSE(Aji ) = SSEmin } (∀j ∈ i[ − 1, i 6= j0 )(Aji = Aji−1 )

(A.7)

Ai =

ozn. SSEmin = {SSE(Aji−1 )|j ∈ i[ − 1}

(A.6) (A.8)

pro Aji 0 a Aii plat´ı 0 Yi ∈ Rn,n , Yi = FT (Aji−1 )

Zi = {Yix|x ∈

0 Aji−1 }

0 ssemin = min{sseu (Aji−1 )|u ∈ n ˆ} j0 u0 = min{u|sseu (Ai−1 ) = ssemin } 0 ri = T (Aji−1 )(u0 ) 0 Aji 0 = {x ∈ Aji−1 |x(u0 ) ≤ ri } 0 Aii = {x ∈ Aji−1 |x(u0 ) > ri }

(A.9) (A.10) (A.11) (A.12) (A.13) (A.14) (A.15)

Rozklad Ak se bude nazývat Rozklad mnoˇziny X do k shluk˚ u zkonstruok vaný metodou DH za pouˇzit´ı funkce FT a znaˇcit DHFT (X) Definice A.6 Rozklad A mnoˇziny X ⊆ Rn z´ıskaný metodou PCA Part se bude nazývat rozklad z´ıskaný metodou DHTk (X), kde funkce T : 2X 7→ Rn,n pˇriˇrazuje mnoˇzinˇe vzor˚ u transformaˇcn´ı matici z´ıskanou z metody hlavn´ıch komponent popsané v kapitole B. Definice A.7 Rozklad A mnoˇziny X ⊆ Rn z´ıskaný metodou LA se bude nazývat rozklad z´ıskaný metodou DHTk (X), kde funkce T : 2X 7→ Rn,n je definována následovnˇe def

T (X) = diag(1, . . . , 1)

(A.16)

Pozn´ amka A.3 Shlukovac´ı metody definované pomoc´ı definic A.6 a A.7 se liˇs´ı pouze zp˚ usobem, jakým se z´ıská transformaˇcn´ı matice, pomoc´ı které se pˇri pˇrechodech mezi jednotlivými následuj´ıc´ımi rozklady rozdˇeluje vybraný shluk na dva nové. 76

A.3

Hierarchick´ e metody

Z hierarchických metod shlukován´ı bylo pouˇzito nˇekolik aglomerativn´ıch metod, které jsou zaloˇzeny na následuj´ıc´ım algoritmu Necht’ X je mnoˇzina vzor˚ u, n = |X|. 1. Utvoˇr´ı se rozklad Ai=1 (i je index rozkladu) obsahuj´ıc´ı n shluk˚ u. Tzn. v kaˇzdém shluku je právˇe jeden vzor. 2. V rozkladu Ai se vyberou dva nejménˇe vzdálené shluky a ty se slouˇc´ı v jeden nový shluk. T´ım vznikne nový rozklad Ai+1 . 3. Pokud rozklad Ai+1 obsahuje v´ıce neˇz jeden shluk, i = i + 1, jde se zpˇet na bod 2. Výsledkem je posloupnost rozklad˚ u A1 , . . . , An−1 , která urˇcuje hierarchickou strukturu vzor˚ u podle podobnosti. Jednotlivé metody se liˇs´ı pouze zp˚ usobem, jakým se urˇcuje vzdálenost D(T, U) mezi shluky T, U ∈ Ak . Tato vzdálenost by mˇela splˇ novat následuj´ıc´ı podm´ınky (D1) D(T, T ) = 0 (D2) D(T, U) ≥ 0 (D3) D(T, U) = D(U, T ) (D4) je-li (T, U) taková dvojice shluk˚ u z rozkladu Ak , pro niˇz plat´ı D(T, U) = min{D(T, U)|T, U ∈ Ak , T 6= U} = µ, potom (∀V ∈ Ak )(D(T ∪ U, V ) ≥ µ) Mezishluková vzdálenost se definuje pomoc´ı vzdálenosti vzor˚ u, vzdálenost dvou shluk˚ u z nichˇz kaˇzdý obsahuje pouze jeden prvek, se definuje jako vzdálenost dvou vzor˚ u obsaˇzených v daných shluc´ıch.

A.3.1

Metoda nejbliˇ zˇ s´ıho souseda (single linkage)

Mezishluková vzdálenost je definována def

D(T, U) =

min d(x, y)

x∈T,y∈U

(A.17)

Tato metoda se pouˇz´ıvá hlavnˇe v situac´ıch, kdy se oˇcekávaj´ı shluky, které nemaj´ı sférický charakter.

77

A.3.2

Metoda nejvzd´ alenˇ ejˇ s´ıho souseda (complete linkage)

Mezishluková vzdálenost def

D(T, U) =

max d(x, y)

x∈T,y∈U

(A.18)

Tato metoda naopak preferuje sférické shluky. Pokud v datech nen´ı ˇzádná výrazná struktura, shluky ve výsledném rozkladu maj´ı tendenci si rovnomˇernˇe rozdˇelit prostor ve smyslu objemu.

A.3.3

Metoda pr˚ umˇ ern´ e nepodobnosti vzor˚ u (average linkage)

Mezishluková vzdálenost D(T, U) =

X 1 d(x, y) |T ||U| x∈T, y∈U

(A.19)

Tato metoda nen´ı pˇr´ıliˇs citlivá na odchylky v datech, je statisticky robustn´ı, coˇz znamená, ˇze pokud jsou vzory rozloˇzeny podle urˇcitého rozdˇelen´ı pravdˇepodobnosti, tak se po pˇridán´ı dalˇs´ıch vzor˚ u pˇr´ıliˇs nenaruˇs´ı výsledek shlukován´ı. Hodnota takto definované mezishlukové vzdálenosti je jednoznaˇcná (u nˇekterých metod m˚ uˇze nastat pˇr´ıpad, kdy je minimáln´ı vzdálenost mezi v´ıce neˇz dvˇema shluky stejná a m˚ uˇze se pokraˇcovat v´ıce r˚ uznými zp˚ usoby, pˇri nichˇz mohou vzniknout stejné rozklady, ale vzájemné vzdálenosti v rámci tˇechto stejných rozklad˚ u se liˇs´ı), z tohoto d˚ uvodu je ménˇe náchylná na nejednoznaˇcnost výsledku shlukován´ı.

A.3.4

Pozn´ amky k implementaci hierarchick´ ych metod

V souvislosti s pˇrep´ınac´ımi jednotkami nen´ı tˇreba z´ıskat celou hierarchii rozklad˚ u. Staˇc´ı z´ıskat pouze jeden rozklad obsahuj´ıc´ı pˇredem urˇcený poˇcet shluk˚ u. Velkým problémem je urˇcen´ı správného poˇctu shluk˚ u. Implementace byla pˇrizp˚ usobena tomuto poˇzadavku a je moˇzné monitorovat postup shlukován´ı a pˇri splnˇen´ı urˇcité podm´ınky shlukován´ı pˇreruˇsit a pouˇz´ıt dále rozklad, pˇri kterém bylo shlukován´ı pˇreruˇseno. Urˇcit vˇsak optimáln´ı poˇcet shluk˚ u v souvislosti s neuronovými s´ıtˇemi je sloˇzité, vˇetˇsina metod optimalizuj´ıc´ıch poˇcet shluk˚ u pˇr´ımo pˇri shlukován´ı vyˇzaduje dodateˇcné nastaven´ı konstant, které zase vyˇzaduj´ı informace o shlukovaných vzorech. Nav´ıc i kdyby se toto podaˇrilo pˇrekonat, nen´ı zaruˇceno, ˇze by z´ıskaný rozklad vyhovoval pˇri uˇcen´ı 78

výpoˇcetn´ıch neuron˚ u. Zkoumán´ı zm´ınˇeného problému by mohlo pˇrinést efektivnˇejˇs´ı uˇcen´ı tohoto typu neuronových s´ıt´ı. Sloˇzitost tˇechto u ´ loh plyne z následuj´ıc´ı u ´ vahy, necht’ n je poˇcet vzor˚ u, na poˇcátku je tˇreba spoˇc´ıtat vzájemné vzdálenosti jednotlivých vzor˚ u. Tyto hodnoty jsou ukládány do matice mezishlukových vzdálenost´ı DM. D´ıky symetriˇcnosti vzdálenosti staˇc´ı pouˇz´ıt napˇr. hodnoty pod diagonálou. D˚ usledkem toho je potˇreba vyhodnotit 12 n(n−1) operac´ı spoˇcten´ı vzdálenosti dvou vzor˚ u. T´ım se uˇsetˇr´ı pamˇet’ i poˇcet operac´ı. Pˇri kaˇzdém kroku metody je tˇreba prohledat celou matici vzdálenost´ı a naj´ıt jej´ı minimáln´ı prvek. V l-tém kroku je tˇreba prohledat 21 (n−l−1)(n−l) prvk˚ u DM (pro l=1 docház´ı k prvn´ımu slouˇcen´ı dvou shluk˚ u). Pokud má být ve výsledném rozkladu k shluk˚ u je tˇreba celkem (n − k) krok˚ u a tedy n−k P 1 (n − i − 1)(n − i) operac´ı pouˇzitých pro urˇcen´ı minima matice. Z toho 2 i=1

je vidˇet ˇze poˇcet takových operac´ı je polynom tˇret´ıho stupnˇe v n. Dále je tˇreba uváˇzit, ˇze pˇri slouˇcen´ı dvou shluk˚ u L a U do shluku S je tˇreba pˇrepoˇc´ıtat shlukové vzdálenosti novˇe vzniklého shluku od vˇsech ostatn´ıch shluk˚ u. Vˇsechny pouˇzité metody umoˇzn ˇ uj´ı vyuˇz´ıt vztah, ve kterém je mezishluková vzdálenost D(S, T ) novˇe vzniklého shluku S od libovolného dalˇs´ıho shluku T pouze funkc´ı D(L, T ), D(U, T ) a D(L, T ) (v´ıce napˇr. v [KR90]). T´ım je v l-tém kroku nutné pˇrepoˇc´ıtat (n − l − 1) hodnot, které lze pˇr´ımo um´ıstit do p˚ uvodn´ı matice. Celkem je nutné provést ˇrádovˇe n2 takových operac´ı. Z toho plyne, ˇze takto implementované metody maj´ı sloˇzitost ve tvaru polynomu tˇret´ıho stupnˇe v n.

79

Dodatek B Metoda hlavn´ıch komponent Metodu hlavn´ıch komponent lze pouˇz´ıt k redukci dimenze obecnˇe n rozmˇerného prostoru. Tato metoda vycház´ı z pˇredstavy, ˇze nejvýznaˇcnˇejˇs´ı prvky datových vektor˚ u jsou ty, jejichˇz rozptyl je nejvˇetˇs´ı. Pˇrejde se tedy k nové bázi prostoru, ve které jsou rozptyly pˇr´ısluˇsej´ıc´ı jednotlivým sloˇzkám datových vektor˚ u co moˇzná nejvˇetˇs´ı. Pokud v takovéto nové bázi je pomˇer rozptylu nˇekteré sloˇzky ku maximáln´ımu rozptylu ze vˇsek sloˇzek dostateˇcnˇe malý, lze takovou sloˇzku povaˇzovat za bezvýznamnou a vypustit ji. T´ım se sn´ıˇz´ı dimenzionalita p˚ uvodn´ıho prostoru za cenu transformace dat, vektory v nové bázi jiˇz totiˇz nemaj´ı p˚ uvodn´ı význam. Pˇri hledán´ı tranformaˇcn´ı matice se vyuˇz´ıvá faktu, ˇze matice kovariance C, jej´ıˇz prvky jsou definovány n

Cij =

1X (xik − x¯i )(xjk − x¯j ) n k=1

(B.1)

má na diagonále rozptyly jednotlivých veliˇcin a stopa matice C (souˇcet vˇsech diagonáln´ıch prvk˚ u) pˇri pˇrechodu k nové bázi z˚ ustává konstantn´ı. Matice C se pˇrevede do diagonáln´ıho tvaru (matice kovariance je symetrická, je tedy vˇzdy diagonalizovatelná a má vˇsechna vlastn´ı ˇc´ısla reálná) a najde se báze, ve které je tato matice diagonáln´ı (tuto bázi lze vˇzdy volit ortogonáln´ı d´ıky symetriˇcnosti a tedy rovnosti algebraické a geometrické násobnosti u vˇsech vlastn´ıch ˇc´ısel). Protoˇze diagonalizovaná matice má na diagonále vlastn´ı ˇc´ısla, která odpov´ıdaj´ı rozptyl˚ um nových souˇradnic, odpov´ıdá nejvˇetˇs´ımu vlastn´ımu ˇc´ıslu souˇradnice s nejvˇetˇs´ım rozptylem atd.. Nyn´ı se vyberou nové bázové vektory tak, aby pomˇer souˇctu odpov´ıdaj´ıc´ı smˇeru rozptyl˚ u ku souˇctu vˇsech rozptyl˚ u byl dostateˇcnˇe bl´ızký jedné. Následnˇe se p˚ uvodn´ı hodnoty pˇrevedou do nové báze o niˇzˇs´ı dimenzi. Výpoˇcet by byl tedy následuj´ıc´ı: 80

Urˇc´ı se vlastn´ı ˇc´ısla a vlastn´ı vektory matice kovariance C, vlastn´ı vektory se znormuj´ı na jednotku, pokud je nˇekteré vlastn´ı ˇc´ıslo v´ıcenásobné, ortogonalizuj´ı se jemu pˇr´ısluˇsné vlastn´ı vektory, jinak vlastn´ı vektory k r˚ uzným vlastn´ım ˇc´ısl˚ um jsou po znormován´ı automaticky ortogonáln´ı. Plat´ı C = P ΛP T

(B.2)

kde P je matice jej´ıˇz sloupce tvoˇr´ı normalizované vl. vektory, Λ je diagonáln´ı matice. Pro sloˇzky vektoru x popisuj´ıc´ı vektor v p˚ uvodn´ı bázi a vektoru y v nové bázi plat´ı transformaˇcn´ı vztahy x = Py y = PTx

(B.3) (B.4)

z matice P se vypust´ı vlastn´ı vektory odpov´ıdaj´ıc´ı malým vlastn´ım ˇc´ısl˚ um, t´ım vznikne matice P ′ . Vzory budou nyn´ı popsány niˇzˇs´ım poˇctem hodnot, tvoˇr´ıc´ı vektor y ′, které se spoˇctou podle vztahu y ′ = P ′x (B.5)

81

Dodatek C Pouˇ zit´ e n´ astroje • Pro napsan´ı diplomové práce byl pouˇzit systém LATEX • schémata topologi´ı neuronovývh s´ıt´ı byly vytvoˇreny v programu dia • veˇskeré uvedené obrázky mimo schémat neuronových s´ıt´ı byly vytvoˇreny pomoc´ı prostˇred´ı jazyka R, tento jazyk byl také pouˇzit pro zpracován´ı z´ıskaných dat • implementaˇcn´ı záleˇzitosti týkaj´ıc´ı se programován´ı kódu pro realizaci zm´ınˇených metod, experiment˚ u a následného sbˇeru dat byly vytvoˇreny jako kód v jazyce c++ a v podobˇe plugin˚ u pˇridány k programu NNSU • pro pˇreklad kódu v jazyce c++ byl pouˇzit pˇrekladaˇc GNU gcc

82

Literatura [AJ96]

Alpaydin, Ethen Jordan, Michael I.: ”Local Linear Perceptrons for Classification”, www.cs.berkeley.edu/∼jordan/papers/llp.pdf, 1996.

[AND85]

Andˇel, Jiˇr´ı: ”Matematická statistika”, Nakladatelstv´ı technické literatury, Praha, 1985.

[AND73]

Anderberg, M. R.: ”Cluster analysis for applications”, Academic Press, New York, 1973.

[BIL98]

Bilmes, Jeff A.: ”A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models”,Computer Science Division - Department of Electrical Engineering and Computer Science, U.C. Berkeley, 1998.

[BIS97]

Bishop, Christopher. M.: ”Neural Networks for Pattern Recognition”, Clarendon Press, 1997, ISBN 0-19-853864-2.

[CHE03]

Chien-Yu Chen: ”Incremental Hierarchical Clustering Algorithms Based on Statistical Models”, PhD Thesis, Department of Computer Science and Information Engineering, National Taiwan University, 2003.

[FF02]

Fraley, Ch. - Raftery, Adrian E.: ”Model-based clustering, discriminant analysis, and density estimation”, Journal of the American Statistical Association, vol. 97, No. 458, 2002.

[HH98]

´ Hakl, F. - Holeˇ na, M.: ”Uvod do teorie neuronových s´ıt´ı”, Vyˇ davatelstv´ı CVUT, 1998, ISBN 80-01-01716-8.

[HLA01]

Hlaváˇcek, Marek: ”Applications of Neural Networks with Switching Units on Higgs Boson search”, Výzkumný u ´ kol, Katedra ˇ Matematiky, CVUT - FJFI, 2001. 83

[HLA02]

Hlaváˇcek, Marek: ”Návrh a analýza neuronové s´ıtˇe s pˇrep´ınac´ımi jednotkami vhodné pro studium proces˚ u rozpadu elementárn´ıch ˇcástic s vyuˇzit´ım moˇznosti genetické optimalizace.”, Diplomová ˇ práce, Katedra Matematiky, CVUT - FJFI, 2002.

[HOL92]

Holland, John H.: ”Adaptation in Natural and Artificial Systems”, The MIT Press, 1992, ISBN 0-262-58111-6.

[JJ91]

Jacobs, Robert A. Jordan, Michael I.: ”Adaptive Mixtures of Local Experts”, www.cs.berkeley.edu/∼jordan/papers/mixtures-of-experts.pdf, 1991.

[KAL02]

Kalous, Roman: ”Návrh, implementace a paralelizace genetických algoritm˚ u pro optimalizaci neuronových s´ıt´ı s hierarchickou strukturou”, Diplomová práce, Katedra Matematiky, ˇ CVUT - FJFI, 2002.

[KR90]

Kaufman, L. - Rousseeuw, P. J.: ”Finding groups in data: An introduction to cluster analysis”, John Wiley & sons, 1990, ISBN 0-471-87876-6.

[KOT80]

Kotek, Z. - Br˚ uha, I. - Chalupa, V. - Jel´ınek, J.: ”Adaptivn´ı a uˇc´ıc´ı se systémy”, SNTL - ALFA, Praha, 1980.

[LS85]

ˇ Lukasová, A. - Sarmanov´ a, J.: ”Metody shlukové analýzy”, SNTL, Praha, 1985.

[NAG05]

´ am: ”The neural Package”, Nágy, Ad´ http://cran.r-mirror.de/doc/packages/neural.pdf, 2005.

[OCY01]

Yen-jen Oyang - Chien-Yu Chen - Tsui-Wei Yang: ”A study on the Hierarchical Data Clustering Algorithm Based on Gravity Theory”, Department of Computer Science and Information Engineering, National Taiwan University.

[PLA04]

Plaˇcek, Ivan: ”Paralelizace modelu neuronových s´ıt´ı s pˇrep´ınac´ımi jednotkami”, Diplomová práce, Katedra Matemˇ atiky, CVUT - FJFI, 2004.

[PRE94]

Prechelt, Lutz: ”PROBEN1 - A Set of Neural Network Benchmark Problems and Benchmarking Rules.”, Fakultät f¨ ur Informatik, Universität Karlsruhe, 1994.

84

[SG02]

Strehl, Alexander - Ghosh, Joydeep: ”Cluster Ensembles - A Knowledge Reuse Framework For Combining Multiple Partitions”, http://citeseer.ist.psu.edu/strehl02cluster.html, 2002.

[SNO02]

ˇ Snorek, Miroslav: ”Neuronové s´ıt’ˇe a neuropoˇc´ıtaˇce”, Vydavatelˇ stv´ı CVUT, 2002, ISBN 80-01-02549-7.

[TD04]

Ting Su - Dy, Jennifer: ”A Deterministic Method for Initializing K-Means Clustering”, Proceedings of The 16th IEEE International Conference on Tools with Artificial Inteligence (ICTAI2004), http://www.ece.neu.edu/∼tsu/papers/init.ps, 2004.

[VSR05]

Venables, W.N. - Smith, D.M. - the R Development Core Team: ”An Introduction to R”,www.r-project.org, 2005, ISBN 3-900051-12-7.

[VIS98]

´ V´ıˇsek, Jan Amos: ”Statistická analýza dat”, Vydavatelstv´ı ˇ CVUT, 1998, ISBN 80-01-01735-4.

[WIS01]

Wishart, David: ”K-Means Clustering with Outlier Detection, Mixed Variables and Missing Values”, Department of Management, University of St. Andrews, 2001.

[ZEL02]

Zelinka, Ivan: ”Umˇelá inteligence v problémech globáln´ı optimalizace”, BEN - Technická literatura, 2002, ISBN 80-7300-69-5.

85

ˇ CESK E VYSOK E U ˇ CEN I TECHNICK E Fakulta jadern a a fyzik alnˇe inˇzen yrsk a DIPLOMOV A PR ACE 2006 Jan Vachulka

Recommend Documents