This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
cogsci:ui [2009/06/18 00:29] vlatko_dz |
cogsci:ui [2009/06/21 21:28] kik |
||
---|---|---|---|
Line 864: | Line 864: | ||
==== 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, | ||
+ | |||
+ | * poskytujú štruktúrovaný, | ||
+ | * umožňujú absolútne presnú reprezentáciu ľubovoľnej konfigurácie sveta a takýto stav je prístupný, | ||
+ | * akosť ich riešenia je dobre merateľná, | ||
+ | * 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í, | ||
+ | Príklad: pri šachu obsahuje strom hľadania približne 35< | ||
+ | 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, | ||
+ | * 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 | ||
+ | |||
+ | {{: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Opísaný algoritmus dokáže robiť efektívne rozhodnutia za predpokladu, | ||
+ | To však nie je realistický predpoklad. Prezetanie treba // | ||
+ | |||
+ | 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 " | ||
+ | * hodnota " | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * 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:// | ||
+ | |||
+ | * ^ 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, | ||
==== 9. Databáza znalostí v predikátovej logike, unifikácia, | ==== 9. Databáza znalostí v predikátovej logike, unifikácia, | ||
Line 1202: | Line 1281: | ||
=== Vizualizácia vysokorozmerných dát === | === Vizualizácia vysokorozmerných dát === | ||
SOM | SOM | ||
+ | |||
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 1207: | Line 1287: | ||
- | text: {{: | + | text v dokumente: {{: |
+ | materialy: kniha UvodDoNS: {{: | ||
==== 13. Rekurentné neurónové siete, architektúry, | ==== 13. Rekurentné neurónové siete, architektúry, | ||
+ | |||
+ | **Motivácia**: | ||
+ | |||
+ | 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:// | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | **Riešenie**: | ||
+ | |||
+ | |||
+ | === 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í | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | |||
+ | **Jordan** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * ak pridáme **decay units** – pre obsah kontext. vrstvz v t+1 zoberieme časť obsahu kontextovej vrstvy z t-1: C< | ||
+ | * 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** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | |||
+ | **Williams a Zipser** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * plne prepojená rekurentná NS | ||
+ | |||
+ | |||
+ | **Mozer a Stornetta** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * 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 | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * v praxi stačí rozvinúť len niekoľko krokov do minulosti (veľkosť okna) | ||
+ | * vzorec: | ||
+ | {{: | ||
+ | {{: | ||
+ | |||
+ | * 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 | ||
+ | |||
+ | {{: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * **Ludove intuitívne vysvetlenie**: | ||
+ | * 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í**: | ||
+ | * podobne: **dopĺňanie** 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: {{: | ||
+ | * Farkašove slajdy: {{: | ||
+ | * TEXT: {{: | ||
==== 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 | ||
+ | * Genetické programovanie | ||
+ | * Evolučné programovanie | ||
+ | * Evolučné stratégie | ||
+ | |||
+ | === Genetické algoritmy === | ||
najpopulárnejší typ EA, využívaný pri riešení problémov a optimalizácií | najpopulárnejší typ EA, využívaný pri riešení problémov a optimalizácií | ||
Line 1263: | Line 1453: | ||
===Zdroje: === | ===Zdroje: === | ||
Návrat, P. a kol., Umelá inteligencia, | Návrat, P. a kol., Umelá inteligencia, | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- |