This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
cogsci:ui [2009/06/19 01:01] vlatko_dz |
cogsci:ui [2009/06/24 01:02] gnd |
||
---|---|---|---|
Line 298: | Line 298: | ||
vyhodnocovacia funkcia f(u) = g(u) + h(u) | vyhodnocovacia funkcia f(u) = g(u) + h(u) | ||
+ | |||
g(u) - cena cesty | g(u) - cena cesty | ||
+ | |||
h(u) - odhad vzdialenosti k cielu | h(u) - odhad vzdialenosti k cielu | ||
Line 875: | Line 877: | ||
Agent musí konať na základe predchádzajúcich skúseností a odhadovať možné dôsledky svojho konania. | 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: | + | **statická vyhodnocovacia funkcia** - odhaduje, nakoľko možno o danom postavení usudzovať, že povedie |
- | odhaduje, nakoľko možno o danom postavení usudzovať, že povedie k víťazstvu. | + | |
== Opis hry ako problému hľadania: == | == 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čí | * 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) | * 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 == | == Algoritmus MiniMax == | ||
Line 901: | Line 906: | ||
* 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 | * 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 | * Vykoná sa ťah, ktorý vedie do najlepšieho postavenia | ||
+ | |||
+ | {{: | ||
+ | |||
+ | {{: | ||
Opísaný algoritmus dokáže robiť efektívne rozhodnutia za predpokladu, | Opísaný algoritmus dokáže robiť efektívne rozhodnutia za predpokladu, | ||
Line 912: | Line 921: | ||
Iná modifikácia minimaxu, ktorá pracuje s dvoma hraničnými hodnotami zodpovedajúcimi dvom protihráčom. | Iná modifikácia minimaxu, ktorá pracuje s dvoma hraničnými hodnotami zodpovedajúcimi dvom protihráčom. | ||
- | * hodnota " | + | * hodnota "**alfa**" - dolné ohraničenie hodnoty, ktorú može nadobudnúť stav, v ktorom je MAX na ťahu |
- | * hodnota " | + | * hodnota "**beta**" - horné ohraničenie hodnoty, ktorú môže nadobudnúť stav, v ktorom je MIN na ťahu |
+ | |||
+ | {{: | ||
* na začiatku sú obe hodnoty +/- nekonečno | * na začiatku sú obe hodnoty +/- nekonečno | ||
Line 1281: | Line 1292: | ||
materialy: kniha UvodDoNS: {{: | 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 ==== | ||
- | najpopulárnejší typ EA, využívaný pri riešení problémov a optimalizácií | + | vo všeobecnosti sú to špecifické typy optimalizačných algoritmov |
+ | EA využívajú mechanizmy, ktoré sú inšpirované biologickou evolúciou | ||
- | každý stav sa označuje pojmom chromozóm, je reprezentovaný binárnym reťazcom x dĺžky N | + | Typy evolučných algoritmov |
- | pracujeme s populáciou P, ktorá obsahuje M chromozómov. dĺžka chromozómu je konštantná pre všetky chromozómy v populácii | + | * Genetické algoritmy -- toto rozpisem |
- | každému chromozómu x ktorý patrí do P sa priraďuje funkcia fitness f(x), ktorá je vyjadrením úspešnosti daného stavu | + | * Genetické programovanie -- toto je take ze namiesto cisielok tie chromozomy predstavuju normalne ze zdrojovy kod programu |
- | podstatou genetického algoritmu | + | * 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.. | ||
- | riešenie problému prebieha pomocou simulovanej evolúcie | + | === Genetické algoritmy === |
- | čas t je diskrétna premenná označujúca epochu, alebo generáciu | + | |
- | P< | + | |
- | === Postup reprodukcie: | + | Najpopulárnejší typ EA, využívaný pri riešení problémov a optimalizácií. V skratke a kusok vulgarne |
- | == Selekcia == | + | |
- | do procesu reprodukcie vstupujú dvojice chromozómov x, x' patriace do P | + | |
- | existuje viacero selekčných metód pre výber populácie určenej na reprodukciu | + | |
- | * náhodne | + | |
- | * v závislosti od úspešnosti, veľkosti fitness funkcie; používa sa pravidlo rulety, | + | |
- | == Kríženie == | + | Nejakym sposobom |
- | proces, pri ktorom | + | |
- | skrížením dostaneme dva nové chromozómy. | + | |
- | < | + | * Zvolime si nejaku velkost populacie P (povedzme 100) |
- | i=4 | + | |
- | x = 000[00111] | + | * Spustime algoritmus |
- | x' = 000[11001] | + | |
- | z = 00011001 | + | Algoritmus: |
- | z' = 00000111 | + | |
- | </ | + | |
+ | **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.\\ | ||
- | Okrem popísaného jednobodového kríženia existujú aj iné typy (dvoj- či viac- bodové) | + | === 1. Fitness funkcia === |
- | == Mutácia == | + | Fitness funkcia |
- | pri mutácií sa preklopia dvom chromozómom (pozn. podľa mna nie je nutné, aby dvom, opravte ma ak sa mylim) náhodne vybraté bity z reťazca, tj 0->1, alebo 1->0. | + | |
- | Pravdepodobnosť mutácie by mala byť dosť malá, približne 10< | + | |
- | dôvodom pre vytvorenie možnosti mutácie je snaha vyhnúť sa uviaznutiu v lokálnom extréme | + | |
- | kríženie a mutácia sú **genetické operátory** | + | === 2. Metody selekcie === |
- | proces reprodukcie sa končí ak: | + | Najpouzivanejsie su Ruleta a Tournament. |
- | * sa našlo riešenie ktoré uspokojuje kritéria | + | |
- | * bol prekročený stanovený počet generácií | + | |
- | * uviazli sme v lokálnom extréme, alebo na plošine (viď. cyklické prehľadávanie v 3) | + | |
- | ===Zdroje: === | + | Ruleta funguje ako ruleta |
- | Návrat, P. a kol., Umelá inteligencia, STU BA, 2006 | + | |
+ | Tournament funguje tak ze si vyberieme k nahodnych chromozomov, | ||
+ | === 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 " | ||
+ | < | ||
+ | i=4 | ||
+ | A = 000[00111] | ||
+ | B = 010[11001] | ||
+ | Decko 1 = 00011001 | ||
+ | Decko 2 = 01000111 | ||
+ | </ | ||
+ | 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 < | ||
+ | |||
+ | 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, | ||
+ | Gonda z hlavy a z wikipedie. |