# Zkouška ## 1. Zavedení pojmů, historie - umělá inteligence – snažíme se, aby stroje zvládly činnosti, které od člověka vyžadují jistou inteligenci - historie ve stručnosti - v počátcích se hlavní důraz kladl na logické a pravděpodobnostní uvažování – symbolic AI - nyní jsme v éře hlubokého učení a neuronových sítí - logika - formalizace racionálního uvažování - Aristoteles – pravidla racionálního přemýšlení - sylogismus – deduktivní argumentační struktura, která nám dává správný výsledek, máme-li správné předpoklady - Sokrates je člověk $\land$ lidé jsou smrtelní $\implies$ Sokrates je smrtelný - René Descartes – porozumění světu skrze racionální uvažování - George Boole – formální logika - pravděpodobnost - někdy věci nejsou černobílé, máme určitou míru nejistoty - Gerolamo Cardamo – možné výsledky hazardních her - Thomas Bayes – dodatečné změny pravděpodobností na základě nových poznatků - ekonomie - jak správným rozhodováním maximalizovat užitek (zisk) - Adam Smith – zakladatel moderní ekonomie - ekonomie = jak se lidé rozhodují, aby dosáhli preferovaných výsledků - teorie užitku – dává formální model preferovaného výsledku - teorie rozhodování – jak se má jedinec (samostatně) rozhodovat? - teorie her – jak se mají agenti rozhodovat, pokud jejich volba ovlivňuje užitek ostatních - operační výzkum – jak s omezenými zdroji optimalizovat použití nástrojů, není-li výsledek okamžitý (při rozmisťování radarů za 2. světové války) - automaty - systémy na zpracování informací - stroj Antikythera – starověké Řecko, pro předvídání pohybů hvězd - Joseph Marie Jacquard – program pro tkalcovský stroj, pomocí děrných štítků - Charles Babbage – Difference Engine, Analytical Engine - Konrad Zuse – Z-3, první programovatelný počítač - Alan Turing – Colossus - kybernetika a teorie řízení - stroje se udržují při (správném) chodu - Ktesibios – regulátor vodního toku - James Watt – regulátor parního stroje - Norbert Wiener – kybernetika (autonomní stroje) - teorie řízení – návrh systémů, které postupně maximalizují cílovou funkci - psychologie – jak lidé a zvířata myslí a jednají - introspekce vlastních myšlenkových procesů – subjektivní - behaviorismus – sledování reakcí zvířat na nějaké podněty - kognitivní psychologie – vnímá mozek jako stroj na zpracování informací - Kenneth Craik – zavedl pojem znalostní (knowledge-based) agent - postupný převod vjemu na vnější akci - lingvistika – jak jazyk souvisí s myšlením - Noam Chomsky – formální teorie - porozumění jazyku vyžaduje porozumění obsahu (nestačí rozumět syntaxi) - neurověda – jak mozek zpracovává informace? - podle poměru velikosti těla a mozku u člověka a u zvířat Aristoteles odhadl, že je centrum myšlení v mozku - až do 18. století nebylo jasné, že mozek je centrum vědění - Broca zkoumal pacienty s poškozením mozku – pozoroval u nich změny chování ### Historický vývoj - před zrozením oboru umělé inteligence - McCulloth, Pitts – model umělého neuronu, neurony lze spojovat a „učit“ - neuron = jednotka s váženými vstupy a výstupem, hodnotu výstupu určuje prahová funkce (tedy hlavní problém spočívá v nastavení vah) - Hebb – pravidlo pro upravování vah - Minski, Edmonds – první počítač s neuronovou sítí - Turing – vize AI - zrod AI - John McCarthy – workshop s názvem umělá inteligence, byť počítačová racionalita by byl lepší název - Newell, Simon – program Logic Theorist, umí dokazovat věty z knihy Principia Mathematica - proč AI (a ne teorie řízení nebo kybernetika)? - snaha napodobit lidské schopnosti – kreativita, učení apod. - zlatá éra, první léto - General Problem Solver – imituje lidské řešení problémů - Geometry Theorem Prover - Lisp – programovací jazyk - microworld – omezená doména problémů, které vyžadují inteligenci k řešení - Analogy – problémy z IQ testů - Student – slovní úlohy z matematiky - blocks world – manipulace s kostkami na stole - „chápání“ obrazců v počítačovém vidění (změť čar se chápe jako krychle apod.) - perceptron – učící se algoritmus - projekt Shakey – robot, který v přirozeném jazyce (angličtině) přijímal úkoly a vykonával je - období velkých slibů a předpovědí - první zima - DARPA přestala financovat základní volný (undirected) výzkum - syntaktický transformační překlad (z ruštiny do angličtiny) nefunguje - problémy neškálujou (příliš mnoho kombinací, algoritmicky těžké problémy) - perceptron hledá přímku, kterou by oddělil hodnoty – u funkce XOR taková přímka neexistuje - druhé léto - expertní systémy – zabývají se konkrétními obory lidské činnosti - druhá zima - systémy jsou křehké a drahé na údržbu - lispové počítače byly nahrazeny obecnými počítači (Apple, IBM) - třetí léto - hluboké učení, big data, počítání na grafických kartách, neuronové sítě - ImageNet - AlphaGo (DeepMind, Google) - Watson (IBM) – poráží lidi ve hře Riskuj - DeepStack, Libratus – programy na hraní Pokeru (na DeepStacku se podíleli studenti MFF UK) - autonomní řízení – Grand Challenges - co bude dál? může nám to naznačit *Gartner Hype Cycle* - innovation trigger - peak of inflated expectations - trough of disillusionment - slope of enlightenment - plateau of productivity - AI je o kontrukci racionálních agentů - racionální agent by měl zvolit akci, o které se očekává, že maximalizuje užitek - vševědoucí (omniscient) agent zná výsledek akce – vševědoucnost není reálně možná - záleží na prostředí, v němž agent operuje - všechno vidím / něco nevidím (fully observable / partially observable) - další stav prostředí je/není předem daný (deterministic / stochastic) - epizodické/sekvenční prostředí – „život“ agenta se může dělit na epizody (kde další epizoda nezávisí na akcích, které agent vykonal v předchozí epizodě) - statické/dynamické prostředí – podle toho, zda se mění během toho, co robot uvažuje - diskrétní/spojité prostředí - agentů může být více – můžou soutěžit nebo kooperovat ## 2. Řešení úloh prohledáváním (A* a spol.) - agent – vnímá prostředí pomocí senzorů, aktuátory mu umožňují jednat - racionální agent – zvolí akci, která maximalizuje jeho výkon - reflex agent - jednoduchý: observation → action - model-based - past state + past action + observation → state - state → action - goal-based agent - jako model-based - kromě aktuální stavu bere v úvahu i cíl a podle toho provede akci - reprezentace stavů - atomic – stav je blackbox - dá se použít prohledávání - factored – stav je vektor - dá se použít constraint satisfaction, výroková logika, plánování - structured – stav je sada objektů, ty jsou propojeny - dá se použít (predikátová) logika prvního řádu - problem solving agent – typ goal-based agenta - atomická reprezentace stavů - cíl = množina cílových stavů - akce = přechody mezi stavy - hledáme posloupnost akcí, kterými se dostaneme z výchozího do nějakého cílového stavu - očekáváme, že prostředí je plně pozorovatelné, diskrétní, statické a deterministické - příklad – Lloydova patnáctka - ne všechny stavy jsou dosažitelné – zachovává se parita permutace - formulace problému - budeme potřebovat abstrakci prostředí (odstraníme detaily z prostředí) - validní abstrakce = abstraktní řešení můžeme expandovat do reálného řešení - užitečná abstrakce = vykonávání akcí v řešení je jednodušší než v původním problému - dobře definovaný problém - výchozí stav - přechodový model `(state, action) -> state` - goal test (funkce, která odpoví true/false podle toho, zda je daný stav cílový) ### Řešení problému prohledáváním grafu - problém převedeme na graf - vrcholy = stavy (kořen = výchozí stav) - hrany = akce - algoritmy prohledávání grafu: graph-search a tree-search - udržujeme si hranici (frontier) prozkoumané oblasti - graph-search si navíc ukládá „uzavřenost“ vrcholu (jestli už jsme vrchol viděli) - takže nenastávají problémy s cykly - kvůli tomu, že stavový prostor může být nekonečný, neinicializujeme všechny vrcholy, ale místo toho použijeme hešovací tabulku - i tree-search lze použít k prohledávání grafů s cykly, ale může se chovat divně - u prohledávání DAGů tree-search nezaručuje, že se prohledané stavy nebudou opakovat - strategie neinformovaného prohledávání - BFS (fronta) - nejmělčí neexpandovaný vrchol je zvolen k expanzi - úplný pro konečně větvící grafy - optimální – pokud je cena cesty nerostoucí funkce hloubky - časová a prostorová složitost $O(b^{d+1})$, kde $b$ je stupeň větvení (branching factor, maximální výstupní stupeň) a $d$ je hloubka nejbližšího cíle - problém je s prostorovou složitostí - DFS (zásobník) - nejhlubší neexpandovaný vrchol je zvolen k expanzi - úplný pro graph-search - neúplný pro tree-search (pokud algoritmus pustíme na grafu, který není strom) - suboptimální – nesměřuje k cíli - časová složitost $O(b^m)$, kde $m$ je maximální hloubka libovolného vrcholu - prostorová složitost $O(bm)$ - pokud použijeme backtracking (generujeme jenom jednoho následníka místo všech), tak nám stačí dokonce jenom $O(m)$ paměti - DFS využívá to, že nám stav může vrátit všechny následníky (pak je držíme v paměti) - backtracking v daném vrcholu generuje jednoho následníka (takže všechny ostatní nemusíme držet v paměti) - ale někdy se nedá generovat jenom jeden následník - rozšíření BFS o funkci určující cenu kroku (tedy cenu hrany) - Dijkstrův algoritmus - taky se tomu říká uniform-cost search - $g(n)$ označuje cenu nejlevnější cesty ze startu do $n$ - místo fronty použijeme prioritní frontu - strategie informovaného (heuristického) prohledávání - best-first search - pro vrchol máme ohodnocovací funkci $f(n)$ - $f(n)$ použijeme v Dijkstrově algoritmu místo $g(n)$ - máme heuristickou funkci $h(n)$, která pro daný vrchol označuje odhadovanou cenu nejlevnější cesty do cílového stavu - best-first je třída algoritmů, kde máme uzly ohodnoceny nějakou funkcí a vybíráme nejmenší z nich - greedy best-first search - $f(n)=h(n)$ - není optimální ani úplný - A* algoritmus - $f(n)=g(n)+h(n)$, kde $h(n)$ je heuristika - optimální a úplný - typicky mu dojde paměť dřív než čas - co chceme od heuristiky $h(n)$ u algoritmu A* - přípustnost – $h(n)$ musí být menší rovna nejkratší cestě z daného vrcholu do cíle, musí být nezáporná - monotónnost (= konzistence) - mějme vrchol $n$ a jeho souseda $n'$ - $c(n,a,n')$ je cena přechodu z $n$ do $n'$ (akcí $a$) - heuristika je monotónní, když $h(n)\leq c(n,a,n')+h(n')$ - tvrzení: monotónní heuristika je přípustná - důkaz - vezmu nejkratší cestu do cíle … $n_1,n_2,\dots,n_k$ - z monotonie pro $i\in[k-1]$ vyjádřím $h(n_i)-h(n_{i+1})\leq c(n_i,a_i,n_{i+1})$ - sečtu to, čímž dostanu $h(n_1)\leq\sum_{i\in[k-1]} c(n_i,a_i,n_{i+1})$ - jelikož $h(n_k)=0$ - příklad přípustné nemonotónní heuristiky – všude samé nuly, kolem cíle jedničky - tvrzení: pro monotónní heuristiku jsou hodnoty $f(n)$ neklesající po libovolné cestě - důkaz - pro $n'$ následníka vrcholu $n$ - $g(n')=g(n)+c(n,a,n')$ - $h(n)\leq c(n,a,n')+h(n')$ - $f(n')=g(n')+h(n')=g(n)+c(n,a,n')+h(n')\geq g(n)+h(n)=f(n)$ - tvrzení: pokud je $h(n)$ přípustná, pak je A* u tree search optimální - do cíle nevedou žádné suboptimální cesty, takže si vystačíme s důkazem optimality Dijkstrova algoritmu - tvrzení: pokud je $h(n)$ monotónní, pak je A* u graph search optimální - s nemonotónní heuristikou jsme mohli najít suboptimální cestu do cíle - když heuristika $h_2$ dává větší hodnoty než $h_1$, tak se říká, že $h_2$ dominuje $h_1$ - pokud je $h_2$ přípustná a pokud se $h_2$ nepočítá výrazně déle než $h_1$, tak je $h_2$ zjevně lepší než $h_1$ ## 3. Splňování podmínek - problém rozmístění královen na šachovnici, aby se neohrožovaly - možný model - stavy – (částečná) rozmístění královen na šachovnici - úvodní stav – prázdná šachovnice - cíl – neznámý stav (ale pozná se tak, že je na šachovnici N královen, které se neohrožují) - akce – umístím královnu tak, aby nevznikl konflikt s již umístěnými královnami - lepší model: královnám přiřadíme sloupce, takže řešíme jenom řádky - alternativní model: všechny královny jsou na šachovnici, jenom měníme jejich pozice - A* je nám k ničemu - víme, v jaké hloubce se cíl nachází - nevíme, jak cíl vypadá - použijeme tree-search, protože stavy tvoří strom - jak to optimalizovat - budeme si dopředu vyškrtávat políčka, kam už nemůžeme nic umístit - tomu se říká forward checking - stav pro nás není černá skříňka - jak to zobecnit? - forward checking v sudoku - královny i sudoku jsou constraint satisfaction problem (CSP) - constraint satisfaction problem (CSP) - konečná množina proměnných - domény – konečné množiny možných hodnot pro každou proměnnou - konečná množina podmínek (constraints) - constraint je relace na podmnožině proměnných - relace = podmnožina kartézského součinu - constraint arity = počet proměnných, které podmínka omezuje - chceme přípustné řešení (feasible solution) - úplné konzistentní přiřazení hodnot proměnným - konzistentní … všechny podmínky jsou splněny - CSP můžeme řešit tree-search backtrackingem - úpravou proměnných v určitém pořadí můžeme získat větší efektivitu - můžeme pročistit hodnoty, které zjevně nesplňují podmínky - příklad - $a\in\set{3,4,5,6,7}$ - $b\in\set{1,2,3,4,5}$ - constraint: $a\lt b$ - ale např. $a=6$ vůbec nedává smysl - odstraněním nekonzistentních hodnot dostaneme $a\in \set{3,4}$, $b\in\set{4,5}$ - můžeme použít metodu hranové konzistence - arc consistency (hranová konzistence) - grafová terminologie - arc = orientovaná hrana - edge = neorientovaná hrana - tedy je to vlastně „konzistence orientovaných hran“ - uvažujme binární podmínky - libovolnou n-ární podmínku lze převést na balík binárních podmínek - každá binární podmínka odpovídá dvojici orientovaných hran v síti podmínek (vrcholy odpovídají proměnným) - pokud je mezi dvěma proměnnými více podmínek, můžeme je sloučit do jedné (abychom neměli multigraf) - orientovaná hrana $(V_i,V_j)$ je hranově konzistentní $\equiv$ pro každé $x\in D_i$ existuje $y\in D_j$ takové, že přiřazení $V_i=x$ a $V_j=y$ splní všechny binární podmínky pro $V_i,V_j$ - může platit, že $(V_i,V_j)$ je hranově konzistentní, ale $(V_j,V_i)$ není - CSP je hranově konzistentní $\equiv$ každá hrana je hranově konzistentní (v obou směrech) - algoritmus AC-3 - začínám se všemi hranami (podmínkami) ve frontě - postupně beru hrany z fronty a pro každou odstraním nekonzistentní prvky z domény - pokud jsem odstranil nějaké prvky z domény, musím zopakovat kontrolu pro hrany směřující do dané proměnné (kromě hrany opačné k té aktuálně zpracované) - složitost $O(cd^3)$, kde $c$ je počet podmínek, $d$ je velikost domény - $O(d^2)$ … kontrola konzistence - každá podmínka se ve frontě může objevit nejvýše $d$-krát, protože se z dané domény dá odstranit nejvýše $d$ prvků - optimální algoritmus má složitost $O(cd^2)$ - jak zkombinovat AC a backtracking - problém uděláme hranově konzistentní - po každém přiřazení obnovíme hranovou konzistenci - této technice se říká *look ahead* nebo *constraint propagation* nebo *udržování hranové konzistence* - rozdíl oproti forward checkingu - FC kontroluje jenom aktuální proměnnou – nedívá se do budoucnosti - kontroly FC/AC jsou v polynomiálním čase, kdežto strom stavů se větví exponenciálně - hranová konzistence je typ lokální konzistence, negarantuje globální konzistenci - silnější konzistence … $k$-konzistence - hranová konzistence = 2-konzistence - konzistence po cestě (path consistency) = 3-konzistence - věta: když je problém $i$-konzistentní pro všechna $i$ od 1 do počtu proměnných, pak ho můžeme vyřešit bez backtrackingu - ale udělat problém $k$-konzistentní je exponenciální vůči $k$ - globální podmínky - vezmeme balík podmínek → z nich uděláme globální podmínku - příklad: globální podmínka *all different* - řešíme pomocí hledání párování v bipartitních grafech - jedna partita = proměnné - druhá partita = hodnoty - pak stačí promazat hrany, které nejsou v žádném párování - v jakém pořadí brát proměnné a hodnoty v backtrackingu - heuristiky pro výběr proměnných - princip prvního neúspěchu (fail-first principle) – vyber nejdřív takovou proměnnou, jejíž přiřazení pravděpodobně skončí neúspěchem - dom heuristic – nejprve zkouším proměnné s nejmenší doménou - deg heuristic – začnu proměnnými, které se účastní největšího počtu podmínek - heuristiky pro výběr hodnot - princip prvního úspěchu (succeed-first principle) – začneme hodnotou, která pravděpodobně odpovídá řešení - můžu použít hodnotu, která nejméně omezuje ostatní proměnné - to je ale výpočetně náročné, takže je lepší použít vhodnou heuristiku podle konkrétního problému - constraint programming je deklarativní přístup k řešení problémů - zkonstruujeme model - použijeme univerzální solver - kombinace prohledávání a odvozování přes podmínky - hranová konzistence a globální podmínky jsou nejčastěji používané inferenční techniky ## 4. Logické uvažování (dopředné a zpětné řetězení, rezoluce, SAT) - často lze u nějakého modelu (třeba CSP) prohodit proměnné a hodnoty → vznikne duální model - hodnoty se stávají proměnnými, proměnné hodnotami - např. u královen jsou jednotlivá políčka proměnné, které nabývají hodnot 0 nebo 1 podle toho, zda tam je královna - podmínky vyjádříme logickými formulemi – lze je zapsat v CNF - k nalezení splňujícího ohodnocení se nejčastěji používá algoritmus DPLL - ryzí (čistý, pure) výskyt – zas tak moc se nepoužívá - jednotková propagace - hledám klauzule o jedné proměnné - je v zásadě ekvivalentní hranové konzistenci - používá se tree-search ke zkoušení hodnot proměnných - další optimalizace SATu - komponentová analýza - pokud se klauzule dají rozdělit na disjunktní podmnožiny, které nesdílejí proměnné, dají se řešit nezávisle - pořadí proměnných (a hodnot) - degree heuristic – začni proměnnou, která se vyskytuje nejčastěji - activity heuristic – vyber proměnnou, která se nejčastěji vyskytuje v konfliktech (tedy v dead-ends, v klauzulích, které nelze ohodnotit, tedy musím backtrackovat) - náhodné restarty - pokud hledám příliš dlouho, náhodně změním způsob volby proměnných apod. - abych se nezaseknul v nějaké slepé větvi při backtrackingu - clever indexing – je potřeba chytře udržovat různé množiny, např. množinu jednotkových klauzulí - dá se pro každou klauzuli udržovat čítač počtu literálů – ale to trvá dlouho - lepší je použít watched literals - vyberu náhodně dva literály - když se jeden z nich ohodnotí, podívám se na klauzuli - buď je jednotková, nebo vyberu nějaký další náhodný watched literal - pokud literály (proměnné) vyberu vhodně, tak mi jich stačí relativně málo pro mnoho klauzulí - clause learning - když dojde k failu (dead-end, musím backtrackovat) - identifikuju podmnožinu proměnných, které fail způsobily - konflikt (špatnou kombinaci hodnot) zakóduju jako klauzuli - znalostní agenti - mají k dispozici znalostní bázi - můžeme jim poskytovat nové informace (operace *tell*) nebo se jich na něco ptát (operace *ask*) - agent používá inferenci – logicky odvozuje - inference se dá dělat tak, že si namodeluju, jak by svět vypadal, a pak modely porovnám s reálným pozorováním – podle toho upravím znalostní bázi - příklad - agent v jeskyni - díry a Wumpus - hromada zlata - agent má šíp - dotaz $\alpha$ … je políčko bezpečné? - udělám množinu světů, kde je políčko bezpečné - porovnám ji se znalostní bází $KB$ - pokud je znalostní báze podmnožinou množiny světů, kde je políčko bezpečné, pak je políčko bezpečné - taky to můžu všechno reprezentovat pomocí formulí - $\alpha$ vyjádřím jako výrokovou formuli - $KB$ vyjádřím jako teorii - zajímá mě, zda $KB\models\alpha$ - tzv. entailment ($KB$ entails $\alpha$) - to platí, právě když $KB\land\neg\alpha$ je nesplnitelné - lze použít rezoluci - použitím rezolučního pravidla z klauzulí $\varphi\lor p$ a $\psi\lor\neg p$ dostaneme $\varphi\lor\psi$ - zkoušíme spolu rezolvovat postupně všechny dvojice klauzulí - pokud v průběhu dostaneme prázdnou klauzuli, máme rezoluční důkaz $\alpha$ z $KB$ - pokud se dostaneme do stavu, kdy nelze použít rezoluční pravidlo na žádnou dvojici klauzulí, tak víme, že neplatí $KB\models\alpha$ - pokud naše znalostní báze obsahuje pouze Hornovy klauzule - Hornova klauzule = disjunkce literálů, z nichž nejvýše jeden je pozitivní - forward chaining … data-driven reasoning - $p\land q\land r\implies s$ - pokud vím, že platí $p$, pak převedu na $q\land r\implies s$ - jakmile se počet předpokladů sníží na 0, vím, že $s$ platí - je to v podstatě speciální případ použití rezolučního pravidla - rezolvuju to, co vím, s libovolnou klauzulí - algoritmus - každá proměnná má počítadlo proměnných, které na ni ukazují - postupně beru pravdivé proměnné, snižuju počítadla u proměnných, na které ukazují - jakmile u proměnné klesne počítadlo na nulu, zařadím mezi pravdivé proměnné - backward chaining … goal-driven reasoning - něco mě zajímá – pokouším se to odvodit - tohle se používá v Prologu - opět vlastně používám rezoluční pravidlo - to, co chci zjistit, rezolvuju s libovolnou klauzulí ## 6a/7. Reprezentace znalostí (situační kalkulus), automatické plánování - jak můžeme reprezentovat informaci, která se mění v čase – třeba pozici agenta? - pomocí časově anotovaných výrokových proměnných (fluents) - $L^t_{x,y}$ … agent je v buňce $(x,y)$ v čase $t$ - observation model – propojuje pozorování s informacemi v modelu světa - $L_{x,y}^t\implies(\text{Breeze}^t\iff B_{x,y})$ - transition model – popisuje vývoj světa po aplikaci akcí - effect axioms – např. $L_{x,y}^t\land\text{FacingEast}^t\land\text{Forward}^t\implies (L^{t+1}_{x+1,y}\land\neg L^{t+1}_{x,y})$ - effect axioms nic neříkají o věcech, které se konkrétní akcí nemění - mohli bychom používat frame axioms - tak zajistíme, že se nedotčené proměnné nezmění - $\text{Forward}^t\implies(\text{HaveArrow}^t\iff\text{HaveArrow}^{t+1})$ - ale takhle budeme mít příliš mnoho frame axioms - místo toho nebudeme psát axiomy o akcích, ale o fluentech - tzv. successor-state axiomy - obecný tvar: $F^{t+1}\iff\text{ActionCausesF}^t\lor(F^t\land\neg\text{ActionCausesNotF}^t)$ - konkrétní příklad: $\text{HaveArrow}^{t+1}\iff(\text{HaveArrow}^t\land\neg\text{Shoot}^t)$ - neexistuje akce, která by HaveArrow mohla nastavit z false na true, takže chybí levá část pravé strany - plánování - hybridní agent pomocí výrokové logiky odvodí stav světa, ale k plánování použije A* - k plánování však můžeme použít přímo logiku - SAT solveru předhodíme formuli: „Lze dosáhnout cíle v přesně $t$ krocích?“ - musíme definovat výchozí stav (nastavit hodnoty všem proměnným kromě těch „akčních“), dále pak successor-state axiomy pro všechny možné akce a také požadovaný cílový stav - z nalezeného modelu zjistíme konkrétní plán - zkoušíme pro $t$ do 1 do $T_{\max}$ (tomu se říká SATPlan) - potřebujeme také zadefinovat podmínky, kdy se akce dají použít - abychom např. nemohli střílet bez šípu - tzv. precondition axioms - $\text{Shoot}^t\implies\text{HaveArrow}^t$ - chceme-li v jednu chvíli provádět nejvýše jednu akci, použijeme action exclusion axioms: $(\forall t)(\forall i{\neq} j)(\neg A_i^t\lor\neg A_j^t)$ - k plánování můžeme používat prohledávání nebo výrokové odvození - prohledávání vyžaduje dobrou doménově-specifickou heuristiku - odvození výrokovou logikou může být zahlcené, pokud máme hodně akcí a stavů - jak předejít opakování axiomů pro různé časy a podobné akce? - použijeme predikátovou logiku prvního řádu (*situation calculus*) - náš modelovaný svět se vyvíjí – postupně nastávají různé *situace* - úvodní situace … $s_0$ - situace po aplikace akce $a$ na situaci $s$ … $\text{Results}(s,a)$ - stavy jsou definovány jako relace mezi objekty - pokud se relace mění, musíme přidat další argument označující situaci, v níž relace platí: `at(robot, location, s)` - pro stálé relace takový argument není potřeba: `connected(loc1, loc2)` - podmínky (předpoklady) akcí jsou definovány possibility axiomem - obecný tvar: $\varphi(s)\implies \text{Poss}(a,s)$ - kde $\varphi$ je formule popisující předpoklady akce $a$ - např. `at(a, l, s) & connected(l, l') => Poss(go(a, l, l'), s)` - vlastnosti dalšího stavu jsou popsány pomocí successor-state axiomů pro každý fluent - `Poss(a, s) => (F(Results(s, a)) <=> (F is made true by a) OR (F(s) & F is not made false by a))` - plánování se provádí tak, že se zeptáme, zda existuje situace, kde je cílová podmínka pravdivá - klasické plánování - stav světa je reprezentován jako množina proměnných - stav je popsán atomy, které platí (ostatní neplatí, používáme předpoklad uzavřeného světa) - pravdivnostní hodnota některých atomů se mění … fluents - u jiných atomů je pravdivostní hodnota stálá … rigid atoms - schémata akcí (operátory) popisují možnosti agenta - schéma akce (operátor) popisuje akci, aniž by specifikovalo objekty, na které se akce vztahuje - operátor je trojice (název, předpoklady, důsledky) - někdy je požadavek, aby předpoklady byly kladné – toho lze docílit typicky přidáním proměnných - akce je plně zinstanciovaný operátor - akce je relevantní pro cíl $g\equiv$ přispívá cíli $g$ a její důsledky (efekty) nejsou v konfliktu s $g$ - dále definujeme výsledek aplikace akce na stav a regresní množinu pro cíl a akci - terminologie - popisu operátorů se obvykle říká doménový model - plánovací problém je trojice $(O,s_0,g)$, kde $O$ je doménový model, $s_0$ je výchozí stav a $g$ je cílová podmínka - plán je posloupnost akcí - plánování je realizováno prohledáváním stavového prostoru - ten je mnohdy dost velký - přístupy k plánování - forward (progression) planning - postupujeme od výchozího k cílovému stavu - prohledávací algoritmus potřebuje dobrou heuristiku - backward (regression) planning - prozkoumávají se jen relevantní akce → menší větvení než u forward planningu - používá množiny stavů spíše než individuální stavy → je těžké najít dobrou heuristiku - potřebujeme heuristiku, aby naváděla prohledávání - musí být přípustná, může být monotónní - můžeme ji najít tak, že zkusíme řešit rozvolněný problém (odstraníme některé constraints) - možné heuristiky - ignorujeme podmínky akcí – najdeme nejmenší množinu akcí, která pokrývá cíl - ignorujeme negativní efekty akcí - další formy plánování - plan-space planning - je bližší tomu, jak plánujou lidé - postupně naplňujeme cíle a řešíme hrozby - hierarchické plánování - rozkládáme úkoly do primitivních úkolů (akcí) - shrnutí – automatizované plánování - doménový model popisuje možnosti agentů - cílem je najít sekvenci akcí ze současného do cílového stavu - realizované prohledáváním stavového prostoru - používáme heuristiky (ty můžou být nezávislé na doméně) ## 5. Pravděpodobnostní uvažování (Bayesovské sítě) - jednání ovlivněné nejistotou - zdroje nejistoty - částečná pozorovatelnost – nelze snadno zjistit současný stav - nedeterminismus – není jisté, jak akce dopadne - logický agent by si musel pamatovat všechny možnosti situací - belief state = množina všech stavů světa, ve kterých se v danou chvíli agent může nacházet - contingency plan = plán, který řeší všechny možné situace - pravděpodobnostní agent každému tvrzení přiřazuje belief mezi 0 a 1 - použijeme teorii pravděpodobnosti - někdy si můžeme udělat tabulku všech možností a určit jejich pravděpodobnosti (full joint probability distribution) - odpověď lze vyjádřit z ní (této metodě se říká enumeration, výčet) – ale u velkých tabulek je někdy potřeba posčítat příliš mnoho hodnot - počítání pravděpodobnosti - poznámka ke značení: čárka je ekvivalentní $\land$ - $P(Y)=\sum_z P(Y\mid z)\cdot P(z)$ - $P(Y\mid e)=\frac{P(Y\land e)}{P(e)}$ - typicky nemusíme znát $P(e)$, stačí použít $\alpha P(Y\land e)$, kde $\alpha$ je normalizační konstanta - velkou tabulku můžeme někdy reprezentovat menším způsobem – pokud jsou proměnné podmíněně nezávislé - Bayesovo pravidlo … $P(Y\mid X)=\frac{P(X\mid Y)P(Y)}{P(X)}=\alpha P(X\mid Y) P(Y)$ - lze odvodit z definice podmíněné pravděpodobnosti - pomůže nám při přechodu z příčinného k diagnostickému směru - P(effect | cause) … casual direction (příčinný směr), obvykle známý - P(cause | effect) … diagnostic direction (diagnostický směr), obvykle chceme zjistit - P(cause | effect) = P(effect | cause) P(cause) / P(effect) - naivní bayesovský model - $P(\text{Cause}, \text{Effect}_1, \dots, \text{Effect}_n) = P(\text{Cause})\prod_iP(\text{Effect}_i\mid\text{Cause})$ - chain rule - $P(x_1,\dots,x_n)=\prod_iP(x_i\mid x_{i-1},\dots,x_1)$ - využívá product rule (lze odvodit z definice podmíněné pravděpodobnosti) - bayesovská síť je DAG, kde vrcholy odpovídají náhodným proměnným - šipky popisují závislost - u každého vrcholu jsou CPD tabulky, které popisujou jeho závislost na rodičích - CPD = conditional probability distribution - konstrukce bayesovské sítě - nějak si uspořádáme proměnné (lepší je řadit je od příčin k důsledkům, ale není to nutné) - jdeme odshora dolů, přidáváme správné hrany - příklad: MaryCalls, JohnCalls, Alarm, Burglary, Earthquake - z MaryCalls povede hrana do JohnCalls, protože nejsou nezávislé (když volá Mary, tak je větší šance, že volá i John) - z obou povede hrana do Alarmu - z Alarmu vedou hrany do Burglary a Earthquake (ale hrany z JohnCalls a MarryCalls tam nepovedou – na těch hranách nezáleží, jsou nezávislé) - z Burglary povede hrana do Earthquake, protože pokud zní alarm a k vloupání nedošlo, tak pravděpodobně došlo k zemětřesení - akorát je těžké určit hodnoty pravděpodobností - z bayesovských sítí můžeme provádět inferenci – odvozovat pravděpodobnost proměnných pomocí pravděpodobností *skrytých* proměnných - $P(X\mid e)=\alpha P(X,e)=\alpha\sum_y P(X,e,y)$ - kde pravděpodobnost $X$ odvozujeme, $e$ jsou pozorované proměnné (evidence) a $y$ jsou hodnoty další skryté proměnné $Y$ - přičemž $P(X,e,y)$ lze určit pomocí $P(x_1,\dots,x_n)=\prod_i P(x_i\mid\text{parents}(x_i))$ - kde parents jsou přímí předci vrcholu (vrcholy, z nichž do něj vedou šipky) - příklad – počítáme pravděpodobnost Burglary, když JohnCalls a MaryCalls - $P(b\mid j,m)=\alpha\sum_e\sum_a P(b)P(e)P(a|b,e)P(j|a)P(m|a)$ - $=\alpha P(b)\sum_e P(e)\sum_aP(a|b,e) P(j|a) P(m|a)$ - když nemůžeme určit konkrétní hodnotu pravěpodobnosti přímo, tak výpočet rozvětvíme - některé větve se objeví vícekrát – hodí se nám dynamické programování - používáme *faktory* (tabulky odpovídající CPD tabulkám) - tabulky s faktory mezi sebou můžeme násobit – tak dostaneme novou tabulku se sjednocením proměnných - poloviny tabulek můžeme sčítat – tak se lze zbavit proměnné - Monte Carlo přístup - odhadujeme hodnoty, které je těžké přímo spočítat - generujeme hodně vzorků, použijeme statistiku - pravděpodobnostní rozdělení náhodných veličin známe - zajímá nás $P(X\mid e)$ - jak generovat vzorky? - rejection sampling = zahodíme vzorky, kde neplatí $e$ - riziko, že zahodíme příliš mnoho vzorků - likelihood weighting - zafixujeme $e$, generujeme jen zbylé proměnné - nastavíme váhy jednotlivým možnostem - problém s příliš malými váhami ## 6b. Reprezentace znalostí (Markovské modely) - každý stav světa je popsán množinou náhodných proměnných - skryté náhodné proměnné $X_t$ – popisují reálný stav - pozorovatelné náhodné proměnné $E_t$ – popisují, co pozorujeme - uvažujeme diskrétní čas, takže $t$ označuje konkrétní okamžik - množinu proměnných od $X_a$ do $X_b$ budeme značit jako $X_{a:b}$ - formální model - transition model - určuje pravděpodobnostní rozložení proměnných posledního stavu, když známe jejich předchozí hodnoty … $P(X_t\mid X_{0:t-1})$ - zjednodušující předpoklady - další stav závisí jen na předchozím stavu … *Markov assumption* - všechny přechodové tabulky $P(X_t\mid X_{t-1})$ jsou identické přes všechna $t$ … *stationary process* - sensor (observation) model - popisuje, jak pozorované proměnné závisí na ostatních proměnných … $P(E_t\mid X_{0:t},E_{1:t-1})$ - zjednodušující předpoklad: pozorování záleží jen na aktuálním stavu … *sensor Markov assumption* - základní inferenční úlohy - filtrování – znám minulá pozorování, zajímá mě přítomný stav - $P(X_{t+1}\mid e_{1:t+1})=P(X_{t+1}\mid e_{1:t},e_{t+1})$ - použijeme Bayesovo pravidlo - $=\alpha\cdot P(e_{t+1}\mid X_{t+1},e_{1:t})\cdot P(X_{t+1}\mid e_{1:t})$ - použijeme *sensor Markov assumption* - $=\alpha\cdot P(e_{t+1}\mid X_{t+1})\cdot P(X_{t+1}\mid e_{1:t})$ - $=\alpha\cdot P(e_{t+1}\mid X_{t+1})\cdot \sum_{x_t}P(X_{t+1}\mid x_t,e_{1:t})\cdot P(x_t\mid e_{1:t})$ - $=\alpha\cdot P(e_{t+1}\mid X_{t+1})\cdot \sum_{x_t}P(X_{t+1}\mid x_t)\cdot P(x_t\mid e_{1:t})$ - užitečný filtrovací algoritmus si musí udržovat odhad současného stavu, jelikož je vzorec rekurzivní - předpověď (prediction) – znám minulá pozorování, zajímají mě budoucí stavy - vlastně jako filtering, akorát nepřidávám další pozorování (měření) - $P(X_{t+k+1}\mid e_{1:t})=\sum_{x_{t+k}} P(X_{t+k+1}\mid x_{t+k})\cdot P(x_{t+k}\mid e_{1:t})$ - po určitém čase (*mixing time*) distribuce předpovědí konverguje ke stacionárnímu rozdělení daného markovského procesu a zůstane konstantní - vyhlazování (smoothing) – znám minulá pozorování, zajímají mě minulé stavy - $P(X_k\mid e_{1:t})=P(X_k\mid e_{1:k},e_{k+1:t})$ - použijeme Bayesovo pravidlo - $=\alpha\cdot P(X_k\mid e_{1:k})\cdot P(e_{k+1:t}\mid X_k,e_{1:k})$ - použijeme *sensor Markov assumption* - $=\alpha\cdot P(X_k\mid e_{1:k})\cdot P(e_{k+1:t}\mid X_k)$ - přitom levý člen známe z filteringu (je to „dopředný směr“), pravý je „zpětný směr“ z naměřených hodnot *v budoucnosti* (relativně vůči danému okamžiku) - nejpravděpodobnější vysvětlení (most likely explanation) – znám minulá pozorování, zajímá mě nejpravděpodobnější posloupnost minulých stavů - opět existuje rekurzivní vzorec – podíváme se na pravděpodobnosti předchozích stavů a na nejpravděpodobnější „cesty“ do těchto stavů - skryté Markovovy modely - předpokládejme, že stav procesu je popsán jedinou diskrétní náhodnou proměnnou $X_t$ (a máme jednu proměnnou $E_t$ odpovídající pozorování) - pak můžeme všechny základní algoritmy implementovat maticově - dynamická bayesovská síť - reprezentuje časový pravděpodobnostní model - zachycuje vztah mezi minulým a současným časovým okamžikem (minulou a současnou vrstvou) - každá stavová proměnná má rodiče ve stejné vrstvě nebo v předchozí (podle Markovova předpokladu) - dynamická bayesovská síť (DBN) vs. skrytý Markovův model (HMM) - skrytý Markovův model je speciální případ dynamické bayesovské sítě - dynamická bayesovská síť může být kódovaná jako skrytý Markovův model - jedna náhodná proměnná ve skrytém Markovově modelu je n-tice hodnot stavových proměnných v dynamické bayesovské síti - vztah mezi DBN a HMM je podobný jako vztah mezi běžnými bayesovskými sítěmi a tabulkou s *full joint probability distribution* - DBN je úspornější - inference v DBN - můžeme použít existující algoritmy pro inferenci v bayesovských sítích - můžeme zkonstruovat celou bayesovskou síť tak, že přidáme vrstvy od začátku až po současnost – do nich dáme pozorování (měření) - tzv. unrolling - exact inference - můžeme si pamatovat jenom poslední dvě vrstvy - ale prostorová složitost bude exponenciální vzhledem k počtu stavových proměnných - approximate inference - samplujeme skryté proměnné v síti v topologickém pořadí pomocí likelihood weighting - vzorky se generují nezávisle na měření, takže jejich váhy klesají - abychom udrželi přesnost, musíme počet vzorků exponenciálně zvětšovat v závislosti na $t$ ## 8. Markovské rozhodovací procesy - rozhodování - racionální agent se rozhoduje na základě svých informací o prostředí a svých cílů - potřebujeme měřit kvalitu výsledku - budeme dělat jednoduchá rozhodnutí (v epizodických prostředích) i posloupnosti mnoha rozhodnutí (v sekvenčních prostředích) - užitek (utility) - pro každý stav známe utility function (funkci užitku) … $U(s)$ - očekávaný užitek (expected utility, EU) akce $a$, máme-li pozorování $e$ - $EU(a\mid e)=\sum_s P(\text{Result}(a)=s\mid a,e)\cdot U(s)$ - maximální očekávaný užitek (maximum expected utility, MEU) - $\text{argmax}_a EU(a\mid e)$ - princip maximálního očekávaného užitku: racionální agent by si měl zvolit akci, která maximalizuje očekávaný užitek agenta, - teorie užitku - očekávaný užitek náhodné volby (loterie) … $\sum_i p_i u_i$ - $p_i$ … pravděpodobnost $i$-té volby - $u_i$ … užitek $i$-té volby - často známe preference agenta spíše než přesné hodnoty utility funkce - $A \lt B$ … agent preferuje B oproti A - $A \sim B$ … agent nerozlišuje mezi A a B (nemá favorita, je indiferentní) - z prefencí se dá dostat utility - $U(A)\lt U(B)\iff A\lt B$ - $U(A)=U(B)\iff A\sim B$ - alternativní způsob – získáme normalizovanou utility funkci - nejlepšímu možnému stavu $S_\max$ přiřadíme $U(S_\max) = 1$ - nejhorší možné katastrofě $S_\min$ přiřadíme $U(S_\min) = 0$ - pro každý další stav $S$ necháme agenta rozhodnout se mezi standardní loterií a stavem $S$ - standardní loterie … $S_\max$ s pravděpodobností $p$ a $S_\min$ s pravděpodobností $1-p$ - upravujeme pravděpodnost $p$, dokud agent není indiferentní mezi $S$ a standardní loterií - pak $U(S):=p$ - rozhodovací sítě (decision networks, influence diagrams) kombinují bayesovské sítě s dodatečnými typy vrcholů pro akce a utility - vyhodnocení rozhodovací sítě: nastavíme proměnné pozorování (evidence variables) na aktuální stav, pro všechna možná rozhodnutí spočítáme utility, vrátíme akci s největší utilitou - decision-theoretic expert systems - vytvoříme kauzální model – znázorníme příznaky, nemoci, léčbu, nakreslíme hrany - zjednodušíme ho na kvalitativní rozhodovací model – odstraníme proměnné, které se nepoužívají při rozhodování - přiřadíme pravděpodobnosti - přiřadíme užitky - ověříme a vyladíme model – porovnáme s týmem expertů - provedeme citlivostní analýzu – malé změny vedoucí k výrazně odlišným rozhnodnutím typicky indikují problémy - markovovský rozhodovací proces (MDP) - řešíme sekvenční rozhodovací problém - pro plně pozorovatelné stochastické (nedeterministické) prostředí - máme Markovův přechodový model a reward - přechodový model $P(s'\mid s,a)$ … pravděpodobnost dosažení stavu $s'$, když ve stavu $s$ použiju akci $a$ - odměna (reward) $R(s)$ … získá ji agent ve stavu $s$, je krátkodobá - utility function $U([s_0,s_1,s_2,\dots])=R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+\dots$ - kde $\gamma$ je *discount factor*, číslo mezi 0 a 1 - utility je „dlouhodobá lokální odměna“ - hodnota utility funkce je konečná i pro nekonečnou posloupnost stavů, protože zjevně $U([s_0,\dots])\leq \frac{R_\max}{1-\gamma}$ - řešením MDP je policy (strategie) – funkce doporučující akci pro každý stav - protože kdyby řešením byla fixní sekvence akcí, tak by to nefungovalo pro stochastická prostředí (mohlo by se stát, že skončíme v jiném stavu, než jsme mysleli) - optimální strategie $\equiv$ strategie, která vrací největší očekávanou utilitu - optimální strategie nezávisí na počátečním stavu – je jedno, kde jsme začali, pro nalezení nejvhodnější další akce by měl být důležitý jen aktuální stav - opravdový užitek stavu je reward (odměna) stavu ve spojení s očekávaným užitkem následného stavu → to vede na Bellmanovu rovnici - Bellmannova rovnice - vezmu reward a discountovaný užitek okolí - akorát nevím, kterou akci provedu, tak vezmu všechny a maximum přes ně (násobím jejich užitek pravděpodobností) - $U(s)=R(s)+\gamma\max_a\sum_{s'}P(s'\mid s,a)\cdot U(s')$ - soustava Bellmanových rovnic není lineární – obsahuje maximum - můžu je řešit aproximací - použiju iterativní přístup - nastavím nějak užitky – třeba jim nastavím nuly - provedu update – aplikuju Bellmanovu rovnici - pokud se dostatečně přiblížím k pevnému bodu, tak toho nechám - je tam ta speciální formule s $\epsilon$, ale nebudeme dokazovat, co přesně říká - → **value iteration** - strategie se ustálí dřív než užitky - policy loss … vzdálenost mezi optimálním užitkem a užitkem strategie - můžeme iterativně zlepšovat policy, dokud to jde - → **policy iteration** - z rovnic nám zmizí maximum → máme lineární rovnice - policy evaluation = nalezení řešení těchto rovnic (tak najdeme utilities stavů) - gaussovka je $O(n^3)$ - algoritmus skončí, protože policies je jenom konečně mnoho a vždycky hledáme tu lepší - částečně pozorovatelný markovský rozhodovací proces (POMDP) - přibude nám sensor model $P(s\mid e)$ - místo reálných stavů můžeme používat ty domnělé (belief states) - modely přechodů a senzorů jsou reprezentovány dynamickou bayesovskou sítí - přidáme rozhodování a užitky, čímž dostaneme dynamickou rozhodovací síť - generujeme si stromeček, kde se střídají vrstvy akcí a belief states - používá se algoritmus podobný algoritmu *expected minimax* ## 9. Hry a teorie her - více agentů - můžeme se tvářit, že další agenti neexistují a že jsou součásti prostředí – informace se k nám dostávají skrz pozorování - pokud víme, že jsou ostatní agenti racionální, můžeme se rozhodovat líp, pokud budeme „přemýšlet za ně“ - to vede na teorii her - nejtypičtější hry – deterministické hry s kompletní informací a nulovým součet pro dva hráče, kteří se střídají (šachy, Go, …) - nulový součet … zisk jednoho hráče je ekvivalentní ztrátě druhého - algoritmus minimax – předpokládá, že oba hráči hrají optimálně - minimax s $\alpha,\beta$ prořezáváním - záleží na pořadí procházení větví – když budu procházet v dobrém pořadí, tak větve můžu dřív zaříznout - vrátí to samé, co klasický minimax - stavový prostor je obrovský – ohodnotíme částečný stav hry (nebudeme ji „dohrávat“ do konce) - ohodnocovací funkce pro šachy bude brát vážený počet figurek - někdy ve hrách hraje roli náhoda (tzv. stochastické hry) - např. házíme kostkou - algoritmus expected minimax - mezi vrcholy s tahy hráčů přidám vrstvy s pravděpodobnostmi - hodnota pravděpodobnostního vrcholu odpovídá $\sum_{s\in S} p_sv_s$, kde $S$ je množina všech synů vrcholu, $p_s$ je pravděpodobnost konkrétního jevu a $v_s$ je hodnota jevu (vrcholu s jevem) - vlastně to odpovídá tomu, jako bych při výpočtu min nebo max vrcholy vážil pomocí pravděpodobností - je důležité lépe sestavit ohodnocovací funkci, protože nezáleží jenom na pořadí hodnot, ale taky na absolutních ohodnoceních - hry na jeden tah - příklady her - kámen, nůžky, papír - dvouprstá Morra - hru tvoří: hráči (agenti), možné akce, payoff function - strategie - čistá (pure) strategie … deterministická strategie - smíšená (mixed) strategie … randomizovaná strategie, volba akce je náhodná s určitým pravděpodobnostním rozdělením - řešení hry = přiřazení racionální strategie každému hráči - vězňovo dilema - vězeň může vypovídat (testify, defect) nebo odmítnout vypovídat (refuse, cooperate) - oba vypovídají → oba ztrácejí málo (5) - jeden vypovídá, druhý ne → jeden neztratí nic (0), druhý hodně ztratí (10) - oba odmítnou → oba ztrácejí velmi málo (1) - vypovídat … čistá strategie dominovaná výsledkem (refuse, refuse) - ale vyhrála policie – lepší by bylo, kdyby oba odmítli vypovídat - našli jsme Nashovo ekvilibrium – nikdo neprofituje ze změny strategie, pokud druhý hráč zůstane u stejné strategie - outcome is Pareto dominated by another outcome $\equiv$ all players would prefer the other outcome - outcome is Pareto optimal $\equiv$ there is no other outcome that all players would prefer - dvouprstá Morra - nemá čistou strategii - jak najít optimální smíšenou strategii? - technika **maximin** - nejdříve si představíme, jak by se hra hrála, kdyby se hráči střídali a kdyby hráli čistou strategii (obě varianty – podle toho, který hráč začíná) - minimaxem vyhodnotíme strom hry - získáme spodní a horní hranici pro skóre - teď si představíme, že hráči mají smíšenou strategii s nějakou pravděpodobností $p$, a uděláme to samé - spočítáme lineární rovnice - opakované hry - známe historii tahů, payoff se sčítá - strategie pro opakované vězňovo dilema - pokud víme, která hra je poslední, vede to na podobnou situaci jako u jedné hry - pokud nevíme, která hra je poslední - perpetual punishment – hráč odmítá vypovídat, právě když druhý hráč nikdy nevypovídal - tit-for-tat – hráč nejprve odmítá vypovídat, pak zrcadlí pohyby protivníka - velmi robustní a efektivní strategie - k čemu používáme teorii her - k návrhu agentů – jak vyhrávat - k návrhu mechanismů (pravidel) – jak nastavit pravidla, aby byli všichni spokojeni - inverzní teorie her (mj. se zabývá aukcemi) - aukce - jak se pozná dobrý mechanismus aukce - maximalizuje výnos pro prodejce - vítěz aukce je agent, který si věci nejvíc cení - zájemci by měli mít dominantní strategii - anglická aukce (ascending-bid) - začnu s $b_\min$, pokud je to nějaký zájemce ochotný zaplatit, tak se ptám na $b_\min+d$ - strategie: přihazuju, dokud cena není vyšší než moje hodnota - jednoduchá dominantní strategie - má to problémy - nepůjdu do aukce s někým hodně bohatým - lidi musejí být ve stejnou chvíli na stejném místě - holandská aukce - začíná se vyšší cenou, snižuje se, dokud ji někdo nepřijme - je rychlá - obálková aukce - největší nabídka vítězí - neexistuje jednoduchá dominantní strategie - pokud věříš, že maximum ostatní nabídek je $b_0$, tak bys měl nabídnout $b_0+\varepsilon$, pokud je to menší částka než hodnota, kterou pro tebe věc má - obálková second-price aukce (Vickrey) - vyhraje ten první, platí druhou cenu - dominantní strategie je tam dát svoji hodnotu - problém sdílení společných zdrojů - znečišťování životního prostředí - pokračovat ve znečišťování je levnější než implementovat potřebné změny - „tragedy of commons“ - když nikdo nemusí platit za sdílený zdroj, může to vést k jeho využívání tím způsobem, že se snižuje utilita pro všechny agenty - podobné vězňovu dilematu - mechanismus Vickrey-Clarke-Groves - zdanění společného zboží - problém – je nezbytné mít centrální autoritu - princip - každý agent nahlásí svoji hodnotu (nabídku) - centrální autorita přiřadí zboží podmnožině agentů tak, aby se maximalizoval celkový nahlášený užitek - každý vítězný agent platí daň odpovídající nejvyšší nahlášené hodnotě mezi těmi, kdo prohráli - dominantní strategie je opravdu nabídnout svoji hodnotu - jak je to s hrami dnes? - počítače už jsou v šachu lepší než lidi, ale není to vyřešená hra – programy nehrajou 100% dobře, nevědí, jak hra dopadne - dáma už je vyřešená hra, optimální strategie vede k remíze - Go – strom hry se hodně větví, těžko se ohodnocuje stav hry; programy AlphaGo a AlphaGo Zero - poker – prvek náhody, programy Deep Stack a Libratus - fotbal – soutěž RoboCup ## 10. Strojové učení (rozhodovací stromy, regrese, zpětnovazební učení) - strojové učení - způsob, jak zlepšit budoucí chování agenta - co učení zvládá lépe než přímé programování chování - scénáře, na které programátor nemyslel - změny v prostředí - někdy není jasné, jak agenta naprogramovat - zpětná vazba, z nichž se agenti učí - učení bez učitele (unsupervised learning) – agent se učí vzory ve vstupu, aniž by měl nějakou explicitní zpětnou vazbu - zpětnovazební učení (reinforcement learning) – agent dostává odměny nebo tresty - učení s učitelem (supervised learning) – agent se učí funkci, která mapuje vstupy na výstupy - učení s učitelem (supervised learning) - máme vstupy a výstupy - chceme najít funkci (její aproximaci), která mapuje vstupy na výstupy - hledáme hypotézu (funkci $h$) z prostoru hypotéz - hypotéza je konzistentní s $i$-tým příkladem, pokud $h(x_i)=y_i$ - princip Occamovy břitvy – preferujeme nejjednodušší hypotézu - např. $n$ bodů určuje polynom stupně $n-1$, ale pokud body leží na přímce, tak nejjednodušší hypotéze je prostě ta přímka - typy úloh - klasifikace – u nečíselných funkcí, data rozdělujeme do množin - regrese – u číselných funkcí - rozhodovací strom - přijímá vektor hodnot atributů, vrací výslednou hodnotu - na základě tabulky příkladů se dá postavit strom - každý vnitřní vrchol odpovídá testu jednoho atributu - dá se zjistit odůvodnění konkrétního rozhodnutí - strom se dá postavit hladovou metodou rozděl a panuj - každý list určuje hodnotu, kterou klasifikační funkce vrátí - zakončení větve (listy) - když jsou ve větvi výsledky jednoho druhu – není co řešit, zvolím daný druh - když je větev prázdná – pak zvolím převažující třídu v nadřazeném vrcholu - když už jsme použili všechny atributy, ale v jedné větvi máme křížky a kolečka – zvolím převažující třídu - prostor hypotéz = množina rozhodovacích stromů - hledáme strom, který je konzistentní s příklady a zároveň je co nejmenší - snažím se vždy (hladově) dělit podle nejdůležitějšího atributu - jak ho najít? - jako metriku použiju entropii – míru neurčitosti náhodné proměnné (měří se v bitech informace, kterou získáme, když známe hodnotu náhodné proměnné) - entropie náhodné proměnné $V$ s hodnotami $v_k$, kde každá má pravděpodobnost $P(v_k)$ se spočítá takto: $H(V)=\sum_k P(v_k)\cdot\log_2\frac1{P(v_k)}$ - pro binární proměnnou je to $B(p)=p\cdot\log_2\frac1p+(1-p)\log_2\frac1{1-p}$ - kde $p$ je pravděpodobnost jedné z variant - dále použijeme *information gain* pro daný atribut – tedy očekávanou redukci entropie - $\text{Gain}(A)=B(\frac{p}{p+n})-\sum_k\frac{p_k+n_k}{p+n}B(\frac{p_k}{p_k+n_k})$ - kde $p$ jsou pozitivní případy, $n$ jsou negativní případy, $p_k$ jsou pozitivní případy v $k$-té podmnožině - z toho levá část vzorce je entropie atributu vůči celé množině, pravá je očekávaná zbývající entropie - poznámky - entropie spravedlivé mince je 1 - zjevně $B(\frac p{p+n})=B(\frac n{p+n})$ - logická formulace učení - hypotézy, příklady a klasifikaci budeme reprezentovat logickými formulemi - tzv. logická klasifikace - příklady (trénovací data) - atributy se stanou unárními predikáty - klasifikace se určí literálem s cílovým predikátem - hypotéza bude mít tvar $\forall x:\text{Goal}(x)\iff C_j(x)$ - kde $C_j$ je nějaká formule (mohla by popisovat rozhodovací strom) - $C_j$ (na vstupních datech) definuje množinu dat klasifikovaných jako true - prostor hypotéz = množina všech hypotéz - učící algoritmus věří, že jedna hypotéza je správná, takže věří formuli $h_1\lor h_2\lor\dots\lor h_n$ - hypotézy, které nejsou konzistentní s příklady, můžeme vyškrtnout - idea … udržujeme jednu hypotézu a upravujeme ji podle toho, jak přicházejí další příklady, abychom ji udržely konzistentní - pokud je příklad konzistentní, neměníme hypotézu - hypotéza může být nekonzistentní dvěma způsoby - false negative - potřebujeme formulit zobecnit - přidáme disjunkci nebo odebereme konjunkci - false positive - potřebujeme formuli specializovat - přidáme konjunkci nebo odebereme disjunkci - chceme udržet jednodušší formuli – podle Occamovy břitvy - tomu se říká **current-best-hypothesis search** - pro každou modifikaci musíme zkontrolovat konzistenci s předchozími příklady - **least-commitment search** - si udržuje všechny možné hypotézy konzistentní s příklady - tzv. version space - jak kompaktně reprezentovat version space - pomocí dolní a horní meze - některé formule jsou obecnější než jiné - je to částečné uspořádání - horní mez – obecné formule (obecnější jsou nekonzistentní) - $G$-set - na začátku True - pokud je příklad false positive pro $G_i$ → nahradíme ho všemi jeho následnými specializacemi - false negative → vyhodíme $G_i$ - dolní mez – specifické formule (specifičtější jsou nekonzistentní) - $S$-set - na začátku False - false positive → vyhodíme $S_i$ - false negative → nahradíme $S_i$ jeho následnými zobecněními - když je šum v datech, může dojít ke kolapsu version space - lineární modely - univariate linear function = přímka - $y=w_1x+w_0$ - multivariate linear function = nadrovina - $y=w_0+\sum_i w_ix_i$ - hledáme přímku (hypotézu), která bude nejlépe odpovídat datům - hypotézu značíme $h_w(x)$ - chybu měříme pomocí square loss function - chyba … $\sum_j(y_j-h_w(x_j))^2$ - → lineární regrese - lze řešit dvěma způsoby - analyticky pomocí rovnic - $\sum_j(y_j-(w_1x_j+w_0))^2=0$ - derivujeme postupně podle $w_0,w_1$ - pomocí metody *gradient descent* - $w_i\leftarrow w_i-\alpha\cdot\frac{\partial}{\partial w_i}\sum_j(y_j-h_w(x_j))^2$ - $\alpha$ … learning rate (step size) - lineární klasifikace - hledáme přímku (hypotézu), která bude oddělovat vstupy klasifikované jedním a druhým způsobem - hledáme lineární separátor - perceptronové pravidlo $w_i\leftarrow w_i+\alpha(y-h_w(x))\cdot x_i$ - kde $y$ je cílová hodnota a $h_w(x)$ je výstup perceptronu pro vektor $x$ - pro lineárně oddělitelné množiny konverguje - jinak „konvergenci“ zajistíme snižováním hodnoty $\alpha$ - můžeme použít logistickou prahovou funkci – není to černá/bílá, ale funkce nám řekne pravděpodobnost, že prvek patří do dané třídy - pak můžeme k nalezení vah použít *gradient descent* ### Umělé neuronové sítě - skládají se z propojených uzlů (jednotek) - každá jednotka nejdříve spočítá vážený součet vstupů - pak aplikuje aktivační funkci, čímž odvodí výstup - perceptron – schodová (step, hard treshold) aktivační funkce - sigmoid perceptron – aktivační funkce s logistickým tresholdem - struktury neuronových sítí - feed-forward network - spoje jenom v jednom směru (DAG) - reprezentuje funkci, která převádí vstup na výstup - žádný interní stav (paměť) kromě vah - recurrent network - výstup vrací zpátky do svých vstupů - reprezentuje dynamický systém, který může dojít do stabilního stavu, oscilovat, nebo se dokonce chovat chaoticky - může mít krátkodobou paměť - učení ve feed-forward vícevrstevných sítích - váhy upravujeme pomocí metody *gradient descent* - chyba na výstupové vrstvě se dá snadno spočítat – prostě porovnáme očekávaný výstup a výsledek neuronu - neznám však chybu u skrytých neuronů uvnitř sítě - získám ji tak, že chybu u výstupních neuronů propaguju zpátky – chyba je vážená, protože propojení neuronů je složité (jeden neuron typicky ovlivňuje více jiných) - parametrický model - vezmeme data - zakódujeme je do **parametrů** neuronky (data „komprimujeme“, zajímá nás jenom část informace) - data zahodíme - neparametrický model - používáme původní data, abychom reprezentovali hypotézu - metoda nejbližších sousedů - na vstupu mám vektor $x$, chci vrátit nějaké odpovídající $y$ - mezi trénovacími příklady najdu $k$ vektorů, které jsou nejbližší k $x$ - tak dostanu $k$ odpovídajících $y$, s nimi něco provedu a výsledek vrátím - klasifikuju → lze zvolit nejčastější $y$ - dělám regresi → spojím tečky nebo použiju průměr - vzdálenosti se typicky měří pomocí Minkowského metriky - $L^p(a,b)=\sqrt[p]{\sum_i|a_i-b_i|^p}$ - pro $p=1$ … manhattanská vzdálenost - pro $p=2$ … euklidovská vzdálenost - máme-li boolovské hodnoty atributů, tak počet atributů, ve kterých se body liší, se nazývá Hammingova vzdálenost - support-vector machine (SVM) - stojí na lineární regresi - pokud lze třídy oddělit nadrovinou, zvolí takovou, která je nejdál od všech dat (příkladů) - nadrovina … maximum margin separator - pokud nejde použít nadrovinu, provede mapování do vícedimenzionálního prostoru (pomocí kernel function), kde už příklady půjde oddělit - SVMs jsou neparametrická metoda – příklady blíže k separátoru jsou důležitější, říká se jim support vectors (vlastně definují ten separátor) ### Bayesovské učení - někdy se neučíme úplně od nuly, už máme částečnou znalost, snažíme se naučit něco navrch – statistické učení - bayesovské učení - bereme v úvahu všechny hypotézy - vracíme vážený průměr všech hypotéz (váha = pravděpodobnost hypotézy) - další přístup – bereme v úvahu nejpravděpodobnější hypotézu - bayesovské sítě, parameter learning (učení se parametrů) - chceme se naučit hodnoty, které vyplníme do CPD tabulek - maximum-likelihood parameter learning - hledáme hypotézu, která nejlépe vysvětluje příklady - nejprve vyjádříme pravděpodobnost dat za podmínky dané hypotézy - pak derivujeme logaritmus téhle pravděpodobnosti postupně podle každého hladeného parametru - určíme hodnoty parametrů tak, aby byly derivace nulové - co když mám skryté proměnné (nejsou v datech)? - můžu udělat bayesovskou síť bez skrytých proměnných, to ale může vést k výraznému zvýšení počtu parametrů - algoritmus expectation-maximization (EM) - předstíráme, že známe parametry modelu - dopočteme očekávané hodnoty skrytých proměnných (E-step, expectation) - upravíme parametry, abychom maximalizovali likelihood modelu (M-step, maximization) - iterujeme (dokud to nezačne konvergovat) ### Reinforcement learning (zpětnovazební učení) - základní myšlenka - nemusíme agentovi říkat $y$ - agent se učí transition model pro své vlastní akce - vychází z markovských rozhodovacích procesů - agent dostává pozitivní nebo negativní zpětnou vazbu (ve formě reward/reinforcement) - aby zjistil, co je dobré a co je špatné - odměna (reward) je součástí *input percept* (vstupního vnímání), ale agent musí být *hardwired*, aby chápal, že je to odměna - cílem zpětnovazebního učení je, aby se agent pomocí odměn naučil optimální strategii pro prostředí - pasivní učení – známe strategii a učíme se, jak je dobrá (učíme se utility funkci) - strategie $\pi$ je pevně daná - agent nezná přechodový model ani reward function - myšlenka: agent se řídí podle policy, vnímá současný stav a reward, z toho odvozuje utility - přímý odhad utility - máme trace (běh) mezi stavy, z toho (postupně) počítáme utility function - pokud stav potkáme víckrát, tak průměrujeme - idea: utilita stavu je očekávaný celkový reward z toho stavu v budoucnu (očekávaný *reward-to-go*) - nevýhody – utilities nejsou nezávislé, ale řídí se Bellmanovými rovnicemi - hledáme v prostoru hypotéz, který je výrazně větší, než by musel být (obsahuje spoustu funkcí, co porušují Bellmanovy rovnice) → algoritmus konverguje pomalu - $U^\pi(s)\leftarrow R(s)+\gamma\sum_{s'}P(s'\mid s,\pi(s))\cdot U^\pi(s')$ - adaptivní dynamické programování (ADP) - agent se učí přechodový model a odměny - utilitu počítá třeba z Bellmanových rovnic třeba pomocí value iteration - upravuje stav, aby odpovídal všem následníkům - temporal-difference (TD) learning - po každém kroku updatuju jedno číslo - nepotřebuju přechodový model (je to model-free metoda) - konverguje to pomaleji než ADP - upravuje stav, aby odpovídal aktuálně pozorovanému následníkovi - když dojde k přechodu ze stavu $s$ do stavu $s'$, tak na $U^\pi(s)$ použijeme update: $U^\pi(s)\leftarrow U^\pi(s)+\alpha\cdot (R(s)+\gamma\cdot U^\pi(s')-U^\pi(s))$ - aktivní učení – agent zjišťuje, co má dělat (učíme se strategii a utility funkci) - agent neví, co má dělat - active ADP agent - agent se učí přechodovou funkci a odměny - používá Bellmanovy rovnice - $U^\pi(s)\leftarrow R(s)+\gamma\max_a\sum_{s'}P(s'\mid s,a)\cdot U^\pi(s')$ - můžeme použít value iteration - získáme utility funkci - ale nemusí se chovat úplně optimálně – opakuje zažité vzory - říká se tomu hladový (greedy) agent - jak může volba optimální akce vést k suboptimálním výsledkům? - naučený model není stejný jako reálné prostředí - akce nejsou pouze zdrojem odměn, ale také přispívají k učení – ovlivňují vstupy - zlepšováním modelu se postupně zvětšují odměny, které agent získává - je potřeba najít optimum mezi exploration a exploitation - pure exploration – agent nepoužívá naučené znalosti - pure exploitation – riskujeme, že bude agent pořád dokola opakovat zažité vzory - základní myšlenka: na začátku preferujeme exploration, později lépe rozumíme světu, takže nepotřebujeme tolik prozkoumávat - exploration policies - agent si zvolí náhodnou akci v $O(1/t)$ případech (kde $t$ je čas), jinak se řídí hladovou strategií - nakonec to konverguje k optimální strategii, ale může to být extrémně pomalé - rozumnější přístup je přiřadit váhu akcím, které agent nezkusil příliš často, a vyhýbat se akcím, o kterých jsme přesvědčeni, že mají malou utilitu - přiřadíme vyšší odhad utility neprozkoumaným dvojicím (stav, akce) - opět použijeme value iteration - používáme optimistický odhad utility, aby se agent dostal i do vzdálenějších neprozkoumaných oblastí - existuje alternativní TD metoda, říká se jí Q-learning - $Q(s,a)$ označuje hodnotu toho, že provedeme akci $a$ ve stavu $s$ - q-hodnoty jsou s utilitou ve vztahu $U(s)=\max_a Q(s,a)$ - můžeme napsat omezující podmínku $Q(s,a)=R(s)+\gamma\sum_{s'} P(s'\mid s,a)\cdot \max_{a'}Q(s',a')$ - tohle vyžaduje, aby se model naučil i $P(s'\mid s,a)$ - tenhle přístup nevyžaduje model přechodů – je to bezmodelová (model-free) metoda, potřebuje akorát q-hodnoty - $Q(s,a)\leftarrow Q(s,a)+\alpha\cdot (R(s)+\gamma\cdot\max_{a'}Q(s',a')-Q(s,a))$ - počítá se, když je akce $a$ vykonána ve stavu $s$ a vede do stavu $s'$ - state-action-reward-state-action (SARSA) - je to varianta Q-učení - $Q(s,a)\leftarrow Q(s,a)+\alpha\cdot (R(s)+\gamma\cdot Q(s',a')-Q(s,a))$ - pravidlo se aplikuje na konci pětice $s,a,r,s',a'$, tedy po aplikaci akce $a'$ - pro hladového agenta (který volí podle největšího $Q$) jsou algoritmy SARSA a základní Q-learning stejné - rozdíl je vidět až u agenta, který není úplně hladový, ale provádí i průzkum (exploration) - u SARSA se bere v úvahu reálně zvolená akce (podle strategie – je to on-policy algoritmus, kdežto Q-learning je off-policy) ## 11. Filozofické a etické aspekty - přístup k AI - myslet lidsky – jako člověk - myslet racionálně – logicky - jednat lidsky – podle Turingova testu - jednat racionálně – jako racionální agent - lidská utility funkce jsou obvykle peníze - ale nedají se použít přímo – nejsou lineární (mezi milionem a dvěma miliony není takový rozdíl jako mezi nulou a milionem) - lidé jsou „předvídatelně iracionální“ - preferují jistotu oproti nejistotě … certainity effect - preferují známou pravděpodobnost oproti té neznámé … ambiguity aversion - mohou stroje myslet? - weak AI … stroje můžou jednat, jako by byly inteligentní - to je zjevné - strong AI … stroje opravdu myslí - není jasné, zda je to vůbec možné - general AI … stroje můžou vyřešit libovolný problém - strong AI je v principu general AI - ale může být i weak AI general AI? - narrow AI … stroje můžou řešit problémy v konkrétní oblasti - určitě - Turingův test - počítač má pětiminutovou konverzaci s člověkem - člověk musí uhodnout, jestli to byl počítač nebo jiný člověk - pokud počítač napálí člověka v aspoň 30 % případů, tak prošel Turingovým testem - povedlo se to programům ELIZA, Eugene Goostman, Google Duplex, … - reverzní Turingův test – počítač se snaží zjistit, jestli komunikuje s počítačem nebo člověkem (např. captcha) - je Gödelova věta o neúplnosti problémem pro AI? - logická omezení se týkají i lidí - mind-body problem - dualistická teorie – tělo a mysl existují v oddělených sférách - jak může mysl ovládat tělo? - monistická teorie – mysl není oddělená od těla - mentální stavy jsou fyzické - tato teorie dnes převažuje - tedy by silná AI měla být možná - myšlenkové experimenty - brain in a vat – dá se poznat život v simulaci? - brain replacement – dají se neurony vyměnit jeden po druhém, aniž bychom přišli o vědomí? - čínský pokoj – poznáme, jestli člověk v pokoji rozumí čínštině? - etické problémy AI - falešné informace (ztráta důvěry) - dohled (ztráta práce) - automatizace (ztráta zaměstnání) - zabijácké stroje (ztráta životů) - konec lidské rasy (singularita) - technické problémy AI - vysvětlitelnost – člověk někdy potřebuje vědět, proč daný systém vrátil konkrétní výstup - křehkost – někdy se stává, že malá změna vstupu dramaticky změní výstup - předpojatost (bias) – může se stát, že systém upřednostňuje určitou skupinu uživatelů - sociální problémy AI - vojenské použití – může AI systém vystřelit? - zaměstnání – zautomatizují AI systémy každý lidský úkon? - dohled – mohou AI systémy nepřímo ovládat lidské životy? - rozhodování – měly by se AI systémy rozhodovat (nebo pouze doporučovat)? - tramvajové dilema