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/16 19:24] kik |
cogsci:ui [2009/06/22 17:14] breakk |
||
---|---|---|---|
Line 267: | Line 267: | ||
- | Zdroje: Návrat, P. a kol., Umelá inteligencia, | + | === 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 | ||
+ | nemusí nájsť optimálne riešenie - nie je prípustné | ||
+ | časová aj pamäťová zložitosť sú exponenciálne, | ||
+ | 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 " | ||
+ | |||
+ | === 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ší, | ||
+ | Nevybraté uzly sa do pamäte neukladajú, | ||
+ | |||
+ | == 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ť, | ||
+ | |||
+ | 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, | ||
+ | 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: | ||
+ | * 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 " | ||
+ | |||
+ | Ú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, | ||
+ | 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, | ||
+ | Russel & Norvig, AIMA | ||
+ | téma prehľadávania a roznych typov stratégií / algoritmov je vcelku vycerpavajuco (pre nase potreby myslim) popisana | ||
==== 4. Constraint satisfaction problém: definícia, hranová a uzlová konzistencia. ==== | ==== 4. Constraint satisfaction problém: definícia, hranová a uzlová konzistencia. ==== | ||
Line 337: | Line 449: | ||
==== 5. Constraint satisfaction problem, heuristiky, prístupy, metódy. ==== | ==== 5. Constraint satisfaction problem, heuristiky, prístupy, metódy. ==== | ||
+ | |||
+ | Definicia CSP je v otazke 4. | ||
+ | |||
+ | === Varianty CSP problémov === | ||
+ | |||
+ | **Discrete variables: | ||
+ | |||
+ | * **finite domains:** n premenných, | ||
+ | * **infinite domains:** integers, strings, etc. (napr., job scheduling, premenné sú e start/end days pre každý job) Potreba constraint language, napr., StartJob1 + 5 ≤ StartJob3 | ||
+ | |||
+ | **Continuous variables: | ||
+ | |||
+ | * e.g., start/end times for Hubble Space Telescope observations linear constraints solvable in polynomial time by linear programming | ||
+ | |||
+ | === Varianty constrainov === | ||
+ | |||
+ | - **Unary** (unárny) constraint ovplyvňuje iba jednu premennú, napr., SA ≠ green (Juhoaustrálčania neznášajú zelenú) | ||
+ | - **Binary** (binárny) constraints ovplyvňujú dvojicu premenných, | ||
+ | - **Higher-order** or n–ary (n-árny) | ||
+ | |||
+ | === Binarizácia === | ||
+ | |||
+ | CSP algoritmy pracujú s unárnymi alebo binárnymi constraintami -> preto pomaha binarizovat n-arne constrainty. | ||
+ | |||
+ | Binárny CSP sa dá zobraziť ako „constraint graph“ (vrcholy su premenne a hrany binarne constrainty). | ||
+ | |||
+ | // | ||
+ | |||
+ | **Konverzia n-árych costraintov na unárne:** n-árny const. sa zmení na unárny tak, že namiesto podmienok kladených na pôvodné premenné, položíme podmienky na zapúzdrenú premennú. | ||
+ | |||
+ | - Binarizácia 1. spôsob - **Hidden variable encoding** - Vytvoria sa väzby originálnej premennej k zapúzdrenej na princípe X= i_th_argument_of(U). | ||
+ | - Binarizácia 2. Spôsob - **Dual encoding** - Používajú sa len zapúzdrené premenné, na princípe i_th _argument_of(U)=j_th_argument_of(V). | ||
+ | |||
+ | === Uzlova a hranova konzistencia === | ||
+ | |||
+ | Uzlova a hranova knzistencia je vysvetlena v otazke 4. Postupna eliminacia nekonzistencii pomaha znizit pocet prehladavanych moznosti pri pridelovani hodnot premennym. | ||
+ | |||
+ | === Generate and test algoritmus (GT) === | ||
+ | |||
+ | Systematicky sa generujú možné priradenia k premenným a kompletné priradenie sa testuje, či spĺňa constrainy. Vracia ako riešenie prvú vhodnú kombináciu. | ||
+ | |||
+ | Algoritmus je: | ||
+ | - kompletný | ||
+ | - neoptimálny | ||
+ | - exponenciálne časovo a priestorovo zložitý | ||
+ | |||
+ | === Backtracking search (spätné prehľadávanie) === | ||
+ | |||
+ | Backracking je v podstate prehľadávanie do hĺbky, ktoré v každom čase priradí hodnotu len jednej premennej. | ||
+ | |||
+ | * Depth-first search pre CSPs so single-variable priradením sa volá backtracking search | ||
+ | * Backtracking search je základný uniformný algoritmus pre CSP problémy | ||
+ | * Dokáže vyriešiť | ||
+ | |||
+ | * neinformovaná stratégia | ||
+ | * neefektívna pre väčšinu CSP | ||
+ | * potreba zlepšenia backtrackingu | ||
+ | |||
+ | **Možnosti zlepšenia: | ||
+ | * Dá sa zlepšiť efektívnosť | ||
+ | * Dá sa dopredu, alebo aspoň dosť včas odhadnúť poradie priradení hodnôt, ktoré nevyhnutne vedie k zlyhaniu? | ||
+ | |||
+ | === Heuristiky pre CSP === | ||
+ | |||
+ | Heuristiky sa týkajú stavu, nie cesty do cieľa. Orientujú sa na včasné odhalenie možnosti porušiť constrainty. | ||
+ | |||
+ | - **Most constrained variable**, alebo minimum remaining value (MRV) heuristika: vyber premennú, s najmenším počtom možných hodnôt (lebo tá najpravdepodobnejšie spôsobí zlyhanie constrainu). | ||
+ | - **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. | ||
+ | |||
+ | === Dopredná | ||
+ | |||
+ | Hneď ako priradíme hodnoty premennej X, pomocou procesu forward checking | ||
+ | |||
+ | 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, | ||
+ | - 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. | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Ako zistiť nekonzistenciu atmost constrainu? | ||
+ | |||
+ | - Zosumujeme minimálne hodnoty domén. | ||
+ | - 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, | ||
+ | |||
+ | |||
+ | === 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), | ||
+ | - Nový stav ohodnotíme pomocou vyhodnocovacej funkcie a prijmeme ho podľa toho, aký algoritmus používame, | ||
+ | |||
+ | |||
+ | |||
+ | |||
==== 6. Logické agenty: výroková a predikátová logika. | ==== 6. Logické agenty: výroková a predikátová logika. | ||
Line 644: | 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, | ||
+ | |||
+ | * 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 726: | Line 1027: | ||
=== Lifting === | === Lifting === | ||
- | - doplnit | + | - 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 953: | Line 1254: | ||
* sila týchto spojení sa so vzdialenosťou od neurónu mení podľa profilu tvaru mexického klobúka – aktívny neurón excituje susedné a inhibuje vzdialené neuróny (čo spôsobí lepšiu profiláciu oblastí na typy vstupov, pre 1 vstup je aktívny viac než 1 neurón, čo zabezpečuje redundanciu, | * sila týchto spojení sa so vzdialenosťou od neurónu mení podľa profilu tvaru mexického klobúka – aktívny neurón excituje susedné a inhibuje vzdialené neuróny (čo spôsobí lepšiu profiláciu oblastí na typy vstupov, pre 1 vstup je aktívny viac než 1 neurón, čo zabezpečuje redundanciu, | ||
{{: | {{: | ||
- | * Hebbovské učenie: fire together wire together; výstup: {{: | + | |
* učenie bez učiteľa, lineárne neuróny, ktoré v podstate priamo reprezentujú vstupy | * učenie bez učiteľa, lineárne neuróny, ktoré v podstate priamo reprezentujú vstupy | ||
- | * algoritmus winner-take-all (z pohľadu susedov winner-take-most) – neurón s maximálnou aktiváciou (best matching unit) vyhráva a upravujú sa mu váhy – učenie so súťažením, | + | * algoritmus |
- | * nevýhoda algoritmu: môžu vzniknúť mŕtve neuróny (váhy sa inicializujú náhodne, môže sa stať, že niektoré neuróny nezareagujú na žiaden vstup, teda sa nebudú vôbec adjustovať a ani ďalej reagovať = ostanú mŕtve) | + | * nevýhoda algoritmu: môžu vzniknúť |
- | * simulácia laterálnej interakcie = adjustovanie váh len vo vybranom okolí neurónu, ktoré sa s pribúdajúcim časom zužuje | + | * simulácia laterálnej interakcie = adjustovanie váh len vo vybranom |
- | * štvorcové (Manhattanské, | + | |
{{: | {{: | ||
=== Algoritmus (Kohonen, 1982) === | === Algoritmus (Kohonen, 1982) === | ||
- náhodne vyber vstup x | - náhodne vyber vstup x | ||
- | - nájdi víťaza i* pre x : i* = argmin< | + | - nájdi víťaza i* pre x : i* = argmin< |
- uprav váhy: | - uprav váhy: | ||
- uprav všeob. parametre siete (rýchlosť učenia, veľkosť okolia) | - uprav všeob. parametre siete (rýchlosť učenia, veľkosť okolia) | ||
Line 973: | Line 1274: | ||
=== Klasterizácia dát (??) === | === Klasterizácia dát (??) === | ||
- | * z Wikipedie: Cluster analysis or clustering is the assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense. Clustering is a method of unsupervised learning, and a common technique for statistical data analysis used in many fields, including machine learning, data mining, pattern recognition, | + | * z Wikipedie: |
- | * Výborná vlastnosť SOM: zachovávanie topológie dát – sieť je po naučení usporiadaná, | + | * Výborná vlastnosť SOM: **zachovávanie topológie dát** – sieť je po naučení usporiadaná, |
- | * Ďalšia vlastnosť: aproximácia hustoty vstupných dát | + | * Ďalšia vlastnosť: aproximácia |
- | * Magnifikačný faktor = počet váhových vektorov pripadajúcich na jednotkovú plochu vstupného priestoru, funkcia pozície v mape | + | |
{{: | {{: | ||
=== 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 987: | Line 1289: | ||
+ | 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í | ||
+ | |||
+ | každý stav sa označuje pojmom chromozóm, je reprezentovaný binárnym reťazcom x dĺžky N | ||
+ | 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 | ||
+ | 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 | ||
+ | čas t je diskrétna premenná označujúca epochu, alebo generáciu | ||
+ | P< | ||
+ | === Postup reprodukcie: | ||
+ | == 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, | ||
+ | == Kríženie == | ||
+ | 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. | ||
+ | skrížením dostaneme dva nové chromozómy. | ||
+ | < | ||
+ | i=4 | ||
+ | x = 000[00111] | ||
+ | x' = 000[11001] | ||
+ | z = 00011001 | ||
+ | z' = 00000111 | ||
+ | </ | ||
+ | Okrem popísaného jednobodového kríženia existujú aj iné typy (dvoj- či viac- bodové) | ||
+ | == Mutácia == | ||
+ | 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-> | ||
+ | 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** | ||
+ | proces reprodukcie sa končí ak: | ||
+ | * 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: === | ||
+ | Návrat, P. a kol., Umelá inteligencia, |