User Tools

Site Tools


cogsci:ui

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
cogsci:ui [2009/06/17 02:30]
breakk
cogsci:ui [2009/06/23 23:02] (current)
Line 267: Line 267:
  
  
-Zdroje: Návrat, P. a kol., Umelá inteligencia, STU BA, 2006 +=== Informované stratégie === 
-téma prehľadávania a roznych typov stratégií / algoritmov je vcelku vycerpavajuco (pre nase potreby myslim) popisana na wikipedii+ 
 +Neinformované stratégie nie sú veľmi efektívne a postačujú iba na riešenie jednoduchých problémov.  
 +Snaha o zefektívnenie pomocou heuristiky - doplňujúcej informácie o probléme. 
 +Heuristika sa vyskytuje zvyčajne v podobe funkcie, ktorá vyjadruje naše poznanie o probléme - zvyčajne v podobe funkcie, ktorá určuje uzol najvhodnejší pre rozvitie. 
 + 
 +Vyhodnocovacia funkcia - po aplikácií na uzol vracia číslo, kvantitatívne ohodnotenie sľubnosti uzla 
 +Sľubnosť uzla vyjadruje nakoľko je želatelné rozviť tento uzol 
 + 
 +== Hľadanie najskôr najlepší (Best-first) == 
 + 
 +všeobecná trieda algoritmov 
 +Na rozvitie vyberie vzdy ten uzol, ktorý je podľa vyhodnocovacej funkcie najlepší. 
 + 
 +dôležité ! vyhodnocovacia funkcia vzdy iba **odhaduje** najlepsi uzol 
 + 
 +== Lačné hľadanie == 
 + 
 +Vyberá uzol, ktorý reprezentuje stav, ktorý je podľa odhadu najbližšie k cielu.  
 +heuristická funkcia h(u) - odhad ceny najlacnejšej cesty z uzla u do cieľového uzla. 
 +Hľadanie sa môže vďaka nevhodnej heuristike rozbehnúť nesprávnym smerom  -> nie je úplné 
 +nemusí nájsť optimálne riešenie - nie je prípustné 
 +časová aj pamäťová zložitosť sú exponenciálne, b^m, všetky vygenerované uhly sa uchovávajú 
 +Lačné hľadanie minimalizuje cenu cesty medzi uzlami, čím sa znižuje celková cena cesty 
 + 
 +== Algoritmus A* == 
 + 
 +Rieši problém úplnosti a prípustnosti lačného hľadania 
 +kombinuje výhody lačného hľadania so stratégiou rovnomernej ceny, ktorá je neinformovaná 
 + 
 +vyhodnocovacia funkcia f(u) = g(u) + h(u)  
 + 
 +g(u) - cena cesty 
 + 
 +h(u) - odhad vzdialenosti k cielu 
 + 
 +hlavná nevýhoda - pamäťová aj časová zložitosť je exponenciálna  
 + 
 +== Cyklicky sa prehlbujúce hľadanie pomocou A* (IDA*) == 
 + 
 +rieši podobne ako v prípade hľadania do hĺbky problém nárokov na pamäť 
 +miesto hraničnej hĺbky sa pracuje s hraničnou cenou, ktorá je určená vyhodnocovacou funkciou.   
 +V jednom cykle sa rozvinú všetky uzly, ktorých hodnotenie nepresiahne hraničnú cenu. Potom sa cena zvýši a hľadanie pokračuje ďalším cyklom. 
 + 
 +== Algoritmus jednoduchého viazania pamäti A* (SMA*) == 
 + 
 +rieši problém algoritmu IDA*, ktorý si nepamatá cestu a teda nevie, či už na daný stav niekedy narazil. 
 +Využíva maximálne množstvo pamäte (ak je pamäte dosť pre vygenerovanie riešenia, je optimálny aj prípustný) 
 +Vygenerované stavy zaraďuje do fronty, keď dôjde pamäť, vyberie jeden uzol, ktorý z pamäte vyhodí a nahradí ho iným.  
 +Vyhadzuje uzly, ktoré majú nízke ohodnotenie 
 +v uzle predka si uchováva informácie o tom, ktorý potomok bol najvhodnejší - ak by došlo k "zabudnutiu" celého podstromu, stále budeme vedieť, ktorá cesta bola najlepšia. 
 +  
 +=== Algoritmy cyklického vylepšovania === 
 + 
 +Nehľadáme cestu, ale cieľový stav, ktorý nepoznáme, ale vieme ako ho rozpoznať 
 +najjednoduhšia metóda - cyklus: vygenerujeme nejaky stav a testujeme, či je riešením problému 
 + 
 +Spôsoby generovania stavov: 
 +  * systematické - exhaustívne 
 +  * náhodné (algoritmus Britského múzea - predmet nájdeme tak, že sa potulujeme náhodne po múzeu) 
 +  * systematické s vynechávaním riešení, ktoré sa nezdajú byť sľubné (sľubnosť vyhodnocuje heuristická funkcia) 
 + 
 +Algoritmus cyklického vylepšovania vychádza z ľubovoľného počiatočného stavu, ktorý popisuje úplnú konfiguráciu a postupne sa tento stav mení tak, aby sa konfigurácia vylepšovala - aby sa približoval k cieľovému stavu 
 + 
 +2 skupiny: 
 +  * algoritmy lokálneho vylepšovania (hill climbing) 
 +  * simulované žíhanie a genetické algoritmy 
 + 
 +== Stratégia lokálneho vylepšovania (Hill Climbing) == 
 + 
 +podstatou je postupovať v každom kroku tak, že daný stav bude zlepšením oproti predchádzajúcemu 
 +Ak hľadáme v stavovom priestore reprezentovanom grafom, tak ide vždy o vybratie jedného uzla a vždy iba z novovygenerovaných uzlov. Vyberá sa ten uzol, ktorý je sľubnejší, ako jeho predchodca. 
 +Nevybraté uzly sa do pamäte neukladajú, rovnako ani strom hľadania sa neudržuje 
 + 
 +== Algoritmus lokálnej optimalizácie == 
 + 
 +je variantom predchádzajúceho.  
 +Rozdiel: 
 +  * v prípade lokálneho vylepšovania sa generovali následovníci dovtedy, kým sa nevygeneroval prvý lepší stav 
 +  * pri lokálnej optimalizácií sa vždy sa vygenerujú všetci následovníci daného uzla, aby sa mohlo vyhodnotiť, ktorý je najlepší 
 + 
 +nazýva sa tiež gradientové hľadanie 
 + 
 +pozn. AIMA neuvádza tieto dve stratégie ako oddelené, ale Návrat áno. Vo všeobecnosti sú obe Hill-Climbing, pretože sa škriabu na nejaký "kopec", ktorého vrchol predstavuje riešenie.  
 +Pojem gradientové hľadanie sa používa podľa AIMA v prípade, ak vyhodnocovacia funkcia hovorí o cene, nie o kvalite daného uzla.  
 + 
 +Ak pomocou lokálnej optimalizácie vygenerujeme dva uzly, ktoré sú rovnako sľubné, vyberieme z nich náhodne. 
 + 
 +Problémy lokálneho vylepšovania: (a teda aj lokálnej optimalizácie) 
 +  * Lokálne maximá: ak narazíme na lokálne maximum, ktoré je nižšie ako globálne maximum, zastaneme aj keď nedosiahneme cieľ 
 +  * Plošina: Oblasť v stavovom priestore, kde sú všetky uzly ohodnotené rovnako. V tomto prípade má hľadanie náhodný charakter. 
 +  * Hrebeň: Označuje situáciu, v ktorej algoritmus postupuje veľmi pomaly po "hrebeni" k vrcholu, alebo osciluje po stranách hrebeňa, hoci bočné strany hrebeňa v stavovom priestore môžu byť dostatočne strmé.  
 + 
 +Úspech týchto stratégií závisí od tvaru povrchu stavového priestoru. Východiskom z uvedených situácií môže byť opätovné, náhodné vygenerovanie počiatočného stavu. 
 + 
 +== Simulované žíhanie == 
 + 
 +(Markošovej obľúbená vec, pretože táto metóda pochádza z fyziky pevných látok a metalurgie) 
 + 
 +Ďalšou možnosťou, ako riešiť uvedené problémy je nezačínať z počiatočného stavu, ale dovoliť algoritmu "zostúpiť nižšie" (analogický moment chladenia pri žíhaní) 
 +Pri simulovanom žíhaní sa nevyberá najlepší krok, ale náhodný. Ak tento krok naozaj zlepšuje situáciu, tak sa vykoná. Inak vykonanie kroku určuje pravdepodobnosť < 1, ktorá má 2 parametre: 
 +  * T - teplota, čím je väčšia, tým je výber tolerantnejší (povolí aj horšie kroky), čím je bližšia k 0, tým viac sa podobá na lokálne vylepšovanie 
 +T sa mapuje pomocou parametra rozvrhu, ktorý určuje ako sa bude hodnota T meniť v čase 
 +  * delta E - ohodnotenie zhoršenia stavu oproti minulému, pravdepodobnosť exponenciálne klesá, čím je zhoršenie väčšie 
 + 
 +ohodnotenie stavu korešponduje s energiou atómov materiálu počas chladnutia 
 + 
 + 
 + 
 + 
 +==Zdroje:==  
 +Návrat, P. a kol., Umelá inteligencia, STU BA, 2006 
 +Russel & Norvig, AIMA 
 +téma prehľadávania a roznych typov stratégií / algoritmov je vcelku vycerpavajuco (pre nase potreby myslim) popisana aj na wikipedii
  
 ==== 4. Constraint satisfaction problém: definícia, hranová a uzlová konzistencia. ==== ==== 4. Constraint satisfaction problém: definícia, hranová a uzlová konzistencia. ====
Line 406: Line 518:
   - **Most constraining variable**, alebo degree heuristika: vyberá premennú, ktorá spôsobuje najviac obmedzení pre ďalšie premenné.   - **Most constraining variable**, alebo degree heuristika: vyberá premennú, ktorá spôsobuje najviac obmedzení pre ďalšie premenné.
   - **Least constraining value** heuristika: vyberie najmenej obmedzujúcu hodnotu - takú ktorá vyradí najmenej hodnôt ostávajúcich premenných.   - **Least constraining value** heuristika: vyberie najmenej obmedzujúcu hodnotu - takú ktorá vyradí najmenej hodnôt ostávajúcich premenných.
 +
 +=== Dopredná  kontrola (forwad checking) ===
 +
 +Hneď ako priradíme hodnoty premennej X, pomocou procesu forward checking  nájdeme Y zviazanú constrainom s X. Z jej domény vymažeme  všetky hodnoty nekonzistentné s hodnotou vybranou pre X.
 +
 +Kombinujeme s MRV (most constrained variable) heuristikou.
 +
 +Metoda hranovej konzistencie (arc consistency) odhali zlyhanie skor ako forward checking.
 +
 +=== Alldiff constraint ===
 +
 +Situacia ked všetky premenné ktoré sú prepojené obmedzujúcimi podmienkami musia mať rôzne hodnoty (premenne mozu tvorit podgraf vacsieho grafu).
 +
 +Ak domény niektorých premenných majú len jednu hodnotu, vymažeme ju z domén ostatných premenných a skonrtolujeme počty podľa 1.
 +
 +  - Máme m premenných, ktoré majú celkovo n rôznych hodnôt.  Nekonzistencia bude ak m < n.
 +  - Ak domény niektorých premenných majú len jednu hodnotu, vymažeme ju z domén ostatných premenných a skonrtolujeme počty podľa 1.
 +  - Opakujeme bod 2, pokiaľ sú domény s jednou premennou.
 +
 +=== Atmost (resource) constraint ===
 +
 +Situacia, kde sucet hodnot priradenych nejakym premennym ma byt najviac (at most) nejaka konstanta.
 +
 +{{:cogsci:statnice16.png|}}
 +
 +Ako zistiť nekonzistenciu atmost constrainu?
 +
 +  - Zosumujeme minimálne hodnoty domén.  Ak v predošlom prípade každá doména je {3,4,5,6}, potom constraint nemožno splniť.
 +  - Konzistenciu možno zlepšiť deletovaním maximálnej hodnoty každej domény, ak nie je konzistentná s minimálnymi hodnotami iných domén. Ak v predošlom príklade každá premenná má doménu {2,3,4,5,6}, potom hodnoty 5, 6, z nich možno vymazať. 
 +
 +
 +=== Lokálne prehľadávanie pre CSP ===
 +
 +  - Zaciname s nejakymi hodnotami vopred priradenymi premennym, napr. nahodne rozlozenie 8 dam na sachovnici. //(Lokálne prehľadávacie metódy aplikujeme na stavy s úplným priradením hodnôt. Priradenie ignoruje constrainy.)//
 +  - Zmeníme hodnotu jednej premennej, ktorá je v konflikte s ostatnými, napr. presunieme jednu damu ktora ohrozuje nejaku inu.
 +  - Vyberieme pre ňu takú hodnotu z danej domény, ktorá spôsobí najmenej konfliktných situácií (min. conflict heuristika), napr. presunieme spominanu damu na take miesto, kde ohrozi najmenej dalsich dam.  
 +  - Nový stav ohodnotíme pomocou vyhodnocovacej funkcie a prijmeme ho podľa toho, aký algoritmus používame, napr. ho ohodnotime podla toho kolko dam sa vzajomne ohrozuje.
 +
  
  
Line 716: Line 866:
  
 ==== 8. Hry: minimax a alfa beta orezávanie. ==== ==== 8. Hry: minimax a alfa beta orezávanie. ====
 +Hry sú špecifickou oblasťou výskumu umelej inteligencie, odlišujú sa v niekoľkých aspektoch:
 +
 +  * poskytujú štruktúrovaný, dobre definovaný problém, v ktorom sa ľahko rozpozná úspech, či neúspech. Tento problém sa dá úplne opísať pravidlami, ktoré sú relatívne jednoduché.
 +  * umožňujú absolútne presnú reprezentáciu ľubovoľnej konfigurácie sveta a takýto stav je prístupný, teda agent môže vnímať všetko, co sa dá o prostredí poznať, riešenie problému sa hľadá v priestore možných pozícií
 +  * akosť ich riešenia je dobre merateľná, čo nebýva pravidlom pri iných druhoch problémov
 +  * agent rieši hru z pohľadu jedného hráča, ale musí brať do úvahy aj kroky protihráča. Prítomnosť protihráča je prvkom neurčitosti
 +
 +Hry sa vo väčšine prípadov nedajú riešiť pomocou bežných prehľadávacích stratégií, najmä z dôvodu veľkej komplexity.
 +  Príklad: pri šachu obsahuje strom hľadania približne 35<sup>100</sup> uzlov, stavový priestor približne 10<sup>40</sup> rôznych pozícií
 +  Agent musí konať na základe predchádzajúcich skúseností a odhadovať možné dôsledky svojho konania.
 +
 +Spôsoby riešenia herných problémov:
 +  * inteligentné metódy - stále nie veľmi úspešné
 +  * tabuľkové metódy - použiteľné napr. na záver partie šachu, takzvané koncovky. sú charakteristické tým, že existujú bohaté znalosti, ako tieto situácie riešiť
 +  * metódy hľadania - bez nich nedokáže agent hrať žiadnu náročnejšiu hru
 +
 +Ťah sa vyberá tak, že sa vyhodnocujú dosiahnuté stavy a urobí sa odhad ich výhodnosti.
 +
 +**statická vyhodnocovacia funkcia** - odhaduje, nakoľko možno o danom postavení usudzovať, že povedie z hľadiska agenta k víťazstvu.
 +
 +== Opis hry ako problému hľadania: ==
 +  * máme hru pre dvoch hráčov, ktorých budeme označovať MAX a MIN, hráči sa striedajú v ťahoch kým hra neskončí
 +  * výsledok hry je reprezentovaný pomocou skóre pridelenom viťazovi (resp. odobratím bodov porazenému)
 +  * **počiatočný stav** - postavenie na hracej doske a príznak, ktorý hráč je na ťahu
 +  * **množina operátorov** - množina povolených ťahov
 +  * **množina stavov** - množina všetkých možných postavení na hracej ploche
 +  * **cieľový test** určuje kedy hra končí
 +  * **bodovacia funkcia** číselne oceňuje výsledok hry
 +
 +== Algoritmus MiniMax ==
 +  * má určiť najlepšiu stratégiu pre hráča MAX
 +  * vychádza z predpokladu, že protivník (MIN) bude vždy hrať tak, aby čo najviac uškodil svojmu MAXovi
 +  * MAX sa snaží maximalizovať svoju výhodu, MIN sa svojou snahou o výhru snaží minimalizovať MAXove skóre
 +
 +Postup určenia najlepšieho ťahu pre hráča MAX:
 +  * Preskúmajú sa všetky stavy, ktoré môžu možnými ťahmi vzniknúť, vygeneruje sa celý strom hľadania, podobne ako pri hľadaní do hĺbky
 +  * Rozhodne sa, ktorý ťah je najlepší:
 +    * na listy stromu (reprezentujú možné koncové stavy) sa aplikuje hodnotiaca funkcia
 +    * postupne sa ohodnotia uzly aj na vyšších úrovniach až po koreňový uzol tak, že do vrcholov, v ktorých je na ťahu MAX sa prenáša maximum z hodnôt potomkov a do vrcholov, v ktorých je na ťahu MIN sa prenáša minimum
 +  * Vykoná sa ťah, ktorý vedie do najlepšieho postavenia
 +
 +{{:cogsci:minimax-2.jpg|}}
 +
 +{{:cogsci:plminmax.gif|}}
 +
 +Opísaný algoritmus dokáže robiť efektívne rozhodnutia za predpokladu, že sú k dispozícií prostriedky k prezretiu celého stromu. 
 +To však nie je realistický predpoklad. Prezetanie treba //useknúť// skôr, než v cieľovom stave a listy sa hodnotia pomocou **heuristickej vyhodnocovacej funkcie**.
 +
 +Minimax sa modifikuje následovne:
 +  * miesto cieľového testu sa použije usekávací test
 +  * miesto bodovacej funkcie sa použije heuristická vyhodnocovacia funkcia
 +
 +== Alfa-beta orezávanie (usekávanie) ==
 +
 +Iná modifikácia minimaxu, ktorá pracuje s dvoma hraničnými hodnotami zodpovedajúcimi dvom protihráčom.
 +  * hodnota "**alfa**" - dolné ohraničenie hodnoty, ktorú može nadobudnúť stav, v ktorom je MAX na ťahu
 +  * hodnota "**beta**" - horné ohraničenie hodnoty, ktorú môže nadobudnúť stav, v ktorom je MIN na ťahu
 +
 +{{:cogsci:080609231536.png|}}
 +
 +  * na začiatku sú obe hodnoty +/- nekonečno
 +  * alfa hodnota MAX uzla sa určí ako súčasná najväčšia minimaxová hodnota jeho následnovníkov a nikdy sa nemože zmenšiť
 +  * beta hodnota MIN uzla sa určí ako súčasná najmenšia hodnota jeho následnovníkov a nikdy sa nemôže zväčšiť
 +
 +  * hľadanie sa môže useknúť pod každým MAX uzlom, ktorého alfa hodnota nie je menšia než beta ľubovoľného predchodcu. ako výsledná hodnota MAX uzla sa použije jeho alfa hodnota -> beta orezávanie
 +  * .. sa môže useknúť pod každým MIN uzlom, ktorého beta hodnota nie je väčšia než alfa jeho predchodcov. -> alfa orezávanie
 +
 +   * http://www.emunix.emich.edu/~evett/AI/AlphaBeta_movie/sld001.htm
 +
 +  * ^ z tohto sa to celkom dobre chape ^
 +
 +! dolezite:
 +  * treba si dôsledne všímať, ktorý hráč je v danom uzle na ťahu a čo to znamená, podľa toho orezávať alebo meniť hodnoty alfa a beta
 +nie je to ťažké, len si treba automatizovať ten princíp
 +
 +Alfa-Beta orezávanie je rovnako efektívne ako minimax, ale zvyčajne sa mu podarí nájsť riešenie skôr, čo však nie je pravidlom - záleží od poradia vygenerovaných uzlov.
 +
 +== Zdroje ==
 +Návrat, P. a kol, Umelá inteligencia, STU BA, 2006
  
 ==== 9. Databáza znalostí v predikátovej logike, unifikácia, lifting, metódy vyvodzovania. ==== ==== 9. Databáza znalostí v predikátovej logike, unifikácia, lifting, metódy vyvodzovania. ====
Line 798: Line 1027:
 === Lifting === === Lifting ===
  
-doplnit (neviem odkial)+lifting je, ked zoberies odvodzovacie pravidla z vyrokovej logiky a modifikujes ich tak aby boli pouzitelne vo FOL (priklad: generalized modus ponens - vid vyssie)
  
  
Line 1054: Line 1283:
 === Vizualizácia vysokorozmerných dát === === Vizualizácia vysokorozmerných dát ===
 SOM   umožňuje   topograficky   zmapovať   (reprezentovať) **distribúciu vstupných dát**, pričom častejšie prípady aplikácie sú tie, keď počet neurónov v sieti za zvolí **menší** ako počet vstupov. V takom prípade každý neurón sa stane reprezentantom nejakej podmnožiny navzájom podobných vstupov. V opačnom prípade množina blízkych neurónov bude reagovať na ten istý vstup, pričom jeden z nich sa stane (najaktívnejším) centrom. V oboch prípadoch susedné neuróny budú mať tendenciu  reprezentovať  blízke oblasti  vo vstupnom priestore.  V prípade nerovnomernej  distribúcie vstupov SOM proporcionálne rozdelí svoje zdroje a viac zahusteným oblastiam pridelí viac neurónov, čím sa zvýši diskriminačná schopnosť siete v tejto oblasti (magnifikačný faktor). Vďaka 2D štruktúre neurónov sa SOM používa hlavne na vizualizáciu vysokorozmerných dát. SOM   umožňuje   topograficky   zmapovať   (reprezentovať) **distribúciu vstupných dát**, pričom častejšie prípady aplikácie sú tie, keď počet neurónov v sieti za zvolí **menší** ako počet vstupov. V takom prípade každý neurón sa stane reprezentantom nejakej podmnožiny navzájom podobných vstupov. V opačnom prípade množina blízkych neurónov bude reagovať na ten istý vstup, pričom jeden z nich sa stane (najaktívnejším) centrom. V oboch prípadoch susedné neuróny budú mať tendenciu  reprezentovať  blízke oblasti  vo vstupnom priestore.  V prípade nerovnomernej  distribúcie vstupov SOM proporcionálne rozdelí svoje zdroje a viac zahusteným oblastiam pridelí viac neurónov, čím sa zvýši diskriminačná schopnosť siete v tejto oblasti (magnifikačný faktor). Vďaka 2D štruktúre neurónov sa SOM používa hlavne na vizualizáciu vysokorozmerných dát.
 +
 Príklady použitia: minimum spanning tree, lexical maps, robotic arm control Príklady použitia: minimum spanning tree, lexical maps, robotic arm control
  
Line 1059: Line 1289:
  
  
-text: {{:cogsci:12_somka.doc|}} {{:cogsci:12_somka.pdf|}} +text v dokumente: {{:cogsci:12_somka.doc|}} {{:cogsci:12_somka.pdf|}}
  
 +materialy: kniha UvodDoNS: {{:cogsci:chapter_07.pdf|}}; Farkasove slidy: {{:cogsci:som.4x.pdf|}}; na Wikipedii si to snad najdete sami :))
 ==== 13. Rekurentné neurónové siete, architektúry, spôsoby učenia, úlohy s časovým kontextom (klasifikácia   sekvencií, predikcia) ==== ==== 13. Rekurentné neurónové siete, architektúry, spôsoby učenia, úlohy s časovým kontextom (klasifikácia   sekvencií, predikcia) ====
 +
 +**Motivácia**: k jednému vstupu viacero výstupov, v závislosti od  časového kontextu. Viacvrstvová sieť by mala byť rozšírená o možnosť reprezentovať  časový kontext, aby tak mohla na základe predloženého vstupu lepšie rozhodnúť o výstupe. 
 +
 +Príklad – paralela: **Mealyho automat** 
 +  * generuje postupnosti znakov z množ. {α, β}
 +  * nedá sa simulovať normálnymi doprednými ANN 
 +  * V informatice se pojmem Mealyho stroj označuje konečný automat s výstupem. Výstup je generován na základě vstupu a stavu, ve kterém se automat nachází. To znamená, že stavový diagram automatu bude pro každý přechod obsahovat výstupní signál.
 +  * [[http://en.wikipedia.org/wiki/Finite_state_machine|viac o konečných automatoch]] alebo [[http://cs.wikipedia.org/wiki/Mealyho_automat|stručne v češtine]] 
 +
 +{{:cogsci:rnn1.png|}} 
 +
 +
 +**Riešenie**: pridáme do siete tzv. kontextovú vrstvu, ktorá si „pamätá“ výstup z predošlého času, ktorý sa dá chápať ako akási vnútorná pamäť siete (v Mealyho automate: info o stave, na obr. 1,2,3). 
 +
 +
 +=== Architektúry ===
 +
 +**Elmanova sieť**
 +  * najznámejšia a najjednoduchšia architektúra
 +  * kontextová vrstva = skrytá vrstva z predošlého kroku: t-1
 +  * rozpoznávanie sekvencií, predikcia, dopĺňanie krátkych sekvencií 
 +
 +{{:cogsci:elman.png|}}
 +
 +
 +
 +**Jordan**
 +
 +{{:cogsci:jordan.png|}}
 +
 +  * ak pridáme **decay units** – pre obsah kontext. vrstvz v t+1 zoberieme časť obsahu kontextovej vrstvy z t-1: C<sub>i</sub>(t+1) = y<sub>i</sub>(t) + αC<sub>i</sub>(t-1) 
 +  * schopnosť nie len rozpoznávať sekvencie ale aj generovať sekvencie rôznej dĺžky
 +  * možnosť: **teacher forcing** = pri učení nahradíme kontextovú vrstvu žiadaným výstupom v t-1
 +
 +
 +
 +**Bengio**
 +
 +{{:cogsci:bengio.png|}}
 +
 +
 + 
 +**Williams a Zipser**
 +
 +{{:cogsci:williams+zipser.png|}}
 +
 +  * plne prepojená rekurentná NS
 +
 +
 +**Mozer a Stornetta**
 +
 +{{:cogsci:mozer+stornetta.png|}} 
 +
 +  * lokálna rekurzia = neurón je rekurentne spojený iba sám so sebou, tzv. local-recurrent-global-feedforward networks.
 +
 +
 +
 +=== Učenie ===
 +
 +**Backpropagation through time**
 +  * učenie spätným šírením chyby v čase
 +  * rozvinutie rekurentnej siete v čase do potenciálne mnohovrstvovej doprednej siete a použití klasického backpropu
 +
 +{{:cogsci:bptt.png|}} 
 +
 +  * v praxi stačí rozvinúť len niekoľko krokov do minulosti (veľkosť okna)
 +  * vzorec: 
 +{{:cogsci:rnn3.png|}} kde x<sub>i</sub> je aktivita na i-tom neuróne v čase t-1, delta<sub>i</sub> je chyba výstupu (očakávaný – skutočný) a alfa je rýchlosť učenia a 
 +{{:cogsci:rnn4.png|}}
 +
 +  * problém pri sekvenciách neurčenej dĺžky, pretože treba mať veľké okno (sieť potrebuje vidieť ďaleko do minulosti) 
 +
 +
 +
 +
 +**Real time recurrent learning**
 +  * rekurentné učenie v reálnom čase
 +
 +{{:cogsci:rnn5.png|}} 
 +
 +{{:cogsci:rnn6.png|}}
 +
 +  * **Ludove intuitívne vysvetlenie**: pre každú váhu si pamätáme jej **vplyv na aktivitu každého neurónu**. Vplyv váhy //ij// (z neurónu //j// do //i//) na neurón k počítame ako váhovanú sumu vplyvov váhy //ij// na neuróny, ktoré kŕmia neurón //k//. V prípade, že //k// = //i// , pripočítame aktivitu neurónu //j// v čase t-1 (člen delta<sup>kr</sup>…). Celé to vynásobíme deriváciou aktivačnej funkcie. Váhu //ij// upravujeme ako sumu chýb na výstupných neurónoch e<sub>k</sub> násobenú vplyvom váhy //ij// na tieto neuróny ∂s<sub>k</sub>(t)/∂w<sub>ij</sub>.
 +  * výpočtovo veľmi náročné: zložitosť **O(n^4)**, kde n je počet neurónov
 +
 +
 +=== Úlohy pre RNN ===
 +  * **rozpoznávanie postupností**: na vstup prichádzajú znaky, sieť naučená na nejaký automat (gramatiku) signalizuje pozitívne (1) ak znak ešte patrí do postupnosti generovanej automatom a negatívne (0) ak znak už nemôže patriť do postupnosti
 +  * podobne: **dopĺňanie** postupností, **predikcia** ďalších znakov, **generovanie** nových postupností
 +  * simulovanie konečno-stavových automatov – formálnych automatov a jazykov – akéhokoľvek turingovho stroja (výpočtová sila)
 +  * **lingvistické úlohy**: predikcia ďalšieho znaku v slove alebo vete, slova vo vete a pod.
 +
 +
 +===Literatúra:===
 +
 +  * Umelá inteligencia a kogntívna veda I (Kvasnička et. al.)
 +  * Úvod do NS: {{:cogsci:chapter_06.pdf|}}
 +  * Farkašove slajdy: {{:cogsci:rnn.4x.pdf|}}
 +  * TEXT: {{:cogsci:13_rekurentneNS.doc|}}, {{:cogsci:13_rekurentneNS.pdf|}}
  
 ==== 14. Evolučné algoritmy: základné koncepty a mechanizmy, využitie v UI ==== ==== 14. Evolučné algoritmy: základné koncepty a mechanizmy, využitie v UI ====
  
 +vo všeobecnosti sú to špecifické typy optimalizačných algoritmov
 +EA využívajú mechanizmy, ktoré sú inšpirované biologickou evolúciou
 +
 +Typy evolučných algoritmov
 +  * Genetické algoritmy -- toto rozpisem
 +  * Genetické programovanie -- toto je take ze namiesto cisielok tie chromozomy predstavuju normalne ze zdrojovy kod programu (reprezentovany ako strom)
 +  * Evolučné programovanie -- toto je to iste ako GP, len v dajakych blbostiach ine ..
 +  * Evolučné stratégie -- toto moze byt fakt hocico co abstahuje od evolucie.. 
 +
 +=== Genetické algoritmy ===
 +
 +Najpopulárnejší typ EA, využívaný pri riešení problémov a optimalizácií. V skratke a kusok vulgarne ide o to, ze mame nejaku populaciu rieseni, a robime umelu evoluciu na rieseniach s cielom najst lepsie riesenia. Riesenia je mozne chapat aj ako stavy/body vo fazovom priestore. Stav/riesenie sa označuje pojmom chromozóm, a je reprezentovaný retazcom v binarnom formate. Vacsinou maju vsetky riesenia rovnaku dlzku n, je to preto aby sa nam lepsie krizili.
 +
 +Nejakym sposobom si teda zvolime dlzku n chromozomu, vacsinou je to tradeoff medzi jemnostou "rozlisenia" a tym aby nam to nebezalo moc pomaly ked budeme narabat s chromozomami o velkosti stoviek bajtov. Okrem dlzky potrebujeme este aj fitness funkciu - sposob akym dokazeme povedat ako dobre riesenie predstavuje dany chromozom. Ked mame fitness funkciu, tak mozme zacat varit:
 +
 +  * Zvolime si nejaku velkost populacie P (povedzme 100)
 +  * Nahodne inicializujeme populaciu P (teda vytvorime 100 nahodnych chromozomov)
 +  * Spustime algoritmus
 +
 +Algoritmus:
 +
 +**1.** Ohodnot pomocou fitness funkcie populaciu P\\
 +**2.** Z populacie P vyber pomocou nejakej metody selekcie jedincov ktori sa budu rozmnozovat\\
 +**3.** Rozmnoz jedincov pomocou krizenia a mutacie\\
 +**4.** Novych jedincov pridaj do populacie P\\
 +**5.** Ak hotovo tak hotovo, ak nie tak chod na 1.\\
 +
 +=== 1. Fitness funkcia ===
 +
 +Fitness funkcia je mrte dolezita, bez dobrej fitness nevieme porovnavat medzi roznymi rieseniami a vybrat to silnejsie. Neexistuje ziadna vseobecna fitness funkcia - vzdy nejaku vymyslime pre dany problem. Vacsinou je fitness funkcia nejake daco co chromozomu priradi nejake cislo - povedzme cim vyssie cislo, tym lepsi chromozom.
 +
 +=== 2. Metody selekcie ===
 +
 +Najpouzivanejsie su Ruleta a Tournament. 
 +
 +
 +Ruleta funguje ako ruleta :) Ked uz mame ohodnotene chromozomy pomocou fitness funkcie, tak im (zjednodusene) pridelime policka rulety v zavislosti od toho ako silne su dane chromozomy. Priklad: mame v populacii jeden chromozom A so silou 0.6 a styri chromozomy B,C,D,E so silou 0.1. Najprv si urcime "velkost" rulety. Mame: 0.6 + 0.1 + 0.1 + 0.1 + 0.1 = 1 ==> toto cislo je celkova dlzka rulety. Ruletu rozdelime takto: <0,0.6> patri najsilnejsiemu chromozomu - A , (0.6,0.7> patri chromozomu B, (0.7,0.8> patri chromozomu C, (0.8, 0.9> patri D, (0.9, 1.0> patri E. Teraz si proste vygenerujeme nahodne cislo z intervalu 0 az 1 (teda nahodne cislo z intervalu nula az velkost rulety). Toto je metaforicke hodenie gulickou. Do akeho intervalu toto cislo spadne, ten chromozom bude vybrany na rozmnozovanie. Kedze chromozom A ma pre seba interval <0, 0.6> je mrte pravdepodobne ze do rozmnozovania vyberieme prave jeho. Takto je zarucene ze sa najviacej mnozia najlepsie chromozomy/riesenia. Rovnako sa ale zachovava geneticka diverzita tym ze existuje sanca ze sa rozmnozovat pojdu aj slabe riesenia. 
 +
 +Tournament funguje tak ze si vyberieme k nahodnych chromozomov, a najsilnejsie z nich nechame sa mnozit. Tournament sa to vola preto lebo v originale tie chromozomy este niesu ohodnotene cez fitness a az priamo v tournamente sa ohodnotia - to je akokeby "suboj" medzi nimi, ze ktory bude lepsi. 
 +
 +=== 3. Krizenie a mutacia ===
 +
 +Proces, pri ktorom si do rozmnozovania vybraté chromozómy vymieňajú podúseky svojich binárnych reťazcov. Skrížením dostaneme dva nové chromozómy. Krizenie moze byt single point crossover alebo multiple point crossover.
 +Single point crossover je jednoducho urcenie si miesta i na chromozome, kde sa chromozomy "rozdelia" a vymenia si svoje polovicky:
 +
 +<code>
 +i=4
 +A  = 000[00111]
 +B  = 010[11001]
  
 +Decko 1  = 00011001
 +Decko 2  = 01000111
 +</code>
  
 +Multiple point crossover je take, ze tych bodov je viacej a povedzme sa vymienaju len useky medzi dvoma bodmi .. 
  
 +Mutacia je jednoducho pravdepodobnost s ktorou sa nejaky bit chromozomu preklopi. Teda jednotka na nulku alebo nulka na jednotku. Vacsinou byva mutacia malinke cislo, nieco ako 0.02 (teda dva pripady zo sto). Vyssia mutacia prinasa viacej novosti do populacie ale rovnako dokaze nicit dobre riesenia. Ako pri vsetkych parametroch - ide najdenie tej spravnej hodnoty pre danu aplikaciu.
  
 +=== 4. Pridavanie novych jedincov do populacie ===
  
 +Tuna existuje zase mrte moznosti, ale najbeznejsia je ze rodicov zmazeme a pridame naspat ich deti. Takto zostane zachovana velkost populacie P. 
 +Ine metody su take, ze deti ohodnotime cez fitness funkciu a vyberieme len tych najsilnejsich spomedzi deti & rodicov a to tiez tak aby zostala zachovana velkost P.
  
 +=== 5. Kedy koniec ===
  
 +GA skonci ked:
 +  * sa našlo riešenie ktoré uspokojuje dopredu zadefinovane kritéria
 +  * bol prekročený stanovený počet epoch (kazdy navrat ku 1. je akoby nova epocha)
 +  * uviazli sme v lokálnom extréme, alebo na plošine (viď. cyklické prehľadávanie v 3) -- toto sa tazko detekuje ale napriklad ak sme sa pocas x epoch nikam nepohli a najsilnejsie chromozomy maju stale rovnaku fitness
  
 +=== Dajake poznamky ===
  
 +Keby sa Markosova pytala ako sa zvoli optimalna dlzka chromozomu - to zavysi od aplikacie. Kedze chromozomy su vacsinou vlastne prirodzene cisla zapisane v binarnom kode, tak ak mame nejaky spojity priestor ktory chceme prehladavat tak by sme mali dlzku n zvolit tak aby tento priestor chromozomy rozdelili na dostatocne jemny pocet casti. Priklad: mame hladat maximum nejakej sialenej funkcie na <0,1>. Povedzme ze si urcime dlzku chromozom na 7 - tym padom to su cisla od 0 po 127 - teda akoby sme si ten interval <0,1> delili na 128 casti. Moze ale aj nemusi stacit. 
  
 +Keby sa Markosova pytala na Hamiltonovu barieru. Mame povedzme chromozomy velkosti n=3. Povedzme ze uz sme nasli riesenie 011 (3) - z tohto riesenia sa ale krizenim a mutaciou strasne tazko dostaneme ku najblizsiemu rieseniu 100 kedze to by si ziadalo sucasnu mutaciu na vsetkych troch bitoch. Toto sa vola Hamiltonova bariera. Ze riesenia ktore lezia vedla seba je tazke dosiahnut pomocou krizenia a mutacie. Niekedy je potrebne aby nam GA vedel takto jemne chodit po stupienkoch - teda lahko prechadzat medzi hodnotami rieseni. V takom pripade pouzijeme Grayovo kodovanie. To je taka funkcia ktora nam spravi taky specialny binarny zapis ze cisla ktore sa lisia o jednotku sa budu v grayovom binarnom zapise lisit len o jeden bit.
  
 +A tak...
  
 +===Zdroje: ===
 +Návrat, P. a kol., Umelá inteligencia, STU BA, 2006
 +Gonda z hlavy a z wikipedie.
cogsci/ui.1245198607.txt.gz · Last modified: 2009/06/17 00:30 (external edit)