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