VUI Neuronové sítě

VUI – 2014 Neuronové sítě      

výpočetní model používaný v oblasti UI vychází z biologického modelu nervové sítě => neurony (perceptrony) propojené synapsemi graf NS = topologie NS, NS se skládá z perceptronů využití u úloh z oblasti klasifikace, aproximace a predikce výhodou paralelizmus při výpočtech typy NS: o Vícevrstvé NS (Multi Layer Perceptron) o Hopfieldovy sítě o RBF sítě (radial basis function) o další modely



Učení – nastavení vah NS (synaptické váhy) pro správnou odezvu: o s učitelem – srovnávání aktuálního výstupu s požadovaným => nastavení vah pro co nejmenší rozdíl o bez učitele – váhy nastaveny pro konzistentní výstup (stejná odezva při stejných nebo obdobných vstupech) o je potřeba rozlišovat učební a testovací data o nejdříve jsou váhy nastaveny náhodně, procesem učení dochází k jejich optimalizaci



Perceptron – matematický model neuronu, ústřední prvek NS

o o o o o

základní klasifikátor, lze použít pro jednoduché rozhodování (není potřeba celá NS) vstup = podnět z vnějšího okolí nebo výstup jiného neuronu váha = hodnota upravující významnost jednotlivých vstupů Prahová hodnota = hodnota, při jejímž překonání je perceptron nabuzen => vyšle výstupní signál modulovaný přechodovou (aktivační) funkcí Aktivační funkce – moduluje výstupní signál neuronu  fce jednotkového skoku (hardlim) => 0 (nenabuzen)/1 (nabuzen)  fce signum (hardlims) => 1 (pro x>0), -1 (pro x<0)  lineární (purelin)  hyperbolický tangent (tansig) – Elmanovy NS  sigmoidální (logsig) – MLP  saturační přenosová fce – omezení velikosti vstupního signálu

1



Vícevrstvé NS – nejrozšířenější a nejpoužívanější o Vlastnosti:  vstupní vrstva, skrytá vrstva, výstupní vrstva  tvořena perceptrony  počet vstupních neuronů dán počtem vstupů matematického modelu  počet výstupních neuronů dán kódováním výstupu  počet neuronů skryté vrstvy dán složitostí úlohy (maximum ze vstupů a výstupů)  aktivační fce lineární nebo sigmoidální  standardně učení s učitelem  učící algoritmus Back Propagation Error (=postupné snižování chyby učebními iteracemi, případně metoda sdružených gradientů)  dlouhý proces učení o Použití:  predikce, klasifikace, aproximace

2



Samoorganizující se NS (Kohonenova) o Vlastnosti:  jednovrstvá, s dopředným šířením  učení bez učitele => shluková analýza vstupních dat (pouze analýza vstupů)  jediná vrstva radiálních neuronů uspořádaná do mřížky  lze rozšířit pro klasifikaci – LVQ1, LVQ2 (Learning Vector Quantization) o Použití:  shlukování (zatřiďování dat), klasifikace o Shlukování – zatřiďování do skupin podle obdobných vlastností => využití Mexického klobouku pro vymezení jasné hranice shluku



Hopfieldovy sítě o pravidla pro učení a odvozování vychází z energetické fce o Vlastnosti:  výstup každého neuronu přiváděn na vstup všech ostatních neuronů => postupné zpřesňování  všechny neurony jsou jak vstupní, tak výstupní  míra spojitosti neuronů dána vahou vzájemné synapse  obvykle binární výstup (0/1) o Použití:  asociativní paměť (postupné vybavování na základě částečné znalosti), klasifikace (rozpoznání SPZ), optimalizace (obchodní cestující)



RBF sítě o rychlejší průběh učení (oproti MLP) => lze nasadit na složitější problémy o Vlastnosti:  2 typy neuronů – radiální a perceptronové  váhy první vrstvy nastaveny na začátku učení, u druhé vrstvy se nastavují obdobně jako u vícevrstvé NS  vybavování pomalejší, než u MLP (dáno složitostí modelu) o Použití:  klasifikace, regrese (odhad na základě historických dat)

3

Expertní systémy  

   

programy budované s cílem dosažení stejné rozhodovací úrovně jako lidský expert pro danou problematiku (podniková, zákaznická podpora) rysy ES: o oddělení znalostí a mechanizmu jejich využívání o rozhodování za stavu neurčitosti o vysvětlovací schopnosti ES = zvláštní typ znalostního systému (využívá expertních znalostí, vysvětlovací mechanismus, dochází ke stírání rozdílu) Základní znalosti vkládá na počátku expert Prázdný systém = ES neobsahující fakta ani znalosti Základní složky ES: o báze znalostí, inferenční mechanizmus, I/O rozhraní, vysvětlovací modul, modul pro akvizici znalostí



Báze znalostí a báze faktů o báze znalostí – znalosti z určité domény a specifické znalosti pro řešení problémů v této doméně o báze faktů – vytvářena v průběhu řešení konkrétního problému, obsahuje data k řešenému problému o inferenční mechanizmus – obecné (doménově nezávislé) algoritmy schopné řešit problémy na základě dat báze znalostí, bává založen na:  inferenčním pravidle – odvozování nových poznatků z existujících znalostí  strategii prohledávání báze znalostí



Neurčitosti v expertních systémech o mohou se nalézat v bázi znalostí i bázi faktů o vychází z reality – ne vždy máme všechna data dostupná a úplná o

Zdroje neurčitosti:  nepřesnost, nekompletnost, nekonzistence dat  vágní pojmy  nejisté znalosti

4

o

Prostředky pro zpracování neurčitosti:  Bayesovský přístup, Bayesovské sítě  faktory jistoty  Dempster-Shaferova teorie  fuzzy logika



Prostředky reprezentace znalostí o pokud je ES zaměřen do specializované domény, musí mít nástroj pro uchování dat, znalostí a informací => různé přístupy (lze nasadit i rozdílné pro 1 ES, ale musí tvořit kompaktní celek), typy:  matematická logika  pravidla (rules)  sémantické sítě (semantic nets  rámce a scénáře (frames and scripts)  objekty (objects)



Typy ES: o Problémově orientovaný ES – báze znalostí obsahuje znalosti z určité domény o Prázdný ES (shell) – báze znalostí je prázdná o Diagnostický ES – určení, která předdefinovaná hypotéza nejlépe koresponduje s daty pro daný případ o Plánovací ES – je znám počáteční a cílový stav, je třeba určit vhodnou posloupnost kroků mezi nimi k dosažení cíle o



Dělení podle vnitřní reprezentace:  pravidlový, nepravidlový, hybridní ES

Vlastnosti ES o Výhody:  schopnost řešit složité problémy  dostupnost expertíz (snížení nákladů na jejich provedení)  trvalost a opakovatelnost expertízy  trénovací nástroj pro začátečníky  uchování znalostí odborníků odcházejících z organizace o Nevýhody:  nebezpečí selhaní ve změněných podmínkách  neschopnost poznat meze své použitelnosti o Možnosti nasazení:  podpora rozhodování – medicína, právo, řízení lidských zdrojů (efektivní metody řízení), plánování výroby (rozvrhování), finančnictví (úvěry), …

5

Fuzzy logika   



postavena nad fuzzy množinami => využívá funkci příslušnosti => popisuje nakolik prvek patří do dané množiny => jeden prvek může patřit zároveň do více množin jeden z možných přístupů zpracování neurčitosti, využívaná v ES a pro klasifikaci Výhody: o dokáže zahrnout nepřesnosti o dokáže pracovat s přirozeným jazykem Definice: FL je vícehodnotová logika definovaná funkcí příslušnosti prvku na intervalu <0;1>



Prvky fuzzy systému, bloky integrující fuzzy logiku: o fuzzifikace – transformace reálných proměnných na jazykové  určuje stupeň členství v příslušných množinách (fce lambda, S-typ, Z-typ) o fuzzy inference – definice pravidel, jazykových proměnných  IF podmínka THEN proved (např. IF cena = vysoká THEN bez prodeje;) o defuzzifikace – logika transformace jazykových proměnných do reálných, často využívá principu maxima nebo těžiště výsledné fuzzy množiny  princip maxima – deffuzifikovaná hodnota = střed intervalu  princip těžiště – deffuzifikovaná hodnota = hodnota těžiště výsledné fuzzy množiny



Využití: fuzzy řízení pračky, automatické ostření foťáku (detekce obličejů, bod ostření), řízení výtahu, řízení brzdné soupravy (ABS), rozpoznávání řeči, identifikace osob, analýza portfolia

Na zkoušce bylo za úkol udělat sjednocení a průnik ze zadaných fuzzy množin (viz přednáška).

Prohledávání stavového prostoru     

Je dán systém, který se může nacházet v různých stavech (stavem může být třeba křižovatka, kde se nachází auto). V každém stavu je dána konečná množina produkčních pravidel (zatoč vlevo, vpravo), ze kterých je možné vybírat. Volba pravidla přepne systém do nového jednoznačně daného stavu. Hledáme posloupnost aktivací produkčních pravidel, které zajistí přechod systému z výchozího Řešení = posloupnost aktivací

Neporadí si:  S nekonečným množstvím pravidel  Neurčitost při aplikaci pravidla (pravidlo vede na více stavů) Prohledávaný stavový prostor lze reprezentovat stromem 

Neinformované algoritmy o Lze odhadnout charakter řešení, jednoduché, paměťově náročné i časově oproti informovaným o Do hloubky – LIFO 6



o Do šířky - FIFO Informované algoritmy o Využívají heuristickou znalost o problému, náročnější na implementaci o Hladový algoritmus, Dijkstrův algoritmus, A*

Teorie her  

Vědní disciplína aplikované matematiky Tvorba modelů sloužících pro o Analýzu situace o Nalezení vítězných strategií

Klasifikace rozhodovacích situací  Dle počtu charakteristik o Monokriteriální rozhodování – výsledky jsou subjektem hodnoceny na základě jedné charakteristiky, jednoho kritéria o Vícekriteriální rozhodování – výsledky jsou subjektem hodnoceny podle více charakteristik  Dle počtu rozhodovatelů o S jedním účastníkem – rozhodování za jistoty x rizika x neurčitosti o Více účastníků = hra  Dle počtu strategií – konečné vs. nekonečné  Dle výskytu prvku náhody – deterministické vs. nedeterministické  Dle informovanosti o stavu hry – s úplnou informací vs. s neúplnou  Dle vzájemného vlivu a ztráty o Antagonistické – co jeden hráč ztratí druhý získá o Neantagonistické – ztráta jednoho hráče nemusí znamenat zisk ve výši ztráty pro druhého hráče  Zápis her o Explicitní (extenzivní) formě  Hráči činí svá rozhodnutí postupně, dá se popsat pomocí stromu, například piškvorky  Algoritmy pro vítěznou strategii:  Minimax  Minimax + alfa-beta prořezávání (zabraňuje vzniku podstromů, které nevedou ke zlepšení)  And-or grafy: úplné vs. částečné  Jednoduchá implementace, ale vyšší paměťová náročnost, nevhodné pro složitější problémy o Normální (normativní) formě  Normální forma se používá u her, ve kterých se hráči rozhodují v jeden okamžik.

7

MATLAB     

Výpočetní prostředí Programovací jazyk Snadná a rychlá práce s matematickými objekty Grafické znázornění Velké množství hotových funkcí

Každá proměnná je matice. M soubory:  Skripty, posloupnost příkazů  Funkce, posloupnost příkazů + vstupní parametry function [s] = soucin(a,b) % SOUCIN - soucin dvou cisel s = a * b; end

function sinus_graf % graf funkce sinus t = 0:0.1:10 % vytvori vektor t o prvcich 0, 0.1 0.2 0.3 az 10 sinus = sin(t) % vektor sinus obsahuje hodnoty sinu pro t plot(t,sinus) % vykresli graf end

Genetický algoritmus Genetický algoritmus je heuristický postup, který se snaží aplikací principů evoluční biologie nalézt řešení složitých problémů, pro které neexistuje použitelný exaktní algoritmus. Patří do evolučních algoritmů (používají techniky napodobující evoluční procesy známé z biologie – dědičnost, mutace, křížení, přirozený výběr). Popis algoritmu 1. (Inicializace) Vytvoř nultou populaci (obvykle složenou z náhodně vygenerovaných jedinců) 2. (Začátek cyklu) Pomocí určité výběrové metody (zpravidla zčásti náhodné) vyber z populace několik jedinců s vysokou zdatností 3. Z vybraných jedinců vygeneruj nové použitím následujících metod (operátorů), čímž vznikne další generace: o křížení - „prohoď“ části několika jedinců mezi sebou o mutace - náhodně změň část jedince o reprodukce - kopíruj jedince beze změny 4. Vypočti zdatnost těchto nových jedinců 5. (Konec cyklu) Pokud není splněna zastavovací podmínka, tak pokračuj od bodu 2 6. (Konec algoritmu) Jedinec s nejvyšší zdatností je hlavním výstupem algoritmu a reprezentuje nejlepší nalezené řešení.

8

Použití: Optimalizace výrobního plánu podniku, výběr investic, klasifikace podniku, problém obchodního cestujícího.

Logické programování Imperativní programovací styl 

JAK se má vypočet provést, program tvořen posloupností příkazů.

Neimperativní (deklarativní) programovací styl -> logické programování 

Důraz kladen na to CO má být vypočteno. Program je tvořen souborem definic funkcí a jejich aplikací ve formě výrazů (funkcionální programování) nebo souborem logických formulí (logické programování), které specifikují řešený problém.

Funkcionální programování      

Algoritmus je tvořen za pomoci vzájemného volání rekurzivních funkcí. Výsledek výpočtu nezávislý na pořadí, v němž se jednotlivé výrazy redukují. Výhody: kratší a elegantnější program, paralelizmus u víceprocesorových systémů, tvorba ve formě specifikací Náhrada statické datové struktury dynamickou Příkladem může být programovací jazyk Lips, FP, Hope, Haskell Rekurze -> rozklad složitého problému na podproblém o Vnořená rekurze – funkce též v argumentu 9

o o o

Kaskádní (stromová) rekurze – několik volání, ale ne vnořené Lineární rekurze – nanejvýš jedno volání Koncová rekurze – rekurzivní volání je poslední operací alternativy definice

Prolog     



Neimperativní (deklarativní) Vhodný tam, kde zkoumáme vztahy mezi objekty Program v Prologu je popis relací pomocí jednoduchých formulí. Rekurze hraje klíčovou roli Klauzule (klauzule definující stejnou relaci vytvářejí proceduru) o Pravidla – Tvrzení závislá na splnění nějakých podmínek. Má hlavu, neprázdné tělo. o Fakta (predikát) – Hlava, prázdné tělo. Vyjadřují bezpodmínečně pravdivé tvrzení. o Dotazy – výpočet, zda tvrzení platí či nikoliv. Klauzule bez hlavy. Datové objekty (termy) o Struktury (složené termy) o Jednoduché objekty  Proměnné – velké písmeno nebo podtržítko na začátku  Konstanty  Atomy – identifikátor, malá písmena  Čísla

Data mining Strojové učení  Technologie pro získávání (dolování) znalostí z dat. Dolování z dat  Zaměřeno na odkrytí znalosti v datech ukryté: data-> informace -> znalost.  Zabývá se řešením problémů pomocí analýzy dat, která jsou v daném čase k dispozici.  Dolování z dat odhaluje různé skryté struktury (podobné popisy objektů). Rozhodovací strom 

Každá větev představuje pravidlo (viz obr. na konci).

Occamovo pravidlo  architektury dávají stejný výsledek, tak volím tu nejjednodušší Entropie  míru „překvapení“ (neuspořádanosti), kvalitní dotazy mají odpovědi, které pro trénovací data vyvolávají co nejmenší „překvapení“ Krosvalidace 

rozdělí náhodným výběrem data na k pokud možno stejně velkých částí (například 10 podmnožin), pak proběhne 10 tréninků, v každém je 9 trénovacích podmnožin a 1 testovací

10

Klasifikace Nejbližší sousedi k-NN 

Příklady mají své zařazení do tříd známé, pokud se objeví případ, jehož příslušnost je neznámá, hledá se jeho nejbližší „nejpodobnější soused“.

Bayesovské učení 

Bayesova metoda inference je založena na použití teorie pravděpodobnosti. Strojové učení poskytuje kvantitativní přístup ke zvažování důkazů podporujících alternativní hypotézy.

11