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 05:23] breakk |
cogsci:ui [2009/06/19 01:24] vlatko_dz |
||
---|---|---|---|
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. ==== | ||
+ | |||
+ | === Definícia CSP === | ||
+ | |||
+ | A **constraint satisfaction problem** (or CSP) is a special kind of problem that satisfies some | ||
+ | additional structural properties beyond the basic requirements for problems in general. In a CSP, | ||
+ | the **states** are defined by the values of a **set of variables** and the goal test specifies a **set of | ||
+ | constraints** that the values must obey. | ||
+ | |||
+ | * **Množina n premenných**: | ||
+ | * **Množina obmedzení, ohraničení (constraints)**: | ||
+ | * Ku každej premennej Xi patrí neprázdna **doména** Di jej **možných hodnôt** | ||
+ | * **Stav:** definovaný priradením hodnôt premenným. | ||
+ | * **Konzistentný stav: | ||
+ | * **Kompletný stav:** stav, v ktorom sa použije každá premenná (kazda premenna ma priradenu hodnotu). | ||
+ | * **Riešenie CSP:** kompletny a konzistentny stav. | ||
+ | * Niekedy berieme riešenie, ktoré maximalizuje vyhodnocujúcu funkciu (objective function). | ||
+ | |||
+ | **Example: | ||
+ | |||
+ | For example, the 8-queens problem can be viewed as a | ||
+ | CSP in which the variables are the locations of each of the eight queens; the possible values are | ||
+ | squares on the board; and the constraints state that no two queens can be in the same row, column | ||
+ | or diagonal. A solution to a CSP specifies values for all the variables such that the constraints | ||
+ | are satisfied. | ||
+ | |||
+ | **Constraint types:** | ||
+ | |||
+ | Constraints come in several varieties. **Unary** constraints concern the value of a single variable. | ||
+ | **Binary** constraints relate pairs of variables. The constraints in the 8-queens problem are all binary constraints. | ||
+ | **Higher-order** constraints involve three or more variables. | ||
+ | |||
+ | |||
+ | === Uzlová konzistencia (Node Consistency) === | ||
+ | |||
+ | V constraint grafe uzol (node) reprezentuje premennú. | ||
+ | |||
+ | //Uzol je **node consistent (uzlovo konzistentný)** ak pre každú hodnotu x v doméne danej premennej sú splnené unárne constrainy.// | ||
+ | |||
+ | **Eliminácia uzlovej nekonzistentnosti: | ||
+ | |||
+ | Ak to tak nie je, eliminujeme „node inconsistency“ odstránením tých hodnôt z domény, ktoré ju vytvárajú. | ||
+ | |||
+ | === Hranová konzistencia (Arc Consistency) === | ||
+ | |||
+ | Binárne constrainy sú reprezentované hranami (arc) constraint grafu (priklad na constraint graf je nizsie). | ||
+ | |||
+ | //Hrana (Vi, Vj) je **hranovo konzistentná (arc consistent)** ak pre každú hodnotu x z domény | ||
+ | |||
+ | **Eliminácia hranovej nekonzistencie: | ||
+ | |||
+ | Ak to tak nie je, vymažeme tie hodnoty z domény Vi ku ktorým niet korešpondujúcich hodnôt v doméne premennej Vj. | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Vidime tu hranovo konzistentny graf, ktory nema riesenie. Domena pre vsetky premenne je rovnka: {1,2} a je jasne ze dany problem nema riesenie. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
==== 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 580: | 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 662: | Line 1025: | ||
=== 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 757: | Line 1120: | ||
* Kto ma zaujem, tak nech si cita na [[http:// | * Kto ma zaujem, tak nech si cita na [[http:// | ||
+ | |||
+ | === Plánovanie v reálnom svete === | ||
+ | |||
+ | * POP metóda sa hodí na predplánovanie. | ||
+ | * POP metóda nič nehovorí o trvaní jednotlivých akcií. | ||
+ | * STRIPS reprezenácia akcií je založená na situačnom kalkule, reprezentuje len akcie, nie ich trvanie. | ||
+ | * Rozšírenie POP: „scheduling“ – časový plán | ||
+ | |||
=== Zdroje: === | === Zdroje: === | ||
Line 869: | Line 1240: | ||
==== 12. Samoorganizujúce | ==== 12. Samoorganizujúce | ||
+ | SOM = SamoOrganizujúca sa Mapa | ||
+ | |||
+ | Zachovanie topológie – zobrazenie charakteristických čŕt trénovacej množiny dát – na vstupy, ktoré sú si blízke vo vstupnom priestore budú reagovať neuróny fyzicky blízke na mape, mapa: zväčša 2 alebo 3 rozmerná mriežka (alebo reťaz), 1 políčko = 1 neurón | ||
+ | |||
+ | Biologická motivácia: mechanizmus projekcie zo sietnice na mozgovú kôru | ||
+ | |||
+ | {{: | ||
+ | |||
+ | === Mechanizmus fungovania === | ||
+ | * okrem prepojení neurónov so vstupmi (každý s každým) aj **laterálne spojenia** medzi neurónmi | ||
+ | * 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 | ||
+ | * 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**, | ||
+ | * 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) | ||
+ | * simulácia laterálnej interakcie = adjustovanie váh len vo vybranom **okolí** neurónu, ktoré sa s pribúdajúcim časom zužuje | ||
+ | * **štvorcové** (Manhattanské, | ||
+ | {{: | ||
+ | |||
+ | === Algoritmus (Kohonen, 1982) === | ||
+ | - náhodne vyber vstup x | ||
+ | - nájdi víťaza i* pre x : i* = argmin< | ||
+ | - uprav váhy: | ||
+ | - uprav všeob. parametre siete (rýchlosť učenia, veľkosť okolia) | ||
+ | - ak splnené kritéria: koniec (počet epoch, miera úspešnosti, | ||
+ | |||
+ | Ako správne nastavovať všeobecné parametre siete: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | === 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, | ||
+ | * 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** | ||
+ | * **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 === | ||
+ | SOM | ||
+ | |||
+ | Príklady použitia: minimum spanning tree, lexical maps, robotic arm control | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | text v dokumente: {{: | ||
+ | |||
+ | materialy: kniha UvodDoNS: {{: | ||
==== 13. Rekurentné neurónové siete, architektúry, | ==== 13. Rekurentné neurónové siete, architektúry, | ||
==== 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í | ||
+ | |||
+ | 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, | ||