# Úvod do umělé inteligence ## Historie - co to znamená správně přemýšlet? - Aristoteles – sylogismy, formalizace logiky - sylogismus – pokud dostane správné předpoklady, vrátí správné důsledky - Descartes, Boole - co když věci nejsou černobílé? - počítání s nejistotou a neúplností – pravděpodobnost - Cardamo, Bayes - 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) - jak navrhovat systémy na zpracování informací? - automaty - stroj Antikythera – starověké Řecko, pro předvídání pohybů hvězd - Jacquard – program pro tkalcovský stroj, pomocí děrných štítků - Babbage – Difference Engine, Analytical Engine - Zuse, Turing - jak se stroje můžou samy udržovat při (správném) chodu? - Ktesibios – regulátor vodního toku - Watt – regulátor parního stroje - Wiener – kybernetika (autonomní stroje) - teorie řízení - 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í - Craik – zavedl pojem znalostní (knowledge-based) agent - postupný převod vjemu na vnější akci - lingvistika – jak jazyk souvisí s myšlením - 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í - 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? - 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 - 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 / stochartic) - … ## Agenti, prohledávání - 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 - reprezentace stavů - atomic – stav je blackbox - factored – stav je vektor - structured – stav je sada objektů, ty jsou propojeny - problem solving agent - akce jsou reprezentovány pomocí přechodové funkce - cílem je najít posloupnost akcí, kterými se dostaneme z výchozího do cílového stavu - cílových stavů může být víc - očekáváme, že prostředí je plně pozorovatelné, diskrétní, statické a deterministické - Lloydova patnáctka - ne všechny stavy jsou dosažitelné – zachovává se parita permutace - budeme potřebovat abstrakci 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ý) - použijeme prohledávání grafu (někdy je graf strom – do každého stavu se lze dostat jedním způsobem) - u prohledávání stromu si nemusíme ukládat „uzavřenost“ vrcholu, stačí nám seznam vrcholů na okraji prozkoumané oblasti (frontier, jsou to otevřené vrcholy) - 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 - graph-search vs. tree-search - algoritmy na prohledávání grafů - graph-search si pamatuje, které vrcholy už expandoval (takže ho cyklus nerozháže) - i tree-search lze použít k prohledávání grafů s cykly, ale může se chovat divně - algoritmy neinformovaného prohledávání - BFS (fronta) - ú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) - úplný pro graph-search - neúplný pro tree-search - pokud algoritmus pustíme na grafu, který není strom - suboptimální - časová složitost $O(b^m)$, kde $m$ je maximální hloubka libovolného vrcholu - prostorová složitost $O(bm)$ - extenze BFS pro 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 - best-first search - pro vrchol máme ohodnocovací funkci $f(n)$ - $f(n)$ použijeme v Dijkstrově algoritmu místo $g(n)$ - 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 - mějme vrchol $n$ a jeho souseda $n'$ - $c(n,a,n')$ je cena přechodu z $n$ do $n'$ - heuristika je monotónní, když $h(n)\leq c(n,a,n')+h(n')$ - tvrzení: monotónní heuristika je přípustná - tvrzení: pro monotónní heuristiku jsou hodnoty $f(n)$ neklesající po libovolné cestě - tvrzení: pokud je $h(n)$ přípustná, pak je A* u tree search optimální - tvrzení: pokud je $h(n)$ přípustná, pak je A* u graph search optimální - 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$ - best-first je třída algoritmů, kde máme uzly ohodnoceny nějakou funkcí a vybíráme nejmenší z nich - backtracking vs. DFS - 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) - 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 - 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 - … - 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 - 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) - relace = podmnožina kartézského součinu - 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 - constraint arity = počet proměnných, které podmínka omezuje - chceme přípustné řešení (feasible solution) - 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 - arc consistency (hranová konzistence) - arc = orientovaná hrana - edge = neorientovaná hrana - 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á podmínka odpovídá orientované hraně v síti podmínek - 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 $V_i,V_j$ - CSP je hranově konzistentní $\equiv$ každá hrana je hranově konzistentní (v obou směrech) - algoritmus AC-3 - jakmile odstraním prvky domény, musím opakovat kontrolu v sousedech (ale stačí kontrolovat jen jednu ze dvou hran) - složitost $O(ed^3)$, kde $e$ je počet podmínek, $d$ je velikost domény - optimální algoritmus má složitost $O(ed^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 (strom se větví exponenciálně) - hranová konzistence je typ lokální konzistence - takže 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 - často lze prohodit proměnné a hodnoty (hodnoty se stávají proměnnými, proměnné hodnotami) → vznikne duální model - 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 - 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 - jak hledat jednotkové klauzule – clever indexing (?) - 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 nebo se jich na něco ptát - agent používá inferenci – logicky odvozuje - agent v jeskyni – díry a Wumpus; má šíp - 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 - 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$ - to platí, právě když $KB\land\neg\alpha$ je nesplnitelné - lze použít rezoluci - Hornova klauzule - 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 - backward chaining … goal-driven reasoning - něco mě zajímá – pokouším se to odvodit - tohle se používá v Prologu --- - plánování… --- - 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é heuristika - 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ě) ## Nejistota - 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í - 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 - velkou tabulku budeme reprezentovat menším způsobem - Bayesovo pravidlo - bayesovská síť je orientovaný acyklický graf, 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 - 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, Earthquakce - 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|e)=\alpha P(X,e)=\alpha\sum_y P(X,e,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))$ - 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 s faktory mezi sebou můžeme násobit - Monte Carlo přístup? ## Čas a nejistota - formální model - transition model - určuje pravděpodobnostní rozložení přes proměnné posledního stavu, když známe předchozí hodnoty - zjednodušující předpoklady - další stav závisí jen na předchozím stavu - všechny přechodové tabulky jsou identické přes všechna $t$ - sensor (observation) model - popisuje, jak se pozorované proměnné mění - … - základní inferenční úlohy - filtrování - predikce - vyhlazování - nejpravděpodobnější vysvětlení - skryté proměnné popisují stavy světa - stavy světa jsou neznámé → proto jsou proměnné skryté - mezi stavy existují pravděpodobnostní přechody - předpoklad: nový stav (jeho pravděpodobnost) závisí jen na tom předchozím - máme pozorované proměnné - předpoklad: pozorování záleží jenom na současném stavu, ne na těch předchozích - základní inferenční úlohy - filtering - prediction - smoothing - most likely explanation - skryté Markovovy modely - máme matici stavů a měření - algoritmy lze formulovat pomocí maticových operací - markovovský rozhodovací proces (MDP) - sekvenční rozhodovací problém - pro plně pozorovatelné stochastické prostředí - máme Markovovův přechodový model a reward - řešením MDP je policy (strategie) – funkce doporučující akci pro každý stav - 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í) - 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 uižtkem a užitkem strategie - můžeme iterativně zlepšovat policy, dokud se nepřestane zlepšovat - z rovnic nám zmizí maximum → máme lineární rovnice - → policy iteration - gaussovka je $O(n^3)$ - částečně pozorovatelný markovský rozhodovací proces (POMDP) - místo reálný 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 a dostaneme dynamickou rozhodovací síť - generujeme si stromeček - „co kdyby pozorování bylo takové?“ „co kdyby bylo jiné?“ - používá se algoritmus ExpectedMiniMax - 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, …) - algoritmus minimax - 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 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 uzly s tahy hráčů přidám vrstvy s pravděpodobnostmi - při výpočtu min nebo max je vážím 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 - kámen, nůžky, papír - dvouprstá Morra - vězňovo dilema - dominantní čistá strategie – testify (defect) - ale vyhrála policie – lepší by bylo, kdyby oba odmítli vypovídat (= refuse/cooperate) - našli jsme Nashovo ekvilibrium – nikdo neprofituje ze změny strategie, pokud druhý hráč zůstane u stejné strategie - definice dominance a čistoty strategie - dvouprstá Morra nemá čistou strategii - jak najít optimální smíšenou strategii? - technika maximin - opakované hry - strategie pro opakované vězňovo dilema - pokud víme, která hra je poslední, vede to na podobnou situaci jako u jedné hry - tit-for-tat - k čemu používáme teorii her - k návrhu agentů - k návrhu mechanismů (pravidel) - inverzní teorie her - aukce - anglická aukce - strategie: přihazuju, dokud cena není vyšší než moje hodnota - 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 - obálková aukce - největší nabídka vítězí - neexistuje jednoduchá dominantní strategie - 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í - „tragedy of commons“ - mechanismus Vickeray-Clarke-Groves - zdanění společného zboží - problém – je nezbytné mít centrální autoritu - 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 ## Strojové učení - způsob, jak zlepšit chování umělého agenta - učení vs. 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 - 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 - máme vstupy a výstupy - chceme najít funkci (její aproximaci), která mapuje vstupy na výstupy - hledáme hypotézu z prostoru hypotéz - princip Occamovy břitvy - typy úloh – klasifikace (u nečíselných funkcí) nebo regrese (u číselných funkcí) - nekonzistence s příkladem – příklad neodpovídá naučené funkci - rozhodovací strom - přijímá vektor hodnot atributů, vrací výslednou hodnotu - na základě tabulky příkladů se dá postavit strom, vnitřní uzly jsou jednotlivé atributy - dá se zjistit odůvodnění konkrétního rozhodnutí - strom se dá postavit hladovou metodou rozděl a panuj - zakončení větve - když jsou ve větvi výsledky jednoho druhu - 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 - snažím se vždy 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é) - logická formulace učení - agent má inferenční mechanismus - přihodíme mu axiom, aby toho mohl odvozovat víc - z větví v rozhodovacím stromu můžeme udělat logické formule - 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 - 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í) - dolní mez – specifické formule (specifičtější jsou nekonzistentní) - když je šum v datech, může dojít ke kolapsu version space - lineární regrese - vzorečky viz prezentace - můžeme ji použít pro klasifikaci – nakreslíme přímku, která bude oddělovat vstupy klasifikované jedním a druhým způsobem - perceptronové pravidlo - 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 - … - zpětné šíření chyby - znám chybu u výstupních neuronů - neznám 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 - lze zvolit nejčastější $y$ - lze použít regresi nebo průměr - vzdálenosti se typicky měří pomocí Minkowského metriky - support-vector machine - stojí na lineární regresi - pokud lze třídy oddělit nadrovinou, zvolí takovou, která je nejdál od všech dat (příkladů) - pokud nejde použít nadrovinu, provede mapování do vícedimenzionálního prostoru, 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 - 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 - 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 - hledáme hypotézu, která nejlépe vysvětluje příklady - derivuju postupně podle každého hledaného parametru a derivaci položím rovnou nule - co když mám skryté uzly v síti - 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 - upravíme parametry, abychom maximalizovali likelihood modelu - iterujeme (dokud to nezačne konvergovat) - reinforcement learning (zpětnovazební učení) - nemusíme agentovi říkat $y$ - agent dostává pozitivní nebo negativní zpětnou vazbu (ve formě reward/reinforcement) - vychází z markovských rozhodovacích procesů - pasivní učení – známe strategii a učíme se, jak je dobrá (učíme se utility funkci) - aktivní učení – agent zjišťuje, co má dělat - pasivní učení - agent nezná přechodový model ani reward function - přímý odhad utility - máme trace (běh) mezi stavy, z toho (postupně) počítáme utility function - nevýhody – utilities nejsou nezávislé, ale řídí se Bellmanovými rovnicemi - adaptivní dynamické programování (ADP) - používá Bellmanovy rovnice - temporal-difference learning - po každém kroku updatuju jedno číslo - nepotřebuju přechodový model - konverguje to pomaleji než ADP - aktivní učení - agent neví, co má dělat - active adaptive dynamic programming agent - používá Bellmanovy rovnice - ale nemusí se chovat úplně optimálně – opakuje zažité vzory - říká se tomu hladový (greedy) agent - je potřeba najít optimum mezi exploration a exploitation - k tomu se dá použít temporální diference a Q funkce – říká se tomu Q učení - variantou Q učení je SARSA (state-action-reward-state-action)