Umělá inteligence

Tento souhrn slouží pro přípravu k magisterským státnicím pro obory Teoretická informatika. Detailní informace o předmětu hledej na stránkách Umělá inteligence I a Umělá inteligence II.

Rozsah látky

Oficiální seznam otázek ([1] léto 2013):

Reprezentace znalostí: stavový prostor, produkční systémy, reprezentace v predikátové logice. Prohledávací algoritmy; stromové, grafové a lokální prohledávání, heuristiky, algoritmus A* a jeho varianty. Hry; minimax a alfa-beta algoritmy. Splňování omezujících podmínek. Strojové dokazování vět, model checking (DPLL), dopředné a zpětné řetězení, rezoluční metoda a unifikace. Automatické plánování; plánovací doména a problém, plánovací operátory. Zpracování neurčité informace; Bayesovské sítě, podmíněná nezávislost, výpočet v Bayesovské síti, rozhodovací grafy, Markovské modely, Kalmanův filtr. Strojové učení; prohledávání prostoru verzí, rozhodovací stromy, Bayesovské učení, maximálně věrohodná hypotéza, EM algoritmus, zpětnovazební učení.

Materiály

• Slajdy: M. Vomlelová [2], R. Barták [3]
• V. Mařík, O. Štěpánková, J. Lažanský a kol., Umělá inteligence 1 - 5, Acaddemia
• S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, Berkeley [4]
• H. Habiballa, Umělá Inteligence, Ostravská Univerzita [5]

Bartákovy slidy pokrývají skoro vše. D-separaci ale například hledejte v Norvigovi.

Způsoby reprezentace znalostí

Viz také #Strojové dokazování vět.

Co se reprezentuje?

• ontologie objektů - typicky hierarchie tříd
• pravidla systému - logická pravidla
• události, akce - situační kalkulus
• tvrzení o čases - intervalová algebra

Proces tvorby báze znalostí

-zkoumá odvětví zvané znalostní inženýrství

Fáze procesu:

• indentifikace úlohy (jaké budou požadavky na výsledný systém)
• získání relevantních informací (objekty, vlastnosti systému)
• vytvoření jazyka pro popis domény
• zakodování axiomů a invariantů
• zakodování instance problému
• dotazy + vyhodnocování
• ladění báze znalostí (pokud něco nefunguje)

Celý proces se typicky opakuje několikrát - podobné postupy jako v softwarovém inženýrství.

Stavový prostor

Stavovým prostorem se v informatice rozumí konfigurace diskrétních stavů sloužící jako výpočetní model. Formálně může být stavový prostor definován jako čtveřice [N, A, S, G], kde:

• N je množina stavů
• A je množina přechodů mezi stavy
• S je neprázdná podmnožina N obsahující počáteční stavy
• G je neprázdná podmnožina N obsahující cílové stavy

Na procházení stavového prostoru je založena metoda řešení úloh zvaná Prohledávání stavového prostoru. S analýzou stavového prostoru souvisí také Teorie grafů.

Zdroje: Převzato z Stavový prostor(wiki)

RUSSEL, S.; NORVIG, P.. Artificial Intelligence: A Modern Approach. 2. vyd. New Jersey, USA : Prentice Hall, 2003. ISBN 0-13-790395-2. S. 59-136.

Produkční systémy

• odvozují pomocí inkrementálního dopředného řetězení (rete algoritmus)
• například přepisování řetězců podle pravidel gramatiky

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

Reprezentace v predikátové logice

• výroková logika má pěkné vlastnosti, ale často je příliš těžkopádná
• predikátová logika popisuje objekty a relace mezi nimi. Součásti: proměnné, konstanty (jména objektů) a funkční symboly dávají dohromady termy (jiná jména pro objekty). Predikáty tvrdí vlastnosti o termech, speciální predikát pro rovnost (identita objektů). Predikáty se spojují logickými spojkami, proměnné v predikátech jsou kvantifikovány.

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

Prohledávací algoritmy

Stromové prohledávání 

Začneme s počátečním stavem jako kořenem, pak vždy vybereme nějaký stav, otestujeme zda není cílový a provedeme jeho expanzi (přidáme následníky podle všech proveditelných akcí). Stavy se vybírají z okraje (fringe), měněním strategie výběru vznikají jednotlivé prohledávací algoritmy.

Grafové prohledávání 

Na rozdíl od stromového neopakuje stavy v různých vrcholech (tady se hodí, aby první nalezená cesta byla ta optimální).

Algoritmy pro neinformované prohledávání

• BFS (breadth first) používá FIFO pro okraj. První nalezené řešení nemusí být optimální. Problém je velká spotřeba paměti (řádově stejně jako spotřebovaný čas). Pokud chceme, aby první nalezené řešení mělo minimální cenu cesty z kořene, použijeme místo FIFO prioritní frontu. To ale ještě zhorší časovou a paměťovou složitost, navíc levné kroky můžou působit potíže.
• DFS (depth first) používá LIFO pro okraj. Není to úplný algoritmus a nemusí najít optimum. Paměťová složitost je nízká a lze ještě vylepšit backtrackingem. Je vhodné omezit maximální hloubku.
• IDS (iterative deepening) iteruje DFS a přitom zvyšuje limit na hloubku. To vede k úplnosti (při konečném větvení), zachovává si nízkou paměťovou náročnost a vystačí s řádově stejným časem jako BFS. Je to preferovaná metoda slepého prohledávání velkých prostorů, kde neznáme hloubku řešení.
• BDS (bidirectional) je vylepšení, které vyhledává paralelně z počátku i cíle. To je výhodné, protože při poloviční délce cesty klesají nároky obvykle mnohem rychleji než konstanta-krát. Pokud je cílových stavů více, můžeme je propojit do meta-stavu. Pokud jsou cílové stavy nebo následníci definováni implicitně, může být zpětné prohledávání příliš obtížné.

Informované prohledávání

Znalost problému lze využít pro zlepšení volby stavů pro expanzi.

evaluační funkce $ f(n) $ 

ohodnocuje uzly podle očekávané vhodnosti výběru (například aproximace zbývající délky do cíle). Při prohledávání budeme vždy expandovat vrchol s minimálním $ f(n) $.

heuristická funkce $ h(n) $ 

aproximuje zbývající cenu nejlevnější cesty z vrcholu $ n $ do cíle. Funkce je nulová právě v cílových stavech.

Prohledávací algoritmy

• greedy BFS (best first) volí $ f(n) := h(n) $, tedy vždy vybírá uzel, který vypadá nejblíže k cíli. Nemusí najít nejlepší řešení, ale pokud detekujeme cykly, vždy najde nějaké řešení.
• A* volí $ f(n) := h(n) + g(n) $, kde $ g(n) $ je délka příslušné cesty do vrcholu $ n $ (tu už známe přesně). A* tedy vybírá uzly s minimální očekávanou délkou celé cesty. Heuristika může být:
  • přípustná – vždy odhaduje skutečnost zdola, zaručuje optimalitu nalezeného řešení při stromovém prohledávání.
  • monotónní – $ h(n) \leq c(n,a,n') + h(n') $. Je to forma trojúhelníkové nerovnosti, implikuje přípustnost a zaručuje, že $ f(n) $ po cestě neklesá. Zaručuje optimalitu nalezeného řešení při grafovém prohledávání.

Pokud A* najde řešení, pak je optimální a navíc jsou vždy expandovány pouze stavy s $ f(n) $ menším než cena optima. Podobně jako u BFS je nejvíce limitující spotřebovaná paměť.

• IDA* (iterative deepening A*) funguje jako IDS, ale místo hloubky je limitována hodnota $ f(n) $. Limit se zvyšuje na nejmenší překročenou hodnotu v předchozí iteraci.
• rekurzivní BFS prohledává rekurzivně v lineárním prostoru. Pamatuje si druhou nejlepší hodnotu $ f(n) $ a používá ji jako limit pro DFS. Při navracení navíc ukládá zpřesněnou hodnotu $ f(n) $.
• zjednodušené MA*. IDA* i RBFS zahazují mnoho informace, chceme lépe využít dostupnou paměť. Hledání probíhá jako A*, ale vždy když dojde paměť, vyhodí list s největší hodnotou $ f(n) $. Podobně jako RBFS zlepšujeme při vyhazování listů hodnotu $ f(n) $ u rodiče.

Volba heuristik

• porovnávání heuristik:
  • dominance (jedna je vždy větší než druhá)
  • efektivní větvící faktor – experimentální metrika. Změřím počet expandovaných uzlů pro nalezení řešení v nějaké hloubce a spočtu, jaký větvící faktor by musel mít úplný strom stejné hloubky, aby obsahoval stejný počet uzlů.
• medoty hledání heuristik
  • relaxace problému – tak, aby byl problém snadno řešitelný a zároveň dával dobré (a přípustné) odhady cen.
  • databáze vzorů – předpočítáme řešení typických podproblémů.
  • kombinace heuristik – máme-li jich více, můžeme v každém vrcholu vybrat tu největší (výsledek dominuje všechny z nich).

Lokální prohledávání

Někdy není důležitá cesta, ale jen cíl. Lokální prohledávání pracuje pouze s aktuálním stavem a v každém kroku ho "trochu změní". Výhodou je jednoduchost a konstantní nároky na paměť. Typicky se začíná v náhodném stavu a z lokálního optima se uniká restartem (pamatujeme si nejlepší řešení). Lokální prohledávání je také vhodné při měnícím se prostředí nebo jako online algoritmus. Algoritmy:

• hill climbing vždy hladově vybere nejlepšího souseda. Problém nastává u hřebenů nebo plateau (plošin).
• stochastický HC volí stav náhodně z okolí, pravděpodobnost výběru závisí na hodnotě objektivní funkce.
• HC první volby bere první nalezený lepší stav z okolí. Vhodné při velkém množství sousedů.
• simulované žíhání kombinuje výhody HC a náhodné procházky. Vybere náhodně souseda a pokud je lepší, přejde do něj. Pokud není, zvolí mezi ním a HC s pravděpodobností závislou na aktuální teplotě a míře zhoršení optimalizované fukce. Idea je, že teplota klesá a hledání se tím ustaluje. Například lze volit o $ \Delta E $ horšího souseda v čase $ T $ s pravděpodobností $ e^{\Delta E / T} $.
• paprskové prohledávání ukládá $ k $ stavů najednou a z jejich společného okolí vždy zvolí nových $ k $ nejlepších stavů (tedy liší se od $ k $ paralelních HC). Takto lze lépe využít dostupnou paměť oproti ostaním lokálním technikám.
• genetické algoritmy jsou variantou paprskového prohledávání, inspirují se Darwinovou teorií. Soubor náhodných stavů se nazývá populace, každý jedinec je kódován řetězcem symbolů (jako DNA). Nová populace se vytváří kombinacemi genů stávající populace (často s pravděpodobnostmi závislými na efektivitách jedinců) a náhodnými mutacemi.

Hry

• v UI především hry dvou hráčů s nulovým součtem, střídáním, úplnou informací a determinismem.
• reprezentace pomocí stromu hry, vrcholy odpovídají stavům hry, akce jsou tvořeny možnými tahy hráčů, listy ohodnoceny funkcí zisku (výhra, remíza, prohra).
• optimální strategie je ta s nejlepším výsledkem proti neomylnému soupeři.

Algoritmus minimax

• ohodnocuje vnitřní vrcholy od listů tak, že hráč na tahu vybere tu hodnotu synů, která je pro něj nejlepší (jeden vybírá MIN, druhý MAX). Najde tedy optimální strategii.
• při více hráčích je potřeba ohodnocovat vrcholy vektory hodnot.
• α-β ořezávání vynechává prohledávání podstromů, které už výsledek nemůžou ovlivnit. První větev se vždy vyhodnotí úplně, nejlepší doposud dosažená hodnota je nastavena jako limit v podstromu pro druhého hráče. Pokud se mu limit podaří překročit, tato větev se už z pohledu rodiče nezlepší a nemůže jím být vybrána. Hodně záleží na uspořádání tahů, oba hráči by měli začínat prozkoumáváním nejvýhodnějších možností. Při ideálním uspořádání lze až zdvojnásobit hloubku prohledaných cest ve stejném čase.

Video s ukázkou

Nedokonalé strategie

• typicky není možné prohledávat strom až do listů, musíme ho ukončit dříve a minimax hodnotu nahradit odhadem, heuristickou evaluační funkcí. Ztrácíme tak záruku optimality nalezené strategie.
• volba evaluační funkce závisí na hře. Například odhad pravděpodobnosti, že je stav výherní, nebo materiální hodnota (šachy, dáma).
• problém uklidnění (quiescent) – dramatická změna evaluační funkce těsně za limitní hloubkou může způsobit velmi špatný odhad (například série výměny figur v šachu). Nestabilní stavy je vhodné selektivně prozkoumat hlouběji.
• efekt horizontu – špatnou situaci lze často odsouvat pod limitní hloubku, přestože je nevyhnutelná.
• možná vylepšení:
  • singulární prodloužení prozkoumá navíc jednotlivou větev výrazně lepších tahů pod limitní hloubkou.
  • dopředné prořezání zcela vynechá některé tahy (lidský přístup). Vhodné pro symetrie a tahy, které "vypadají nesmyslně".
  • transpoziční tabulky – pokud je možné dostat se do stejných pozic více způsoby, bývá výhodné zapamatovat si jejich ohodnocení.
• u her s náhodou je potřeba přidat uzly náhody. Větve popisují možné výsledky, ohodnocení je průměr ze synů vážený pravděpodobnostmi (očekávaná hodnota). Nezáleží tedy pouze na pořadí dané ohodnocením ale i na velikostech hodnot. Pokud je funkce zisku omezená, lze prořezávat ve stylu α-β. Problémem bývá příliš velké větvení.
• hry s částečnou informací jsou ještě komplikovanější. Je nutné nejen uvažovat více možností, ale také zda bude informace dostupná (aby bylo možné tah zvolit).

Splňování omezujících podmínek

CSP je jedna z možností pro reprezentaci problémů. Skládá se z proměnných s doménami (povolenými hodnotami) a množinou podmínek na proměnných (typicky binárních). Úkolem je najít ohodnocení proměnných splňující všechny podmínky, někdy se také optimalizuje hodnota objektivní funkce. Příklad: sudoku. Používá se deklarativní přístup k problému – vytvoří se model a pustí se obecný řešič podmínek.

CSP lze řešit standardními prohledávacími technikami – stav je částečné ohodnocení proměnných a akce je ohodnocení jedné proměnné. Výhoda je, že známe předem hloubku řešení (za předpokladu že existuje), navíc nelze cyklit a akce komutují. Lze také větvit jinak než ohodnocením proměnné, například lze půlit jejich domény. Obecné CSP je NP-těžký problém, ale při použití dobrých heuristik je na reálných problémech snadno řešitelné.

Problémově nezávislé heuristiky a techniky

• nejprve ohodnocovat nejvíce omezenou proměnnou, tedy tu s nejmenší doménou nebo nejmenším počtem možných akcí. V případě rovnosti se volí proměnná s nejvíce podmínkami s doposud neohodnocenými proměnnými. Tento fail-first princip vede k rychlejšímu odřezání neperspektivních větví (stejně je tu proměnnou někdy nutné ohodnotit).
• nejprve vybírat nejlépe vypadající hodnoty. Například ty, které nejméně omezují ostatní doposud neohodnocené proměnné. Je lepší ale použít problémově závislou heuristiku pro dobré hodnoty.
• forward checking – při instanciaci jsou přefiltrovány domény volných proměnných svázaných podmínkami s ohodnocovanou proměnnou. Pokud se některá doména vyprázdní, můžeme větev hned odříznout.
• konzistenční techniky – pokud se odfiltrují některé hodnoty z domén, lze změny propagovat i do dalších proměnných. Používají se především algoritmy pro hranovou konzistenci (například AC-3). Místo silnější konzistence se používají globální podmínky (například all_different, přes párování bipartitních grafů).

Strojové dokazování vět

Ve výrokové logice

Typická reprezentace znalostí je množina klauzulí, tedy CNF. Odvozování lze převést na test splnitelnosti (věta je logickým důsledkem znalostní báze, pokud by přidání její negace způsobilo nesplnitelnost). Metody testování splnitelnosti ve VL:

1. pomocí ověřování modelů
   • enumerace pravdivostní tabulky, tedy primitivní vyzkoušení všech kombinací hodnot proměnných.
   • DPLL algorirtmus, je úplný a korektní. Prohledává prostor částečných ohodnocení proměnných, kde akce jsou různá ohodnocení jedné proměnné. Pro zrychlení používá mnoho heuristik: test zda už jsou všechny klauzule splněné nebo nějaká nesplněná, výběr proměnné s výskyty vždy bez negace nebo vždy s negací, výběr klausule s jedním literálem.
   • lokální prohledávání prostoru úplných ohodnocení. Například WalkSAT používá kombinaci hill climbingu s náhodnou procházkou, kde sousední ohodnocení se liší v právě jedné proměnné a je minimalizován počet nesplněných klauzulí.
2. pomocí odvozování
   • rezoluční metoda: ze dvou klauzulí sdílejících komplementární literály udělá jednu klauzuli obsahující všechny literály z obou klauzulí kromě onoho komplementárního páru. Pokud existuje více párů, vzniká tautologická klauzule. Pokud v množině nelze rezolučním pravidlem odvodit novou klauzuli, je CNF splnitelná a lze najít ohodnocení. Výhodné jsou báze s Hornovskými klausulemi. Ty obsahují nejvýše jeden pozitivní literál. Dotazy v Hornovské bázi lze pak vyhodnocovat lineárně vzhledem k její velikosti, pomocí dopředného řetězení a zpětného řetězení.
     • dopředné řetězení je metoda řízená daty, postupuje od báze znalostí a odvozuje nové klauzule dokud neodvodí dotaz nebo nic dalšího nelze odvodit.
     • zpětné řetězení je metoda řízená dotazem. Vždy vezme jeden cíl a zkusí splnit libovolné pravidlo, které ho odvozuje.
     • Vysvětlění rezolučního kroku

V predikátové logice

Viz také #Reprezentace v predikátové logice. Možnosti odvozování v PL:

1. převedením do VL pomocí uzemnění (grounding)
   • za všechny univerzálně kvantifikované (nebo volné) proměnné dosadíme všechny možné termy
   • každou existenčně kvantifikovanou proměnnou nahradíme novou Skolemovou konstantou
   • pokud máme funkční symboly, existuje nekonečně mnoho termů. Herbrand: pokud odvození v PL existuje, pak stačí vygenerovat jen konečně mnoho termů. Můžeme tedy přidávat termy, dokud nenajdeme odvození. Pokud ale odvození neexistuje, nikdy neskončíme.
2. přímo v PL
   • skolemizace vytváří místo konstanty Skolemovu funkci. To je vždy nová funkce závisející na všech dříve univerzálně kvantifikovaných proměnných.
   • liftování: aplikace groundingu jen tam, kde je to nutné pro odvozování. Používá se zobecněný Modus Ponens, kde místo rovnosti předpokladů stačí substituovatelnost. Kromě formulí se tedy v důkazu udržuje substituce proměnných, která zaručuje platnost odvození.
   • unifikace najde nejobecnější substituci takovou, že dva termy jsou identické. Pokud nějaká substituce existuje, pak existuje právě jedna taková, že je obecnější než všechny ostatní (nejobecnější unifikátor, mgu).
   • hledání vzorů (pattern matching) – hledání faktů unifikovatelných s daným termem
   • unifikace potřebuje, aby oba termy používaly disjunktní množiny proměnných. Proto je potřeba před každým použitím pravidla provést standardizaci stranou, kde se všechny proměnné přejmenují na nová, nikde nepoužitá jména.
   • dopředné řetězení
     • pomocí zobecněného MP pravidla postupně odvozuje všechna platná tvrzení, dokud neodvodí nějaké unifikovatelné s dotazem nebo dokud nedosáhne pevného bodu.
     • je to korektní a úlný algoritmus, ale nemusí skončit kvůli funkčním symbolům.
     • rete algoritmus využívá faktu, že každé pravidlo má smysl znova zkoušet jen když byl odvozen nový fakt unifikovatelný s částí těla pravidla (inkrementální dopředné řetězení). Rete předzpracuje pravidla do sítě závislostí, takže lze relevantní pravidla rychle nalézt. Je využíván v produkčních systémech.
     • pravidla lze upravit tak, aby umožňovala pouze relevantní navázání proměnných z magické množiny.
   • zpětné řetězení
     • obpovídá prohledávání do hloubky, takže pro běh stačí prostor úměrný délce důkazu, ale lze se zacyklit a tedy prohledávání není úplné.
     • používá se v logickém programování (Prolog), kde je navíc přesně dáno pořadí vyhodnocování.
   • obecná rezoluční metoda pro CNF
     • používá liftovanou verzi rezolučního pravidla (s unifikací), potřebuje také klauzule standardizované stranou.
     • pro úplnost je nutné buď rozšířit binární rezoluci na více literálů nebo použít factoring pro odstranění redundantních (unifikovatelných) literálů
     • pro Hornovské klauzule odpovídá dopřednému řetězení, ale je to obecnější metoda.
     • pro efektivitu se používá řada heuristik, které rezoluci "vedou správným směrem". Především se preferují kroky, které vytváří co nejkratší klauzule (chceme totiž vyvodit spor, tedy prázdnou klauzuli).

Automatické plánování

• klasická reprezentace pomocí predikátové logiky bez funkcí. Úloha je tedy speciálním připadem strojového dokazování.
• atom je predikátový symbol s argumenty. Atomy dělíme na flexibilní (fluent) a neměnné (rigidní) podle toho, zda můžou měnit svoji pravdivost.
• stav je množina instanciovaných atomů. Používá se předpoklad uzavřeného světa (closed world assumption), tedy v každém stavu jsou pravdivé pouze instanciované atomy (na rozdíl od klasické logiky).
• plánovací operátor $ o $ je trojice:
  • jméno operátoru name$ (o) $ ve tvaru název(parametry), kde mezi parametry musí být všechny proměnné použité v operátoru.
  • předpoklady precond$ (o) $ jsou množina literálů, které musí být splněny, aby šel operátor použít.
  • efekty effects$ (o) $ je množina (flexibilních) literálů, které se stanou platnými po aplikaci operátoru.
• akce je plně instanciovaný operátor (za proměnné dosazeny konstanty). Použitelnost akce ve stavu je dána splněním předpokladů.
• plánovací doména $ \Sigma $ nad jazykem $ L $ s operátory $ O $ je trojice $ (S,A,\gamma) $ udávající množiny všech stavů, akcí a přechodovou funkci. Požadujeme uzavřenost $ S $ na aplikovatelné funkce.
• plánovací problém $ P $ je trojice $ (\Sigma,s_0,g) $ udávající plánovací doménu, počáteční stav a množinu literálů charakterizující cílový stav (to, co chceme aby platilo).
• plán $ \pi $ je posloupnost akcí. Při splnění podmínek plánovacího problému je jeho řešením.

Typy plánování

• plánování v prostoru stavů: uzly prostoru odpovídají stavům, hrany použitelným akcím, hledáme cestu z počátečního stavu do některého splňujího koncové podmínky.
  • dopředné plánování (forward search, progression) prohledává standardním dopředným způsobem (jako dopředné řetězení).
  • zpětné plánování (backward search, regression) hledá pozpátku. Pozor na to, že cíl je množina stavů. Používá se liftování (částečná instanciace akcí) pro další redukci větvícího faktoru, ale komplikuje se tím detekce cyklů. Viz standardizaci stranou a unifikaci. Neexistence plánu je jistá až po prohledání celého prostoru.
• plánování v prostoru plánů (PSP): uzly prohledávaného prostoru jsou částečné plány. Začínáme s prázdným plánem a postupně v něm opravujeme kazy tak, abychom plnili podmínky akcí a dosáhli cíle.
  • přidáváme akce a svazujeme proměnné (co se bude dít s čím)
  • přidáváme podmínky na vzájemné uspořádání akcí (robot musí před naložením přijet)
  • přidáváme kauzální vazby (mezi příjezdem robota a naložením se nesmí stát nic, co by naložení překazilo, například robot nesmí odjet)
  • počáteční a cílový stav je vhodné implementovat jako speciální akce (musí být první/poslední, počáteční/cílové parametry zakódovány v efektech/předpokladech)
  • odstraňujeme otevřené cíle – předpoklady o kterých ještě nebylo rozhodnuto, jak budou splněny. Najdeme operátor, který lze použít pro splnění předpokladu, přidáme ho do plánu (nebo přesuneme v plánu), svážeme proměnné a přidáme kauzální vazbu pro plněný cíl.
  • odstraňujeme hrozby – akce ohrožující kauzální vazbu. Pomocí definování uspořádání nebo navázání proměnných, aby efekt akce nebyl unifikovatelný s negací některého z předpokladů.
  • částečný plán je řešícím plánem, pokud je konzistentní a zcela bez kazů.

Zpracování neurčité informace

Různé přístupy k nejistotě v UI:

• nemonotónní logika (logika defaultů). Oproti klasické logice se přidáváním pravidel množina dokazatelných formulí nemusí jen zvětšovat, ale i zmenšovat.
• pravidla s mírou jistoty (fudge factors).
• pravděpodobnost. Kompletní sdružené hustoty bývají exponenciálně náročné na reprezentaci, (nejen) proto se využívá (podmíněné) nezávislosti. Typickým příkladem je #Bayesovská síť.
• fuzzy pravidla – míra pravdivosti, to není nejistota.

Bayesovská síť

Síť se skládá z DAG a CPT. DAG (orientovaný acyklický graf) má za vrcholy náhodné proměnné modelované sítí, hrany představují závislosti (které nemusí být kauzální). CPT (conditional probability tables) pro každý vrchol vyjadřuje rozdělení hodnot proměnné v závislosti na hodnotách přímých předchůdců v DAGu.

• d-separace ($ \perp_d $, strukturální podmíněná nezávislost): uzly $ i $ a $ j $ jsou d-separovány množinou uzlů $ Y $, jestliže pro všechny neorientované cesty mezi $ i $ a $ j $ platí, že obsahuje uzel ve kterém nastává jedna z možností:
  • hrany cesty se nesetkávají head-to-head a vrchol patří do $ Y $,
  • hrany cesty se setkávají head-to-head a vrchol ani žádný jeho následovník (přímý nebo nepřímý) nepatří do $ Y $.

(head-to-head znamená, že oba sousedi vrcholu na cestě jsou jeho předchůdci v DAGu)

• úkoly v BN (b. síti):
  • dotazy na podmíněné pravděpodobnosti za daných pozorovaných hodnot (za dané evidence).
  • cena informace: která evidence by nám nejvíce pomohla rozhodnout?
  • analýza senzitivity: na kterých proměnných je výsledek nejvíce závislý?
  • hledání příčiny: co nejppravděpodobněji způsobilo pozorovaný stav?

Odvozování v Bayesovské síti

1. přesné metody
   • enumerace: triviální algoritmus pro BN. Rekurzivně ohodnocuje volné proměnné a nasčítává faktory pravděpodobností. Mnoho podstromů se opakuje, a proto metoda potřebuje exponenciální čas. Řešením je následující metoda eliminace.
   • eliminace(X,e,bn) vrátí distribuci proměnné X za evidence e v síti bn. Pseudokód:
     • factors ← []
     • vars ← Reverse(Vars(bn))     // bereme proměnné v obráceném topologickém pořadí
     • for all var in vars do
       • factors ← [MakeFactor(var,e) | factors]     // vyrobíme faktor pro var, tedy matici $ \Pr\left[ \textit{var}=x \mid \textit{parents}=\vec y \right] $, a přidáme ho do seznamu
       • if var is hidden     // skryté proměnné jsou ty, které se nevyskytují dotazu ani evidenci

         then factors ← SumOut(var,factors)     // faktory nezávislé na var jsou nezměněny, zbytek se vysčítá přes všechny možné hodnoty var

     • return Normalize(PointwiseProduct(factors))     // znásobení faktorů a normalizace tak, že dostaneme distribuci (jednotkový součet hodnot)
2. přibližné metody

Pomocí stochastické simulace. Idea: vytvoříme $ N $ vzorků z distribuce dané sítí, spočteme odhad rozdělení, ukážeme konvergenci odhadů ke skutečnosti. Vzorkování v prázdné síti: procházím proměnné (vrcholy sítě) v nějakém topologickém uspořádání a vždy náhodně vyberu hodnotu z distribuce dané hodnotami rodičů a tabulkou pro proměnnou. Takto vždy získám vzorek ze sdruženého rozdělení daného sítí.

Při přítomnosti evidence je možné odmítat vzorky nesouhlasící s evidencí, ale pokud je jí více, zahodíme téměř všechny. Alternativou je likelihood weighting. Idea: evidenci bereme za instanciované proměnné a každý vzorek vážíme věrohodností, tedy $ w = \Pr\left[ \textit{evidence} \mid \textit{zbyla\ data\ vzorku} \right] $. Algoritmus pro prázdnou síť upravíme tak, že navíc pro každý vzorek uvažujeme věrohodnost $ w $ (=1 na začátku). Kdykoliv pak narazíme na vrchol s evidencí, místo generování hodnoty vynásobíme $ w $ pravděpodobností jejího nastání za platnosti hodnot rodičů. Vzorky vážené svými věrohodnostmi se nasčítávají do výsledku, který je potřeba na konci normalizovat, abychom dostali distribuci (odhad odpovědi na dotaz). Stále je potřeba relativně velké množství vzorků pro dostatečnou přesnost odpovědi.

Bayesovské učení

Naivní bayesovský klasifikátor

Jako trénovací množinu máme množinu vektorů {x1 ... xK}, každému je přiřazená jedna z tříd C1 .. CL. Později budeme dostávat neznámé vektory (mimo trénovací množinu) a úkolem je odhadnout, do jaké třídy nejspíše patří. Bayesovský klasifikátor je jedna z možností, jak toto řešit.

Chceme pro každou třídu C spočítat šanci, že x patří do třídy C (pak třeba vybereme tu nejpravděpodobnější). Dle Bayesovy věty: $ P(C | x) = \frac{P(x|C) \cdot P(C) }{P(x)} = \frac{P(x \wedge C)}{P(x)} $. Jmenovatel P(x) bude pro všechny C stejný, není třeba ho vyčíslovat, abychom našli nejpravděpodobnější C.

Rozepišme si x na jednotlivé složky a rozvineme dle podmíněné pravděpodobnosti : $ P(x, C) = P(x_1 .. x_n, C) = P(x_1 | x_2, .. x_n, C) \cdot P(x_2 | x_3, .. x_n, C) \cdot ... \cdot P(C) $.

Teď uplatníme naivní předpoklad, že hodnoty jednotlivých xi nejsou závislé na hodnotě ostatních: $ P(x, C) = P(x_1 .. x_n, C) = P(x_1 | C) \cdot P(x_2 | C) \cdot ... \cdot P(C) $.

Hodnotu P(xi | C) snadno zjistíme z trénovací množiny (vyfiltrujeme jen vektory patřící do C; spočítáme, jaká část z nich má hodnotu xi na i-té pozici). Hodnota P(C) je pravděpodobnost dané třídy (počet trénovacích vzorků patřících do C ku celkovému počtu vzorků). Tyto věci si lze předpočítat před klasifikací (do tabulek / matic ...).

Naivní klasifikátor vlastně odpovídá Bayesovské síti s určitou topologií: kořenový uzel je třída C (+ tabulka pravděpodobností jednotlivých hodnot C), ze které vedou šipky do uzlů X1 ... XN (složky vektorů). Ke každému Xi se pojí tabulka pravděpodobnosti hodnoty Xi při určité hodnotě C. Postup popsaný výše vlastně říká, jak z trénovací množiny "naučit síť" (vytáhnout hodnoty do tabulek ke každému uzlu).

Bayesovské učení

Příklad: Máme 5 druhů balení bombonů s různým poměrem příchutí třešeň a citron. 1: 100t:0c, 2: 75t:25c, 3: 50t:50c, 4: 25t:75c, 5: 0t:100c . Otevřeme neznámé balení a vytáhneme 5x třešeň. Úloha je odhadnout dle vytažených bombonů, o jaký druh balení (1 až 5) se jedná.

Úloha je podobná té předchozí. K vektoru hodnot x (druhy vytažených bombonů) máme přiřadit nejpravděpodobnější třídu (1 až 5) - zde se třídě říká hypotéza. Místo trénovacích dat máme přímo dané hodnoty P(x | H) (pravděpodobnost třešně při hypotéze 2 apod.) a hodnoty P(H) (pravděpodobnosti výskytu jednotlivých typů balení).

Opět vyjdeme z Bayesovy věty: $ P(H | x) = \frac{P(x|H) \cdot P(H) }{P(x)} $. Jmenovatel bude pro všechny hypotézy stejný. P(H) máme dané na začátku (např. rovnoměrné pro všechny balení), $ P(x | H) = P(x_1, ... x_n | H) = P(x_1| H) \cdot ... \cdot P(x_n | H) $.

Pro 5 třešní dostáváme P(H1) = 1*1*1*1*1 = 1; P(H2) = 0.75*0.75*0.75*0.75*0.75 = 0.237; dopočítáme pro ostatní hypotézy, normalizujeme, nejpravděpodobnější vyjde H1 - samé třešně.

Rozhodovací stromy a grafy

Rozhodovací stromy (and-or-tree)

• mají 3 typy uzlů:
  • rozhodovací, značeny obdélníky, umožňují pokračovat cestu do libovolného syna.
  • pravděpodobnostní, značeny elipsami, zachycují distribuci nastání synů.
  • listové, udávají užitek příslušné cesty z kořene.
• užitek je sice jednoznačně určen listem, ale typicky se dává na hrany a bere se součet přes všechny hrany cesty.
• na každé cestě z kořene do listu se každá proměnná vyskytuje právě jednou. Často se ale proměnné irrelevantní pro cestu vynechávají.
• každá cesta odpovídá časovému uspořádání.
• vyhodnocení pomocí minimax algoritmu s náhodou. V rozhodovacích uzlech si vybírám tu nejlepší možnost, v náhodném beru očekávaný zisk.
• problém: velikost stromu příliš roste s hloubkou a podstromy se často opakují. Řešení: zobecnění na DAG.

Rozhodovací grafy (influenční diagramy)

• zobecnění rozhodovacích stromů na DAG (orientovaný acyklický graf).
• místo listových uzlů jsou uzly užitkové, které jsou značeny kosočtverci, můžou se vyskytovat libovolně a udávají aditivní změnu užitku, která platí pro všechny cesty vedoucí přes uzel.
• předpoklad nezapomínání: při rozhodování máme také všechny informace, které jsme měli při předchozích rozhodováních.
• vyhodnocení užitků vrcholů a volba optimální strategie analogicky, průchodem v topologicky opačném pořadí.

Markovské modely

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

Markovský rozhodovací proces

• plně pozorovatelný
• rozdělení pravděpodobností následujícího stavu závisí na současném stavu a vybrané akci, značení $ T(s,a,s') $.
• výplata v každém kroku dle stavu, značení $ R(s) $.
• cílem je najít strategii optimalizující celkový očekávaný zisk.
• je potřeba zabránit nekonečnosti optimální strategie, 2 možnosti:
  • konečný horizont – dáno časové omezení, ale to by vedlo k nestacionární strategii (rozhodnutí závisí na zbývajícím čase)
  • diskontní faktor $ 0<\gamma<1 $ zaručí konečnost celkového užitku pomocí postupného snižování významu budoucích výplat: užitek $ U(s_0,\dots,s_t) = \sum_{i=0}^t{R(s_i) \gamma^i} $.
• algoritmus řešení iterací hodnot užitku:
  • vyjde z nulových užitků a v každém kroku vypočte novou sadu odhadů užitku všech stavů
  • vždy vybere nejlepší akci z předchozího odhadu a přepočítá nový očekávaný užitek
• algoritmus řešení iterací strategií:
  • vyjde z náhodné strategie a v každém kroku ji upraví (nebo dosáhne pevného bodu a skončí)
  • vždy pro aktuální strategii $ \pi $ získá užitky $ U(s) $ všech stavů tak, že vyřeší lineární soustavu rovnic $ U(s) = R(s) + \gamma \sum_{s'}{\left[ T(s,\pi(s),s') U(s') \right]} $
  • pak je vždy strategie upravena tak, že jsou podle vypočítaných užitů znovu vybrány optimální akce

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

Kalmanův filtr

Doporučuji přečíst:

Chapter 1 of Peter Maybeck's Stochastic Models, Estimation, and Control, Volume 1, Academic Press, Inc (copyright now owned by Navtech Seminars & GPS Supply)

Využití KF v robotice, odvození vztahů

Kalman filter for dummies

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

Strojové učení

Tato část je neúplná a potřebuje rozšířit. Obecné kecy, cíle, ...

Prohledávání prostoru verzí

Tato část je neúplná a potřebuje rozšířit. Prostor hypotéz, algoritmus Candidate-Elimination.

Rozhodovací stromy

Tato část je neúplná a potřebuje rozšířit. Entropie, ID3 algoritmus, prořezávání při přeučení.

Bayesovské učení

Tato část je neúplná a potřebuje rozšířit. Bayesovsky optimální odhad, nejpravděpodobnější hypotéza, maximálně věrohodná hypotéza, BIC kriterium.

Maximálně věrohodná hypotéza

Tato část je neúplná a potřebuje rozšířit. Viz bayesovské učení?

EM algoritmus

Tato část je neúplná a potřebuje rozšířit. Obecný algoritmus, příklady s k-means.

Mějme dvě mince A,B. Nejsou spravedlivé, na minci A padne rub s pravděpodobností Ra, na minci B padne rub s pravděpodobností Rb. Úkolem je určit hodnoty Ra, Rb. Experiment: bereme mince a provádíme 10 hodů.

A: (R,R,R,L,R,L,L,R,R,R)

A: (L,R,L,R,R,R,R,L,R,R)

B: (L,R,R,L,L,R,R,R,L,R)

A: (R,L,R,R,R,L,R,R,R,L)

B: (R,L,R,R,L,R,L,L,L,R)

Vidíme, že na minci A padl rub 7 + 7 + 7 = 21 krát, Ra = 21/30 = 0.7. Na minci B padl rub 6 + 5 = 11 krát, Rb = 11/20 = 0.55 (= maximálně věrohodná hypotéza).

Představme si, že máme stejných 5 pokusů (10 hodů v každém), avšak nevíme, kdy se házelo mincí A a kdy B. Pokud bychom věděli, kdy se házelo A a kdy B, dokážeme určit Ra, Rb (viz výše). Obráceně, pokud bychom znali Ra, Rb, dokážeme určit, kdy se házelo A a kdy B. Když neznáme ani jedno, úloha zjištění Ra,Rb je jaksi ekvivalentní úloze "rozclusterovat" našich 5 experimentů - přiřadit jim mince.

EM algoritmus říká, že máme nejdříve aspoň trochu chytře odhadnout Ra, Rb, např. Ra = 0.6, Rb = 0.5. Se znalostí Ra,Rb určíme pro každý experiment, s jakou pravděpodobností ho vygenerovala mince A a s jakou B.

(R,R,R,L,R,L,L,R,R,R), pro A: $ 0.6^7\cdot 0.4^3 = 0.001791 $, pro B: $ 0.5^7\cdot 0.5^3 = 0.000976 $, normalizujeme, spíš to byla mince A.

Každému experimentu jsme "přiřadili mince", z toho spočítáme nové Ra, Rb, a zase to celé dokola. Celý proces opakujeme, dokud Ra, Rb někam nedokonvergují. Obecně říkáme, že statistický model generuje pozorovaná data X (5 vektorů po 10 hodnotách), má chybějící hodnoty Z (označení vektorů mincemi A / B) a neznámé parametry θ (= Ra, Rb).

Poznámky: na začátku nemůžeme ohodnotit Ra stejně jako Rb (rovnost by se zachovala i v dalších krocích). Pokud ohodnotíme Ra<Rb, pak se mince B "prosadí" jako ta, kde častěji padá rub. EM algoritmus nám tedy najde clustery, ale neřekne "který je který" (což ze vstupu ani nelze odvodit). Algoritmus může konvergovat k různým hodnotám v závislosti na počátečním ohodnocení. Opravdu lze věřit jeho výsledkům? Nelze. Nelze věřit ani Ra = 0.7 a Rb = 0.55 (mohlo být klidně Ra = Rb = 0.1, akorát jsme měli při experimentu šťastnou ruku).

Zpětnovazební učení

Tato část je neúplná a potřebuje rozšířit. Svět dle MDP, Q-učení s TD aktualizací, explore vs. exploit, aproximace funkcí.

Téměř celé Zpětnovazební učení (reinforcement learning) se točí kolem MDP (markovský rozhodovací proces). Oproti klasickému studiu MDP v tomto případě nevíme nic o MDP (nevíme, jaká je mapa, jaké jsou pravděpodobnosti přechodů při akci, odměny atd.). Můžeme pouze ve stavu provést jednu z možných akcí, po jejich provedení se dozvíme odměnu a systém se posune do nového stavu. Cílem je maximalizovat odměnu. Zpětnovazební učení se používá i v případech, kdy známe celé prostředí (MDP), avšak nedokážeme najít analytické řešení.

Předpokládejme, že vždy známe celou mapu a aktuální stav (stále neznáme přechodový model a odměny). Pasivní učení má pevně zadanou strategii (pro každý stav má zadanou akci), cílem je zjistit (naučit se) kvalitu dané strategie.

Algoritmus ADP (adaptive dynamic programming) plní danou strategii, eviduje počty přechodů N[s,a,t] (kolikrát se ze stavu S přešlo akcí A do stavu T) a zkouší se naučit přechodový model P[s,a,t], odměny R[s] a užitek U[s]. Po každém kroku dostane nový stav s a odměnu r.

• Pokud stav ještě nebyl navštíven, položí R[s]=U[s]=r.
• Inkrementuje N[ps,pa,s] dle předchozího stavu a akce.
• Aktualizuje celou 3D tabulku : $ P[s,a,t] = N[s,a,t] / N[s,a,*] $ (např. 4x jsem ve stavu S použil akci A, z toho dvakrát jsem se dostal do T, P[S,A,T] = 0.5).
• Aktualizuje užitečnost U dle nové znalosti o MDP, např. s pomocí Bellmanových rovnic.
• Pokud není v cílovém stavu, vrátí další akci dle strategie.

Algoritmus TD (temporal difference) plní danou strategii, eviduje počty přechodů N[s] (kolikrát navštívil stav S) a učí se rovnou užitek U[s]. Po každém kroku dostane nový stav s a odměnu r.

• Pokud stav ještě nebyl navštíven, položí U[s]=r.
• Inkrementuje N[s].
• Aktualizuje užitečnost předchozího stavu: $ U[ps] = U[ps] + \alpha \cdot N[ps] \cdot (r + \gamma \cdot U[s] - U[ps]) $
• Pokud není v cílovém stavu, vrátí další akci dle strategie.

Aktivní učení nemá pevnou strategii, samo ji zkouší najít. Při simulaci ADP bez pevné strategie se i přesto učíme užitečnosti stavů U[s]. Nabízí se v každém stavu volit akci s nejvyšším užitkem (hladový agent). Nevýhoda: jakmile najde jednu cestu k cíli, bude vždy vracet akce dle dané cesty, jelikož užitečnost nenavštívených stavů je nulová. Vylepšení: s pravděpodobností P volíme náhodnou akci, jinak volíme nejužitečnější.

Chování agenta lze rozdělit do dvou kategorií: explorace (objevování, průzkum MDP, mapy, odměn) a exploitace (využívání znalostí k plnění cíle). Při exploraci se odměna většinou snižuje, při exploitaci se zvyšuje. Agent by měl chytře balancovat mezi těmito dvěma činnostmi. Cílem aktivního zpětnovazebního učení je volit dobré akce v závislosti na předchozích zkušenostech.

V dalším textu uvažujeme nějakou funkci průzkumu f(u,n), která upraví užitečnost u v závislosti na n (roste v U, klesá v N). Cílem je, aby při častém použití akce klesala její užitečnost a tím aby ostatní akce dostaly větší šanci.

Algoritmus Q-učení (Q-learning) eviduje Q[s,a] - užitečnost akce a ve stav s (užitečnost stavu je pak maximální Q přes možné akce). Eviduje počty použití akce ve stavu N[s,a]. Po každém kroku dostane nový stav s a odměnu r.

• Inkrementuje N[ps, pa].
• Aktualizuje užitečnost: $ Q[ps,pa] = Q[ps,pa] + \alpha \cdot N[ps,pa] \cdot (r + \gamma \cdot max_{a}Q[s,a] - Q[ps,pa]) $
• Pokud není v cílovém stavu, vrátí akci a s nejvyšším $ f(Q[s,a],N[s,a]) $.