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/21 21:10]
kik
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 1291: Line 1293:
 materialy: kniha UvodDoNS: {{:cogsci:chapter_07.pdf|}}; Farkasove slidy: {{:cogsci:som.4x.pdf|}}; na Wikipedii si to snad najdete sami :)) 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. + 
 +**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**  Príklad – paralela: **Mealyho automat** 
Line 1297: Line 1300:
   * nedá sa simulovať normálnymi doprednými ANN    * 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.   * 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.
-  * viac o konečných automatoch: http://en.wikipedia.org/wiki/Finite_state_machine alebo stručne v češtine: http://cs.wikipedia.org/wiki/Mealyho_automat +  * [[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|}}  {{: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). +**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 ==+=== Architektúry ===
  
 **Elmanova sieť** **Elmanova sieť**
Line 1313: Line 1316:
  
 {{:cogsci:elman.png|}} {{:cogsci:elman.png|}}
- 
  
  
Line 1328: Line 1330:
  
 **Bengio** **Bengio**
 +
 {{:cogsci:bengio.png|}} {{:cogsci:bengio.png|}}
  
Line 1347: Line 1350:
  
  
-== Učenie ==+=== Učenie ==
 **Backpropagation through time** **Backpropagation through time**
   * učenie spätným šírením chyby v čase   * učenie spätným šírením chyby v čase
Line 1360: Line 1364:
  
   * problém pri sekvenciách neurčenej dĺžky, pretože treba mať veľké okno (sieť potrebuje vidieť ďaleko do minulosti)    * problém pri sekvenciách neurčenej dĺžky, pretože treba mať veľké okno (sieť potrebuje vidieť ďaleko do minulosti) 
 +
  
  
Line 1370: Line 1375:
 {{:cogsci:rnn6.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 ek násobenú vplyvom váhy ij na tieto neuróny ∂s<sub>k</sub>(t)/∂w<sub>ij</sub>.+  * **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   * výpočtovo veľmi náročné: zložitosť **O(n^4)**, kde n je počet neurónov
  
  
- +=== Úlohy pre RNN ===
-== Ú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   * **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í   * 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)+  * 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.   * **lingvistické úlohy**: predikcia ďalšieho znaku v slove alebo vete, slova vo vete a pod.
  
  
-**Referencie:** +===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|}}+
  
 +  * 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 ====
Line 1394: Line 1399:
  
 Typy evolučných algoritmov Typy evolučných algoritmov
-  * Genetické algoritmy +  * Genetické algoritmy -- toto rozpisem 
-  * Genetické programovanie +  * Genetické programovanie -- toto je take ze namiesto cisielok tie chromozomy predstavuju normalne ze zdrojovy kod programu (reprezentovany ako strom) 
-  * Evolučné programovanie +  * Evolučné programovanie -- toto je to iste ako GP, len v dajakych blbostiach ine .. 
-  * Evolučné stratégie+  * Evolučné stratégie -- toto moze byt fakt hocico co abstahuje od evolucie.. 
  
 === Genetické algoritmy === === 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í. 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.
  
-každý stav sa označuje pojmom chromozóm, je reprezentovaný binárnym reťazcom x dĺžky N +Nejakym sposobom si teda zvolime dlzku n chromozomuvacsinou je to tradeoff medzi jemnostou "rozlisenia" a tym aby nam to nebezalo moc pomaly ked budeme narabat chromozomami o velkosti stoviek bajtovOkrem dlzky potrebujeme este aj fitness funkciu - sposob akym dokazeme povedat ako dobre riesenie predstavuje dany chromozom. Ked mame fitness funkciutak mozme zacat varit:
-pracujeme populáciou P, ktorá obsahuje M chromozómovdĺžka chromozómu je konštantná pre všetky chromozómy v populácii +
-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 +
-podstatou genetického algoritmu je nájsť globálne maximum fitness+
  
-riešenie problému prebieha pomocou simulovanej evolúcie +  * Zvolime si nejaku velkost populacie P (povedzme 100) 
-čas t je diskrétna premenná označujúca epochu, alebo generáciu +  * Nahodne inicializujeme populaciu (teda vytvorime 100 nahodnych chromozomov) 
-P<sub>t</sub> označuje populáciu v čase t, chromozómy v P<sub>0</sub> sa vygenerujú náhodne+  * Spustime algoritmus
  
-=== Postup reprodukcie=== +Algoritmus:
-== 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, ide o kvázináhodný výber, pri ktorom veľkosť fitness zodpovedá veľkosti príslušného chlievika na rulete+
  
-== Kríženie == +**1.** Ohodnot pomocou fitness funkcie populaciu P\\ 
-proces, pri ktorom si vybraté chromozómy vymieňajú rovnako dlhé podúseky svojich binárnych reťazcov. index i, ktorý určuje poradie bitu, 0 =< I =< N, sa volí rovnomerne náhodne. +**2.** Z populacie P vyber pomocou nejakej metody selekcie jedincov ktori sa budu rozmnozovat\\ 
-skrížením dostaneme dva nové chromozómy.+**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> <code>
 i=4 i=4
- = 000[00111] + = 000[00111] 
-x' 000[11001]+B  010[11001]
  
- = 00011001 +Decko 1  = 00011001 
-z' 00000111+Decko 2  01000111
 </code> </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 ===
  
-Okrem popísaného jednobodového kríženia existujú aj iné typy (dvojči viacbodové)+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
  
-== Mutácia == +=== Dajake poznamky ===
-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<sup>-4 .. -5</sup> +
-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**+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. 
  
-proces reprodukcie sa končí ak: +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.
-  * 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)+
  
 +A tak...
  
 ===Zdroje: === ===Zdroje: ===
 Návrat, P. a kol., Umelá inteligencia, STU BA, 2006 Návrat, P. a kol., Umelá inteligencia, STU BA, 2006
 +Gonda z hlavy a z wikipedie.
cogsci/ui.txt · Last modified: 2009/06/23 23:02 (external edit)