Masarykova univerzita Fakulta informatiky
Vizualizace vybraných metod strojového učení Diplomová práce
Brno, duben 2002
Bc. Petr Marťán
Č
estné prohlášení
Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.
-------------------------------------
Poděkování Na tomto místě bych rád poděkoval panu. Ing. Janu Žižkovi, CSc., vedoucímu této diplomové práce, za podnětné připomínky, cenné rady, zapůjčenou literaturu a ochotu, s jakou k této diplomové práci přistupoval.
Shrnutí V posledních letech se v oblasti informačních technologií stále více klade důraz na inteligenci strojů, počítačů a na jejich schopnost učit se novým poznatkům a dovednostem a adekvátně reagovat na podobné, či zcela nové situace. Vyřešení tohoto problému si klade za cíl strojové učení, které se stává stále více populárnějším mezi odborníky i mezi studenty. V poslední době se navíc k popisu a vysvětlení principů strojového učení stále více využívá vizualizačních metod, které přispívají k lepší představě o fungování principů strojového učení. Tato diplomová práce se zabývá vytvořením systému vizuálně demonstrujícího nejdůležitější metody strojového učení. Účelem je vytvoření výukových pomůcek vhodných jak pro názorné předvedení algoritmů, tak pro samostatné experimentování studentů s nimi.
Klíčová slova Strojové učení, vizualizace, neuronové sítě, genetické algoritmy, NetVisualiser, GaVisualiser, klasifikace, aproximace.
4
OBSAH
Obsah OBSAH ....................................................................................................................................... 4 SEZNAM OBRÁZKŮ ................................................................................................................ 6 1
ÚVOD ................................................................................................................................ 7
2
NEURONOVÉ SÍTĚ ......................................................................................................... 8 2.1 HISTORIE..................................................................................................................... 9 2.2 ÚVOD DO NEURONOVÝCH SÍTÍ ...................................................................................... 9 2.2.1 Základní model neuronu ......................................................................................... 9 2.2.2 Neuronová síť ....................................................................................................... 10 2.3 MODELY NEURONOVÝCH SÍTÍ ..................................................................................... 11 2.3.1 Lineární perceptron .............................................................................................. 11 2.3.2 Zpětné šíření chyby - Backpropagation.................................................................. 12 2.3.3 RBF...................................................................................................................... 15 2.3.4 Kohonenova síť..................................................................................................... 16 2.3.5 Kohonenovy samoorganizační mapy...................................................................... 18 2.3.5.1
3
GENETICKÉ ALGORITMY ......................................................................................... 20 3.1 3.2
4
LVQ..............................................................................................................................18
GENETICKÉ OPERÁTORY ............................................................................................ 21 Ú ELOVÁ FUNKCE A VÝB R ....................................................................................... 22 Č
Ě
IMPLEMENTACE ......................................................................................................... 23 4.1 NETVISUALISER ........................................................................................................ 23 4.1.1 Lineární perceptron .............................................................................................. 24 4.1.2 Backpropagation .................................................................................................. 27 4.1.3 RBF...................................................................................................................... 29 4.1.4 Kohonenova síť..................................................................................................... 32 4.1.5 Kohonenovy samoorganizační mapy...................................................................... 34 4.1.6 Vizualizační režimy pro lineární perceptron, backpropagation a RBF.................... 37 4.1.6.1 4.1.6.2 4.1.6.3 4.1.6.4 4.1.6.5 4.1.6.6 4.1.6.7 4.1.6.8
Výstup neuronové sítě....................................................................................................37 Správnost klasifikace neuronové sítě ..............................................................................37 Mřížka ..........................................................................................................................38 Hranice .........................................................................................................................39 Aproximace funkce – diskrétní.......................................................................................39 Aproximace funkce – spojitá..........................................................................................40 Zobrazování stopy při překreslování...............................................................................41 Vypnutá vizualizace.......................................................................................................42
4.2 GAVISUALISER .......................................................................................................... 42 4.2.1 Genetický algoritmus ............................................................................................ 42 4.2.1.1
Jednoduchý (simple) ......................................................................................................43
5
OBSAH
4.2.1.2 4.2.1.3 4.2.1.4 4.2.1.5 4.2.1.6
4.2.2
Genetické operátory.............................................................................................. 46
4.2.2.1 4.2.2.2 4.2.2.3
4.2.3
Stabilní (steady–state)....................................................................................................43 Stabilní s podporou rozmanitosti (steady–state with sharing)...........................................44 Přírustkový (incremental)...............................................................................................44 Crowding ......................................................................................................................45 Deme – více populací (Deme – multi population) ...........................................................45 Výběr............................................................................................................................46 Křížení ..........................................................................................................................47 Mutace ..........................................................................................................................48
Funkce ................................................................................................................. 49
4.2.3.1 4.2.3.2 4.2.3.3 4.2.3.4 4.2.3.5
Himmelblauova funkce ..................................................................................................49 Sinus .............................................................................................................................50 Schwefelova funkce.......................................................................................................51 Vlnění ...........................................................................................................................52 1-dimenzionální funkce..................................................................................................53
ZÁVĚR ............................................................................................................................ 55
5
LITERATURA ......................................................................................................................... 56 A.
OBSAH PŘILOŽENÉHO CD ........................................................................................ 57
B.
NETVISUALISER - MANUÁL ...................................................................................... 58 Ř
P ÍKAZY PRO PRÁCI S NEURONOVOU SÍTÍ ................................................................................. 58 P ÍKAZY PRO U ENÍ NEURONOVÉ SÍT ..................................................................................... 58 P ÍKAZY PRO PRÁCI S DATY .................................................................................................... 59 P ÍKAZY PRO VIZUALIZACI ...................................................................................................... 61 VYTVO ENÍ NEURONOVÉ SÍT ................................................................................................. 62 DIALOG STATISTIKY NEURONOVÉ SÍT ..................................................................................... 63 DIALOG PARAMETR NEURONOVÉ SÍT .................................................................................... 64 GRAF CHYBOVÉ FUNKCE ......................................................................................................... 65 DATA ..................................................................................................................................... 65 Formáty dat pro práci se soubory....................................................................................... 65 Zadávání dat pomocí grafického rozhraní........................................................................... 66 K ÍŽOVÉ OV ENÍ – CROSSVALIDACE ...................................................................................... 66 Ř
Č
Ě
Ř
Ř
Ř
Ě
Ě
Ů
Ř
C.
Ě
ĚŘ
GAVISUALISER - MANUÁL ........................................................................................ 68 Ř
P ÍKAZY PRO VIZUALIZACI ...................................................................................................... 68 P ÍKAZY PRO EVOLUCI ............................................................................................................ 68 INICIALIZACE GENETICKÉHO ALGORITMU................................................................................. 69 DIALOG STATISTIKY EVOLUCE ................................................................................................. 69 DIALOG NASTAVENÍ PARAMETR EVOLUCE .............................................................................. 70 GRAF EVOLUCE ....................................................................................................................... 71 Ř
Ů
SEZNAM OBRÁZKŮ
6
Seznam obrázků OBR. 2.1 SCHÉMA LINEÁRNÍHO PERCEPTRONU ..................................................................................... 12 OBR. 2.2 GRAF STANDARDNÍ SIGMOIDY............................................................................................... 13 OBR. 4.1 VÝSLEDEK ÚSP ŠNÉHO U ENÍ LINEÁRNÍHO PERCEPTRONU. .................................................... 26 OBR. 4.2 PR B H U ENÍ LINEÁRN NEODD LITELNÝCH DAT. ............................................................... 26 OBR. 4.3 APROXIMACE FUNKCÍ POMOCÍ LINEÁRNÍHO PERCEPTRONU..................................................... 27 OBR. 4.4 ROZMÍST NÍ 20 ST ED RBF JEDNOTEK ............................................................................... 31 OBR. 4.5 ROZMÍST NÍ DVOU RBF JEDNOTEK ....................................................................................... 31 OBR. 4.6 ADAPTACE KOHONENOVY SÍT NA NEROVNOM RN ROZLOŽENÝCH DATECH ......................... 33 OBR. 4.7 GRAFY CHYBOVÉ FUNKCE PRO LOKÁLNÍ PAM (VLEVO) A LOKÁLNÍ PAM 2 (VPRAVO) ........ 34 OBR. 4.8 TOPOLOGIE KOHONENOVY SAMOORGANIZA NÍ MAPY 5X5 (VLEVO) A 1X20 (VPRAVO) . ......... 35 OBR. 4.9 KONFIGURACE SÍ P ED SPUŠT NÍM LVQ (VLEVO) A PO JEHO UKON ENÍ (VPRAVO).............. 36 OBR. 4.10 POSUNY VÝSTUPNÍCH NEURON V PR B HU DOU ENÍ SÍT POMOCÍ LVQ ............................. 36 OBR. 4.11 ZOBRAZENÍ KLASIFIKACE SÍT V REŽIMU M ÍŽKA ................................................................ 38 OBR. 4.12 ZOBRAZENÍ KLASIFIKACE SÍT V REŽIMU HRANICE............................................................... 39 OBR. 4.13 APROXIMACE FUNKCE SINUS V DISKRÉTNÍM ZOBRAZENÍ ...................................................... 40 OBR. 4.14 APROXIMACE FUNKCE SINUS VE SPOJITÉM ZOBRAZENÍ ......................................................... 41 OBR. 4.15 GENETICKÝ ALGORITMUS V GALIB ..................................................................................... 43 OBR. 4.16 OBSAZENÍ LOKÁLNÍCH MINIM JEDINCI P I POUŽITÍ STABILNÍHO GA S PODPOROU ROZMANITOSTI........................................................................................................................... 44 OBR. 4.17 UKÁZKA EVOLUCE POMOCÍ GENETICKÉHO ALGORITMU DEME. ........................................... 46 OBR. 4.18 SCHÉMA JEDNOBODOVÉHO K ÍŽENÍ .................................................................................... 47 OBR. 4.19 SCHÉMA DVOUBODOVÉHO K ÍŽENÍ ..................................................................................... 48 OBR. 4.20 PR B H EVOLUCE P I EXTRÉMNÍM POUŽITÍ HRANICOVÉ MUTACE ......................................... 49 OBR. 4.21 GRAFY HIMMELBLAUOVY FUNKCE...................................................................................... 50 OBR. 4.22 Ú ELOVÁ FUNKCE PRO SINUS.............................................................................................. 51 OBR. 4.23 GRAF SCHWEFELOVY FUNKCE A P ÍSLUŠNÉ Ú ELOVÉ FUNKCE ............................................. 52 OBR. 4.24 GRAFY Ú ELOVÉ FUNKCE VLN NÍ ....................................................................................... 53 OBR. 4.25 GRAF JEDNODIMENZIONÁLNÍ FUNKCE ................................................................................. 54 OBR. B.1 DIALOG NÁVRHU NEURONOVÉ SÍT ...................................................................................... 62 OBR. B.2 STATISTIKA NEURONOVÉ SÍT .............................................................................................. 63 OBR. B.3 DIALOG PRO NASTAVENÍ PARAMETR NEURONOVÉ SÍT ........................................................ 64 OBR. B.4 GRAF CHYBY NEURONOVÉ SÍT ............................................................................................ 65 OBR. C.1 STATISTIKA EVOLUCE .......................................................................................................... 70 OBR. C.2 GRAF VÝVOJE EVOLUCE ...................................................................................................... 72 Ě
Ů
Ě
Č
Č
Ě
Ě
Ř
Ě
Ů
Ě
Ě
Ě
Ě
ĚŤ
ĚŤ
Č
Ť
Ě
Ř
Ě
Č
Ů
Ů
Ě
Ě
Č
Ě
Ř
Ě
Ř
Ř
Ř
Ů
Ě
Ř
Č
Ř
Č
Č
Ě
Ě
Ě
Ů
Ě
Ě
ÚVOD
7
1 Úvod Strojové učení patří v posledním desetiletí k jedné z nejprogresivněji se rozvíjejících oblastí IT. Tato oblast se zabývá způsobem konstrukce programu, který automaticky zlepšuje svou dovednost. V posledních letech bylo vyvinuto mnoho úspěšných aplikací využívajících strojové učení, od programů pro dolovaní dat, které zjišťují podvodné transakce prostřednictvím kreditních karet až po k programům, které se učí řídit auta na dálnicích. Mezi oblasti, které již mají ve strojovém učení pevné místo, patří mimo jiné neuronové sítě a genetické algoritmy. A právě těmito dvěma oblastmi se bude zabývat tato diplomová práce. Neuronové sítě i genetické algoritmy se snaží aplikovat zákony, které dobře fungují v přírodě, na svět počítačů a algoritmů s cílem získat nový a mnohdy efektivnější přístup k učení se počítačů. Proces činnosti lidského mozku je podroben již po několik let intenzivnímu zkoumání a získané výsledky se nyní lidé mimo jiné snaží využít s cílem zdokonalit práci počítačů. Svět počítačů, čili svět umělé inteligence, se stále více snaží přiblížit se k myšlení a inteligenci člověka a procesu učení, neboť člověk se učí novým poznatkům a dovednostem často právě na základě poznatků a zkušeností předchozích, které následně zobecní, a tak je dokáže použít při řešení podobné, nebo i zcela nové situace. Stejně jako je tomu při klasickém učení, i ve světě výpočetní techniky hraje vizuální stránka důležitou roli. Novým trendem současné doby se tedy bezesporu stává právě vizualizace, která umožňuje uživateli vytvořit si bezesporu lepší a konkrétnější představu o dané problematice. Vizualizace nám umožňuje posunout se tak od čistě abstraktního chápání ke konkrétnějšímu a hlubšímu pochopení zkoumaného problému. Tato diplomová práce by měla přispět k lepšímu a rychlejšímu pochopení principů neuronových sítí a genetických algoritmů. Měla by více zpřístupnit tuto oblast studentům, kteří o její studium projeví zájem a poskytnout jim tak prostředek, aby mohli hlouběji do této problematiky proniknout. Programy, které z této práce vzejdou, by měli umožnit jednak demonstraci vlastností, principů a silných a slabých stránek vybraných oblastí strojového učení, a také umožnit studentům, ale i odborníkům touto oblastí se zabývajících, experimentovat s různými parametry, topologiemi a daty, v případě neuronových sítí a s různými typy genetických algoritmů, genetických operátorů, účelových funkcí a populací v případě genetických algoritmů. Toto experimentování by mělo umožnit odhalit a pochopit vlastnosti, které nemusí být na první pohled zřejmé. A právě k dosažení tohoto cíle by měla přispět velkou měrou výše zmíněná vizualizace.
NEURONOVÉ SÍTĚ
8
2 Neuronové sítě V jistém smyslu představují neuronové sítě univerzální výpočetní prostředek a mají stejnou výpočetní sílu jako klasické počítače např. von neumannovské architektury. Hlavní odlišností neuronových sítí od klasické architektury počítačů je jejich schopnost učit se. Požadovanou funkci sítě neprogramujeme tak, že bychom popsali přesný postup jak získat její funkční hodnotu, ale síť sama abstrahuje a zobecňuje charakter funkce v procesu učení ze vzorových příkladů. Tato schopnost, zvaná generalizace či zobecnění, přibližuje svět počítačů nedeterministické přírodě. V tomto smyslu neuronová síť připomíná inteligenci člově ka, který získává mnohé své znalosti a dovednosti ze zkušenosti, kterou ani není schopen ve většině případů analyticky formulovat pomocí přesných pravidel nebo algoritmu. Na jedné straně jsou mechanické výpočty jedné či několika výpočetních jednotek podle předem známých pravidel a na straně druhé vzájemné ovlivňování se tisíců až miliard jednotek v centrální nervové soustavě člověka. Umělé neuronové sítě se za použití výpočetní techniky chovají podobně, jako jejich biologické vzory. Toto přináší obrovské možnosti, které mohou změnit způsob vývoje nových programů i jejich schopností. Současná práce analytika spočívá v popisu dat, nalezení algoritmu a jeho zápisu do umělého jazyka. U některých problémů je tento způsob velmi náročný a zdlouhavý anebo nevede k požadovanému výsledku. Je pak nemožné vytvořit běžnými prostředky program, který by byl schopen ze vstupních dat odvodit správná data výstupní. Neuronová síť modeluje schopnost člověka učit se dovednosti či znalosti z příkladů, které není schopen řešit algoritmicky pomocí klasických počítačů, protože jim chybí analytický popis nebo je jejich analýza příliš složitá. Není tudíž třeba znát algoritmus, který pro daná vstupní data vrátí požadovaná výstupní data. Stačí mít jen dostatečnou kolekci dat, která se předloží neuronové síti. Neuronová síť si sama najde vlastní algoritmus k transformaci vstupních údajů. Přitom si nestačí jen pamatovat všechny vzorové příklady např. v tabulce v paměti klasického počítače, ale je navíc třeba zobecnit jejich zákonitosti, které pak umožní řešit nové, neznámé případy na základě podobnosti. Tomu pak také odpovídají oblasti aplikace neuronových sítí, tam kde klasické počítače selhávají. Mezi hlavní oblasti aplikace neuronových sítí patří: • Rozpoznávání obrazců • Řízení • Predikce • Komprese dat • Transformace signálů • Analýza signálů • Expertní systémy • Optimalizace • Redukce šumu
NEURONOVÉ SÍTĚ
9
2.1 Historie Za prvopočátek oboru umělých neuronových sítí je považována práce Warrena McCullocha a Waltera Pittse z roku 1943 [McCulloch], kteří vytvořili velmi jednoduchý matematický model neuronu, základní buňky nervové soustavy. Zobecněním tohoto modelu neuronu byl tzv. perceptron vynalezený Frankem Rosenblattem v roce 1957. Pro tento model navrhl Rosenblatt učící algoritmus, pro který matematicky dokázal, že nalezne pro daná tréninková data po konečném počtu kroků odpovídající váhový vektor parametrů, nezávisle na svém počátečním nastavení. Krátce po objevu perceptronu vyvinul Bernard Widrow se svými studenty další typ neuronového výpočetního prvku, který nazval ADALINE. Tento model byl vybaven novým výkonným učícím pravidlem, které se využívá až dodnes. Na přelomu 50. a 60. let došlo k úspěšnému rozvoji v oblasti návrhu nových modelů neuronových sítí a jejich implementací. Přes nesporné úspěchy dosažené v tomto období, se obor neuronových sítí potýkal i nadále se dvěma zřejmými problémy. Za prvé, se k neuronovým sítím přistupovalo především z experimentálního hlediska a zanedbával se analytický výzkum neuronových modelů. Za druhé, nadšení některých výzkumných pracovníků vedlo k velké publicitě neopodstatněných prohlášení, například o umělém mozku. Tyto skutečnosti diskreditovaly neuronové sítě v očích mnoha odborníků. V roce 1969 byla publikována kniha Perceptrons [Minsky] od Marvina Minského a Seymoura Paperta, ve které využili známého triviálního faktu, že jeden perceptron nemůže počítat jednoduchou logickou funkci, tzv. vylučovací disjunkci (XOR). Tato kniha způsobila odklon od výzkumu v oboru neuronových sítí. V období od roku 1969 do roku 1982 probíhal výzkum neuronových sítí ojediněle a izolovaně. Novým impulsem pro teorii umělých neuronových sítí byl v roce 1986 objev učení pomocí zpětného šíření chyby pro vícevrstvou neuronovou síť. Tento algoritmus popsali ve svém článku David Rummelhart, Geoffrey Hinton a Ronald Williams [Rummelhart] a vyřešili tak problém, který se jevil Minskému a Papertovi v 60.letech jako nepřekonatelná překážka. Tento algoritmus je doposud nejpoužívanější učící metodou neuronových sítí. Od této doby se pravidelně uskutečňují konference specializované na neuronové sítě; začalo vycházet několik specializovaných časopisů a mnoho renomovaných univerzit založilo nové výzkumné ústavy zabývající se neuronovými sítěmi. Tento trend pokračuje až dodnes.
2.2 Úvod do neuronových sítí V následující teoretické části bude čerpáno především z knihy Jiřího Šímy a Romana Nerudy: Teoretické otázky neuronových sítí [Šíma-Neruda].
2.2.1 Základní model neuronu Základem matematického modelu neuronové sítě je neuron. Jeho struktura je znázorněna na obrázku Obr. 2.1. Neuron má n obecně reálných vstupů x1,…,xn. Vstupy jsou ohodnoceny
NEURONOVÉ SÍTĚ
10
odpovídajícími obecně reálnými váhami w1,…,wn. Zvážená suma vstupních hodnot představuje vnitřní potenciál neuronu: n
ξ = wi xi
(2.1)
i =0
Hodnota vnitřního potenciálu ξ po dosažení prahové hodnoty h indikuje výstup neuronu y.
Nelineární nárůst výstupní hodnoty y = σ (ξ ) při dosažení prahové hodnoty potenciálu h je dán přenosovou (aktivační) funkcí nelinearita, která má tvar:
. Nejjednodušším typem přenosové funkce je ostrá
σ
jestliže ξ ≥ h 1 σ (ξ ) = jestliže ξ < h 0
(2.2)
Formální úpravou lze docílit toho, že funkce σ bude mít nulový práh a vlastní práh neuronu se záporným znaménkem budeme chápat jako váhu, tzv. bias, w0 = -h dalšího formálního vstupu x0 = 1 s konstantní jednotkovou hodnotou jak je naznačeno na obrázku Obr. 2.1. Matematická formulace neuronu je pak dána vztahem: n jestliže ξ ≥ h 1 , kde ξ = wi xi σ (ξ ) = jestliže ξ < h i =1 0
(2.3)
Vstupy neuronu lze chápat jako souřadnice bodu v n-rozměrném euklidovském, tzv. vstupním prostoru En. Nadrovina daná rovnicí: n
w0 + wi xi = 0 i =0
(2.4)
pak dělí vstupní prostor na dva poloprostory.
2.2.2 Neuronová síť Neuronová síť se skládá z formálních neuronů, které jsou vzájemně propojeny tak, že výstup neuronu je vstupem obecně více neuronů. Počet neuronů a jejich vzájemné propojení v síti určuje architekturu (topologii) neuronové sítě. Z hlediska využití rozlišujeme v síti vstupní, skryté a výstupní neurony. Stavy všech neuronů určují stav neuronové sítě a váhy všech spojů představují konfiguraci neuronové sítě. Neuronová síť se v čase vyvíjí, mění se propojení a stav neuronů, adaptují se váhy. V souvislosti se změnou těchto charakteristik v čase se celková dynamika neuronové sítě někdy
NEURONOVÉ SÍTĚ
11
rozděluje do tří dynamik: organizační (změna topologie), aktivní (změna stavu) a adaptivní (změna konfigurace, učení).
2.3 Modely neuronových sítí Konkretizací jednotlivých dynamik, uvedených v předchozí kapitole, získáme různé modely neuronových sítí vhodné pro řešení různých tříd úloh. V následujících kapitolách budou shrnuty základní modely neuronových sítí a jejich vlastnosti. Bude se jednat o tyto modely neuronových sítí: • Lineární perceptron • Zpětné šíření chyby - Backpropagation • RBF • Kohonenova síť • Kohonenova mapa
2.3.1 Lineární perceptron Prvním úspěšným modelem neuronové sítě byl perceptron. Perceptron se skládá z jediného výkonného prvku modelovaného obvykle McCullochovým a Pittsovým modelem neuronu. Perceptron s jedním výkonným prvkem umožňuje nanejvýše klasifikaci do dvou tříd. Vstupní neurony jsou označeny x1,…,xn a výstupní neuron je označen písmenem y. Váhy mezi i-tým vstupním neuronem a výstupním neuronem y jsou označeny wi, kde w0 = -h je bias. Výstup sítě se vypočte tak, že se nejdříve spočte pomocí příslušného vzorce (2.1) vnitřní potenciál ξ výstupního neuronu y. Výstup (stav) perceptronu se pak určí z jeho vnitřního potenciálu aplikací přechodové funkce σ, která má tvar ostré nelinearity (2.2). To znamená, že funkce lineárního perceptronu je dána vztahem:
y = σ (ξ )
1 0
, kde σ (ξ ) =
jestliže ξ ≥ h jestliže ξ < h
(2.5)
V adaptivním(učícím) režimu je funkce sítě zadána tréninkovou množinou
Τ = { ( xk , d k ) xk = ( xk 1 ,..., xkn ) ∈ ℜ n , d k ∈ { 0, 1 }, k = 1,..., p
}
(2.6)
Cílem adaptace je, aby síť pro každý vstup xk z tréninkové množiny odpovídala požadovaným výstupem dk. Ovšem ne vždy je toto možné splnit, protože ne každou funkci lze počítat lineárním perceptronem (např. funkce XOR), nebo tréninková množina nemusí být vždy funkcí.
NEURONOVÉ SÍTĚ
12
Obr. 2.1 Schéma lineárního perceptronu
Na začátku adaptace jsou váhy nastaveny náhodně blízko nuly. V každém časovém kroku je síti předložen vzor z tréninkové množiny a síť podle něj adaptuje své váhy. Změna vah v čase t je dána následujícím perceptronovým učícím pravidlem:
((
)
wi(t ) = wi( t −1) − εxki y w(t −1) , xk − d k
)
(2.7)
Učící konstanta (learning factor) 0 < ε ≤ 1 je mírou vlivu vzorů na adaptaci. Většinou se
(
)
na začátku volí malá hodnota, která později během adaptace roste. Výraz y w(t −1) , xk − d k je rozdílem mezi skutečným výstupem sítě pro k-tý tréninkový vzor a požadovanou hodnotou odpovídajícího výstupu tohoto vzoru. Určuje tedy chybu sítě pro k-tý tréninkový vzor. Pokud je tato chyba nulová, váhy se neadaptují. Protože lineární perceptron může počítat jen omezenou třídu funkcí, je význam tohoto modelu spíše teoretický. Také generalizační schopnost tohoto modelu není příliš velká, protože ho lze použít jen v případě, kdy jsou klasifikované objekty ve vstupním prostoru lineárně separabilní. Tento model je však základem složitějších modelů, např. je základem pro obecnou vícevrstvou síť s učícím algoritmem backpropagation.
2.3.2 Zpětné šíření chyby - Backpropagation Nejznámějším a nejpoužívanějším modelem neuronové sítě je vícevrstvá neuronová síť s učícím algoritmem zpětného šíření chyby (backpropagation) používaným ve velké většině aplikací neuronových sítí. Z hlediska topologie se jedná o vícevrstvou neuronovou síť, standardně se používá dvouvrstvá nebo třívrstvá. Oproti lineárnímu perceptronu je zavedeno navíc následující značení. Množina n vstupních neuronů je označena X a množina m výstupních neuronů Y. Množina všech neuronů, z nichž vede spoj do neuronu j je označena j . Podobně j pak bude množinou neuronů, do nichž vede spoj z neuronu j, a pro které je pak neuron j vstupem. →
←
NEURONOVÉ SÍTĚ
13
V aktivním režimu počítá vícevrstvá síť pro daný vstup funkci y (w) : ℜ n → (0,1) . m
Výpočet probíhá tak, že se na vstup sítě nejdříve nastaví odpovídající stavy vstupních neuronů. V dalším časovém kroku se vypočtou hodnoty vnitřních potenciálů všech neuronů j, jejichž vstupy již mají svůj stav určen podle následujícího vzorce:
ξj =
w ji yi
(2.8)
i∈ j ←
Z vnitřního potenciálu je stanoven stav y = σ (ξ ) neuronu j pomocí diferencovatelné
přechodové funkce σ : ℜ → (0,1) standardní sigmoidy:
σ (ξ ) =
1 1 + e − λξ
(2.9)
Reálný parametr strmosti λ určuje nelineární nárůst standardní sigmoidy v okolí nuly, tj. míru rozhodnosti neuronu. V základním modelu se obvykle uvažuje λ = 1 . Graf standardní sigmoidy je znázorněn na obrázku Obr. 2.1.
Obr. 2.1 Graf standardní sigmoidy
Tímto způsobem jsou v aktivním režimu postupně vypočteny výstupy všech neuronů. Aktivní režim je ukončen, jakmile je stanoven stav všech neuronů, speciálně výstupních neuronů, které určují výstup sítě. Adaptivní (učící) režim vícevrstvé sítě má podobný průběh jako u sítě perceptronové. Požadovaná funkce je opět zadána tréninkovou množinou (2.6). Chyba sítě Ek(w) vzhledem ke k-tému tréninkovému vzoru úměrná součtu mocnin odchylek skutečných hodnot výstupů sítě od odpovídajících požadovaných hodnot výstupů u tohoto vzoru:
Ek ( w ) =
1 2 ( y j (w, xk ) − d kj ) 2 j∈Y
(2.10)
NEURONOVÉ SÍTĚ
14
Chyba sítě E(w) k celé tréninkové množině je pak definována jako součet těchto parciálních chyb sítě Ek(w). Cílem adaptace je minimalizace chyby sítě ve váhovém prostoru. Na začátku adaptace jsou váhy nastaveny náhodně, blízko nuly. Adaptace probíhá v diskrétních časových krocích. Nová konfigurace w(t) v čase t > 0 se vypočte:
w(jit ) = w(jit −1) + ∆w(jit ) Změna vah v bodě w(t-1):
(2.11)
w(t) v čase t > 0 je úměrná zápornému gradientu chybové funkce E(w)
∆
∆w(jit ) = −ε
δE ( t −1) (w ) δw ji
(2.12)
kde 0 < ε ≤ 1 je učící konstanta (rychlost učení), jejíž význam je podobný jako u lineárního perceptronu. K realizaci uvedené adaptivní dynamiky potřebujeme vypočítat gradient chybové funkce, což není triviálním problémem. Při výpočtu se chyba sítě šíří směrem od výstupních, přes skryté, až k vstupním neuronům a právě proto hovoříme o strategii zpětného šíření chyby. Po úpravě rovnice (2.12) dostaneme tento vzorec:
∆w(jit ) = −ετ j yi
(2.13)
kde τj je chyba j-tého neuronu vypočtená pro výstupní neurony ze vztahu:
τ j = ( y j − d kj )λ j y j (1 − y j ) pro j ∈ Y
(2.14)
a pro skrytou vrstvu ze vztahu:
τ j = λ j y j (1 − y j ) τ r wrj pro j ∉ X ∪ Y
(2.15)
r∈ j →
Podrobné odvození výše uvedených vzorců viz. např [Šíma-Neruda]. Uvedená gradientní metoda se často používá, i když není příliš efektivní. Při malé velikosti učící konstanty je konvergence této metody pomalá, avšak při větší hodnotě metoda diverguje. Jednou z modifikací, která se snaží tento nedostatek odstranit, zohledňuje při výpočtu změny váhy ve směru gradientu chybové funkce navíc i předchozí změnu vah, tzv. moment:
NEURONOVÉ SÍTĚ
∆w(jit ) = −ε
15
δE ( t −1) (w ) + α ⋅ ∆w(jit−1) , kde 0 ≤ α ≤ 1 δw ji
(2.16)
je parametr momentu, který určuje míru vlivu předchozí změny. Pomocí momentu gradientní metoda lépe opisuje tvar chybové funkce E(w), protože bere do úvahy předchozí gradient.
2.3.3 RBF RBF sítě představují vícevrstvé neuronové sítě s jednotkami odlišného typu, než jsou perceptrony. Můžeme si ji představit jako třívrstvou síť, kde vstupní vrstva slouží pouze k přenosu vstupních hodnot. Druhá (skrytá) vrstva sestává z RBF jednotek, které realizují jednotlivé radiální funkce. Třetí výstupní vrstva je lineární. Radiální bazické funkce si můžeme představit jako funkce určené středem, které pro argumenty se stejnou vzdáleností od tohoto středu dávájí stejné funkční hodnoty. Ve dvojrozměrném vstupním prostoru a při euklidovské metrice, pak množiny se stejnou funkční hodnotou tvoří kružnici. Z vnějšího pohledu se RBF jednotka podobá perceptronu, má také n vstupů x = ( x1 ,..., xn ) , z nichž každé je přiřazena váha ci. RBF jednotka má také jeden reálný výstup y a může mít i další parametr b, kterému se říká šířka. Ovšem přechodová funkce RBF jednotek je odlišná, její vnitřní potenciál ξ se nepočítá jako vážená suma vstupů RBF jednotky, ale jako vzdálenost vstupního vektoru x od středu c, případně dělená šířkou b.
ξ=
x−c b
(2.17)
Výstupní hodnotu y získáme aplikací přechodové funkce φ na potenciál ξ.
y = σ (ξ )
(2.18)
Jelikož je formálně RBF síť druhem dopředné sítě, stejně jako vícevrstvý perceptron, můžeme k jejímu učení použít modifikaci algoritmu zpětného šíření chyby. Architektura RBF sítě byla motivací k vytvoření učícího algoritmu, který sestává ze tří fází, kdy v každé z nich se určují hodnoty jiné skupiny parametrů. Úkolem první fáze je určení pozice středů RBF jednotek, jenž jsou reprezentovány vahami
{c
ji
; i = 1,..., n ; j = 1,..., h } mezi vstupní a skrytou vrstvou. Existuje řada přístupů, jak tento
problém řešit. Prvním z nich je rovnoměrné rozložení. Jedná se o rovnoměrné pravidelné rozmístění středů jednotek po vstupním prostoru. To je vhodné, jestliže vstupní data jsou také rozmístěna přibližně rovnoměrně. Další metodou, jak zvolit středy jednotek, jsou náhodné
NEURONOVÉ SÍTĚ
16
vzorky. Jde o vybrání h náhodných tréninkových vzorů a umístění RBF jednotek na jejich vstupní části. Podobná metoda optimálních vzorků se liší pouze v tom, že tréninkové příklady nejsou vybírány náhodně, ale používá se metoda ortogonálních nejmenších čtverců k tomu, aby se minimalizovala chyba sítě. Poslední jmenovanou metodou je samoorganizace, která se používá pro lepší zachycení rozmístění tréninkových vzorů. Druhá fáze učení slouží k nastavení dalších parametrů RBF jednotek, existují-li a jsou-li adaptovány. Nejčastěji používané přechodové funkce pro RBF jednotky, Gaussovy radiální bazické funkce, mají následující tvar:
ϕ (x ) = e
x−c
b
−
2
(2.19)
Parametr b reprezentuje šířku φ a určuje tak velikost radiální oblasti okolo středu c, v němž má daná RBF jednotka významné výstupní hodnoty. Šířka b má vliv na generalizační schopnosti sítě. Čím je menší, tím horší generalizaci lze očekávat. Často se šířka volí úměrně průměru vzdáleností q nejbližších sousedů dané jednotky. Hodnota q se přitom často pokládá rovna jedné. Třetím krokem je obvyklé učení s učitelem, které adaptuje váhy mezi skrytou a výstupní vrstvou. Váhy nižší vrstvy jsou již fixovány. Adaptace vah probíhá minimalizací chybové funkce:
E (w) =
(
1 k m (t ) (t ) d s − ys 2 t =1 s =1
)
2
(2.20)
kde ys(t ) označuje aktuální výstup s-té výstupní jednotky a d s(t ) označuje požadovaný výstup tréninkového vzoru předloženého v čase t. Změnu váhy mezi s-tou výstupní jednotkou a i-tou RBF jednotkou v čase t určuje následující rovnice:
(
)
∆wsi(t ) = ε y s − d s(t ) yi
(2.21)
kde 0 < ε ≤ 1 je učící konstanta (rychlost učení), jejíž význam je podobný jako u lineárního perceptronu.
2.3.4 Kohonenova síť Tento model neuronové sítě využívá soutěžní strategie učení. Jedná se o asi nejdůležitější neuronovou architekturu vycházející ze soutěžního učení. Poprvé byla popsána v roce 1982 [Kohonen1], podrobněji je popsána například v [Kohonen2]. Principem modelů se soutěžní strategií je to, že výstupní neurony soutěží spolu o to, který z nich bude aktivní.
NEURONOVÉ SÍTĚ
17
Jedná se dvouvrstvou síť s úplným propojením jednotek mezi vrstvami. Vstupní vrstvu tvoří n neuronů pro distribuci vstupních hodnot a výstupní vrstvu tvoří m výstupních jednotek.
(
)
Váhy w j = w j1 ,..., w jn , j = 1,..., m náležející výstupní jednotce j určují její polohu ve vstupním prostoru. Zatímco vstupy x ∈ ℜn mohou být libovolná reálná čísla, výstupy yj jsou obvykle jen hodnoty 0 nebo 1, přičemž aktivní je vždy právě jeden výstupní neuron, ten který vyhrál kompetici. Výstup každého neuronu se vypočte v závislosti na jeho vzdálenosti od vstupního vektoru x(t) takto: 1 y (jt ) = 0
j = arg min
l =1,..., m
{x
(t )
− wl
}
(2.22)
jinak
Tento principu se zpravidla nazývá „vítěz bere vše“. Princip adaptivní dynamiky je také jednoduchý. Prochází se celá tréninková množina a po předložení jednoho tréninkového vzoru proběhne mezi jednotkami obvyklá kompetice. Její vítěz změní své váhy podle následujícího vzorce:
(
w(jit −1) + θ xi(t −1) − w(jit −1)
w ji
w = (t ) ji
)
{
j = arg min x (t ) − wl l
jinak
}
(2.23)
Reálný parametr 0 < θ < 1 určuje míru změny vah. Na počátku učení je obvykle blízký jedné a postupně se zmenšuje. Jednou z možných modifikací tohoto algoritmu, řešící některé jeho slabiny, je lokální paměť navržená Deseinem [Desieno]. Myšlenka této modifikace spočívá v tom, že každá z k jednotek by měla zvítězit v kompetici zhruba 1/k krát. Každé jednotce j jsou přidány dva parametry: odhad relativní četnosti výher v kompetici fj a práh bj vypočtený na základě této hodnoty. Učící algoritmus pak vypadá takto: V čase t je síti předložen vzor x a podle (2.22) vypočtena odezva výstupních jednotek. Pak je pro každou jednotku j vypočtena nová hodnota parametru fj:
(
f j(t ) = f j(t −1) + β y j − f j(t −1)
)
(2.24)
Podle hodnoty fj se vypočítá práh bj následovně:
1 − f j(t ) N
b(jt ) = γ
(2.25)
NEURONOVÉ SÍTĚ
18
Po určení prahu každé jednotky proběhne druhá kompetice, která probíhá vzhledem k hodnotě
x j − wl − b j
(2.26)
Vítězná jednotka po té změní své váhy podle vzorce 2.24.
2.3.5 Kohonenovy samoorganizační mapy Kohonenovy samoorganizační mapy jsou vylepšením předchozího modelu. Rozdíl spočívá v tom, že výstupní jednotky jsou navíc uspořádány do topologické struktury, nejčastěji do dvourozměrné mřížky. Pro učící proces zavedeme pojem okolí Ns(c) o velikosti s neuronu c v síti, což je množina všech neuronů, jejichž vzdálenost v síti od neuronu c je menší nebo rovna s. To, jak měříme tuto vzdálenost, záleží právě na topologické struktuře výstupních neuronů. V aktivním režimu pracuje síť jako předchozí model, vzdálenost neuronů v topologické struktuře se neprojevuje. Učící proces již bere v úvahu uspořádání neuronů a na místo samotné vítězné jednotky se upravují váhy i všech neuronů, které jsou v jejím okolí. Velikost okolí přitom není konstantní, na začátku učení je okolí obvykle velké a na konci učení potom zahrnuje jen samotný vítězný neuron. Celý učící postup je analogický s učícím algoritmem předchozího modelu, pouze adaptace vah se neřídí rovnicí (2.23), ale má tvar:
(
w(jit −1) + θ xi(t −1) − w(jit −1) w ji
w(jit ) =
)
j ∈ N s (c ) , kde c = arg min x (t ) − wl l =1,..., m jinak
{
}
(2.27)
2.3.5.1 LVQ Doposud jsme uvažovali využití Kohonenové mapy a Kohonenové sítě pro učení bez učitele, lze ji ovšem použít i pro řešení problémů klasifikace dat do kategorií. Mějme tréninkovou množinu tvaru:
{(xn , d n ); n = 1,..., k }
{
, kde xn ∈ ℜ a d n ∈ C1 ,..., C q
Učení Kohonenovy sítě bude pak mít tři fáze: 1. Učení bez učitele 2. Označení výstupních neuronů kategoriemi 3. Doučení sítě pomocí LVQ
}
(2.28)
NEURONOVÉ SÍTĚ
19
Požadované výstupy dk použijeme až ve druhém kroku. U každého výstupního neuronu vytvoříme tabulku četností jednotlivých kategorií, které tento neuron reprezentuje. Každému neuronu j přiřadíme kategorii, kterou reprezentoval nejčastěji a označíme ji vj. Ve třetí fázi se síť doladí pomocí LVQ. Existuje několik variant tohoto algoritmu, viz. [Šíma-Neruda], zde je uvedena ta základní. Vychází z myšlenky posílení správné klasifikace vstřícným posunutím neuronu a naopak, snahou o napravení nesprávné klasifikace odsunutím neuronu od daného vstupu. Postupně sítí předkládáme všechny tréninkové vzory. K danému vzoru nejprve určíme nejbližší neuron c:
c = arg min
l =1,..., m
{x
(t )
− wl
}
(2.29)
Po té provedeme úpravu vah u tohoto neuronu:
( (
wc(t −1) + α x (t ) − wc(t −1) (t −1) − α x (t ) − wc(t −1) wc
wc(t ) =
) )
d (t ) = vc d (t ) ≠ vc
(2.30)
Parametr α by měl mít počáteční hodnotu poměrně malou, asi 0,01 až 0,02 a postupně by měl klesat k nule.
GENETICKÉ ALGORITMY
20
3 Genetické algoritmy Genetické algoritmy jsou prohledávací metodou založenou na principech přírodního výběru a genetiky. Začínáme s počáteční populací jedinců. Členové současné populace následně pomocí mutace a křížení ovlivňují vznik další generace. Výběr těchto jedinců je dán funkcí, která přiřazuje každému jedinci hodnotu jeho míry kvality. Na základě této hodnoty jsou pak jedinci vybíráni, aby se podíleli na vzniku další generace. Za objevitele genetických algoritmů (GA) tak, jak je známe dnes, je považován Holland, který se svými kolegy a studenty na univerzitě v Michiganu položil v sedmdesátých letech základy této disciplíny. Problémem, který řeší GA, je nalezení nejlepšího řešení v prostoru možných řešení. V GA je nejlepší řešení definováno jako to, které optimalizuje předdefinované numerické ohodnocení pro daný problém, nazývané skóre (fitness). Například při aproximaci neznámé funkce zadané vstupními hodnotami a požadovanými výstupními hodnotami, by skóre mělo být definováno jako přesnost řešení nad tréninkovými daty. Toto ohodnocení daného řešení provádí účelová funkce přiřazující každému řešení jeho skóre. Kandidát řešení je nazýván jedinec. Jedinci jsou seskupováni do množin nazývaných populace a po sobě následující populace se nazývají generace. Ve většině aplikací obsahuje jedinec jeden chromozóm. Chromozóm délky n je vektor tvaru:
x1, x2 ,..., xn kde xi se nazývá gen, nebo také alela. Přestože se různé aplikace genetických algoritmů ve svých detailech liší, mají většinou následující společnou strukturu: GA(F,p,k,m) F – účelová funkce p – počet jedinců v populaci k – pravděpodobnost křížení m – pravděpodobnost mutace t := 0 Inicializace populace: Náhodně generuj p jedinců do počáteční generace G0. Ohodnocení: Pro všechny jedince j v G0 spočti F(j). Dokud není splněna ukončovací podmínka proveď: Výběr: Pravděpodobnostně vyber (1-k)p jedinců z Gt a přidej je do Gt+1. Křížení: Pravděpodobnostně vyber dvojce jedinců dle k. Pro každou vybranou dvojici jedinců vytvoř pomocí operátoru křížení dva jejich potomky a přidej je do Gt+1. Mutace: Vyber m procent členů populace Gt+1 a změň u nich náhodně jeden gen.
GENETICKÉ ALGORITMY
21
Ohodnocení: Pro všechny jedince j v Gt+1 spočti F(j). t:= t+1 Vrať Gt. GA se liší od tradičních vyhledávacích technik v několika směrech: • GA pracují s řetězcem zakódovaných hodnot parametrů, ne s parametry samotnými. • GA představují vyvážený poměr mezi hledáním nových řešení v parametrickém prostoru a využíváním informací již objevených. • GA jsou náhodnostními algoritmy v tom směru, že používají operátory, jejichž výsledek závisí na pravděpodobnosti. Výsledky těchto operací jsou založeny na hodnotě náhodného čísla. • GA pracují s několika řešeními zároveň, shromažďující informace z aktuálního hledání přímo do následného hledání. Schopnost pracovat s několika řešeními zároveň dělá GA méně náchylnými na problémy lokálních minim a šumu. • GA mají vlastnost implicitního paralelismu, takže populace jedinců najde řešení rychleji, než kdyby prohledávali prostor izolovaně. • GA využívají pouze informace poskytované účelovou funkcí, ne derivace nebo další doplňující znalosti. Cílem GA je kombinovat nejvhodnější jedince ve snaze vytvořit ještě kvalitnějšího jedince. Výběr „rodičů“ i postup při jejich kombinaci je založen na náhodnostním principu.
3.1 Genetické operátory Generace následníků je v GA závislá na genetických operátorech, které kombinují a mutují vybrané členy aktuální populace. Použití typických genetických operátorů pro manipulaci s jedinci je ilustrováno ve struktuře genetického algoritmu v předchozí kapitole. Tyto operátory odpovídají idealizovaným verzím genetických operací, které můžeme nalézt v přírodě, v biologické evoluci. Dvěma nejběžnějšími operátory jsou křížení a mutace. Operátor křížení vytváří ze dvou jedinců, rodičů, dva nové potomky. Gen na i-té pozici každého potomka je zkopírován z i-té pozice jednoho z rodičů. Výběr, který z rodičů je původcem daného genu, záleží na typu křížení. Prvním typem je jednobodové křížení, které vybere náhodně jeden gen z jedince a v tomto místě oba jedince rozdělí na dvě části, ty se pak navzájem vymění. Dvoubodové křížení rozdělí jedince ve dvou bodech, tj. na tři části, a vymění mezi sebou prostřední části. Posledním základním typem křížení je uniformní křížení. U tohoto typu křížení se určuje zcela náhodně, který z rodičů kopíruje svůj i-tý gen na místo itého genu daného potomka. Oproti kombinačním operátorům, které vytváří potomky kombinováním částí jejich dvou rodičů, druhý typ operátorů vytváří nového jedince jen z jednoho rodiče. Takový genetický operátor se nazývá mutace. Mutace provádí malé změny v jedinci, tím že náhodně vybere jeden gen a změní jeho hodnotu. Mutace se většinou provádí až po křížení a provádí se také řádově méně často než křížení. Význam mutace je v tom, že dokáže vytvářet zcela nové
22
GENETICKÉ ALGORITMY
hodnoty genů a zabraňuje tak uvíznutí celého procesu evoluce v lokálním extrému optimalizované funkce.
3.2 Účelová funkce a výběr Účelová funkce definuje kritérium pro ohodnocení kandidátů řešení, jedinců a jejich pravděpodobnostní výběr do další generace. Jestliže máme klasifikační úlohu, pak účelová funkce typicky hodnotí klasifikační přesnost přes množinu dat daných tréninkovými příklady. Výběr jedinců, nebo také selekce, je založen na účelové funkci, která využívá znalosti o cíli adaptace, resp. evoluce. V principu je to jediné místo v algoritmu, kde je tato znalost nezbytná. Čím má jedinec vyšší skóre, tím je větší pravděpodobnost, že bude vybrán pro nové zkombinování svých genů, nebo pro přímý postup do další generace. Pravděpodobnost, že bude jedinec vybrán, je dána poměrem skóre daného jedince ke skóre ostatních jedinců v populaci. Základní typy výběru (selekce) jsou následující: • Ruleta (roulette whell) – Pravděpodobnost Pr, že jedinec hi, bude vybrán je dána rovnicí:
Pr(hi ) =
•
•
F (hi ) p
i =1 F
(hi )
(3.1)
kde F je účelová funkce a p je počet jedinců v populaci. Turnaj (tournament) – Zvolí se náhodně dva jedinci, z nichž je pak s předdefinovanou pravděpodobností p vybrán ten s vyšším skóre a s pravděpodobností 1-p, ten s menším skóre. Pořadí (rank) – Jedinci jsou setříděni do seznamu podle svého skóre. Pravděpodobnost výběru je pak přímo úměrná pořadí jedince v setříděném seznamu.
IMPLEMENTACE
23
4 Implementace Realizace zadání diplomové práce byla uskutečněna pomocí dvou programů. Programem NetVisualiser, který se soustřeďuje na vizualizaci neuronových sítí a experimentování s nimi a programem GaVisualiser, jehož cílem je seznámit uživatele pomocí vizuálních pomůcek s genetickými algoritmy.
4.1 NetVisualiser Tato kapitola se bude zabývat implementací neuronových sítí uvedených v kapitole 2.3 v programu NetVisualiser. Při implementaci neuronových sítí jsem čerpal především z knih [Šíma-Neruda], [Novák], [Hassoun] a [Kohenen2]. Nejdříve něco o programu NetVisualiser obecně. NetVisualiser umožňuje pracovat s následujícími neuronovými sítěmi: • Lineární perceptron • Backpropagation • RBF síť • Kohonenova síť • Kohonenova mapa Tyto modely neuronových sítí byly zvoleny, neboť reprezentují základní typy neuronových sítí a současně je jich často využíváno v praxi, s výjimkou lineárního perceptronu, který má význam spíše teoretický. Program NetVisualiser umožňuje tyto modely vytvářet, podle zadaných parametrů, umožňuje jejich učení, kde si lze vybrat z několika různých rychlostí učení a různých režimů vizualizace. V průběhu učení je možno sledovat měnící se graf chyby učení či statistiku sítě, anebo měnit některé parametry sítě ovlivňující proces adaptace. Program pracuje s modely neuronových sítí ve dvou základních režimech – klasifikace vzorů a aproximace funkcí, pokud je tento režim pro daný model sítě relevantní. Natrénovanou neuronovou síť je možné kdykoli uložit a později ji opět načíst pro další trénování nebo demonstraci jejich vlastností. Tento program také umožňuje uživateli práci s tréninkovými či testovacími daty. V případě, že se jedná o dvourozměrná data, lze tato data pomocí grafického uživatelského rozhraní vytvářet přímo v programu, nebo lze využít možnost automatického generování příslušných dat, kde lze zvolit mezi několika možnostmi typu dat. Vždy je tu možnost uložení aktuálních dat a načtení uložených či externích dat. Program také podporuje automatickou normalizaci dat do intervalu 0,1 , avšak data lze normalizovat i do libovolného intervalu. Vizualizaci učení neuronové sítě lze využít v režimu klasifikace vzorů pro dvourozměrná data a v režimu aproximace funkcí pro data jednorozměrná. Uživatel si může vybrat mezi několika typy vizualizace a zvolit si tak jeho potřebě nejvíce vyhovující režim či jejich kombinaci.
24
IMPLEMENTACE
4.1.1 Lineární perceptron Implementace lineárního perceptronu by měla uživatele seznámit se základním principem dopředných neuronových sítí a naznačit základní princip změny vah. Topologie lineárního perceptronu obsahuje vstupní vrstvu s n neurony a vrstvu výstupní s jedním neuronem. Mezi vrstvami existuje úplné propojení. Uživatel si může vybrat z následujících typů přechodových funkcí: • 0 a 1. Tato přechodová funkce je dána následujícím předpisem:
1 jestliže ξ ≥ 0
0 jestliže ξ < 0
σ (ξ ) =
n
, kde ξ = wi xi
(4.1)
i =0
Jedná se o nejpoužívanější přechodovou funkci a doporučuji ji používat také pro většinu běžných příkladu v programu NetVisualiser. Práh této funkce pro vizualizaci je 0,5. •
-1 a 1. Tato funkce je dána obdobným předpisem jako předchozí funkce: n 1 jestliže ξ ≥ 0 , kde ξ = wi xi σ (ξ ) = i =0 - 1 jestliže ξ < 0
(4.2)
Prakticky by mezi těmito přechodovými funkcemi měly být jen minimální rozdíly. Obě se používají především pro klasifikační úlohy. Práh této funkce pro vizualizaci je 0. •
Lineární. Tato přechodová funkce má následující tvar: n
σ (ξ ) = ξ , kde ξ = wi xi
(4.3)
i =0
Její tvar ji předurčuje pro použití v aproxima čních úlohách, protože její funkční hodnota není omezena pouze 0 a 1, resp. -1 a 1, ale může nabývat libovolných hodnot. Práh této funkce pro vizualizaci je 0,5, tato funkce by se ovšem pro klasifikační úlohy neměla používat.
25
IMPLEMENTACE
Klasifikační možnosti perceptronu jsou omezené, neboť jeho jednoduchá topologie dovoluje klasifikaci vzorů nejvýše do dvou tříd. Pro dvourozměrná vstupní data je přímka oddělující tyto klasifikace dána následující rovnicí:
x1w1 + x2 w2 + w0 = 0
(4.4)
Obecně má oddělující nadrovina tvar uvedený v rovnici (2.4). V průběhu učení se tato přímka oddělující různé klasifikace zobrazuje a mění svoji polohu podle aktuálního stavu neuronové sítě. Průběh učící fáze lze ovlivňovat nastavením učící konstanty, viz. vzorec (2.7), v dialogu Parametry sítě. Hodnoty tohoto parametru by se měly pohybovat v intervalu od 0 do 1. Čím je hodnota učící konstanty blíže nule, tím dochází k menší úpravě vah. Pro nulu se pak váhy přestávají adaptovat úplně. Většinou se na začátku volí malá hodnota, která později během adaptace roste. To odpovídá počátečnímu povrchnímu seznámení se s tréninkovou množinou a pozdějšímu důkladnému doučení detailů, viz. [Šíma-Neruda]. V dialogu Parametry sítě lze zapnout automatickou úpravu tohoto parametru. Poté se učící konstanta sama pomalu zvyšuje směrem k 1. Úprava probíhá podle následujícího vzorce:
ε (t ) = ε (t −1) + 0.00002 * (1 - ε (t −1) )
(4.5)
Na obrázku Obr. 4.1 je vidět výsledek úspěšného procesu učení. Jako tréninková množina byl použit soubor LP1.dat a jako neuronová síť lineární perceptron se dvěma vstupními neurony a jedním výstupním neuronem. Jako přechodová funkce byla použita funkce 0 a 1. Na obrázku je vidět zelená přímka oddělující dvě různé klasifikace, znázorněné červenou a modrou barvou. Konkrétní poloha přímky záleží na počátečním nastavení vah, které je náhodné. Obrázek Obr. 4.2 zachycuje proces učení na lineárně neoddělitelných datech. Topologie neuronové sítě je stejná jako v předchozím případě a tréninková množina byla načtena ze souboru LP2.dat. Obrázek byl pořízen v režimu zobrazování stopy, při němž jsou vidět i předchozí polohy přímky, takže si uživatel může udělat představu o tom, v jakých mezích se přímka pohybuje. Samozřejmě učení lineárního perceptronu s touto tréninkovou množinou neskončí nikdy s nulovou chybou sítě, protože lineární perceptron není tyto dvě klasifikace schopen od sebe úplně oddělit. Oddělovací přímka se bude pohybovat zhruba na rozmezí těchto dvou klasifikací, ale pravděpodobně se nikdy nezastaví na optimální kompromisní hranici. Pro trénování lineárního perceptronu na lineárně neseparabilních datech existují modifikované algoritmy, viz. například Pocket algoritmus [Hassoun], protože základní algoritmus uvedený v kapitole 4.1 není pro učení na těchto datech příliš vhodný.
26
IMPLEMENTACE
Obr. 4.1 Výsledek úspěšného učení lineárního perceptronu.
Obr. 4.2 Průběh učení lineárně neoddělitelných dat.
Teoreticky lze lineární perceptron použít i pro aproximaci funkcí, i když zde nelze očekávat žádné velké výsledky. Prakticky se jedná o proložení přímky skupinou bodů, tj. tréninkovou množinou. Pro aproximaci funkcí je třeba vytvořit neuronovou síť s jedním
27
IMPLEMENTACE
vstupním neuronem a jedním výstupním neuronem. Jako přechodovou funkci je zapotřebí zvolit funkci lineární, v ostatních případech by se na výstupu sítě střídaly pouze dvě hodnoty, 0 a 1 nebo -1 a 1. Výsledek aproximace funkce pomocí lineárního perceptronu je znázorněn na obrázku Obr. 4.3. Modré body znázorňují data z tréninkové množiny, tj. vybrané funkční hodnoty aproximované funkce a červená přímka znázorňuje výslednou funkci lineárního perceptronu.
Obr. 4.3 Aproximace funkcí pomocí lineárního perceptronu.
4.1.2 Backpropagation Strategie zpětného šíření chyby patří mezi nejpoužívanější modely neuronových sítí. Program NetVisualiser ukazuje tento model z hlediska klasifikačních a aproximačních úloh. Jak již bylo řečeno, jedná se o vícevrstvou neuronovou síť. Uživatel si může zvolit počet skrytých vrstev a počet neuronů v jednotlivých vrstvách, včetně vrstvy vstupní a výstupní. Pro většinu úloh by mělo být dostatečné zvolit si síť s jednou nebo dvěma skrytými vrstvami. Počty skrytých neuronů by měly odpovídat složitosti řešeného problému, tj. počtu tréninkových vzorů, jejich vstupů a výstupů a struktuře vztahů, které popisují. Je třeba upozornit, že příliš malá síť se obvykle zastaví v nějakém mělkém lokálním minimu a je zapotřebí topologii doplnit o další skryté neurony. Na druhou stranu příliš velká síť pravděpodobně najde globální minimum, ale za cenu velké výpočetní náročnosti. V praxi se obvykle počet neuronů volí heuristicky. Jedna z heuristik tvrdí, že v první skryté vrstvě by mělo být o něco více neuronů než je vstupů a ve druhé skryté vrstvě by měl být počet neuronů roven aritmetickému průměru počtu výstupů a počtu neuronů v první skryté vrstvě. Následuje přehled přechodových funkcí dostupný pro tento model: • Sigmoida. Tato standardní přechodová funkce má následující tvar:
28
IMPLEMENTACE
σ (ξ j ) =
1 −ξ 1+ e j
, kde ξ j =
w ji yi
(4.6)
i∈ j ←
Práh této funkce pro vizualizaci je 0,5. •
Tanh - Hyperbolický tangens. Jedná se taktéž o sigmoidní funkci s tímto předpisem:
1− e σ (ξ ) = j
1+ e
−ξ j −ξ j
, kde ξ j =
w ji yi
(4.7)
i∈ j ←
Jedním z rozdílů těchto dvou funkcí je, že standardní sigmoida má obor hodnot roven
(0,1) , zatímco hyperbolický tangens má obor hodnot roven (− 1,1) . Ob
ě
tyto funkce lze
použít jako přechodovou funkci pro skrytou nebo výstupní vrstvu. Práh této funkce pro vizualizaci je 0. •
Lineární. Přechodové funkce pro výstupní vrstvu doplňuje lineární funkce, která je vhodná pro aproximační úlohy. Její tvar je:
σ (ξ j ) = ξ j , kde ξ j =
w ji yi
(4.8)
i∈ j←
Práh této funkce pro vizualizaci je 0,5, tato funkce by se ovšem pro klasifikační úlohy neměla používat. Úprava vah v adaptivní fázi probíhá dle vzorců (2.11), (2.13), (2.14) a (2.15) uvedených v podkapitole 3.2. Protože je implementován modifikovaný algoritmus momentu, je navíc místo vzorce (2.12) použit vzorec (2.16). Adaptace konfigurace sítě probíhá po předložení každého tréninkového vzoru, čímž se sníží paměť ová náročnost ve srovnání s akumulovanou variantou, kde se váhy adaptují až po projití celé tréninkové množiny. Oproti akumulované variantě však může dojít ke zpomalení konvergence, protože se gradient nepočítá k celé tréninkové množině, ale k aktuálnímu tréninkovému vzoru. V klasifikačních úlohách si tento model poradí téměř s jakýmkoli problémem, samozřejmě konkrétní výsledky závisí od zvolené topologie. Uživatel může pozorovat učící režim v několika vizualizačních režimech, které mu zpřístupní celý režim adaptace konfigurace sítě. Více se o nich lze dozvědět v podkapitole 4.1.6.
29
IMPLEMENTACE
Proces adaptace lze ovlivňovat dvěma faktory, učící konstantou a mírou vlivu momentu. Jak ovlivnit proces učení pomocí učící konstanty je již popsáno v podkapitole 4.1.1. Pomocí vlivu momentu můžeme urychlit konvergenci sítě. Obvykle se volí hodnota přibližně 0,9, viz. [Šíma-Neruda]. V praxi to znamená, že se k aktuální změně váhy přičte i 0,9ti násobek předchozí změny. I když tento model neuronové sítě patří mezi nejznámější a nejčastěji používané, rychlost a efektivnost jeho adaptivního režimu nepatří k nejlepším. Ukázku klasifikačního režimu tohoto modelu můžeme vidět na obrázcích Obr. 4.1 a Obr. 4.1. Tréninková množina byla načtena ze souboru XOR4.dat, který simuluje klasifikaci logickou funkcí vylučovací disjunkce. Na obrázcích je vidět, jak si tento model poradil s problémem, který je pro lineární perceptron neřešitelný. Neuronová síť měla jednu skrytou vrstvu s 20ti neurony, tento počet byl pro pořízení tohoto obrázku zvolen pouze experimentálně, jinak by na řešení tohoto problému zcela jistě stačila například síť se dvěma skrytými neurony, která by pravděpodobně i rychleji konvergovala.
4.1.3 RBF Tento model nepatří mezi nejrozšířenější modely, což však nesnižuje jeho důležitost. Uživatel si může zvolit počet vstupních neuronů, počet skrytých neuronů, tzv. RBF jednotek, v jediné skryté vrstvě a počet výstupních neuronů. Přechodovou funkcí pro skrytou vrstvu je tzv. Gaussova funkce:
ϕ (z j ) = e
−
zj bj
2
(4.9)
kde zj je vzdáleností vstupního vektoru x od středu j-té RBF jednotky cj vypočtené následovně:
zj =
i∈ j ←
(x − c )
2
i
(4.10)
ji
Práh této funkce pro vizualizaci je 0,5. Přechodové funkce přístupné pro výstupní vrstvu jsou: • 0 a 1. Tato přechodová funkce má následující tvar:
1 jestliže z j ≥ 0
0 jestliže z j < 0
σ (z j ) =
Práh této funkce pro vizualizaci je 0,5.
, kde z j =
i∈ j ←
(x − c )
2
i
ji
(4.11)
30
IMPLEMENTACE
•
Lineární. Tato přechodová funkce je zadána následujícím předpisem:
σ
(z j ) = z j , kde z j =
i∈ j ←
(x − c )
2
i
ji
(4.12)
Lineární přechodová funkce je opět určena pro aproximační úlohy. Práh této funkce pro vizualizaci je 0,5, tato funkce by se ovšem pro klasifikační úlohy neměla používat. Každá RBF jednotka si oproti ostatním modelům neuronů pamatuje svoji šířku bj. Šířka určuje velikost radiální oblasti okolo středu cj, v ně mž má daná RBF jednotka významné výstupní hodnoty. Střed j-té RBF jednotky cj je dán hodnotami jí příslušejících vah, u jiných modelů obvykle značenými wj. Adaptace neuronové sítě probíhá ve třech fázích. První dvě fáze probíhají pouze jednou a to po inicializaci sítě či po její reinicializaci. První fáze určuje středy RBF jednotek ve skryté vrstvě. Určení středů probíhá náhodným výběrem vzorů z tréninkové množiny a nastavením středů jednotek, tj. vah mezi vstupní a skrytou vrstvou, na jejich vstupy. V případě, že je více RBF jednotek, než vzorů v tréninkové množině, budou mít některé RBF jednotky totožné středy. Ve druhé fázi probíhá nastavení šířek RBF jednotek. Ke každé RBF jednotce se najde jednotka, která je jí nejblíže, přičemž se vzdálenost dvou RBF jednotek počítá jako vzdálenost jejich středů. Hodnota šířky jednotky se pak nastaví jako vzdálenost těchto jednotek. Ve třetí fázi se adaptují pouze váhy mezi skrytou a výstupní vrstvou. Změna vah probíhá dle rovnice (2.21) uvedeného v kapitole 2.3.3. Středy RBF jednotek jsou v programu NetVisualiser znázorněny tmavě zelenými křížky a dávají tak uživateli představu o tom jak jsou rozmístěny po tréninkové množině. Na obrázku Obr. 4.1 vidíme rozmístění středů RBF jednotek při klasifikační úloze. Tréninková data byla nahrána ze souboru KoloTrojte.dat, RBF síť měla dva vstupní neurony, dvacet skrytých RBF jednotek a jeden výstupní neuron. Lze si všimnout, že kolem středů RBF-jednotek se tvoří oblasti klasifikací podobné kruhům. V podstatě se o kruhy jedná, ale protože síť obsahuje dvacet RBF jednotek, tak se tyto jednotky navzájem ovlivňují, kombinují a deformují. Na obrázku Obr. 4.2 jsou na stejných tréninkových datech použity pouze dvě RBF jednotky a vidíme, že oblast klasifikovaná červenou barvou je souvislejší a komplexnější. Pravděpodobně se ale této síti nikdy nepodaří správně klasifikovat čtyři vzory uprostřed kruhu. Jestliže se nacházíme v aproxima čním režimu jsou středy RBF jednotek umístěny u horního okraje okna, jak je vidět na obrázcích Obr. 4.1 a Obr. 4.1. Rozmístění RBF jednotek může uživatel přímo ovlivnit pomocí funkce Změna středů RBF jednotek. Tato funkce umožňuje přemísťovat středy RBF jednotek pomocí myši a uživatel tak může sám určit, kde daná RBF jednotka bude mít svůj střed. Uživatel tak může experimentovat s optimálním rozmístěním jejich středů a dosáhnout tak lepších výsledků, než by dosáhla sama
31
IMPLEMENTACE
síť. Po každém přemístění středu RBF jednotky se znovu provede druhá fáze učení, tj. určení šířky všech RBF jednotek. Proces adaptace lze ovlivňovat pomocí nastavení učící konstanty, jež bylo již popsáno v podkapitole 4.1.1.
Obr. 4.1 Rozmístění 20 středů RBF jednotek
Obr. 4.2 Rozmístění dvou RBF jednotek
32
IMPLEMENTACE
4.1.4 Kohonenova síť I když i poslední dva implementované modely jsou založeny na dopředné neuronové síti, od předchozích modelů se liší. Jedná se o základní modely pro samoorganizaci a soutěžní učení. V případě Kohonenovy sítě se jedná o dvouvrstvou síť bez skrytých jednotek. Uživatel si může zvolit počet vstupních a výstupních neuronů a vybrat si jednu ze dvou modifikací. Počet vstupních neuronů závisí na dimenzi vstupů tréninkových dat, pro vizualizaci se však musí volit dvourozměrná data. Počet výstupních neuronů na vizualizaci závislý není, a tak jich lze zvolit libovolný počet. Vnitřní stav ξj výstupního neuronu j se vypočítá jako rozdíl mezi vstupem a pozicí tohoto
(
)
neuronu, danou jemu příslušejícími vahami w j = w j1 ,..., w jn , kde n je počet vstupních neuronů. Výstup neuronu s nejmenší vzdáleností od vstupu se nastaví na 1 a výstupy ostatních neuronů na 0, viz. rovnice (2.22). U neuronu, který bude mít na výstupu 1, se upraví váhy podle rovnice (2.23). Chyba sítě se u tohoto modelu vypočítá jako součet kvadrátů vzdáleností tréninkových vzorů od nejbližšího výstupního neuronu podle následující rovnice:
E (w) =
1 p 2 (xk − wkj ) 2 k =1
, kde
j = arg min { xk − wl l
}
(4.13)
a kde p je počet tréninkových příkladů. Jednou ze slabin tohoto algoritmu je, že se v případě nerovnoměrného rozmístění tréninkových vzorů, například v několika velkých shlucích, z počátku adaptace přisune do každého shluku většinou jen jeden neuron, a ten pak už vždy bude nejblíže tomuto shluku, tudíž kompetici náležející vzorům z tohoto shluku vždy vyhraje, a tak, se ostatní neurony nikdy nepřisunou blíže. Tuto situaci znázorňuje obrázek Obr. 4.1, tréninková data byla načtena ze souboru Kohonen1.dat. Výstupní neurony jsou znázorně ny šedými kolečky a tréninková data modrými čtverečky. Na obrázku lze vidět, že se ke každému shluku dostal pouze jeden výstupní neuron a ostatní výstupní neurony tak podávají chybnou informaci o rozložení vstupních dat.
IMPLEMENTACE
33
Obr. 4.1 Adaptace Kohonenovy sítě na nerovnoměrně rozložených datech
Předchozí slabinu řeší modifikace tohoto algoritmu lokální paměti, jejíž princip je popsán v kapitole 2.3.4. V programu NetVisualiser je tato modifikace implementována přesně dle vzorců (2.24), (2.25) a (2.26). V programu je implementována ještě jedna modifikace, a to pod názvem lokální paměť 2. Tato modifikace lokální paměti odstraňuje teoretickou slabinu spočívající v tom, že vzdálený neuron, který nikdy nevyhraje první kompetici, právě díky tomu, že ji nikdy nevyhrál, vyhraje vždy druhou kompetici a změna vah proběhne pouze u něho. Ovšem to, že vyhrál druhou kompetici se již nepromítá do jeho relativní četnosti výher f. Druhá modifikace tudíž zohledňuje výhru neuronu i ve druhém kole kompetice v jeho relativní četnosti výher f, která se pro vítězný neuron druhého kola upraví dle rovnice (2.24). Ze zkušeností vyplynulo, že tato druhá modifikace rychleji konverguje a rozmístění neuronů pak více odpovídá tréninkovým datům. Chybové funkce obou modifikací na tréninkových datech Kohonen2.dat lze porovnat na následujícím obrázku.
34
IMPLEMENTACE
Obr. 4.2 Grafy chybové funkce pro lokální paměť (vlevo) a lokální paměť 2 (vpravo)
Proces adaptace konfigurace sítě můžeme ovlivnit nastavením třech parametrů. Prvním z nich je učící konstanta, jejíž nastavení je popsáno v podkapitole 4.1.1. Další nastavitelné parametry mají význam jen pro dvě výše uvedené modifikace. Parametry nastavující míru vlivu modifikací na proces učení, jsou nazývány beta a gama. Parametr beta reprezentuje parametr β z rovnice (2.24) a parametr gama odpovídá parametru γ z rovnice (2.25). Další postup adaptace Kohonenovy sítě je popsán v závěru následující kapitoly 4.1.5.
4.1.5 Kohonenovy samoorganizační mapy Druhým implementovaným modelem učení bez učitele je Kohonenova samoorganizační mapa. Tento model je rozšířením předchozího modelu o topologickou strukturu, do níž jsou výstupní neurony uspořádány. Uživatel si volí počet vstupních neuronů. Počet výstupních neuronů se volí velikostí dvourozměrné mřížky, tj. zadáním x-ové a y-ové velikosti mřížky. Počet výstupních neuronů je tedy roven součinu x a y. Výpočet vnitřního stavu výstupních neuronů je implementován stejně jako v předchozím modelu, tj. dle rovnice (2.22). Oproti předchozímu modelu si neuron pamatuje navíc svou pozici v topologii, která se využije při změně vah. Vzdálenost neuronů v topologii se počítá v euklidovské metrice. Změna vah v adaptivní dynamice probíhá podle rovnice (2.27). Průběh učení může uživatel ovlivňovat dvěma parametry, učící konstantou a velikostí okolí. Nastavení učící konstanty je popsáno v podkapitole 4.1.1. Velikost okolí určuje, které neurony adaptují svoje váhy. Změna vah se provede vždy u vítězného neuronu a navíc u všech neuronů, které leží v jeho aktuálním okolí. Na začátku obvykle okolí zahrnuje polovinu sítě a na konci učení zahrnuje jen vítězný neuron. Jak již bylo uvedeno vzdálenosti v topologii se počítají v euklidovské metrice, tj. okolí velikosti menší než 1 obsahuje pouze jeden neuron, okolí velikosti větší než 1 a menší než 2 zahrnuje vítězný neuron a čtyři nejbližší okolní neurony atd. U tohoto parametru lze v dialogu Parametry sítě zvolit jeho automatickou úpravu, která probíhá podle tohoto vzorce:
θ (t ) = 0,9993 * θ (t −1)
(4.14)
IMPLEMENTACE
35
kde θ je velikost okolí. Koeficient 0,9993 byl odhadnut experimentálně. Při vytvoření sítě je velikost okolí implicitně rovna druhé odmocnině počtu výstupních neuronů. V případě, že se síť „zasukuje“, tzn. čáry spojující sousední neurony jsou překříženy, stačí nastavit velikost okolí na větší hodnotu a síť se začne organizovat znovu do nové struktury. Chyba sítě se počítá stejně jako u předchozího modelu, tj. podle rovnice (4.13). S topologií výstupní vrstvy lze různě experimentovat a zkoušet, která topologie se pro danou úlohu lépe hodí. Na obrázku Obr. 4.1 můžeme porovnat topologii 5x5 a 1x20 pro tréninkovou množinu načtenou ze souboru kolo.dat znázorňující kruh. Šedými kolečky jsou znázorněny výstupní neurony a každý výstupní neuron je propojen zelenou čarou s nejbližšími okolními neurony, jejichž vzdálenost od tohoto neuronu je 1. Na obrázku je vidět, že pro tuto jednoduchou tréninkovou množinu se hodí lépe jednodušší topologie 1x20, protože rozmístění výstupních neuronů u této topologie více odpovídá rozmístění tréninkových vzorů, než u topologie 5x5.
Obr. 4.1 Topologie Kohonenovy samoorganizační mapy 5x5 (vlevo) a 1x20 (vpravo) .
Pokud máme k dispozici tréninkovou množinu včetně klasifikovaných vstupů můžeme výstupní neurony oklasifikovat jednou z kategorií. U každého výstupního neuronu se vytvoří pole četností klasifikací, které neuron reprezentuje pro danou tréninkovou množinu. Neuronu se pak přiřadí právě ta klasifikace, kterou reprezentoval nejčastěji, a neuron bude zbarven podle příslušnosti k této klasifikaci. Pokud neuron nereprezentuje ani jednu kategorii, tj. není nejblíže žádnému tréninkovému vzoru, což se může stát při velkém počtu výstupních neuronů a malém počtu tréninkových vzorů, přiřadí se mu klasifikace vzoru nejbližšího. Poté co uživatel oklasifikuje výstupní neurony, může pro doučení a jemné doladění sítě použít algoritmus LVQ, popsaný v podkapitole 2.3.5.1. V programu NetVisualiser je algoritmus LVQ implementován přesně podle tohoto odstavce a změna vah se provádí podle rovnic (2.29) a (2.30). Uživatel může sledovat působení LVQ na neuronovou síť, kde lze dobře vidět, jak se výstupní neurony přisunují ke vzorům odpovídajícím jejich klasifikacím a naopak, jak se snaží co nejdále odsunout od opačných klasifikací. Situaci před spuštěním a po ukončení LVQ můžeme porovnat na obrázku Obr. 4.2. Celý průběh doučení pomocí LVQ je znázorněn na obrázku Obr. 4.1, kde je názorně vidět, jak se červeně obarvené neurony odsunuly od modře klasifikovaných vzorů a směrem k jejich původní pozici se posunuly neurony obarvené
36
IMPLEMENTACE
modrou barvou. Pro vizualizaci byla použita Kohonenova mapa o velikosti 5x5 a tréninková datová sada ze souboru kohonen4.dat. Průběh doladění sítě pomocí LVQ můžeme ovlivnit nastavením parametru Alfa LVQ v dialogu Parametry sítě, který odpovídá parametru α v rovnici (2.30). Lze zvolit i jeho automatickou adaptaci, která implicitně začíná na hodnotě 0,02 a dále probíhá podle následujícího vzorce:
α (t ) = 0,9993 * α (t −1)
(4.15)
Koeficient 0,9993 byl převzat z rovnice (4.14).
Obr. 4.2 Konfigurace síťě před spuštěním LVQ (vlevo) a po jeho ukončení (vpravo)
Obr. 4.3 Posuny výstupních neuronů v průběhu doučení sítě pomocí LVQ
IMPLEMENTACE
37
4.1.6 Vizualizační režimy pro lineární perceptron, backpropagation a RBF Pro tyto tři modely neuronových sítí, tj. pro lineární perceptron, backpropagation a RBF, NetVisualiser umožňuje volbu mezi několika viziualizačními režimy. Jsou to: • Výstup neuronové sítě • Správnost klasifikace neuronové sítě • Mřížka • Hranice • Aproximace funkce – diskrétní • Aproximace funkce – spojitá • Zobrazování stopy při překreslování • Vypnutá vizualizace Každý z těchto režimů má jiné vlastnosti a každý z nich je vhodný pro jiný úhel pohledu na proces adaptace. Pro klasifikační úlohy neuronových sítí jsou určeny první čtyři režimy, pro aproximační úlohy pak následující dva režimy a poslední dva režimy lze využít v obou typech úloh.
4.1.6.1 Výstup neuronové sítě Tento režim přiřazuje tréninkovým vzorům zabarvení podle toho, jak je klasifikuje síť. Jestliže síť klasifikuje příklad kladně, tj. výstup prvního výstupního neuronu sítě je větší než práh zvolené přechodové funkce, je mu přiřazena barva modrá. V opačném případě bude příklad zobrazen barvou červenou. Tento režim je vhodný, pokud uživatel potřebuje vidět aktuální ohodnocení tréninkových vzorů, a nepotřebuje mít k dispozici komplexní mapu klasifikací. Režim není výpočetně náročný a je vhodný pro online sledování adaptivní fáze.
4.1.6.2 Správnost klasifikace neuronové sítě V tomto režimu je kritériem pro přiřazení barvy tréninkovým vzorům správnost klasifikace sítě. Jestliže síť klasifikuje příklad kladně a požadovaná klasifikace tréninkového vzoru je taktéž větší než práh aktuální přechodové funkce, pak je vzor zobrazen barvou modrou. V opačném případě je vzor zbarven červeně. V případě, že jsou všechny příklady zbarveny modře, je chyba sítě nulová. Režim je využíván, pokud je tréninková množina příliš různorodá na to, aby si uživatel zapamatoval, které vzory byly ohodnoceny kladně a které záporně a není si tudíž jistý, do jaké míry je současná klasifikace na výstupu sítě správná a do jaké míry nikoliv. Tento režim není taktéž výpočetně náročný a je vhodný taktéž pro online sledování adaptivní fáze.
38
IMPLEMENTACE
4.1.6.3 Mřížka Mřížka poskytuje uživateli komplexní přehled o mapě klasifikací, tj. o tom, ve kterých bodech dává síť výstup kladný a ve kterých záporný. Protože z konfigurace složitější vícevrstvé sítě nelze nekomplikovaným způsobem zjistit hranici oddělující různé klasifikace, jak je tomu například u lineárního perceptronu, byla pro tuto potřebu vytvořena virtuální datová množina, v níž jsou vzory rovnoměrně rozmístěny do čtvercové topologie, tj. mřížky. Tato datová množina je pak předkládána neuronové síti v aktivním režimu a její oklasifikování se následně zobrazí na obrazovce. Rozsah hodnot vstupů mřížky se přizpůsobuje tréninkové
množině, tj. pokud uživatel normalizuje tréninkovou množinu do intervalu (0,10) bude se i
mřížka do tohoto intervalu automaticky normalizovat. Ukázku zobrazení režimu mřížky vidíme na obrázku Obr. 4.1, kde byl pro vstup ze souboru XOR4.dat, který simuluje klasifikaci logickou funkcí vylučovací disjunkce, použit model neuronové sítě backpropagation. Mřížka je vhodná pro sledování komplexní mapy klasifikací na tréninkové množině. Pro svou výpočetní složitost není příliš vhodná pro online sledování učení, neboť by se v tomto režimu výrazně zpomalilo. Tento režim je vhodný spíše pro občasné nahlížení do procesu učení, tzn. v průběhu adaptace se sleduje graf chyby sítě. V případě výraznější změny chyby nebo jen potřeby nahlédnout do mapy klasifikací, se pak lze do tohoto režimu přepnout.
Obr. 4.1 Zobrazení klasifikace sítě v režimu mřížka
39
IMPLEMENTACE
4.1.6.4 Hranice Vizualizační režim hranice je založen na režimu předchozím. Tento režim využívá stejnou virtuální datovou množinu pro zjištění hranic rozdílných klasifikací. V tomto režimu prochází algoritmus každý vzor v mřížce a zjišťuje, zda mají sousední vzory shodnou či odlišnou klasifikaci než aktuální vzor, přičemž se zároveň sestavuje hranice klasifikací. Přesnost hranice je závislá na počtu prvků v mřížce, čím více prvků bude mřížka mít, tím jemnější a přesnější hranice bude. Cílem tohoto režimu není ukázat hranici klasifikací exaktně, ale vymezit ji pouze přibližně a dát tak uživateli informaci o tom, kde a jak se hranice pohybuje. Omezení tohoto režimu jsou stejná jako u režimu mřížka, i když je tento režim nepatrně rychlejší a vhodný spíše pro nahlížení než online sledování učení. Rozdíl oproti režimu mřížka spočívá jednak už ve zmíněné rychlosti, a jednak v tom že režim mřížka, i přesto, že vykresluje nejdříve mřížku a pak teprve tréninkové a testovací vzory, může rozmístění vzorů mírně znepřehlednit. Na obrázku Obr. 4.1 je znázorněna situace identická se situací na obrázku Obr. 4.1, jen s tím rozdílem, že jako vizualizační režim byla zvolena místo mřížky hranice.
Obr. 4.1 Zobrazení klasifikace sítě v režimu hranice
4.1.6.5 Aproximace funkce – diskrétní Pro aproximaci funkcí slouží následující dva vizualizační režimy. Při využití těchto režimů musí mít tréninková množina velikost vstupu i výstupu rovnu jedné. V prvním režimu jsou tréninková data znázorněna jako body, přičemž na pomyslnou osu x se vynáší vstup a na osu y
40
IMPLEMENTACE
hodnota požadovaného výstupu. Pro zobrazení výstupu sítě na tréninkových datech se použije virtuální datová množina se stejným rozsahem vstupů jako má množina tréninková. Virtuální datová množina obsahuje 100 vzorků rovnoměrně rozmístěných po vstupním prostoru tréninkové množiny. Tréninková data nejsou vhodná pro vizualizaci, protože mohou obsahovat příliš málo příkladů, což by zapříčinilo nepřesnou vizualizaci výstupu sítě, anebo naopak příliš velké množství příkladů, což by mělo za následek nárůst doby potřebné k překreslování obrazovky v průběhu učení neuronové sítě. Na obrázku Obr. 4.1 můžeme vidět tento režim při aproximaci funkce sinus, zadané pomocí 50 tréninkových vzorů, pomocí RBF modelu neuronové sítě. Modré body znázorňují vzory z tréninkové množiny, červená čára znázor ňuje aktuální výstup sítě na virtuální datové množině. Tento režim je pro svou grafickou a výpočetní nenáročnost vhodný pro online sledování učení. Lze ho využít v případě, že uživatel chce vidět přesné rozmístění tréninkových vzorů a porovnávat tak například požadované výstupy vzorů s výstupem sítě právě v těchto bodech.
Obr. 4.1 Aproximace funkce sinus v diskrétním zobrazení
4.1.6.6 Aproximace funkce – spojitá Druhý z vizualizačních režimů pro znázornění aproximace funkce nezobrazuje tréninková data jako samostatné body, ale tyto body jsou propojeny do jediné čáry. Princip vynášení bodů je stejný jako v předchozím případě. Každý bod je spojen s následujícím přímkou, což vyvolává dojem, že je aproximovaná funkce definována v každém bodě zobrazeného intervalu. Samozřejmě tato čára nemusí přesně odpovídat aproximované funkci, ta může mít mezi
41
IMPLEMENTACE
jednotlivými body například tvar oblouku. Čím více bude vzorů v tréninkové množině a tedy čím menší budou rozestupy mezi nimi, tím více se tato čára přiblíží skuteč né hodnot ě. Tento režim je vhodný v případě, že uživatel chce porovnat výstup sítě s požadovanými výstupy v bodech, které nejsou zadány tréninkovou množinou. Lze ho bez obtíží využít i pro online sledování adaptivního režimu. Na obrázku Obr. 4.1 je pomocí tohoto vizualizačního režimu znázorněna ta samá situace jako na obrázku Obr. 4.1.
Obr. 4.1 Aproximace funkce sinus ve spojitém zobrazení
4.1.6.7 Zobrazování stopy při překreslování Tento vizualizační režim lze využít jak pro klasifikační, tak pro aproximační úlohy. V případě, že se v průběhu adaptivního režimu vykreslují prvky nebo čáry, které mění svou pozici, lze v tomto režimu sledovat jejich předešlé pozice a uživatel si tak může udělat představu o tom, jak učení dosud probíhalo a kde docházelo k nejčastějším a nejvýraznějším změnám. Zobrazování stopy je vhodné pro online učení a lze ho kombinovat s ostatními vizualizačními režimy. Ukázku tohoto režimu můžeme vidět na obrázku Obr. 4.2 či Obr. 4.3.
IMPLEMENTACE
42
4.1.6.8 Vypnutá vizualizace Poslední z vizualizačních režimů vypne jakoukoliv vizualizaci a umožní tak rychlejší učení neuronové sítě. V případě, že se nám zdá, že adaptivní režim probíhá při zapnuté vizualizaci pomalu, tak ji můžeme vypnout a sledovat vývoj učení například jen na grafu chyby sítě. Vizualizaci lze během učení kdykoliv znovu zapnout.
4.2 GaVisualiser Pro implementaci programu GaVisualiser jsem použil knihovnu GAlib. Knihovna je volně ke stažení na adrese http://lancet.mit.edu/ga/ a lze ji volně použít jak pro nekomerční, tak i komerční účely. Knihovna je napsána v jazyce C++ a kromě zdrojových kódů obsahuje i rozsáhlou dokumentaci ve formátu HTML a PDF. Dokumentace je zde velmi důležitá, neboť knihovna je velmi rozsáhlá, obsahuje několik typů genomů (tak se v této knihovně nazývají chromozómy), 1D, 2D a 3D pole, seznam a strom. Genom může obsahovat několik těchto základních typů. Pro každý z uvedených typů existují vlastní genetické operátory, které si programátor může předefinovat. Knihovna dále obsahuje pět typů genetických algoritmů, z nichž byly všechny implementovány. Pro demonstraci těchto genetických algoritmů a genetických operátorů a experimentování s nimi bylo implementováno pět funkcí, na kterých lze vše uvedené vyzkoušet. Pro implementaci byly použity genomy, které pracují s reálnými čísly, protože právě ony se pro vizualizaci nejlépe hodí. Popis implementovaných genetických operátorů, genetických algoritmů a funkcí je uveden v následujících podkapitolách. Program GaVisualiser poskytuje uživateli vizuální přehled aktuálního stavu populace a rozmístění jejich jedinců. Jedinci jsou znázorněni šedými body, resp. malými čtverečky. Nejlepší jedinec z aktuální populace je znázorněn větším červeným čtverečkem, což je zřetelně znát na obrázcích Obr. 4.1 a Obr. 4.1. V případě existence více populací zároveň, jsou nejlepší jedinci těchto populací znázorněni odlišnou barvou a prvky jim příslušných populací jsou znázorněny jiným odstínem téže barvy, viz obrázek Obr. 4.1. Oblasti globálních minim jsou znázorněny červenými křížky, nebo v případě spojitých globálních minim červenou tenkou čarou. Cílem evoluce je přiblížení se jedinců v populaci těmto globálním minimům.
4.2.1 Genetický algoritmus Struktura genetického algoritmu, tak jak je implementován v knihovně GAlib, je znázorněna na obrázku Obr. 4.1. Tato architektura se nijak výrazně neliší od jiných aplikací genetických algoritmů, ani od struktury genetického algoritmu uvedené v kapitole 3.
43
IMPLEMENTACE
Vytvoření poč áteč ní populace
Výběr jedinc ů pro k řížení
Křížení rodičů a vytvoření potomk ů
Mutace potomků
Vložení potomk ů do populace
Slpně ní ukonč ovací podmínky
Konec
Obr. 4.1 Genetický algoritmus v GAlib
V programu GaVisualiser je implementováno všech pět typů genetických algoritmů knihovny GAlib a stabilní genetický algoritmus je implementován, včetně jedné modifikace. Uživatel má tedy na výběr z několika typů genetických algoritmů. Jsou to: • Jednoduchý (simple) • Stabilní (steady–state) • Stabilní s podporou rozmanitosti (steady–state with sharing) • Crowding • Přírustkový (incremental) • Deme – více populací (Deme – multi population) Všechny tyto algoritmy kromě posledně jmenovaného pracují s jednou populací jedinců. Hlavní rozdíl mezi nimi spočívá ve způsobu vytváření nové generace jedinců.
4.2.1.1 Jednoduchý (simple) Tento genetický algoritmus je „jednoduchým“ genetickým algoritmem, který popsal Gilbert ve své knize [Golgberg]. Algoritmus používá nepřekrývající se populace, tedy každá generace, kterou vytvoří je zcela nová. Algoritmus nejdříve vybere jedince z předešlé generace, a poté je zkříží a vytvoří tak jedince pro populaci novou. Uvedený algoritmus podporuje elitářství, což znamená, že nejlepší jedinec z každé generace je přenesen do generace následující. Algoritmus dobře konverguje především se strategií výběru nejlepší a turnaj. Dobré výsledky s téměř jakýmikoli parametry poskytuje především pro Schwefelovu funkci.
4.2.1.2 Stabilní (steady–state) Tento genetický algoritmus je podobný tomu, který popsal DeJong. Používá překrývající se populace s 50% překrytím. Každou generaci vytváří algoritmus provizorní populaci jedinců, kteří jsou přidáni do předešlé generace a následně jsou odstraněni jedinci s nejmenším skóre tak, aby velikost populace zůstala konstantní. Pokaždé se tedy nahradí slabší polovina jedinců jedinci nově vytvořenými křížením a mutací. Algoritmus dobře konverguje na všech funkcích, problémy má jen s deterministickou strategií výběru.
IMPLEMENTACE
44
4.2.1.3 Stabilní s podporou rozmanitosti (steady–state with sharing) Jedná se o modifikaci předchozího algoritmu, kdy se také nahrazuje slabší polovina jedinců jedinci novými. Tento genetický algoritmus podporuje vytváření druhů, neboli tříd jedinců. Při určování skóre jedince se navíc jedinec porovnává s ostatními členy populace. Jestliže jsou v populaci jíní podobní jedinci je jeho skóre je sníženo. Podobnost jedinců se určí pomocí tzv. odlišnostní funkce, která určuje, jak jsou si dva jedinci podobní. Podrobnosti o této funkci najdete na straně 75 manuálu knihovny GAlib [GAlib]. Účinek tohoto algoritmu lze dobře pozorovat na Schwefelově funkci, kde jedinci obsadí více lokálních minim, a na 1-dimenzionální funkci, kde jedinci obsadí všechny lokální minima, viz obrázek Obr. 4.1.
Obr. 4.1 Obsazení lokálních minim jedinci při použití stabilního GA s podporou rozmanitosti.
4.2.1.4 Přírustkový (incremental) Tento genetický algoritmus je podobný těm algoritmům, které jsou založeny na modelu GENITOR, viz. [Genitor1] nebo [Genitor2]. Jedná se genetický algoritmus s překrýváním, i když velmi malým. V každé generaci se nahrazují pouze dva nejhorší jedinci, a to dvěma jinými jedinci nově vzniklými křížením a případnou následnou mutací.
IMPLEMENTACE
45
Algoritmus konverguje dobře na všech funkcích a se všemi genetickými operátory. Rychlost konvergence je také dobrá, pouze u 1-dimenzionální funkce konverguje algoritmus pomaleji.
4.2.1.5 Crowding Tento genetický algoritmus vybírá z populace dvojce jedinců, tzn. rodiče, dokud nevyčerpá celou populaci. Poté vytvoří postupně z každé dvojce rodičů jednoho potomka a následně ho porovná s rodiči. U rodiče, který je mu více podobný, porovná jeho skóre se skóre potomka a v případě, že rodič má skóre horší, nahradí ho jeho potomkem. Ihned po křížení rodičů se provede případná mutace potomka. U tohoto algoritmu se tedy nahradí vždy nejvýše jedna polovina populace, ale většinou je procento nahrazených jedinců mnohem menší. Algoritmus dobře konverguje u všech funkcí a se všemi genetickými operátory. Nevýhodou je, že konverguje pomalu, což je dáno tím, že se v každé generaci nahradí pouze velmi malá část populace.
4.2.1.6 Deme – více populací (Deme – multi population) Tento genetický algoritmus podporuje evoluci více populací. Každá populace používá pro evoluci stabilní genetický algoritmus, viz. 4.2.1.2. Navíc jsou každou generaci přesunuti někteří jedinci z jedné populace do populace jiné. Algoritmem pro migraci je deteministic stepping-stone, který z každé populace migruje pevný počet nejlepších jedinců, v našem případě 5, do sousední populace. Navíc se hlavní populace aktualizuje každou generaci nejlepšími jedinci ze všech ostatních populací. Konverguje výborně a rychle na všech funkcích, pouze občas během testování se stalo, že jedna z populací se „zapomněla“ a nekonvergovala ke globálnímu minimu, jak je znázorněno na levém obrázku na Obr. 4.1, kde modře znázorněná populace nekonvergovala ke globálnímu minimu. Na pravém obrázku na Obr. 4.1 jedinci obsadili téměř všechna, i méně význačná lokální minima, což můžeme srovnat s grafem účelové funkce na témže obrázku. Nevýhodou tohoto algoritmu, či spíše jeho implementace je, že knihovna GAlib nevrací aktuální hodnoty skóre populací, takže graf evoluce nemusí být vždy korektní.
46
IMPLEMENTACE
Obr. 4.1 Ukázka evoluce pomocí genetického algoritmu DEME.
4.2.2 Genetické operátory
4.2.2.1 Výběr Cílem operace výběru (selekce) je zvolit ty jedince, ze kterých budou vytvořeni jedinci noví. Existuje několik způsobů, jak jednice vybrat. V programu GaVisualiser si lze zvolit z následujících typů selekcí: • Nejlepší. Tento operátor vždy vybere z populace jedince s nejvyšším skórem. • Ruleta. Tato metoda výběru jedince je založena na poměru skóre jedince vzhledem ke zbytku populace. Čím vyšší skóre jedinec má, tím větší má šanci na to, že bude vybrán. Pravděpodobnost i-tého jedince pi, že bude vybrán, je:
pi =
ei n
(4.16)
ej j =1
•
•
kde n je počet jedinců v populaci a ej je skóre j-tého jedince. Z pohledu rulety si to můžeme představit tak, že ruletové kolo rozdělíme na výseče, odpovídajícím jedincům v populaci o velikosti úměrné jejich skóre. Turnaj. Tento selektor používá předchozí metodu k výběru dvou jedinců, z nichž vybere toho s vyšším skóre. Tato metoda typicky vybere častěji jedince s vyšším skóre, než metoda rulety. Deterministický. Deterministický selektor užívá dvoufázové selekční procedury. V první fázi se vypočítá předpokládané skóre jedince. Dočasná populace je naplněna jedinci s nejvyššími očekávanými hodnotami. Ostatní pozice jsou obsazeny původními
47
IMPLEMENTACE
•
•
jedinci s nejvyšší pozicí v seznamu setříděném podle desetinné části jejich skóre. Druhá fáze je uniformní náhodnou selekcí z dočasné populace. Stochastický. Tento selektor využívá také dvoufázové selekční procedury. První fáze vypočítá předpokládané skóre a naplní dočasnou populaci jedinci s nejvyššími hodnotami. Každá desetina očekávaného skóre dává jednici pravděpodobnost být vybrán. Například jedinec se skórem 1,4 má jistou jednu pozici a dále má 40 procentní šanci na druhou pozici. Druhá fáze je opět uniformní náhodnou selekcí z této dočasné populace. Uniformní. Tento selektor vybírá jedince náhodně z celé populace. Každý jedinec má pravděpodobnost p, že bude vybrán:
p =
1 n
(4.17)
kde n je počet jedinců v populaci.
4.2.2.2 Křížení V programu GaVisualiser si uživatel může vybrat ze třech standardních typů křížení. Jsou to: •
Jednobodové. Při tomto typu křížení se vybere náhodně jedna pozice, na níž jsou jedinci rozděleni, a jejich části jsou pak navzájem vyměněny, jak je znázorněno na obrázku Obr. 4.1.
Obr. 4.1 Schéma jednobodového křížení
•
Dvoubodové. Dvoubodové křížení je obdobou křížení jednobodového, jen s tím rozdílem, že jsou náhodně vybrány dvě dělící pozice a kombinace jedinců se provede podle obrázku Obr. 4.2.
48
IMPLEMENTACE
Obr. 4.2 Schéma dvoubodového křížení
•
Uniformní. U uniformního křížení je pro každý gen náhodně určeno, do kterého z nových jedinců se zařadí.
4.2.2.3 Mutace Význam mutace v GA byl již popsán v úvodu. V programu GaVisualiser jsou implementovány tři typy mutací, viz. níže. Tyto mutace pracují tak, že každého jedince prochází gen po genu a každý jejich gen má pravděpodobnost p, že bude změněn. Pravděpodobnost p uživatel definuje při inicializaci genetického algoritmu. Jakým způsobem bude gen změněn, závisí na typu mutace. Typy implementovaných mutací jsou: • Uniformní. Uniformní mutace mění hodnotu genu u jedince zcela náhodně v definovaném rozmezí. • Hranicová. Tato mutace mění hodnotu genu, se stejnou pravděpodobností, buď na horní nebo dolní hranici povoleného intervalu. • Gaussova. Jak název napovídá používá se při mutaci genu Gaussova rozložení. Nová hodnota genu je určena z Gausova rozložení, kde střed rozložení je v nule a rozptyl je roven staré hodnotě genu. Nová hodnota musí ležet v předem definovaném rozmezí účelové funkce. Pravděpodobnost mutace p je implicitně nastavena na 0,01. Pokud chce uživatel pozorovat rozdíl mezi jednotlivými mutacemi, doporučuje se nastavit pravděpodobnost mutace přibližně na 0,5 a pravděpodobnost křížení na 0. Například u hranicové mutace lze takto pozorovat, jak mutace posouvá jedince do krajních hodnot povoleného rozmezí, což je zřetelné na obrázku Obr. 4.1.
49
IMPLEMENTACE
Obr. 4.1 Průběh evoluce při extrémním použití hranicové mutace
4.2.3 Funkce Pro demonstraci vlastností genetických algoritmů a genetických operátorů jsou v programu GaVisualiser implementovány následující funkce: • Himmelblauova • Sinus • Schwefelova • Vlnění • 1-dimenzionální Tyto funkce jsou implementovány pomocí účelových funkcí ohodnocujících jednotlivá řešení, jedince.
4.2.3.1 Himmelblauova funkce Pro demonstraci optimalizačních problémů se často využívá Himmelblauova funkce, která má jedno globální a několik lokálních minim. Tato funkce je dána následujícím předpisem:
(
) (
f ( x, y ) = x 2 + y − 11 + x + y 2 − 7 Její grafy můžeme vidět na obrázku Obr. 4.1.
2
)
2
(4.18)
50
IMPLEMENTACE
Obr. 4.1 Grafy Himmelblauovy funkce
Na uvedeném obrázku jsou dobře znatelná různá minima této funkce. Z hlediska matematické analýzy má funkce tři minima lokální a jedno minimum globální.
f (3,2) = 0
Globální minimum: Lokální minima:
f (− 3.78,−3.28) = 0.0054
f (− 2.81,−3.13) = 0.0085
f (3.85,−1.85) = 0.0011
Implementace účelové funkce Himmelblauovy funkce pak vypadá následovně:
((
) ( 2
− g12 + g 2 − 11 + g1 + g 22 − 7 f (g ) = 2000
) ) + 2000 2
(4.19)
Kde g je jedinec a g1, resp. g2, označuje první, resp. druhý gen jedince g. Konstanta 2000 normalizuje funkční hodnotu do intervalu 0,1 . Interval funkce v programu GaVisualiser v ně mž probíhá evoluce je − 6,6 .
4.2.3.2 Sinus Tato funkce má jedno globální minimum ve tvaru funkce sinus. Funkce je dána následujícím předpisem:
f ( x ) = sin x V programu GaVisualiser je realizována pomocí následující účelové funkce:
(4.20)
51
IMPLEMENTACE
f (g ) =
10 − 3 ⋅ sin (g1 ) − g 2 10
(4.21)
Kde g je jedinec a g1, resp. g2, označuje první, resp. druhý gen jedince g. Konstanta 10 normalizuje funkční hodnotu do intervalu 0,1 a konstanta 3 zvýrazňuje rysy funkce sinus. Interval funkce v programu GaVisualiser v ně mž probíhá evoluce je − 6,6 . Graf účelové funkce můžeme vidět na obrázku Obr. 4.1.
Obr. 4.1 Účelová funkce pro sinus.
4.2.3.3 Schwefelova funkce Schwefelova funkce klame v tom, že globální minimum je geometricky vzdáleno, přes parametrický prostor od dalšího nejbližšího lokálního minima, což způsobuje, že jsou prohledávací algoritmy potenciálně náchylné ke konvergování špatným směrem. Tato funkce je dána následujícím předpisem: n
(
f ( x ) = − x(i ) ⋅ sin i =1
kde − 500 ≤ x (i ) ≤ 500 . Graf funkce je znázorněn na obrázku Obr. 4.1.
x(i )
)
(4.22)
52
IMPLEMENTACE
Obr. 4.1 Graf Schwefelovy funkce a příslušné účelové funkce
Funkce má jedno globální miminum v bodě (420.96, 420.96), které je na grafu i v programu umístěno v pravém horním rohu, a dále spoustu minim lokálních, z nichž jsou nejvýznačnější dvě, a to přibližně na souřadnicích (200,50) a (50,200) v grafu účelové funkce, a jedno na souřadnicích (50,50) na obrázku Obr. 4.1. Tato funkce je implementována pomocí následující účelové funkce:
f (g ) =
g1 ⋅ sin
g1 + g 2 ⋅ sin
g 2 + 2 ⋅ 420.96
4 ⋅ 420.96
(4.23)
kde g je jedinec a g1, resp. g2, označuje první, resp. druhý gen jedince g. Konstanta 420,96 normalizuje funkční hodnotu do intervalu 0,1 . S touto funkcí si i přes její složitost poradily všechny implementované genetické algoritmy.
4.2.3.4 Vlnění Tato funkce je někdy také nazývána mexický klobouk, a to pro její graf, který je mu podobný, viz. obrázek Obr. 4.1.
53
IMPLEMENTACE
Obr. 4.1 Grafy účelové funkce vlnění
Tato funkce je implementována pomocí následující účelové funkce:
(sin f ( g ) = 0,5 −
g12 + g 22
(1 + 0,001 ⋅ (g
2 1
) − 0,5 2
+ g 22
))
2
(4.24)
kde g je jedinec a g1, resp. g2, označuje první, resp. druhý gen jedince g. Funkce má jedno globální maximum ve středu grafu přibližně na souřadnicích (52,52). Každý další kruh má své maximum o něco níže, viz. pravý graf na obrázku Obr. 4.1.
4.2.3.5 1-dimenzionální funkce Tato funkce je dána předpisem:
f ( x ) = x ⋅ sin
1 x
(4.25)
a obsahuje na daném intervalu dvě lokální a jedno globální minimum, viz obrázek Obr. 4.1. Název 1-jednodimenzionální je použit proto, že každý jedinec obsahuje pouze jeden gen, který reprezentuje jeho pozici v intervalu, tj. hodnotu x.
54
IMPLEMENTACE
Obr. 4.1 Graf jednodimenzionální funkce
Pro tuto účelovou funkci je výhodné vytvořit počáteční populaci s velmi malým počtem jedinců, např. s pěti jedinci, na kterých lze lépe pozorovat konvergenci nejlepšího jedince ke globálnímu minimu.
ZÁVĚR
55
5 Závěr Během jednoho roku se podařilo vytvořit dva programy pro demonstraci vlastností neuronových sítí a genetických algoritmů a experimentování s nimi. Na internetu lze sice najít několik programů zabývajících se neuronovými sítěmi či genetickými algoritmy, které obsahují do jisté míry i jejich vizualizaci. Jedná se však většinou o programy zabývající se pouze konkrétním modelem neuronové sítě či typem genetického algoritmu, anebo pouze určitým problémem. Programy, které zpracovávají tuto problematiku komplexněji, však chybí, nebo se jedná o komer ční produkty, jejichž primárním cílem není sloužit k výukovým účelům. Vytvořené programy zaplňují tuto mezeru a dávají tak studentům i odborníkům uživatelsky příjemný nástroj, který jim, především díky schopnosti vizualizace, bude prospěšný pro hlubší pochopení této problematiky. Cílem těchto programů nebylo postihnout všechny modely neuronových sítí a typy genetických algoritmů, protože jejich škála je dnes opravdu široká. Proto program NetVisualiser je zaměřen na nejpoužívanější modely neuronových sítí a na modely, které jsou pro výuku neuronových sítí přínosem. Stejně tak program GaVisualiser demonstruje nejznámější typy genetických algoritmů a genetických operátorů. Prostor pro další rozšíření programů lze spatřovat především v přidání dalších modelů neuronových sítí do programu NetVisualiser, v rozšíření jeho konfiguravatelnosti a konfiguravatelnosti neuronové sítě. V případě rozšiřování programu GaVisualiser lze uvažovat o rozšíření množiny účelových funkcí, přidání nástroje pro přímou práci s jedinci v populaci, či rozšíření 2D zobrazení populace na 3D.
LITERATURA
56
Literatura [Buckles] [Desieno]
[Fausett] [GAlib] [Genitor1] [Genitor2] [Golgberg] [Hassoun] [Kohonen1] [Kohonen2] [McCulloch]
[Minsky] [Novák] [Rojas] [Rummelhart] [Šíma-Neruda]
Bill P.Buckles and Frederick E. Petry: Genetic Algorithms, IEEE Press, 1992 D.Deseino: Adding a consience to competitive learning, v Proceedings of the International Konference on Neural Network, volume 1, strany 117-127, IEEE Press, 1988 Laurene Fausett: Fundamentals of Neural Networks, Archticture, Algorithms and Applications, Prentice Hall, 1994 Galib Version 2.4, Document Revision B, viz přiložené CD, 1996 http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/genetic/ ga/systems/genitor/0.html http://www.wior.uni-karlsruhe.de/Bibliothek/Software_for_OR/ Genetic_Algorithms/pub/Genitor.html David E. Golgberg: Genetic Algorithms in Search, Optimazation & Machine Learning, Addison Wesley, 1989 Mohamed h. Hassoun: Fundamentals of artifical neural network, MIT press, 1995 Teuvo Kohonen: Self-organized formation of topologically correct feature maps., Bilogical Cybernetics, 1982 Teuvo Kohonen: Self-organizing maps Third edition, Springer, 2001 W. S. McCulloh and W. Pits: A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5:115-133, 1943 M. L. Minksy and S. A. Papert: Perceptrons. MIT Press, 1969 Mirko Novák a kolektiv: Umělé neuronové sítě teorie a aplikace, C.H.Beck, 1998 R.Rojas: Neural Network, A Systematic Introduction, Springer, 1996 D. E. Rummelhart, G. E. Histon, and R. J. Williams: Learning internal representations by error propagation. MIT Press, 1986 Jiří Šíma & Roman Neruda: Teoretické otázky neuronových sítí, Matfyzpress, 1996
OBSAH PŘILOŽENÉHO CD
57
A. Obsah přiloženého CD Přiložené CD obsahuje následující adresáře a podadresáře: • Programy o GaVisualiser Help – obsahuje nápovědu k programu GaVisualiser. GaVisualiser.exe – spustitelný soubor programu GaVisualiser. o NetVisualiser Data – obsahuje data odkazovaná v diplomové práci. Help – obsahuje nápovědu k programu NetVisualiser. NetVisualiser.exe – spustitelný soubor programu NetVisualiser. • Zdrojové soubory o GaVisualiser – obsahuje projekt a zdrojové soubory pro kompilaci programu GaVisualiser v prostředí MS Visual C++ 6.0. o GAlib – obsahuje soubory potřebné pro kompilaci knihovny GAlib. o NetVisualiser – obsahuje projekt a zdrojové soubory pro kompilaci programu NetVisualiser v prostředí MS Visual C++ 6.0. o Knihovny pro překlad – knihovny potřebné pro překlad v prostředí MS Visual C++ 6.0 (standardně jsou dodávány s MS Visual Studiem 6.0). o All.dsw – workspace pro MS Visual C++ 6.0 obsahující oba projekty. • Dokumenty o HTML – obsahuje HTML verzi diplomové práce. o DP-PetrMartan2002.doc – diplomová práce ve formátu MS Word XP(2002). Lze otevřít i v MS Word 97 a MS Word 2000. Pro věrné zobrazení doporučuji používat tento dokument. o DP-PetrMartan2002.pdf – diplomová práce ve formátu PDF. o DP-PetrMartan2002.ps – diplomová práce ve formátu PS. o galibdoc.pdf – dokumentace ke knihovně GAlib • Ostatní o Screenshots – screenshoty z vytvořených programů a z programu Matlab 6 použité i nepoužité v diplomové práci.
58
NETVISUALISER - MANUÁL
B. NetVisualiser - manuál Cílem tohoto manuálu je seznámit uživatele s významy všech příkazů a ikon, popsat ty nejdůležitější dialogy a poskytnout uživateli návod, jak s těmi nejdůležitějšími dialogy a příkazy pracovat.
Příkazy pro práci s neuronovou sítí Všechny příkazy pro práci s neuronovou sítí jsou umístěny v menu Síť. Ty nejdůležitější z nich jsou pak přístupné z nástrojové lišty Síťová lišta. Příkaz Nová Reinicializace Otevřít Uložit Uložit jako Kohonen – LVQ
Kohonen – klasifikace RBF – posun RBF jednotek
Ikona Popis Vytvoření nové neuronové sítě. Přesný postup je popsán v kapitole Vytvoření neuronové sítě. Nastavení konfigurace sítě do počátečního náhodného stavu. Načtení uložené neuronové sítě ze souboru. Program načítá pouze soubory vytvořené pomocí programu NetVisualiser. Uložení aktuální neuronové sítě do souboru, ze kterého byla načtena, nebo do kterého již byla předtím uložena. Uložení aktuální neuronové sítě do souboru s volbou cesty a jména souboru. Zapnutí/vypnutí LVQ režimu (třetí fáze učení) pro Kohonenovu mapu nebo Kohonenovu síť. Návod: Jestliže je režim aktivní, můžeme neuronovou síť učit pomocí standardních příkazů pro učení sítě. Provedení klasifikace výstupních neuronů (druhé fáze učení) pro Kohonenovu mapu nebo Kohonenovu síť. Zapnutí/vypnutí režimu pro posun RBF jednotek pomocí myši. Návod: Jestliže je režim aktivní, klikneme levým tlačítkem myši na RBF jednotku, kterou chceme posunout. Jako potvrzení jejího výběru se RBF jednotka obarví červenou barvou. Poté klikneme levým tlačítkem myši na místo, kde chceme tuto RBF jednotku umístit. Program RBF jednotku přesune a je připraven přemístit další RBF jednotku.
Příkazy pro učení neuronové sítě Všechny příkazy pro učení neuronové sítě jsou umístěny v menu Učení a všechny jsou také přístupné z nástrojové lišty Učící lišta.
NETVISUALISER - MANUÁL
Příkaz Jeden příklad
Všechny příklady jednou Učení – pomalé
Učení – rychlé
Ukončení učení Ukončovací podmínka
Křížové ověření
59
Ikona Popis Předložení jednoho náhodně vybraného příkladu neuronové síti v adaptivním režimu. Poznámka: Příklady jsou vybírány náhodně s podmínkou, aby byly postupně vybrány všechny příklady z tréninkové množiny. Postupně se v náhodném pořadí předloží síti k učení všechny příklady z tréninkové množiny. Spuštění plynulého učení neuronové sítě. Neuronové síti se předkládají příklady v náhodném pořadí. Po vyčerpání všech příkladů z tréninkové množiny se předkládají síti na vstup příklady v jiném náhodném pořadí. Učení se ukončí v případě splnění ukončovací podmínky. Interval mezi průchody celé tréninkové množiny je 200 ms. Příkaz se chová stejně jako předcházející příkaz pouze s tím rozdílem, že interval mezi jednotlivými průchody tréninkovou množinou je 10 ms. Zastavení probíhajícího učení. Nastavení ukončovací podmínky. Zde můžeme nastavit podmínku zastavení učení buď na počet průchodů daty, minimální velikosti chyby neuronové sítě a velikosti změny této chyby, nebo na kombinaci všech uvedených podmínek. Spuštění učení v režimu křížového ověření. Popis je uveden v kapitole Křížové ověření – crossvalidace.
Příkazy pro práci s daty Všechny příkazy pro práci s daty jsou umístěny v menu Data. Ty nejdůležitější z nich jsou pak přístupné z nástrojové lišty Datová lišta.
Příkaz Trénovací Testovací Normalizace Uložit
Ikona Popis Načtení tréninkových dat ze souboru. Soubor musí být ve formátu uvedeném v kapitole Formáty dat pro práci se soubor. Načtení testovacích dat ze souboru. Soubor musí být ve formátu uvedeném v kapitole Formáty dat pro práci se soubor. Normalizace dat do zadaného intervalu. Uložení tréninkových nebo testovacích dat do souboru, ze kterého byly načteny, nebo již předtím uloženy. Formát uložených dat je uveden v kapitole Formáty dat pro práci se
NETVISUALISER - MANUÁL
Uložit jako
Generovat Trénovací Lineárně sep.
Generovat Trénovací Sinus
60
soubor. Uložení tréninkových nebo testovacích dat do souboru s volbou cesty a jména souboru. Formát uložených dat je uveden v kapitole Formáty dat pro práci se soubor. Generování lineárně oddělitelných tréninkových dat. Počet příkladů lze zvolit v dialogu, který se následně zobrazí. Poznámka: Vygenerované příklady mají dvě vstupní hodnoty v rozmezí 0 a 1 a jednu výstupní hodnotu, která je rovna buď 0 nebo 1. Vygenerovaná data jsou určena pro klasifikační úlohy. Generování tréninkových dat simulující funkci sinus. Počet příkladů lze zvolit v dialogu, který se následně zobrazí. Poznámka: Vygenerované příklady mají jednu vstupní hodnotu odpovídající úhlu v radiánech a jednu výstupní hodnotu odpovídající hodnotě funkce sinus v tomto bodě. Po vygenerovaní jsou data automaticky normalizována do intervalu 0,1 . Vygenerovaná data
Generovat Testovací
Vyčistit Přidat příklad
Smazat příklad
Prohlížeč
jsou určena pro aproximační typy úloh. Generování testovacích dat z dat tréninkových. V zobrazeném dialogu lze zvolit rozptyl testovacích dat vzhledem k tréninkovým a zda budou zašuměny vstupní nebo výstupní hodnoty. Poznámka: Zašumění vstupních hodnot se lépe hodí pro data určená pro klasifikační úlohy a zašumění výstupních hodnot pro aproximační úlohy. Smaže všechny tréninkové nebo testovací příklady. Zapnutí/vypnutí režimu pro vkládání kladných/záporných příkladů pomocí myši. Viz. kapitola Zadávání dat pomocí grafického rozhraní. Poznámka: Po ukončení ručního vkládání příkladů se doporučuje data normalizovat pomocí příkazu Normalizace. Implicitně se vkládají tréninkové příklady, ale jestliže je aktivní režim testovacích dat, viz. příkaz Testovací data, vkládají se data testovací. Zapnutí/vypnutí režimu pro mazání příkladů pomocí myši. Návod: Jestliže je režim aktivní, klikneme levým tlačítkem myši na příklad, který chceme smazat. Poznámka: Implicitně se příkaz vztahuje na tréninkové příklady, ale jestliže je aktivní režim testovacích dat, viz. příkaz Testovací data, odstraňují se data testovací. Spuštění prohlížeče dat. Umožňuje prohlížet tréninková a testovací data a vyvolat externí editor dat (Poznámkový blok). Poznámka: Po ukončení editace již načtených dat mimo aplikaci lze
NETVISUALISER - MANUÁL
Velikost mřížky Znovunačtení Testovací data
61
data opětovně rychle načíst pomocí příkazu Znovunačtení. Změna velikosti mřížky pro vizualizaci výstupů sítě. Poznámka: Pouze pro klasifikační úlohy. Znovunačtení dat v případě jejich modifikace mimo program. Zapnutí/Vypnutí režimu testovacích dat. Jestliže je režim aktivní, pak se příkazy Přidat příklad a Smazat příklad vztahují na testovací data, jinak se tyto příkazy vztahují na data tréninková.
Příkazy pro vizualizaci Všechny příkazy pro vizualizaci jsou umístěny v menu Zobrazit. Ty nejdůležitější z nich jsou pak přístupné z nástrojové lišty Vizualizační lišta. Příkaz Ikona Vypnout vizualizaci Aproximace – spojitá Aproximace – diskrétní Mřížka Hranice Výstup sítě Správnost klasifikace sítě Stopa Graf chyby učení Parametry
Statistika Učící lišta
Popis Vypnutí vizualizace pro rychlejší učení neuronové sítě.Viz. diplomová práce, kapitola 4.1.6.8. Zapnutí/vypnutí vizualizačního režimu Aproximace funkce – spojitá. Viz. diplomová práce, kapitola 4.1.6.6. Zapnutí/vypnutí vizualizačního režimu Aproximace funkce – diskrétní. Viz. diplomová práce, kapitola 4.1.6.5. Zapnutí/vypnutí vizualizačního režimu Mřížka. Viz. diplomová práce, kapitola 4.1.6.3. Zapnutí/vypnutí vizualizačního režimu Hranice. Viz. diplomová práce, kapitola 4.1.6.4. Zapnutí/vypnutí vizualizačního režimu Výstup sítě. Viz. diplomová práce, kapitola 4.1.6.1. Zapnutí/vypnutí vizualizačního režimu Správnost klasifikace sítě. Viz. diplomová práce, kapitola 4.1.6.2. Zapnutí/vypnutí vizualizačního režimu Stopa. Viz. diplomová práce, kapitola 4.1.6.7. Zobrazení grafu chyby učení. Popis dialogu je uveden v kapitole Graf chybové funkce. Zobrazení dialogu pro nastavení parametrů neuronové sítě. Popis dialogu je uveden v kapitole Dialog statistiky neuronové sítě. Zobrazení dialogu se statistikou neuronové sítě. Popis dialogu je uveden v kapitole Dialog parametrů neuronové sítě. Zobrazení/skrytí nástrojové lišty pro učení neuronové sítě.
NETVISUALISER - MANUÁL
Datová lišta Vizualizační lišta Síťová lišta Stavový řádek
62
Zobrazení/skrytí nástrojové lišty pro práci s daty. Zobrazení/skrytí nástrojové lišty pro vizualizaci dat a učení neuronové sítě. Zobrazení/skrytí nástrojové lišty pro práci s neuronovou sítí. Zobrazení/skrytí stavového řádku. Na stavovém řádku se v průběhu učení zobrazuje počet iterací a počet průchodů daty.
Vytvoření neuronové sítě Při vytvoření nové neuronové sítě budeme postupovat podle následujícího postupu: 1. Vybereme v menu Síť příkaz Nová, nebo použijeme Síťovou lištu a klikneme na následující ikonu . 2. V dialogu návrhu sítě, který je zobrazen na obrázku Obr. B.1 budeme postupovat následovně:
Obr. B.1 Dialog návrhu neuronové sítě
2.1. Nejdříve vybereme typ sítě, protože na něm závisí vlastnosti a vzhled dialogu. Viz. zelené číslo 1 na obrázku Obr. B.1 2.2. Nastavíme počet neuronů ve vstupní a výstupní vrstvě a počet skrytých vrstev neuronové sítě. Poté ještě vybereme typy přechodových funkcí pro skrytou a výstupní vrstvu. Viz. zelené číslo 2 na obrázku Obr. B.1 2.3. Jestliže síť obsahuje skryté vrstvy, musíme nastavit počet neuronů v jednotlivých skrytých vrstvách. Implicitně je počet neuronů ve všech skrytých vrstvách roven dvěma. Pro změnu postupujeme tak, že nejdříve v položce Skrytá vrstva vybereme číslo skryté vrstvy, u které chceme nový poč et neuronů a poté v položce Poč et neuronů nastavíme požadovaný počet neuronů, který potvrdíme tlačítkem Nastavit. V případě, že chceme nastavit tento počet skrytých neuronů pro všechny skryté vrstvy, stiskneme tlačítko Nastavit vše.
63
NETVISUALISER - MANUÁL
3. Vše zkontrolujeme a potvrdíme tlačítkem Vytvořit.
Dialog statistiky neuronové sítě Dialog Statistika zobrazuje informace o topologii a konfiguraci aktuální neuronové sítě. Jeho ukázku můžeme vidět na obrázku Obr. B.1.
Obr. B.1 Statistika neuronové sítě
Dialog je rozdělen do následujících šesti částí: • Typ sítě – identifikuje o jaký model neuronové sítě se jedná. • Přechodová funkce/Modifikace – podle typu modelu buď ukazuje použité přechodové funkce pro skrytou a výstupní vrstvu, anebo typ modifikace Kohonenovy sítě a Kohonenovy mapy. • Počet o Vstupů – počet vstupních neuronů, tj. neuronů ve vstupní vrstvě. Počet je vyjádřen ve tvaru n + m, kde n je počet vstupních neuronů a m je rovno 1 v případě, že vstupní vrstva obsahuje bias, tj. neuron s výstupem vždy 1. Jinak je m rovno 0. o Výstupů – počet výstupních neuronů, tj. neuronů ve výstupní vrstvě. o Skrytých vrstev – počet skrytých vrstev. o Neuronů – počet všech neuronů v neuronové síti včetně biasů. Bias je počítán pro každou vrstvu jednou. o Propojení – počet všech propojení mezi neurony v síti včetně biasů. o Iterací – počet všech příkladů předložených síti v adaptivním režimu.
NETVISUALISER - MANUÁL
64
Průchodů dat – počet předložení celé tréninkové množiny neuronové síti v adaptivním režimu. Neurony ve skryté vrstvě – Ukazuje počet neuronů v uživatelem zvolené skryté vrstvě. Počet je vyjádřen ve tvaru n + m, kde n je počet neuronů v dané skryté vrstvě a m je rovno 1 v případě, že skrytá vrstva obsahuje bias. V opačném případě je m rovno 0. Topologie – Pro Kohonenovu mapu ukazuje velikost topologie, do které jsou uspořádány výstupní neurony. Chyby a váhy – Ukazuje váhy propojení mezi jednotlivými neurony a v závislosti na modelu neuronové sítě ukazuje i chyby jednotlivých neuronů. Pomocí přepínačů Výstup, Skrytá vrstva a Vstup a v případě více skrytých vrstev pomocí položky Skrytá vrstva si zvolíme vrstvu, jejíž vlastnosti neuronů chceme pozorovat. Poté si zvolíme číslo neuronu v dané vrstvě a v případě, že nás zajímá váha propojení zvolíme ještě číslo jeho vstupního neuronu. o
• • •
Dialog parametrů neuronové sítě Tento dialog slouží k nastavení parametrů učení neuronové sítě. Všechny parametry lze měnit v průběhu učení, bez nutnosti restartování učení. Dialog zobrazuje čtyři parametry z nichž nemusí být vždy všechny využity.
Obr. B.1 Dialog pro nastavení parametrů neuronové sítě
Ukázku tohoto dialogu můžeme vidět na obrázku Obr. B.1. V prvním sloupci jsou názvy parametrů, které lze měnit. Druhý sloupec ukazuje jejich hodnoty. Třetí sloupec je zaškrtávací tlačítko, které udává, zda je aktivována automatická úprava hodnoty daného parametru. Ne všechny parametry mají tuto možnost, někdy je tlačítko deaktivováno. Čtvrtý sloupec jsou posuvníky pro přímou změnu hodnoty pomocí myši. Posuvník je aktivní pro většinu parametrů. Změnu hodnoty parametru lze provést dvěma způsoby: 1. Přímým vepsáním hodnoty do odpovídajícího pole ve druhém sloupci a následným stisknutím tlačítka Použít. 2. Pomocí posuvníku v případě, že je aktivní. V tomto případě probíhá změna okamžitě a není potřeba ji potvrdit tlačítkem Použít.
65
NETVISUALISER - MANUÁL
Graf chybové funkce Graf chybové funkce znázorňuje průběh chyby neuronové sítě v čase, resp. znázorňuje chybu sítě vzhledem k průchodům tréninkovou množinou. Chyba neuronové sítě se zobrazuje pro tréninková i testovací data. Chyba na tréninkových datech se vynáší modrou a na testovacích datech červenou čarou. Po dosažení konce vykreslovací plochy se pokračuje ve vykreslování znovu od levého okraje a stará data se postupně umazávají. Velikost intervalu, ve kterém se data budou vynášet si lze nastavit v pravém horním rohu, kde zadáme novou hodnotu určující potřebný počet průchodů daty než se chyba vynese (vynáší se průměr chyb těchto průchodů). Po zadání nové hodnoty musíme stisknout tlačítko Použít. Počet průchodů daty se vynáší na vodorovnou osu po 20ti vyneseních chyby do grafu. Na obrázku Obr. B.1 byl zadaný interval nejdříve 10, po té 1, a na konec 100. Na svislé ose nahoře se vypisuje aktuální maximum, které je v grafu zobrazeno a graf se automaticky přizpůsobuje tomuto intervalu - (0, zobrazené maximum). Tlačítko Smazat slouží pro restartování vykreslování, tj. smaže se aktuální graf a začne se vykreslovat znovu od aktuálního stavu sítě. Tlačítko Překreslit slouží k překreslení grafu, jestliže se manipulací s jinými okny obsah tohoto okna vymazal.
Obr. B.1 Graf chyby neuronové sítě
Data Data můžeme do programu buď zadat pomocí grafického rozhraní nebo je nahrát ze souboru. Data vytvořená nebo upravená pomocí programu NetVisualiser můžeme do souboru uložit pro pozdější využití.
Formáty dat pro práci se soubory Program ukládá data do souboru v následujícím formátu: • Na jednom řádku je zadán právě jeden příklad. • Každý příklad obsahuje nejdříve všechny vstupní hodnoty a poté až všechny výstupní hodnoty. • Vstupní a výstupní hodnoty jsou od sebe odděleny středníkem. • Hodnoty jednotlivých vstupů a výstupů jsou od sebe odděleny mezerou. • Je-li hodnota reálné číslo, pak je desetinná část oddělena tečkou.
NETVISUALISER - MANUÁL
66
Program načítá data, které odpovídají tomuto formátu: • Jestliže se na prvním řádku vyskytuje nečíselný znak kromě mezery, čárky a středníku, bere se první řádek jako seznam možných klasifikací. Tyto klasifikace mohou být od sebe odděleny mezerou,čárkou nebo středníkem. Každé z nich je přiřazeno číslo a při načítání je klasifikace nahrazena tímto číslem. • Na jednom řádku je zadán právě jeden příklad, kromě prvního, kde se může vyskytovat seznam klasifikací. • Každý příklad obsahuje nejdříve všechny vstupní hodnoty a poté až všechny výstupní hodnoty. • Vstupní a výstupní hodnoty jsou od sebe odděleny středníkem. • Jestliže se na řádku zadávajícím příklad nevyskytuje středník, tak se poslední hodnota bere jako výstup. • Hodnoty jednotlivých vstupů a výstupů jsou od sebe odděleny mezerou nebo čárkou. • Je-li hodnota reálné číslo, pak je desetinná část oddělena tečkou.
Zadávání dat pomocí grafického rozhraní Program NetVisualiser umožňuje zadávat nová data nebo měnit data již načtená pomocí grafického rozhraní a myši. Jestliže chceme přidat příklad do tréninkové množiny, postupujeme následujícím způsobem: 1. Volba typu dat. Jestliže chceme přidávat příklady s jedním vstupem a jedním výstupem, tj. vhodné pro aproximace funkcí, přepneme se do režimu Aproximace funkce – diskrétní pomocí . Pro vkládání menu Zobrazit a příkazu Aproximace funkce – diskrétní nebo tlačítka dat se dvěma vstupy a jedním výstupem musí být vizualizační režimy pro aproximaci funkcí neaktivní. 2. Volba výstupu příkladu. Jestliže vkládáme data pro klasifikaci, vybereme si jednu ze dvou klasifikací, kladnou nebo zápornou, tj. výstupy budou 1 nebo 0. Stiskneme příslušné tlačítko, tj. pro kladné příklady a pro záporné příklady. 3. Volba vstupních hodnot příkladu. Klikneme na místo, kam chceme příklad umístit. Program poté přepočítá souřadnice vzhledem k současnému zobrazení. V případě aktivního aproximačního režimu se souřadnice na vodorovné ose bere jako vstup a souřadnice na svislé ose jako výstup. V opačném případě se jako vstup použijí obě souřadnice a jako výstup se použije buď 0 nebo 1, podle toho jestli přidáváme záporné nebo kladné příklady.
Křížové ově ření – crossvalidace Křížové ověření neboli crossvalidace slouží k zamezení přeučení neuronové sítě. Program rozdělí tréninková data na n disjunktních množin, z nichž jedna je vždy tzv. validační množina, která tvoří testovací data. Ostatní množiny tvoří data tréninková. Křížové ověření poté probíhá
NETVISUALISER - MANUÁL
67
v n krocích, kde má každý krok různou validační množinu. Učení se zastaví, jestliže chyba neuronové sítě klesne na tréninkové nebo validační množině pod hodnotu stanovenou pomocí ukončovací podmínky. Uživatel nastaví při inicializaci crossvalidace v dialogu hodnotu n a počet cyklů, průchodů daty, po nichž se budou validační množiny střídat.
68
GAVISUALISER - MANUÁL
C. GaVisualiser - manuál Cílem tohoto manuálu je seznámit uživatele s významy všech příkazů a ikon, popsat ty nejdůležitější dialogy a poskytnout uživateli návod, jak s těmi nejdůležitějšími dialogy a příkazy pracovat.
Příkazy pro vizualizaci Všechny příkazy pro vizualizaci jsou umístěny v menu Zobrazit. Ty nejdůležitější z nich jsou pak přístupné z nástrojové lišty Nástrojová lišta. Příkaz Minima
Ikona Popis Zobrazení/skrytí oblastí globálních a lokálních minim.
Statistika
Graf evoluce
Zobrazení statistiky evoluce. Viz. kapitola Dialog statistiky evoluce. Zobrazení dialogu pro nastavení parametrů evoluce. Viz. kapitola Dialog nastavení parametrů evoluce. Zobrazení grafu evoluce. Popis viz. kapitola Graf evoluce.
Graf účelové funkce
Zobrazení grafu účelové funkce.
Vypnout vizualizaci
Vypnutí vizualizace. Mírně zrychlí evoluci.
Nástrojová lišta Evoluční lišta Stavový řádek
Zobrazení/skrytí nástrojové lišty. Zobrazení/skrytí evoluční lišty. Zobrazení/skrytí stavového řádku.
Parametry
Příkazy pro evoluci Všechny příkazy pro ovládání evoluce jsou umístěny v menu Evoluce a jsou přístupné také z nástrojové lišty Evoluční lišta. Příkaz Inicializace Reinicializace 1 generace
Ikona Popis Inicializace genetického algoritmu. Podrobněji popsáno v kapitole Inicializace genetického algoritmu. Reinicializace genetického algoritmu a vytvoření nové počáteční populace. Evoluce jedné generace.
10 generací
Evoluce deseti generací.
Start evoluce Ukončení evoluce
Spuštění evoluce. Evoluce se ukončí v případě splnění ukončovací podmínky. Zastavení probíhající evoluce.
Ukončovací
Nastavení ukončovací podmínky. Zde můžeme nastavit
69
GAVISUALISER - MANUÁL
podmínka
podmínku zastavení evoluce buď na maximální počet generací od spuštění evoluce, poměr nejlepšího a průměrného jednice a velikost konvergence, nebo na kombinaci všech uvedených podmínek.
Inicializace genetického algoritmu Dříve než spustíme evoluci, je třeba genetický algoritmus inicializovat. Inicializaci provedeme příkazem Inicializace v menu Evoluce nebo kliknutím na tlačítko . V části dialogu Účelová funkce a GA vybereme účelovou funkci, genetický algoritmus a v části dialogu Evoluce a Populace nastavíme pravděpodobnost mutace a křížení, velikost a počet populací. Počet populací má význam pouze v případě, že vybereme genetický algoritmus DEME. Genetické algoritmy jsou popsány v diplomové práci v kapitole 4.2.1 a účelové funkce v kapitole 4.2.3.
Dialog statistiky evoluce Dialog statistiky evoluce můžeme vyvolat pomocí příkazu Statistika v menu Zobrazit nebo . Dialog je zobrazen na obrázku Obr. C.1 a je rozdělen do kliknutím na tlačítko následujících pěti částí: • Generace – zobrazuje počet generací od počátku evoluce. • Nastavení o Algoritmus – Typ genetického algoritmu vybraného při inicializaci. o Funkce – Účelová funkce zvolená při inicializaci. • Data zaznamenávaná od inicializace o Globální maximum – Nejvyšší skóre, kterého jedinec dosáhl. o Globální minimum – Nejnižší skóre, kterého jedinec dosáhl. o Počet mutací – Počet všech uskutečněných mutací, závisí na pravděpodobnosti nastavené při inicializaci genetického algoritmu. o Počet křížení – Počet všech uskutečněných křížení, závisí na pravděpodobnosti nastavené při inicializaci genetického algoritmu. • Skóre současné populace o Nejlepší – skóre nejlepšího jedince v současné populaci o Průměrné – průměrné skóre jedinců v současné populaci o Nejhorší – skóre nejhoršího jedince v současné populaci o Odchylka – odchylka skóre mezi jedinci současné populace • Skóre původní generace – stejně jako v předchozím případě, jen místo současné generace bereme generaci původní, tj. nultou generaci.
70
GAVISUALISER - MANUÁL
Obr. C.1 Statistika evoluce
Dialog nastavení parametrů evoluce Tento dialog slouží ke změně parametrů evoluce v jejím průběhu. Měnit lze genetické operátory mutace, křížení a výběru. Lze si vybrat z následujících typů operátorů. • Mutace o Uniformní. Uniformní mutace mění hodnotu genu u jedince zcela náhodně v definovaném rozmezí. o Hranicová. Tato mutace mění hodnotu genu, se stejnou pravděpodobností, buď na horní nebo dolní hranici povoleného intervalu. o Gaussova. Nová hodnota genu je určena z Gausova rozložení, kde střed rozložení je v nule a rozptyl je roven staré hodnotě genu. Nová hodnota musí ležet v předem definovaném rozmezí účelové funkce. • Křížení o Jednobodové. Při tomto typu křížení vybereme náhodně jednu pozici, na níž jedince rozdělíme a jejich části navzájem vyměníme. o Dvoubodové. Dvoubodové křížení je obdobou křížení jednobodového, jen se vyberou náhodně dvě dělící pozice a prostřední části jedinců se navzájem vymění. o Uniformní. Pro každý gen náhodně určí, do kterého z nových jedinců se zařadí. • Výběr o Nejlepší. Tento operátor vybere z populace vždy jedince z nejvyšším skórem. o Ruleta. Tato metoda výběru jedince je založena na poměru skóre jedince vzhledem ke zbytku populace. Čím větší skóre jedinec má, tím má větší šanci na to, že bude vybrán. Pravděpodobnost i-tého jedince pi, že bude vybrán, je:
71
GAVISUALISER - MANUÁL
pi =
ei n
ej j =1
o
o
o
o
kde n je počet jedinců v populaci a ej je skóre j-tého jedince. Z pohledu rulety si to můžeme představit tak, že ruletové kolo rozdělíme na výseče odpovídající jedincům v populaci o velikosti úměrné jejich skóre. Turnaj. Tento selektor používá předchozí metodu k výběru dvou jedinců, z nichž vybere toho s vyšším skóre. Tato metoda typicky vybere jedince s vyšším skóre častěji, než metoda rulety. Deterministický. Deterministický selektor užívá dvoufázové selekční procedury. V první fázi se vypočítá předpokládané skóre jedince. Dočasná populace je naplněna jedinci s nejvyššími očekávanými hodnotami. Ostatní pozice jsou obsazeny původními jedinci s nejvyšší pozicí v seznamu setříděném podle desetinné části jejich skóre. Druhá fáze je uniformní náhodnou selekcí z dočasné populace. Stochastický. Tento selektor také využívá dvoufázové selekční procedury. První fáze počítá předpokládané skóre a naplní dočasnou populaci jedinci s nejvyššími hodnotami. Každá desetina očekávaného skóre dá jednici pravděpodobnost být vybrán. Například jedinec se skórem 1,4 má jistou jednu pozici a dále má 40ti procentní šanci na druhou pozici. Druhá fáze je opět uniformní náhodnou selekcí z této dočasné populace. Uniformní. Tento selektor vybírá jedince náhodně z celé populace. Každý jedinec má pravděpodobnost p, že bude vybrán:
p =
1 n
kde n je počet jedinců v populaci.
Graf evoluce Graf evoluce znázorňuje průběh evoluce v čase, resp. znázorňuje skóre populace vzhledem ke generacím. Skóre populace se znázorňuje skóre jako nejlepšího jedince, tj. toho, který má nejvyšší skóre, a jako průměrné skóre populace, které se vypočítá ze skóre všech jedinců. Skóre nejlepšího jedince se vynáší modrou barvou a průměrné skóre populace červenou barvou. Po dosažení konce vykreslovací plochy se pokračuje ve vykreslování znovu od levého okraje a stará data se postupně umazávají. Velikost intervalu, ve kterém se data budou vynášet, si lze nastavit v pravém horním rohu, kde zadáme novou hodnotu určující potřebný počet generací než se chyba vynese (vynáší se průměr skóre těchto generací). Po zadání nové hodnoty musíme stisknout tlačítko Použít. Počet generací se vynáší na vodorovnou osu po 20 vynesených skóre do grafu. Na svislé ose nahoře se vypisuje aktuální maximum, které je
72
GAVISUALISER - MANUÁL
v grafu zobrazeno a graf se automaticky přizpůsobuje tomuto intervalu – (0, zobrazené maximum). Ukázku grafu vidíme na následujícím obrázku.
Obr. C.1 Graf vývoje evoluce
Tlačítko Smazat slouží pro restartování vykreslování, tj. smaže se aktuální graf a začne se vykreslovat znovu od aktuálního stavu sítě. Tlačítko Překreslit slouží k překreslení grafu, jestliže se manipulací s jinými okny obsah tohoto okna vymazal.
