This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
cogsci:ui [2009/06/16 17:53] breakk |
cogsci:ui [2009/06/23 23:02] |
||
---|---|---|---|
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 | ||
- | |||
- | |||
- | |||
- | Zdroje: Návrat, P. a kol., Umelá inteligencia, | ||
- | téma prehľadávania a roznych typov stratégií / algoritmov je vcelku vycerpavajuco (pre nase potreby myslim) popisana 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. | ||
- | |||
- | //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. ==== | ||
- | |||
- | ==== 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. ==== | ||
- | |||
- | ==== 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 === | ||
- | |||
- | - doplnit (neviem odkial) | ||
- | |||
- | |||
- | === 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 | ||
- | |||
- | ==== 13. Rekurentné neurónové siete, architektúry, | ||
- | |||
- | ==== 14. Evolučné algoritmy: základné koncepty a mechanizmy, využitie v UI ==== | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||