Ú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)