Zkouška

• 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í

• 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

• 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ů

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

• 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

• 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

• 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

• Noam Chomsky – formální teorie
• porozumění jazyku vyžaduje porozumění obsahu (nestačí rozumět syntaxi)

• 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í

• 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

• 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.

• 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í

• 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

expertní systémy – zabývají se konkrétními obory lidské činnosti

• systémy jsou křehké a drahé na údržbu
• lispové počítače byly nahrazeny obecnými počítači (Apple, IBM)

• 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

• innovation trigger
• peak of inflated expectations
• trough of disillusionment
• slope of enlightenment
• plateau of productivity

• 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á

• 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

• 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

• 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

• 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

• 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ý)

• vrcholy = stavy (kořen = výchozí stav)
• hrany = akce

• 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

• 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

• 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$

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

• 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

• 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

• 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$

• 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í

• 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

• 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

• 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

• 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

• 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

• 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í

• 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$

$L_{x,y}^t\implies(\text{Breeze}^t\iff B_{x,y})$

• 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

• 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)$

• 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ů

• 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á

• 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ý

• 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

• 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í

• 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í)

• 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ě)

• 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

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

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

• šipky popisují závislost
• u každého vrcholu jsou CPD tabulky, které popisujou jeho závislost na rodičích
  • CPD = conditional probability distribution

• 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í

• $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é

• 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

• 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}$

• 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

• 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ů

• 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ě

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

• 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ší

• 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$

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

• 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,

• 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$

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

• 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

• ř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ší

• 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

• 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

• 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

• 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

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

• 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

• 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

• 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

• 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í

• 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})$

• 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

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

• 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

• 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

• 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ěť

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

• vezmeme data
• zakódujeme je do parametrů neuronky (data „komprimujeme“, zajímá nás jenom část informace)
• data zahodíme

• 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

• 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í
  • 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

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

• 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í

• 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))$

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

• myslet lidsky – jako člověk
• myslet racionálně – logicky
• jednat lidsky – podle Turingova testu
• jednat racionálně – jako racionální agent

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)

• preferují jistotu oproti nejistotě … certainity effect
• preferují známou pravděpodobnost oproti té neznámé … ambiguity aversion

• 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ě

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

logická omezení se týkají i lidí

• 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á

• 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ě?

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

• 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ů

• 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