This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
cogsci:ui [2009/06/23 23:02] |
cogsci:ui [2009/06/24 01:00] gnd |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== otazky z ui ===== | ||
+ | [[itchybit|naspat na cogsci]] | ||
+ | ==== 1. Prehľadávanie: | ||
+ | |||
+ | Všeobecné riešenie problémov | ||
+ | |||
+ | **pojmy:** | ||
+ | * stav - konfigurácia sveta | ||
+ | * stavový priestor - množina všetkých dosiahnuteľných stavov | ||
+ | * počiatočný stav - východzí bod, v strome je to často východzí uzol 0 | ||
+ | * množina operátorov - subor akcií, ktorými sa svet dostáva z jedného stavu do nasledujúceho | ||
+ | * riešenia - môže ním byť stav, alebo cesta k stavu | ||
+ | |||
+ | Prehľadávanie, | ||
+ | |||
+ | Základom takéhoto algoritmu je **prehľadávanie stavového priestoru**. Na počiatočný stav aplikujeme dostupné operátory, výsledkom sú nové stavy. | ||
+ | * úplné rozvitie stavu - na daný stav aplikujeme všetky dostupné operátory | ||
+ | * čiastočné rozvitie - aplikácia jedného operátora | ||
+ | Po rozvinutí predchádzajúceho stavu získame obvykle viacero nových stavov. Metódu výberu nasledujúceho stavu, ktorý budeme rozvíjať nazývame **stratégiou hľadania**. | ||
+ | Hľadanie riešenia prebieha v stavovom priestore, ten je možné reprezentovať orientovaným grafom. Tá časť grafu, ktorá bola preskúmaná a algoritmus má k dispozcii nejaku jej reprezentáciu sa nazýva strom hľadania. Hľadať teda znamená generovať tento strom. | ||
+ | |||
+ | * Koreň - začiatočný uzol stromu | ||
+ | * Listy - uzly, ktoré predstavujú nerozvité stavy, ktoré buď ešte neboli rozvinuté, alebo ich rozvitím vznikla prázdna množina uzlov | ||
+ | |||
+ | Stavový priestor je tiež na rozdiel od stromu hľadania často konečný, no strom môže prostredníctvom určitých operátorov generovať v uzloch aj predchádzajúce stavy, čím sa teoreticky môže stať nekonečným. (o.i. z toho vyplýva, že dva rôzne uzly môžu byť reprezentáciou rovnakého stavu) | ||
+ | |||
+ | Pojmy k reprezentacii uzlov v strome: | ||
+ | * danému uzlu zodpovedajúci stav | ||
+ | * rodičovský uzol | ||
+ | * operátor, ktorý bol aplikovaný pri generovaní uzla | ||
+ | * hĺbka uzla (počet uzlov z koreňa do aktuálneho uzlu) | ||
+ | * cena cesty z počiatočného uzla do aktuálneho | ||
+ | |||
+ | !! uzol je údajová štruktúra, | ||
+ | |||
+ | Stratégie hľadania a ich vlastnosti: | ||
+ | Stratégia hľadania je kritérium podľa ktorého sa riadime pri vyberaní nasledujúceho stavu | ||
+ | * Úplnosť: ak riešenie existuje, tak sa nájde | ||
+ | * Časová zložitosť: | ||
+ | * Pamäťová zložitost: koľko pamäti zaberie | ||
+ | * Prípustnosť: | ||
+ | |||
+ | Dva základné typy hľadania: | ||
+ | * Slepé / Neinformované - všeobecné stratégie hľadania riešenia | ||
+ | * Heuristické / informované - Heuristika je doplňujúca informácia, | ||
+ | |||
+ | Niektoré vlastnosti heuristík: | ||
+ | * Dobrá (účinná) heuristika nemusí vždy zaručovať prípustnosť - zvyčajne pomôže nájsť dobré, ale nie najoptimálnejšie riešenie | ||
+ | * Nemusí vždy zaručovať úplnosť - účinné heuristiky môžu spôsobiť prehliadnutie riešenia | ||
+ | * Heuristiky sa zvyčajne viažu k špecifickým problémom a v prípade že ich je viac, môžu si navzájom protirečiť (odporúčať protirečivé akcie) | ||
+ | |||
+ | == to be continued == | ||
+ | |||
+ | |||
+ | Zdroje: | ||
+ | Návrat, P. a kol., Umela inteligencia, | ||
+ | |||
+ | ==== 2. Agent, typy jednoduchých agentov, agentová funkcia, agentový program. ==== | ||
+ | |||
+ | === Agent === | ||
+ | |||
+ | An agent is just something that perceives and acts. There are many definitions: | ||
+ | |||
+ | //"An agent is anything that can be viewed as **perceiving** its environment through sensors and **acting** | ||
+ | upon that environment through effectors."// | ||
+ | |||
+ | //" | ||
+ | |||
+ | A human agent has eyes, ears, and other organs for sensors, and hands, legs, mouth, and other body parts for effectors. A robotic agent substitutes cameras and infrared range finders for the sensors and various motors for the effectors. A software agent has encoded bit strings as its percepts and actions. | ||
+ | |||
+ | |||
+ | A generic agent: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Agents interact with environments through sensors and effectors. | ||
+ | |||
+ | === Performance Measure (miera úspešnosti) === | ||
+ | |||
+ | //Russell & Norvig:// | ||
+ | |||
+ | We use the term **performance measur**e for the how—the criteria that determine how | ||
+ | successful an agent is. We as outside observers establish a standard of what | ||
+ | it means to be successful in an environment and use it to measure the performance of agents. | ||
+ | As an example, consider the case of an agent that is supposed to vacuum a dirty floor. A | ||
+ | plausible performance measure would be the amount of dirt cleaned up in a single eight-hour shift. | ||
+ | |||
+ | //ZUI slajdy:// | ||
+ | |||
+ | **Performance measure**: hodnotí | ||
+ | - voľba: Merajme p.m. množstvom špiny vysatej za 8 hodín. | ||
+ | - voľba: Merajme p.m. časom, počas ktorého ostane dlážka čistá | ||
+ | - voľba: Meranie p.m. minimálnym počtom krokov, ktoré agent urobí so zohľadnením 1. a 2. | ||
+ | - voľba: Možno brať do úvahy aj iné faktory, napr. hlučnosť. | ||
+ | |||
+ | **Racionálny agent**: koná tak, aby bol úspešný, aby robil rozumné akcie z hľadiska miery úspešnosti. | ||
+ | |||
+ | Rozumná akcia v čase t závisí od: | ||
+ | - kritéria miery úspešnosti | ||
+ | - postupnosti doterajších vnemov (na jej základe sa agent učí) | ||
+ | - znalosti prostredia v ktorom koná (môže mať napr. model prostredia) | ||
+ | - akcií ktoré dokáže vykonať | ||
+ | |||
+ | //Russell & Norvig:// | ||
+ | |||
+ | **Ideal Rational Agent / Ideálny racionálny agent:** | ||
+ | |||
+ | "For each possible percept sequence, an | ||
+ | ideal rational agent should do whatever action is expected to maximize its performance measure, | ||
+ | on the basis of the evidence provided by the percept sequence and whatever built-in knowledge | ||
+ | the agent has." | ||
+ | |||
+ | " | ||
+ | |||
+ | === Autonomy === | ||
+ | |||
+ | // | ||
+ | |||
+ | " | ||
+ | an external assistance." | ||
+ | |||
+ | //ZUI slajdy:// | ||
+ | |||
+ | " | ||
+ | |||
+ | === PEAS === | ||
+ | |||
+ | **Task environment**: | ||
+ | |||
+ | **PEAS** is a specification of agent' | ||
+ | * P - Performance measure (miera úspešnosti) | ||
+ | * E - Environment | ||
+ | * A - Actuators | ||
+ | * S - Sensors | ||
+ | |||
+ | === Environments === | ||
+ | |||
+ | {{: | ||
+ | |||
+ | //ZUI slajdy:// | ||
+ | |||
+ | * **Obsiahnuteľné (observable) vs. neobsiahnuteľné**: | ||
+ | * **Deterministické vs. nedeterministické**: | ||
+ | * **Epizodické vs. neepizodické**: | ||
+ | * **Statické vs. dynamické**: | ||
+ | * **Diskrétne vs. spojité**: Ak je množstvo vnemov a akcií s nimi spojených obmedzený a jasne definovaný počet, prostredie je diskrétne (šach). | ||
+ | * **Jednoagentové vs. multiagentové**: | ||
+ | |||
+ | === Agent Types === | ||
+ | |||
+ | Typy jednoduchých agentov - 4 basic types in order of increasing generality: | ||
+ | - Simple reflex agents (jednoduchý reflexný agent) - spolieha sa na jeden okamžitý vnem, na jeho základe vyberie akciu | ||
+ | - Model-based reflex agents (refl. agent využívajúci model prostredia) - vhodný pre čiastočne pozorovateľné prostredie; má vedomosti o tých častiach prostredia, ktoré nevidí | ||
+ | - Goal-based agents (agent orientovaný na cieľ) - využíva informáciu o cieli (popis situácií, ktoré chceme dosiahnuť); | ||
+ | - Utility-based agents (agent zohľadňujúci cenu cesty) - nielen cieľ je dôležitý, | ||
+ | |||
+ | |||
+ | **Príklad**: | ||
+ | |||
+ | **Reflexný agent: | ||
+ | - Vníma, či auto pred ním brzdí, ak áno, brzdí tiež. | ||
+ | |||
+ | **Agent s modelom prostredia: ** | ||
+ | - Vníma, či auto pred ním brzdí, ak áno, brzdí tiež. | ||
+ | - Má model prostredia, napr. aká je priemerná rýchlosť ak som na trojprúdovej diaľnici, poľnej ceste, vlhkej ceste....apod. A brzdí aj vtedy, keď sa zmení cesta. | ||
+ | |||
+ | **Agent orientovaný na cieľ: ** | ||
+ | - Vníma, či auto pred ním brzdí, ak áno, brzdí tiež. | ||
+ | - Má model prostredia, napr. aká je priemerná rýchlosť ak som na trojprúdovej diaľnici, poľnej ceste, vlhkej ceste....apod. A brzdí aj vtedy, keď sa zmení cesta. | ||
+ | - Má informáciu o cieli cesty, keď je v cieli, brzdí a zastane. | ||
+ | |||
+ | **Agent orientovaný na cenu cesty (utility): ** | ||
+ | - Vníma, či auto pred ním brzdí, ak áno, brzdí tiež. | ||
+ | - Má model prostredia, napr. aká je priemerná rýchlosť ak som na trojprúdovej diaľnici, poľnej ceste, vlhkej ceste....apod. A brzdí aj vtedy, keď sa zmení cesta. | ||
+ | - Má informáciu o cieli cesty, keď je v cieli, brzdí a zastane. | ||
+ | - Vie si z viacerých možností ako sa dostať do cieľa vyberie tú, ktorá ho najmenej stojí. | ||
+ | |||
+ | |||
+ | === Agent Function and Agent Program === | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **Agent function** maps the percept histories to actions (mathematical abstraction): | ||
+ | |||
+ | //[f: P* -> A]// | ||
+ | |||
+ | The **agent program** runs on the physical architecture to produce f | ||
+ | |||
+ | //agent = architecture + program// | ||
+ | |||
+ | |||
+ | === Zdroje === | ||
+ | * [[http:// | ||
+ | * Prednášky zo ZUI1 | ||
+ | * [[http:// | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ==== 3. Informované a neinformované stratégie, popis, zložitosti. ==== | ||
+ | |||
+ | Hľadanie sa nazýva: | ||
+ | * neinformované, | ||
+ | * informované, | ||
+ | |||
+ | === Neinformované stratégie === | ||
+ | |||
+ | == Hľadanie do šírky == | ||
+ | postup: najskôr rozvinieme koreňový uzol v hĺbke //d//=0, potom rozvijeme všetky uzly nasledujúcej hĺbky //d//=1, atd. Vo všeobecnosti vždy najskôr rozvinieme všetky uzly v hĺbke //d//, až potom rozvíjame hĺbku //d//+1. | ||
+ | algoritmus generuje stavy a radí ich na koniec frontu, je to FIFO algoritmus (First In, First Out) | ||
+ | |||
+ | priklad: | ||
+ | {{: | ||
+ | |||
+ | Je to systematická stratégia, to znamená, že nevynechá ani jeden uzol a žiadny uzol nevyberie dva krat. | ||
+ | Ak existuje riešenie hľadaného problému, pomocou tejto stratégie sa určite nájde, to znamená, je to **úplná** stratégia. | ||
+ | Ak hrany grafu nie sú vážené a každá cesta má teda rovnakú cenu, je tento algoritmus **prípustný**. | ||
+ | Jeho nevýhodou je **exponenciálna** pamäťová, | ||
+ | |||
+ | == Stratégia rovnomernej ceny == | ||
+ | |||
+ | Ide o modifikáciu hľadania do šírky, resp. BFS je špeciálnym prípadom stratégie rovnomernej ceny s jednotnou cenou cesty. Na rozvitie vyberáme v tomto prípade vždy uzol //u//, ktorý je na najlacnejšej ceste g(u) a nie ten, ktorý je na najplytšej úrovni. | ||
+ | |||
+ | == Hľadanie do hĺbky == | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Hľadanie do hĺbky znamená, že vždy rozvíjame uzol, ktorý je na najhlbšej úrovni. V prípade, že pri prehľadávaní narazíme na uzol, ktorý už nemá následovníkov, | ||
+ | |||
+ | Algoritmus má exponenciálnu časovú zložitosť, | ||
+ | Nevýhodou je, že nie je prípustný t.j. nezaručuje nájdenie najlepšieho riešenia, avšak ani úplný t.j. nezaručuje, | ||
+ | Algoritmus môže zlyhať na zlom počiatočnom zvolení cesty, kedy by do nekonečna hľadal na ceste, na ktorej nie je riešenie, alebo sa môže zacykliť v štruktúre uzlov reprezentujúcich rovnaké stavy. | ||
+ | |||
+ | == Ohraničené hľadanie do hĺbky == | ||
+ | |||
+ | Takáto modifikácia sa pokúša zabrániť problému uviaznutia v hĺbke stromu bez nájdenia riešenia. Určíme hĺbku //m// a budeme predpokladať, | ||
+ | |||
+ | == Cyklicky sa prehlbujúce prehľadávanie do hĺbky == | ||
+ | |||
+ | V prípade, že nevieme zvoliť vhodnú hĺbku ohraničenia, | ||
+ | |||
+ | == Hľadanie do hĺbky s návratom == | ||
+ | |||
+ | klasické hľadanie do hĺbky rozvíja vždy všetkých následovníkov daného uzla, hľadanie s návratom rozvinie vždy iba jedneho následníka a ak nejde o listový uzol, tak rozvinie ďalej iba jedného následovníka aktuálneho uzla a skúma, či nejde o listový uzol. | ||
+ | Výhodou je šetrenie pamäte, kedže udržuje v pamäti vždy iba jedného následovníka. To ale znamená, že nemôžeme s istotou vybrať optimálneho následníka pomocou doplňujúcej informácie. | ||
+ | Nerieši problém úplnosti, kombinuje sa s ohraničeným a cyklicky sa prehlbujúcim hľadaním do hĺbky. | ||
+ | |||
+ | == Obojsmerné hľadanie == | ||
+ | |||
+ | Využíva sa v prípadoch, ak hľadaným riešením je cesta. Cieľová konfigurácia je známa, hľadáme ako ju dosiahnuť. Podmienkou je, že všetky operátory musia byť inverzné. | ||
+ | Hľadanie postupuje z počiatočného aj cieľového stavu vždy do opačného, vygenerovanie spoločného stavu znamená spojenie ciest, teda riešenie. | ||
+ | Časová aj pamäťová zložitosť je exponenciálna, | ||
+ | |||
+ | | ^ Do šírky | ||
+ | ^ Čas | b%%^%%d | ||
+ | ^ Pamäť | ||
+ | ^ Prípustná | ano | ano | nie | nie | ano | ano | | ||
+ | ^ Úplná | ||
+ | |||
+ | b - faktor vetvenia, d - hĺbka riešenia, m - maximálna hĺbka stromu hľadania, l - hraničná hĺbka | ||
+ | |||
+ | |||
+ | |||
+ | === Informované stratégie === | ||
+ | |||
+ | 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 aj na wikipedii | ||
+ | |||
+ | ==== 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. ==== | ||
+ | |||
+ | 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. | ||
+ | |||
+ | === Reflexní agenti vs. znalostní agenti === | ||
+ | |||
+ | * **Reflexný agent:** reaguje len na okamžitý vnem, má implementované pravidlá typu ak vnem potom akcia | ||
+ | * **Znalostný agent:** dokáže sa učiť, vyvodzovať z naučeného nové poznatky. Má implementovanú databázu znalostí (knowledge base). | ||
+ | |||
+ | === Znalostný agent (Knowledge-based Agent) === | ||
+ | |||
+ | The central component of a knowledge-based agent is its knowledge base, or KB. Informally, a | ||
+ | knowledge base is a set of representations of facts about the world. Each individual representation | ||
+ | is called a sentence. The sentences are expressed in a language called a knowledge representation language. | ||
+ | Initially, agent' | ||
+ | |||
+ | //Čo obsahuje znalostný agent?// | ||
+ | |||
+ | - Databázu poznatkov o svete (KB, knowledge base). | ||
+ | - Základnú databázu poznatkov (background knowledge base; môže byť prázdna) | ||
+ | - Mechanizmus usudzovania. | ||
+ | |||
+ | //Ako znalostný agent pracuje?// | ||
+ | |||
+ | * **Tell:** funkcia, pomocou ktorej do KB pridávame nové vety | ||
+ | * **Ask:** funkcia, pomocou ktorej sa pýtame na poznatky uložené v KB | ||
+ | |||
+ | Ako KB oznámiť vnemami získané nové znalosti? Ako ich zapísať do KB? -> **rečou logiky** | ||
+ | |||
+ | === Logic as a Knowledge Representation Language === | ||
+ | |||
+ | //" | ||
+ | |||
+ | The object of knowledge representation is to express knowledge in computer-tractable form, such that it can used to help agents perform well. A knowledge representation language is defined by two aspects: | ||
+ | - **The syntax** of a language describes the possible configurations that can constitute sentences. Usually, we describe syntax in terms of how sentences are represented on the printed page, but the real representation is inside the computer: each sentence is implemented by a physical configuration or physical property of some part of the agent. For now, think of this as being a physical pattern of electrons in the computer' | ||
+ | - **The semantics** determines the facts in the world to which the sentences refer. Without semantics, a sentence is just an arrangement of electrons or a collection of marks on a page. With semantics, each sentence makes a claim about the world. And with semantics, we can say that when a particular configuration exists within an agent, the agent believes the corresponding sentence. (ako sa vety vzťahujú k reálnemu svetu, významová stránka jazyka) | ||
+ | |||
+ | **Interpretácia: | ||
+ | |||
+ | **Model:** Matematická abstrakcia reálneho sveta, v ktorej je daná veta pravdivá. | ||
+ | |||
+ | === Vyplývanie (entailment) === | ||
+ | |||
+ | We want to generate new sentences that are necessarily true, given that the old sentences are true. This relation between sentences is called entailment, and mirrors the relation of one fact following from another. | ||
+ | |||
+ | Označujeme: | ||
+ | |||
+ | Logika pozostáva z: | ||
+ | * Formálneho systému opisujúceho problém t.j. zo syntaxe a sémantiky | ||
+ | * Teórie dokazovania t.j. množiny pravidiel logického odvodzovania | ||
+ | |||
+ | === Logické odvodzovanie (logical reasoning) === | ||
+ | |||
+ | Na základe logických relácií odvodzujeme zo známych výrokov neznáme. | ||
+ | |||
+ | Algoritmus odvodzovania (inference) je **korektný (sound)** ak odvodí len vety, ktoré z KB vyplývajú. | ||
+ | |||
+ | Algoritmus odvodzovania je **kompletný** ak dokáže odvodiť všetky vety , ktoré z KB vyplývajú. | ||
+ | |||
+ | === Výroková logika (Propositional Logic) === | ||
+ | |||
+ | //" | ||
+ | |||
+ | * **Jednoduchý výrok | ||
+ | * **Zložený výrok (sentence, formula):** obsahuje aspoň jednu logickú spojku | ||
+ | |||
+ | == Syntax (jazyk) výrokovej logiky == | ||
+ | |||
+ | symboly: | ||
+ | - logické konštanty True , False | ||
+ | - výrokové symboly | ||
+ | - unárna spojka negácie a binárne spojky konjunkcie, disjunkcie, implikácie, | ||
+ | - zátvorky (, | ||
+ | |||
+ | **Formula** je každý atomický výrok, jeho negácia, alebo množina takýchto formúl pospájaných logickými spojkami. Nič iného formula nie je. | ||
+ | |||
+ | == Sémantika výrokovej logiky == | ||
+ | |||
+ | Sémantika definuje pravidlá určovania pravdivosti formúl (viet) vo výrokovej logike a to vzhľadom na danú interpretáciu, | ||
+ | |||
+ | Pravidlá: | ||
+ | |||
+ | True je pravdivé v každej interpretácii a false je v každej nepravdivé. | ||
+ | |||
+ | Pravdivostná hodnota jednoduchého výroku musí byť v každej interpretácii určená. | ||
+ | |||
+ | Pre zložené vety máme pravidlá odvodzovania pravdivosti. | ||
+ | |||
+ | |||
+ | {{: | ||
+ | |||
+ | * **tautológia: | ||
+ | * **kontradikcia: | ||
+ | * **splniteľná formula (satisfability): | ||
+ | * **logická ekvivalencia: | ||
+ | * **platnosť (validity): | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | == Modus Ponens == | ||
+ | |||
+ | Modus ponens (Pravidlo odstránenia implikácie): | ||
+ | |||
+ | A ∧ (A => B) => B | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | == And Elimination == | ||
+ | |||
+ | And – elimination (pravidlo odstránenia konjukcie): Z konjukcie sa dá odvodiť ľubovoľný z jej konjuktov. Ak celá konjunkcia je pravdivá, všetky konjunkty musia byť pravdivé. | ||
+ | |||
+ | (A1, A2, ... An) => Ai | ||
+ | |||
+ | == And Introduction == | ||
+ | |||
+ | And introduction (pravidlo vovedenia konjukcie): Umožní z viacerých formúl odvodiť ich konjukciu. Ak sú formuly pravdivé, aj ich konjunkcia je pravdivá. | ||
+ | |||
+ | (A1, A2, ... An) => (A1 ∧ A2 ∧ ... ∧ An) | ||
+ | |||
+ | == Or Introduction == | ||
+ | |||
+ | Or introduction (pravidlo vovedenia dizjunkcie): | ||
+ | |||
+ | == Double Negative Elimination == | ||
+ | |||
+ | Pravidlo odstránenia dvojitej negácie: | ||
+ | |||
+ | ¬ ¬ A => A | ||
+ | |||
+ | == Unit Resolution == | ||
+ | |||
+ | Unit resolution (pravidlo jednotkovej rezolvencie): | ||
+ | |||
+ | (A ∨ B) ∧ ¬A => B | ||
+ | |||
+ | * Jednotková rezolvencia je zovšeobecniteľná na tzv. plnú rezolvenciu | ||
+ | * Resolvencia je špeciálny prípad modus ponens! | ||
+ | * Dôležitá vlastnosť resolvencie: | ||
+ | |||
+ | === Normálne formy === | ||
+ | |||
+ | * Resolvenčné pravidlá sa dajú aplikovať len na disjunkcie výrazov. | ||
+ | * Ak KB nie je v takejto forme, dajú sa tieto pravidlá uplatniť? | ||
+ | * Je možné každú formulu, vetu vo výrokovej logike previesť na disjukcie? | ||
+ | |||
+ | //Každá veta vo výrokovej logike je logicky ekvivalentná konjunkcii disjunkcií výrazov CNF (conjunctive normal form).// | ||
+ | |||
+ | == Algoritmus CNF: == | ||
+ | |||
+ | 1. X <=> Y nahradime (X => Y) ∧ (Y => X) | ||
+ | |||
+ | 2. X => Y nahradime (¬X ∨ Y) | ||
+ | |||
+ | 3. urobime upravy negacii: | ||
+ | |||
+ | * ¬ ¬ X ... X | ||
+ | * ¬(X ^ Y) ... ¬X v ¬Y | ||
+ | * ¬(X v Y) ... ¬X ∧ ¬Y | ||
+ | |||
+ | 4. vyuzijeme distributivitu konjunkcie a disjunkcie: | ||
+ | * X v (Y ∧ Z) ... (X v Y) ∧ (X v Z) | ||
+ | * (X ∧ Y) v Z ... (X v Z) ∧ (Y v Z) | ||
+ | |||
+ | 5. odstranime redundancie (napriklad X v X nahradime len X) | ||
+ | |||
+ | |||
+ | === Hornove Klauzy === | ||
+ | |||
+ | //" | ||
+ | |||
+ | Každú Hornovu klauzu možno napísať ako implikáciu. Predpokladom je konjunkcia pozitívnych literálov a záver je jeden pozitívny literál. | ||
+ | |||
+ | Napr. hornova klauza (¬L11 v ¬Breeze v B11) sa dá napísať ako implikácia (L11 ∧ Breeze) => B11. | ||
+ | |||
+ | " | ||
+ | |||
+ | " | ||
+ | |||
+ | Inferencia (vyvodzovanie nových poznatkov) v KB zloženej | ||
+ | * algoritmus dopredného zreťazenia (**forward chaining**) | ||
+ | * algoritmus spätného zreťazenia (**backward chaining**) | ||
+ | |||
+ | Vyvodzovanie v KB, ktorá je vo forme Hornových kláuz je prevediteľné v čase lineárnom vzhľadom na veľkosť KB. | ||
+ | |||
+ | == Forward Chaining == | ||
+ | |||
+ | Chceme ukázať, či literál Q vyplýva z KB. Najprv vezmeme všetky pozitívne literály z KB. Ak tie spĺňajú premisy nejakej implikácie, | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Theorem: //FC derives every atomic sentence that is entailed by KB.// | ||
+ | |||
+ | == Backward Chaining == | ||
+ | |||
+ | Máme literál Q. Nevieme, či je pravdivý. Hľadáme teda v KB tie implikácie, | ||
+ | |||
+ | == Forward vs. Backward Chaining == | ||
+ | |||
+ | * FC is data-driven, | ||
+ | * May do lots of work that is irrelevant to the goal | ||
+ | * BC is goal-driven, | ||
+ | * Complexity of BC can be **much less** than linear in size of KB | ||
+ | |||
+ | |||
+ | === Predikátová logika prvého rádu (first order logic, FOL) === | ||
+ | |||
+ | Predikátová logika má silnejšie výrazové prostriedky ako výroková. | ||
+ | |||
+ | Propositional logic has very limited expressive power (unlike natural language). E.g., cannot say "pits cause breezes in adjacent squares“ except by writing one sentence for each square. | ||
+ | |||
+ | Whereas propositional logic assumes the world contains facts, first-order logic (like natural language) assumes the world contains of: | ||
+ | - **Objects: | ||
+ | - **Relations: | ||
+ | - **Functions: | ||
+ | |||
+ | === Syntax predikátovej logiky === | ||
+ | |||
+ | - **Individuové premenné: | ||
+ | - **Predikátové symboly:** P, Q, R, | ||
+ | - **Konštanty: | ||
+ | - **Funkčné symboly:** f,g,h, tiež môžu menovať, špecifikovať indivíduum: | ||
+ | - **Logické symboly: | ||
+ | |||
+ | // | ||
+ | |||
+ | //** Funkcia:** reprezentuje zložené meno objektu. Priraďuje objektu iný objekt.// | ||
+ | |||
+ | Rozdiel medzi predikátom a funkciou je ten, že n-árny predikát priradí n-tici objektov nejakú pravdivostnú hodnotu, zatiaľ čo funkcia im priradí ďalší objekt. | ||
+ | |||
+ | // | ||
+ | |||
+ | //**Atóm / Atomická formula:** Ak P je n-árny predikátový symbol a p1, p2, ... pn sú termy, potom výraz P(p1, p2, ... pn) je atomická formula. Nič iné nie je atomická formula.// | ||
+ | |||
+ | // | ||
+ | |||
+ | === Sémantika predikátovej logiky === | ||
+ | |||
+ | Pravdivostná hodnota formule je určená interpretáciou I premenných, | ||
+ | |||
+ | == Interpretácia == | ||
+ | |||
+ | Príklad: ∀x (S(x) => S(f(f(X)))) | ||
+ | |||
+ | - Objekty sú ľudia, predikát S je „byť | ||
+ | - Objekty sú prir. čísla, S je „byť párny“, f (x)=x+1, veta znamená | ||
+ | |||
+ | Interpretácia I formuly predikátovej logiky priradí každej konštante a každej premennej objekty z domény D (obor interpretácie), | ||
+ | |||
+ | == Počítanie pravdivostných hodnôt formuly == | ||
+ | |||
+ | 1. Nech atomická formula A = P(t1 ... tn), P je n – árny predikát s termami t1 ... tn. Vrámci interpretácie | ||
+ | |||
+ | 2. Ak A a B sú formule vyhodnotené v kroku 1, potom: | ||
+ | * ¬A je pravdivá vtedy a len vtedy ak A je nepravdivá. | ||
+ | * Formula A∧B je pravdivá vtedy a len vtedy ak A a B sú pravdivé. | ||
+ | * Formula A∨B je pravdivá vtedy a len vtedy ak aspoň jeden z atómov A a B je pravdivý. | ||
+ | * Formula A=>B je pravdivá vtedy a len vtedy ak A je nepravdivá alebo B je pravdivá. | ||
+ | * Formula A<=>B je pravdivá vtedy a len vtedy ak A a B sú súčasne pravdivé alebo nepravdivé. | ||
+ | * Formula ∀x A(x) je pravdivá vtedy a len vtedy ak atomická | ||
+ | * Formula ∃x A(x) je pravdivá vtedy a len vtedy, ak atomická formula A(x) je pravdivá aspoň pre jedno x z domény D, ktorá je súčasťou zvolenej interpretácie I. | ||
+ | |||
+ | |||
+ | // | ||
+ | |||
+ | // | ||
+ | |||
+ | // | ||
+ | |||
+ | // | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ==== 7. Databáza znalostí vo výrokovej logike, metódy vyvodzovania. ==== | ||
+ | |||
+ | * KB je konjunkcia logických viet, zapísaných nejakym jazykom na reprezentaciu znalosti (knowledge representation language) - napriklad **vyrokovou logikou**. | ||
+ | * Aby sme KB vedeli vytvoriť, musíme vedieť ako pracovať s logickými vetami (syntax a semantika - popisane v otazke 6). | ||
+ | * Ulohou agenta (znalostneho) je zapísať vnemy do KB, odvodiť z KB najlepšiu akciu, zmenšiť KB tak, aby sme tam nemali zbytočné vety. | ||
+ | |||
+ | === Odvodzovacie pravidla vyrokovej logiky I. - Zaklady === | ||
+ | |||
+ | * Pozri otázku 6 | ||
+ | |||
+ | === Odvodzovacie pravidla vyrokovej logiky II. - Rezolvencne pravidlo === | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **Dôležitá vlastnosť resolvencie: | ||
+ | |||
+ | **Pouzitie: | ||
+ | |||
+ | === Odvodzovacie pravidla vyrokovej logiky II. - Forward a Backward Chaining === | ||
+ | |||
+ | * Popis algoritmov je v otazke 6. | ||
+ | |||
+ | |||
+ | |||
+ | ==== 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, | ||
+ | |||
+ | * Bavime sa hlavne o prvoradovej logike (first-order logic, FOL). Jej syntax a semantika su popisane v otazke 6. | ||
+ | * Higher-order logic allows us to quantify over relations and functions as well as over objects. | ||
+ | |||
+ | === Metódy vyvodzovania I. - Reduction to propositional inference by instantiation === | ||
+ | |||
+ | Suppose the KB contains just the following: | ||
+ | * ∀ x King(x) ∧ Greedy(x) ⇒ Evil(x) | ||
+ | * King(John) | ||
+ | * Greedy(John) | ||
+ | * Brother(Richard, | ||
+ | |||
+ | Instantiating the universal sentence in all possible ways, we have | ||
+ | * King(John) ∧ Greedy(John) ⇒ Evil(John) | ||
+ | * King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard) | ||
+ | * King(John) | ||
+ | * Greedy(John) | ||
+ | * Brother(Richard, | ||
+ | |||
+ | The new KB is propositionalized: | ||
+ | |||
+ | Ked si takto instancijujeme KB, tak mozme usudzovat tak isto ako vo vyrokovej logike (otazka 6). | ||
+ | |||
+ | **Problem: | ||
+ | |||
+ | === Metódy vyvodzovania II. - Generalized Modus Ponens === | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * Modus ponens is sound and complete. It derives only true sentences, and it can derive any true sentence that a knowledge base of this form entails (Zdroj: [[http:// | ||
+ | * Modus ponens works only for knowledge bases that contain only implications of positive literals (definite horn clauses). | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | === Metódy vyvodzovania III. - Forward a Backward Chaining === | ||
+ | |||
+ | * Vysvetlene v otazke 6. | ||
+ | |||
+ | == Forward Chaining == | ||
+ | |||
+ | * Sound and complete for first-order definite clauses | ||
+ | * Forward chaining is widely used in deductive databases | ||
+ | |||
+ | == Backward Chaining == | ||
+ | |||
+ | * Depth-first recursive proof search: space is linear in size of proof | ||
+ | * Incomplete due to infinite loops | ||
+ | * Inefficient due to repeated subgoals (both success and failure) | ||
+ | * Widely used (without improvements!) for logic programming | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | === Prolog Systems === | ||
+ | |||
+ | * Basis: backward chaining with Horn clauses + bells & whistles | ||
+ | * Logic programming | ||
+ | * Program = set of clauses = "'' | ||
+ | |||
+ | Example: | ||
+ | |||
+ | '' | ||
+ | |||
+ | |||
+ | === Unifikácia === | ||
+ | |||
+ | Example: We can get the inference immediately if we can find a substitution θ such that '' | ||
+ | * θ = {x/John, y/John} works. In that case, substitution θ is called a **unifier** (Zdroj: [[http:// | ||
+ | |||
+ | The **unification** of p and q is the result of applying unifier θ to both of them. | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | === Lifting === | ||
+ | |||
+ | - lifting je, ked zoberies odvodzovacie pravidla z vyrokovej logiky a modifikujes ich tak aby boli pouzitelne vo FOL (priklad: generalized modus ponens - vid vyssie) | ||
+ | |||
+ | |||
+ | === Zdroj: === | ||
+ | * {{: | ||
+ | |||
+ | |||
+ | ==== 10. Plánovanie: | ||
+ | |||
+ | === Plánovanie === | ||
+ | |||
+ | //Pod plánovaním rozumieme také zoradenie akcií agenta, ktoré ho dovedie od počiatočného stavu k cieľovému stavu.// | ||
+ | |||
+ | Predpoklad: Prostredie nech je typu classical planning environment, | ||
+ | |||
+ | Problémy plánovania: | ||
+ | - Vylúčenie irelevantných akcií | ||
+ | - Nájdenie spojitosti akcií a stavov | ||
+ | - Dobrá heuristika | ||
+ | - Rozloženie problémov na podproblémy | ||
+ | - Dobrá reprezentácia stavov a akcií | ||
+ | |||
+ | === STRIPS reprezentácia (STanford Research Institute Problem Solver) === | ||
+ | |||
+ | Skratka STRIPS sa pouziva v dvoch vyznamoch: | ||
+ | - Program vytvoreny cca v roku 1971 na STanford Research Institute, ktory vtedy volali " | ||
+ | - Formalizmus na reprezentaciu akcii - toto je pre nas dolezitejsie... | ||
+ | |||
+ | Pred tym ako vysvetlime STRIPS formalizmus, | ||
+ | |||
+ | Kazda akcia reprezentovana pomocou STRIPSu ma dve zlozky: abstraktny **operator** a jeho priradenu rutinu (**routine**). Operator je matematicka abstrakcia aplikovatelna na dany **model sveta**, ktora z neho vytvori novy model (aplikacia operatorov na modely sveta prebieha pri planovani). Vykonanim priradenej rutiny agent/robot skutocne posobi na svoje prostredie efektormi. Rutiny su teda programy, ktore mozu byt volane s parametrami, | ||
+ | |||
+ | Planovanie so STRIPS reprezentaciou je vlastne hladanie vhodnej postupnosti operatorov, veducich do cieloveho stavu. Kazdy z operatorov je popisany troma zlozkami: | ||
+ | - **Jeho meno a parametre** (s ktorymi ho aplikujeme na model sveta) | ||
+ | - **Preconditions** - podmienky aplikovatelnosti danej akcie na model | ||
+ | - **Effects** - dvojica mnozin **Add list** a **Delete list**, ktore popisuju ako dany operator upravuje model sveta (pridava atomy z add listu a maze atomy z delete listu) | ||
+ | |||
+ | **Je akcia aplikovateľná? | ||
+ | |||
+ | **Výsledok akcie:** Ak štartujeme v stave s, vplyvom akcie sa dostaneme do stavu s´. Každý literál, ktorý nie je v EFFECT časti schémy, ostáva nezmenený. Inak pozitívne literály (z Add listu) sú do s´ dodané (do konjunkcie), | ||
+ | |||
+ | **Frame problem:** Rieši sa pomocou „close world assumption“, | ||
+ | |||
+ | **Riešenie planning problému: | ||
+ | |||
+ | **Obmedzenia STRIPS reprezentácie: | ||
+ | * nesmú byť funkcie (aby sa akcie dali prepísať do výrokovej podoby) | ||
+ | * stavy opísané len pozitívnymi literálmi | ||
+ | |||
+ | |||
+ | === Total-order planning vs. Partial-order planning === | ||
+ | |||
+ | * **total order planning** -> Plánovanie ako prehľadávací problém (notacia napriklad STRIPS; modely su vrcholy, akcie su hrany stromu, plan je cesta z korena do jedneho z listov) | ||
+ | * **partial order plannning** -> Plánovanie ako CSP problém (notacia ADL podobna STRIPSu; graf nemusi byt strom) | ||
+ | |||
+ | === POP - Partial Order Planning === | ||
+ | |||
+ | //A **partial plan** is a plan which specifies all actions that need to be taken, but does not specify an exact order for the actions as the order does not matter.// | ||
+ | |||
+ | //A **linearization** of a partial order plan is a total order plan derived of the particular partial order plan.// The number of total-order linearizations for a given partial-order plan can be determined mathematically: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | where: | ||
+ | * n is the number of total-order linearizations | ||
+ | * a is the number of actions in the partial-order plan, not counting Start or Finish | ||
+ | * o is the number of ordering constraints, | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Takze partial-order planner produkuje partial-order plany, co su mnoziny akcii (pozor, nie postupnosti!), | ||
+ | |||
+ | |||
+ | === ADL Notácia === | ||
+ | |||
+ | * Notácia podobná STRIPS notácii. | ||
+ | * Rozdiel: V predpokladoch akcie dovoľuje aj negované litarály | ||
+ | * Príklad v ADL notácii – výmena vyfučanej pneumatiky: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Constrainty pre poradie akcii vyplyvaju z **kauzalnych liniek** medzi dvoma akciami. Ak akcia A ma za efekt //p//, ktore je podmienkou pre akciu B, znamena to ze je medzi A a B kauzalna linka a A musi byt vykonana niekedy skor ako B. | ||
+ | |||
+ | == Konzistentný plán == | ||
+ | |||
+ | - Neobsahuje slučky v radení constrainov. | ||
+ | - Nemá konflikty v kauzálnych linkách: Ak je akcia C zamenená za A, potom je v konflikte s kauzálnou linkou A ->p-> B prave vtedy, ak jej efektom je ¬p. | ||
+ | - Konzistentný plán bez otvorených predpokladov je riešením. | ||
+ | - Každá linearizácia, | ||
+ | |||
+ | === Graphplan Algoritmus === | ||
+ | |||
+ | Je to algoritmus, ktorý dokáže z grafov istého typu (tzv. planning graphs) vytiahnuť riešenie, teda plán. -> Alternatívny prístup k POP plánovaniu | ||
+ | |||
+ | * 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: === | ||
+ | |||
+ | * {{: | ||
+ | * {{: | ||
+ | * [[http:// | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ==== 11. Dopredné | ||
+ | |||
+ | |||
+ | === Konekcionizmus === | ||
+ | |||
+ | Prúd v rámci Umelej inteligencie a Kognitívnych vied, ktorý pracuje s konceptom mnohých identických výpočtových jednotiek ktoré sú spojené v nejakej sieti vzťahov. Väčšinou sa predpokladá, | ||
+ | |||
+ | * 1. Jednotky môžu predstavovať neuróny a spojenia synapsie, | ||
+ | * 2. Jednotky majú aktivačnú funkciu, ktorá rozhoduje o výstupnej aktivite jednotky (porovnanie s neurónmi a dynamikou ich vybudenia) | ||
+ | * 3. Spojenia medzi jednotkami sa premieňajú v čase v závislosti od chyby výstupu – učenie | ||
+ | * 4. Informácie sú uložené distribuovane medzi jednotkami – analógia ku distribuovanému fungovaniu mozgu a predpokladanej distribuovanej povahe pamäte. | ||
+ | * 5. Výpočet prebieha (aspoň teoreticky) paralelne | ||
+ | |||
+ | Konekcionistické architektúry sú hlavne zastúpené neuronovými sieťami. História neurónových sietí sa ťahá až do polovice 20tého storočia, kedy ich základy položil Rosenblatt svojou prácou na Perceptrone. | ||
+ | |||
+ | === Perceptron === | ||
+ | |||
+ | Perceptron je zjednodušený model neurónu. Tak ako neurón má vstupy od iných neŕonov (synapsie), centrálnu časť ktorá vstupy nejako spracuje (soma) a produkuje výstup (axón). Perceptrón môže byť diskrétny alebo lineárny – rozdiel je v tom, akým spôsobom sa zo vstupných dát produkuje výstup. | ||
+ | |||
+ | **Diskrétny perceptron** má prahovanie: pokiaľ suma váhovaných vstupov neprekročí nejaký prah, tak na výstup pošle nulu (prípadne -1, (prípadne hocičo, to je vlastne jedno)). Tým pádom je jasné, že diskrétny perceptron pracuje nespojito – buď vypľuje a, alebo b, ale nič medzi tým. | ||
+ | |||
+ | **Spojitý perceptrón** naproti tomu nemá prahovaciu funkciu (aj keď neskôr spomeniem tzv. Bias) a výstup je spojitou funkciou sumy váhovaných vstupov. Ako aktivačná funkcia sa najčastejšie sa používa [[http:// | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | Štruktúra perceptrónu je na obrázku hore. Perceptrónu sa prezentuje nejaký vstup, ktorý je vektor a ma X[i], I = 1...n zložiek (napr. Vektor (1,0,1,1,0) má päť zložiek). w[i] je váha vstupu x[i]. Každá | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Toto je všeobecná aktivačná funkcia perceptrónu. Diskrétny perceptrón má aktivačnú funkciu prahovanie, tj. ak suma vážených vstupov prekročí nejaký prah (povedzme 0.5 alebo 0), tak až potom dá perceptron nejaký výstup, inakšie dá nulu (alebo -1). Spojitý má napríklad už spomínanú sigmoidálnu funkciu. | ||
+ | |||
+ | Ako bolo spomenuté, neurónové siete sa učia, tj. pomocou nejakého pravidla učenia si upravujú svoje váhy. Podľa toho akým spôsobom prebieha učenie môžeme neurónové siete rozdeliť na | ||
+ | |||
+ | * 1. siete s učením s učiteľom | ||
+ | * 2. siete s reinforcement učením | ||
+ | * 3. siete s učením bez učiteľa | ||
+ | |||
+ | Perceptrón je zástupcom sietí v ktorých učenie prebieha s učiteľom. Základná myšlienka takéhoto upravovania váh je taká, že perceptrónu prezentujeme nejaký vstup, a on vypľuje výstup. Získaný výstup porovnáme s očakaványm výstupom (tj. takým aký by sme si želali) a vypočítame chybu, ktorú perceptrón spravil (napr. odrátame želaný výstup od získaného). Túto chybu potom použijeme na úpravu váh. | ||
+ | |||
+ | Konkrétne pravidlo učenia v diskrétnom perceptróne je: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Kde w(j) je j-ta váha, alfa je nejaký koeficient učenia, y je želaný výstup a f(x) je získaný výstup. x(j) je j-ty komponent vstupu. | ||
+ | |||
+ | Učenie v spojitom perceptróne je kúsok komplikovanejšie. Všeobecne sa tejto metóde hovorí gradient descent, pretože sa pre jej metaforické vyjadrenie používa predstava chybového priestoru, ktorý vyzerá ako lievik, na ktorého dne je optimálna (nulová) hodnota chyby. Gradient descent po tomto lieviku kráča tak, že sa snaží ísť stále smerom dolu, čo nás raz privedie na dno lievika. Toto je robené cez derivácie (pamätáme si, že nulová hodnota derivácie nejakej funkcie | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Všimnime si že používame deriváciu aktivačnej funkcie. D je želaný výstup, y je yískaný. Tie horné indexy p znamenajú “pre daný pattern” – tj. nejaký konkrétny vstup. | ||
+ | |||
+ | Diskrétne aj spojité perceptróny slúžia ako binárne klasifikátory. Majme nejakú skupinu dvoch rôznych entít, po natrénovaní sa perceptrón naučí rozoznávať medzi nimi. Problém nastáva, keď entity niesú lineárne separovateľné: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | |||
+ | Medzi zelenými a modrými bodkami sa nedá viesť priama čiara v 2D priestore a túto klasifikačnú úlohu by perceptróny vyriešiť nevedeli. Toto koncom 60tých rokov ukázali v knihe Perceptrons Minsky a Papert, s tým že ako konkrétny príklad použili fakt, že perceptrón sa nedokáže naučiť funkciu XOR. Ďalej predpokladali, | ||
+ | |||
+ | Tento problém v skutočnosti možno riešiť dvoma spôsobmi. Buď rožšírime dimenziu v ktorej pracujeme (v tomto prípade povedzme z 2D na 1000D), praktika, ktorá sa volá kernelová metóda, alebo použijeme, navzdory predpokladom Minského a Paperta viacvrstvové perceptróny. | ||
+ | |||
+ | |||
+ | === Viacvrstvové perceptróny === | ||
+ | |||
+ | Viacvrstvové perceptróny sa už prestali volať perceptróny, | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Viacvrstvové perceptróny vedia robiť všelijaké pekné veci, ako napríklad naučiť sa funkciu XOR, klasifikovať vzory, etc. Ich používanie je zhruba rovnaké ako u jednovrstvých, | ||
+ | V skratke ide o to, že sa na výstupnej vrstve vypočíta štandardným spôsobom chyba (želaný výsledok mínus získaný), táto chyba sa sieťou šíri naspäť tak že sa prenásobí váhami medzi daným neurónom v nižšej vrstve a neurónom vo vyššej vrstve, keď dorazí na začiatok, použije sa gradientová metóda a postupne sa upravia váhy medzi vrstvami. | ||
+ | |||
+ | === Voľba optimálneho modelu, zovšeobecnenie, | ||
+ | |||
+ | Voľba optimálneho modelu vlastne znamená, akú architektúru siete a reprezentácie vstupných a výstupných dát si zvolíme. Napríklad pokiaľ je náš klasifikačný problém lineárne separovateľný, | ||
+ | * Na binárne klasifikačné úlohy použijeme sigmoidu a povedzme prahovanie. | ||
+ | * Na klasifikačné úlohy s vyšším počtom tried použijeme 1-of-M kódovanie, teda výstupná vrstva bude mať M neurónov a pokiaľ budé vstup patriť do n-tej triedy, tak n-tý výstupný neurón dá jednotku, ostatné daju nulu. Inými slovami výstupný vektor bude mať samé nuly a len jednu jednotku na n-tom mieste. Aktivačnú funkciu softmax. | ||
+ | * Pre spojité ciele, ktoré sú ohraničené použijeme sigmoidu alebo tanh | ||
+ | * Pre zhora neohraničené ciele exponenciálnu aktivačnú funkciu. | ||
+ | |||
+ | Sieť pokiaľ je navrhnutá správne má vlastnosť, ktorej sa hovorí zovšeobecnenie. Pokiaľ ju natrénujeme na rozlišovanie medzi štvorcami a kruhmi, tak že štvorec bude na výstupe 0 a kruh 1, správne natrénovaná sieť by pravidelnému n-uholníku mala priradiť nejaké čislo medzi nula a 1, pričom by sa výsledok s rastúcim počtom strán asi približoval ku jednotke. Zovšeobecnenie vlastne znamená, že si sieť vztvorí akúsi reprezentáciu vstupnej funkcie, ktorú má aj pre jej časti, na ktorých nebola trénovaná. | ||
+ | |||
+ | S generalizáciou súvisí aj fenomén, ktorý sa volá overfitting. Pokiaľ použijeme moc veľa neurónov a vrstiev, može sa stať, že sieť po čase začne aproximovať oveľa komplikovanejšiu funkciu ako od nej chceme. Toto sa rieši tým že prebytočné neuróny a vrstvy odstraňujeme – tomuto sa hovorí network pruning. | ||
+ | |||
+ | Úspešnosť natrénovanej siete overíme tak, že jej prezentujeme vstupy a sledujeme ako ich dokáže klasifikovať. Pokiaľ by sme jej ale prezentovali vstupy na ktorých sieť bola trénovaná, | ||
+ | |||
+ | Regresia je asi lineárna regresia, ale niesom si istý, napíšem Farkašovi a moc sa mi to nechce, to je hnusná lineárna algebra/ | ||
+ | |||
+ | === Zdroje === | ||
+ | |||
+ | Haykina ani Kvasničku sa mi kvôli tomuto nechcelo čítať. | ||
+ | |||
+ | * Tento text vo formáte pdf: {{: | ||
+ | * Farkašov predmet [[http:// | ||
+ | * Wikipedia [[http:// | ||
+ | |||
+ | ==== 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, | ||
+ | |||
+ | **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 ==== | ||
+ | |||
+ | 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 -- toto rozpisem | ||
+ | * Genetické programovanie -- toto je take ze namiesto cisielok tie chromozomy predstavuju normalne ze zdrojovy kod programu (reprezentovany ako strom) | ||
+ | * 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.. | ||
+ | |||
+ | === Genetické algoritmy === | ||
+ | |||
+ | 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/ | ||
+ | |||
+ | Nejakym sposobom si teda zvolime dlzku n chromozomu, vacsinou je to tradeoff medzi jemnostou " | ||
+ | |||
+ | * Zvolime si nejaku velkost populacie P (povedzme 100) | ||
+ | * Nahodne inicializujeme populaciu P (teda vytvorime 100 nahodnych chromozomov) | ||
+ | * Spustime algoritmus | ||
+ | |||
+ | Algoritmus: | ||
+ | |||
+ | 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. | ||
+ | |||
+ | === 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 " | ||
+ | |||
+ | 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. |