Skip to content

Latest commit

 

History

History
1118 lines (1086 loc) · 69.4 KB

zkouska.md

File metadata and controls

1118 lines (1086 loc) · 69.4 KB
Raw

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