Základy umělé inteligence: kartičky

Řešení úloh prohledáváním

formulace úlohy

agent – vnímá prostředí pomocí senzorů, aktuátory mu umožňují jednat
- racionální agent
  - zvolí akci, která maximalizuje jeho výkon
- simple reflex agent
  - observation → action
- model-based reflex agent
  - past state + past action + observation → state
  - state → action
- goal-based agent
  - state + goal → action
reprezentace stavů agenta
- 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í úloh prohledáváním

stromové vs. grafové prohledávání

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 (opakovat se můžou, pokud do stejného vrcholu vedou dvě orientované cesty)

Řešení úloh prohledáváním

neinformované prohledávání (DFS, BFS, uniform-cost search)

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
  - úplný = nalezne řešení vždy, když existuje (a v opačném případě hlásí, že řešení neexistuje)
- 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)$ $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

Řešení úloh prohledáváním

informované prohledávání (algoritmus A*, přípustné a konzistentní heuristiky)

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)$ $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í: monotonie implikuje přípustnost, opačná implikace neplatí
- tvrzení: pro monotónní heuristiku jsou hodnoty $f(n)$ neklesající po libovolné cestě
- tvrzení: pokud je $h(n)$ $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)$ $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$ $h_{2}$ dává větší hodnoty než $h_1$ $h_{1}$ , tak se říká, že $h_2$ $h_{2}$ dominuje $h_1$ $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$

Splňování omezujících podmínek

problém splňování podmínek

= 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 (je to podmnožina kartézského součinu domén)
- 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

Splňování omezujících podmínek

hranová konzistence (algoritmus AC-3)

= arc consistency (arc … orientovaná hrana)
uvažujme binární podmínky
- libovolnou n-ární podmínku lze převést na balík binárních podmínek
každá 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)$ $(V_{i}, V_{j})$ je hranově konzistentní $\equiv$ $\equiv$ pro každé $x\in D_i$ $x \in D_{i}$ existuje $y\in D_j$ $y \in D_{j}$ takové, že přiřazení $V_i=x$ $V_{i} = x$ a $V_j=y$ $V_{j} = y$ splní všechny binární podmínky pro $V_i,V_j$ $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)$ $O (c d^{3})$ , kde $c$ $c$ je počet podmínek, $d$ $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)$
hranová konzistence je typ lokální konzistence, negarantuje globální konzistenci
arc consistency (AC) vs. forward checking (FC)
- FC je jednodušší (a rychlejší) než AC, slouží ke stejnému účelu – zrychlení prohledávání
- FC na základě přiřazení do proměnné (v daném kroku prohledávání) pročistí domény dosud nepřiřazených proměnných
- AC k tomu navíc zajišťuje vzájemnou kompatibilitu domén nepřiřazených proměnných

Splňování omezujících podmínek

algoritmus hledání řešení (MAC)

chceme 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 (MAC, maintaining arc consistency)
kontroly FC/AC jsou v polynomiálním čase, kdežto strom stavů se větví exponenciálně

Logické uvažování

základy výrokové logiky (konjunktivní a disjunktivní normální forma)

viz Společná matematika
výrokovou logiku lze použít k logickému odvozování znalostí na základě znalostní báze

Logické uvažování

algoritmus DPLL

literál $\ell$ $ℓ$ má čistý výskyt ve $\varphi$ $φ$ , pokud se $\ell$ $ℓ$ vyskytuje ve $\varphi$ $φ$ a opačný literál $\overline\ell$ $\overline{ℓ}$ se ve $\varphi$ $φ$ nevyskytuje
- takový literál můžu nastavit na 1
- to neovlivní splnitelnost výroku, ale zmenší to množinu modelů, které jsem schopen nalézt
algoritmus
- dokud $\varphi$ $φ$ obsahuje jednotkovou klauzuli $\ell$ $ℓ$ , ohodnoť $\ell=1$ $ℓ = 1$ a proveď jednotkovou propagaci
  - každou klauzuli obsahující $\ell$ odstraníme (protože je takto splněna)
  - $\overline\ell$ odstraníme ze všech klauzulí, které ho obsahují (protože $\overline\ell$ nemůže zajistit splnění dané klauzule)
- dokud existuje literál $\ell$ , který má ve $\varphi$ čistý výskyt, ohodnoť $\ell=1$ a odstraň klauzule obsahující $\ell$
- pokud $\varphi$ neobsahuje žádnou klauzuli, je splnitelný
- pokud $\varphi$ obsahuje prázdnou klauzuli, není splnitelný
- jinak zvol dosud neohodnocenou výrokovou proměnnou $p$ a zavolej algoritmus rekurzivně na $\varphi\land p$ a na $\varphi\land\neg p$
algoritmus běží v exponenciálním čase
praktické poznámky
- čistý výskyt se zas tak moc nepoužívá
- jednotková propagace
  - hledám klauzule o jedné proměnné
  - je v zásadě ekvivalentní hranové konzistenci
- ke zkoušení hodnot proměnných se používá tree search

Logické uvažování

dopředné a zpětné řetězení (Hornovské klauzule)

mám dotaz $\alpha$ $α$ , ten vyjádřím jako výrokovou formuli
- znalostní bázi $KB$ vyjádřím jako teorii
- zajímá mě, zda $KB\models\alpha$ (to platí, právě když $KB\land\neg\alpha$ je nesplnitelné)
řetězení můžeme použít, pokud znalostní báze obsahuje pouze Hornovy klauzule
- Hornova klauzule = disjunkce literálů, z nichž nejvýše jeden je pozitivní
- Hornovu klauzuli $\neg p\lor\neg q\lor\neg r\lor s$ lze zapsat jako implikaci $p\land q\land r\implies s$
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
  - najdu klauzule, kde je nějaký literál z $\alpha$ na pravé straně implikace
  - tak dostanu další literály, které musím dokázat
  - postupuju tak dlouho, dokud se nedostanu k faktům (literálům, o nichž vím, že platí)
- tohle se používá v Prologu
- opět vlastně používám rezoluční pravidlo
  - to, co chci zjistit, rezolvuju s libovolnou klauzulí
forward chaining prochází spoustu klauzulí, které nás nezajímají – backward chaining může mít výrazně menší složitost

Logické uvažování

rezoluce

mám dotaz $\alpha$ $α$ , ten vyjádřím jako výrokovou formuli
- znalostní bázi $KB$ vyjádřím jako teorii
- zajímá mě, zda $KB\models\alpha$ (to platí, právě když $KB\land\neg\alpha$ je nesplnitelné)
$KB\land\neg\alpha$ převedeme do CNF → dostaneme množinu klauzulí (formuli $S$ )
použijeme rezoluci (zkonstruujeme rezoluční zamítnutí formule $S$ $S$ )
- 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$

Pravděpodobnostní uvažování

základy teorie pravděpodobnosti (úplná sdružená distribuce, nezávislost, Bayesovo pravidlo)

viz Společná matematika
pravděpodobnostní uvažování umožňuje agentovi zacházet s nejistotou
zdroji nejistoty jsou částečná pozorovatelnost (nelze snadno zjistit současný stav) a nedeterminismus (není jisté, jak akce dopadne)
agent si pamatuje belief state – pravděpodobnostní distribuce přes všechny možné stavy světa, v nichž se agent může nacházet

Pravděpodobnostní uvažování

pravděpodobnostní uvažování (vysčítání, normalizace)

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
$P(Y)=\sum_z P(Y\mid z)\cdot P(z)$
$P(Y\mid e)=\frac{P(Y\land e)}{P(e)}$ $P (Y ∣ 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)$ $P (Y ∣ X) = \frac{P ( X ∣ Y ) P ( Y )}{P ( X )} = α P (X ∣ 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(\mathrm{effect} \mid \mathrm{cause})$ … casual direction (příčinný směr), obvykle známý
  - $P(\mathrm{cause} \mid \mathrm{effect})$ … diagnostic direction (diagnostický směr), obvykle chceme zjistit
  - známe důsledky; chceme zjistit, jaké příčiny k nim mohly vést
naivní bayesovský model
- $P(\text{Cause}, \text{Effect}_1, \dots, \text{Effect}_n) = P(\text{Cause})\prod_iP(\text{Effect}_i\mid\text{Cause})$
- předpokládáme nezávislost důsledků
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)

Pravděpodobnostní uvažování

Bayesovské sítě: konstrukce a vztah k úplné sdružené distribuci

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
  - pro každou kombinaci hodnot rodičů jsou v CPD tabulce pravděpodobnosti hodnot dané náhodné proměnné
- autorem obrázku je Roman Barták
- proměnné jsou binární, proto má tabulka vždy jen jeden sloupec (druhý sloupec by mohl obsahovat pravděpodobnost, že jev nenastane – lze ho dopočítat z prvního sloupce)
konstrukce bayesovské sítě
- nějak si uspořádáme proměnné
  - lepší je řadit je od příčin k důsledkům – budeme mít menší síť a CPD tabulky se nám budou vyplňovat snáze
- jdeme odshora dolů, přidáváme správné hrany
- příklad: MaryCalls, JohnCalls, Alarm, Burglary, Earthquake (záměrně jdeme od důsledků k příčinám, byť to není praktické)
  - 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 se nám v tomto pořadí budou špatně určovat CPD
bayesovská síť zachycuje úplnou sdruženou (joint) distribuci
- dokážeme určit pravděpodobnost libovolné kombinace hodnot náhodných proměnných
- pronásobíme mezi sebou hodnoty z tabulek

Pravděpodobnostní uvažování

Bayesovské sítě: exaktní odvozování (enumerace, eliminace proměnných)

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)$ $P (X ∣ e) = α P (X, e) = α \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)$ $P (X, e, y)$ lze určit pomocí CPD tabulek
- když nemůžeme určit konkrétní hodnotu pravdě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
- eliminace
  - mějme faktor s pravděpodobnostmi $P(A,B,C)$ pro všechny možné kombinace hodnot proměnných
  - můžeme ho rozdělit na dvě půlky (v jedné bude všude platit $A$ , v druhé $\neg A$ )
  - tyhle dvě půlky můžeme sečíst (vždy odpovídající řádky)
  - tak eliminujeme proměnnou $A$ , dostaneme faktor s pravděpodobnostmi $P(B,C)$

Pravděpodobnostní uvažování

Bayesovské sítě: aproximační odvozování (Monte Carlo, zamítání, vážení věrohodností)

odhadujeme hodnoty, které je těžké přímo spočítat
- třeba když je síť moc velká a hustě propojená
- zajímá nás $P(X\mid e)$
generujeme hodně vzorků, použijeme statistiku
pravděpodobnostní rozdělení náhodných veličin známe (postupujeme topologicky bayesovskou sítí a generujeme hodnoty)
jak generovat vzorky?
- rejection sampling = zahodíme vzorky, kde neplatí $e$ $e$
  - odhadneme $P(X\mid e)\approx\frac{N(X,e)}{N(e)}$ $P (X ∣ e) \approx \frac{N ( X , e )}{N ( e )}$
    - $N(X,e)$ … počet vzorků, kde platí $X,e$
  - riziko, že zahodíme příliš mnoho vzorků
- likelihood weighting
  - zafixujeme (ignorujeme) $e$ , generujeme jen zbylé proměnné
  - počtům $N$ přidělíme váhy podle pravděpodobnosti $e$ (např. místo toho, abychom zahodili cca 90 % vzorků, přiřadíme těm počtům váhu 0.1)
  - problém nastává, když jsou váhy příliš malé

Reprezentace znalostí

situační kalkulus, problém rámce

problém rámce
- návrh: stav světa/agenta budeme popisovat pomocí časově anotovaných výrokových proměnných
- musíme definovat spoustu axiomů, které zajistí, že se hodnoty proměnných mezi časovými kroky nemění náhodně
- tak bychom snadno zahltili odvození pomocí výrokové logiky, protože bychom měli 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í: $\mathrm{at}(\mathrm{robot}, \mathrm{location}, s)$
  - pro stálé relace takový argument není potřeba: $\mathrm{connected}(l, l')$
- podmínky (předpoklady) akcí jsou definovány possibility axiomem
  - obecný tvar: $\varphi(s)\implies \text{Poss}(a,s)$ $φ (s) ⟹ Poss (a, s)$
    - kde $\varphi$ je formule popisující předpoklady akce $a$
  - např. $\mathrm{at}(a, l, s) \land \mathrm{connected}(l, l') \implies \mathrm{Poss}(\mathrm{go}(a, l, l'), s)$
- vlastnosti dalšího stavu jsou popsány pomocí successor-state axiomů
  - např. $\mathrm{Poss}(a, s) \implies$ $(\mathrm{at}(a,y,\mathrm{Results}(s, a)) \iff a=\mathrm{go}(a,x,y) \lor (\mathrm{at}(a,y,s) \land a\neq \mathrm{go}(a,y,z))$
- plánování se provádí tak, že se zeptáme, zda existuje situace, kde je cílová podmínka pravdivá

Reprezentace znalostí

Markovské modely – filtrace, predikce, vyhlazování, nejpravděpodobnější průchod

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})$ $P (X_{t + 1} ∣ e_{1 : t + 1}) = P (X_{t + 1} ∣ 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})$ $= α \cdot P (e_{t + 1} ∣ X_{t + 1}, e_{1 : t}) \cdot P (X_{t + 1} ∣ 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í
  - používá se forward algoritmus
- 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})$ $P (X_{k} ∣ e_{1 : t}) = P (X_{k} ∣ 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})$ $= α \cdot P (X_{k} ∣ e_{1 : k}) \cdot P (e_{k + 1 : t} ∣ 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)
  - používá se forward-backward algoritmus
- nejpravděpodobnější vysvětlení (most likely explanation) – znám minulá pozorování, zajímá mě nejpravděpodobnější posloupnost minulých stavů
  - hledáme posloupnost $X_{1:t}$ takovou, že má největší $P(X_{1:t+1}\mid e_{1:t+1})$
  - 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ů
  - používá se Viterbiho algoritmus

Reprezentace znalostí

skryté Markovské modely (HMM) vs. dynamické Bayesovské sítě

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 (filtering, prediction, smoothing, …) implementovat maticově
dynamická bayesovská síť
- umožňuje popsat víc náhodných proměnných
- 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
  - v HMM vlastně celý stav světa komprimujeme do jedné náhodné proměnné – v DBN jich můžeme mít víc
- 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ší

Automatické plánování

formulace plánovacího problému (definice operátoru)

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ázev – obsahuje rovněž parametry operátoru (proměnné, které se objevují v předpokladech a důsledcích)
  - předpoklady – musí platit v daném stavu, aby se operátor dal použít
  - důsledky – literály (fluenty!), které budou platit, jakmile se operátor provede
- akce je plně zinstanciovaný operátor (za proměnné jsme dosadili konstanty)
- 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ý

Automatické plánování

dopředné a zpětné 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

Markovské rozhodovací procesy (MDP)

formulace problému (výpočet užitku, strategie)

ř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\in A(s)$
- 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$ $U ([s_{0}, s_{1}, s_{2}, \dots]) = R (s_{0}) + γ R (s_{1}) + γ^{2} R (s_{2}) + \dots$
  - kde $\gamma$ $γ$ je discount factor, číslo mezi 0 a 1
    - jak moc si ceníme budoucích odměn
  - 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_\text{max}}{1-\gamma}$
řešením MDP je policy (strategie) – funkce doporučující akci pro každý stav
- tzn. strategie je zobrazení $\pi:S\to A$
- potřebujeme zobrazení, 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ší střední hodnotu užitku (utility)
- 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

Markovské rozhodovací procesy (MDP)

Bellmanova rovnice

opravdový užitek stavu je reward (odměna) stavu ve spojení se střední hodnotou užitku následného stavu → to vede na Bellmanovu rovnici
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')$

Markovské rozhodovací procesy (MDP)

iterace hodnot, iterace strategií

předpoklad: známe reward $R$ $R$ a transition model $P$ $P$
- chceme najít užitek $U$ nebo optimální strategii $\pi$
soustava Bellmanových rovnic není lineární – obsahuje maximum
- můžeme je řešit aproximací
- použijeme iterativní přístup
  - nastavíme nějak užitky – třeba jako nuly
  - provedeme update – aplikujeme Bellmanovu rovnici
  - iterujeme, dokud to nezkonverguje
- → 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)$
  - u velkých stavových prostorů dává smysl k policy evaluation použít value iteration
- algoritmus doběhne, protože policies je jenom konečně mnoho a vždycky hledáme tu lepší

Markovské rozhodovací procesy (MDP)

POMDP (základní definice)

máme přechodový model $P(s'\mid s,a)$ , akce $A(s)$ i odměny $R(s)$
navíc nám přibude 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

Hry a teorie her

algoritmy Minimax a alfa-beta prořezávání

algoritmus minimax umožňuje u hry dvou hráčů s nulovým součtem a s úplnou informací určit optimální strategie obou hráčů
- procházíme strom hry
- v listech nebo v určité hloubce získáme ohodnocení vrcholů
  - omezení hloubky je důležité zvláště u her, jejichž stromy se hodně větví – je potřeba zvolit vhodný přístup k ohodnocení konkrétní herní situace
- následně vždy v rodiči zvolíme minimum nebo maximum ze synů (v závislosti na tom, který hráč je zrovna na tahu – volba minima a maxima se střídají stejně jako tahy hráčů)
- takto pro každý vrchol určíme, jaký tah je v dané situaci optimální
  - za předpokladu, že protihráč hraje optimálně – což je nejhorší možný scénář
alfa-beta prořezávání
- je to rozšíření minimaxu, které může zrychlit jeho běh tak, že omezuje počet větví, které je potřeba projít a vyhodnotit
- vycházíme z následujícího pozorování
  - v algoritmu typicky hledáme maximum z několika hodnot, které jsou minimy (nebo naopak)
  - v určitém vrcholu máme seznam doposud určených minim z jednotlivých větví (z nich je nějaké maximální)
  - snažíme se určit další minimum, na základě jedné z podvětví máme nějaké prozatímní minimum (museli bychom projít další podvětve pod daným vrcholem, abychom dostali výsledné minimum)
  - pokud je tohle prozatímní minimum menší než prozatímní maximum (ve vyšší úrovni), tak už ty další větve nemusíme procházet, protože výsledné minimum nemůže být větší než prozatímní minimum
- alfa-beta prořezávání nemá vliv na výsledek algoritmu
- záleží na pořadí, ve kterém tahy (větve) procházíme
- minimax se obvykle používá rekurzivně, meze určující prořezávání (pro jednoho hráče je to maximum, pro druhého minimum) se do funkce předávají jako parametry alfa a beta

Hry a teorie her

základy teorie her (vězňovo dilema, Nashovo ekvilibrium)

jednou z úloh teorie her je volba vhodné strategie – tedy návodu, jak hru hrát
- uvažujeme hry v normálním tvaru: hru tvoří hráči, jejich akce a užitkové funkce
- hráči táhnou zároveň, každý provede jedinou akci
- strategie může být čistá (přímo konkrétní akce) nebo smíšená (pravděpodobnostní rozdělení přes akce)
díváme se na optimalitu strategie nebo strategického profilu (množiny strategií všech hráčů) z různých úhlů pohledu
- strategie $s_1$ $s_{1}$ dominuje strategii $s_2$ $s_{2}$ , pokud při volbě $s_1$ $s_{1}$ získá hráč větší užitek než při volbě $s_2$ $s_{2}$ nehledě na strategie ostatních hráčů
  - strategie je dominantní, pokud dominuje všechny ostatní strategie
- Nashovo ekvilibrium je takový strategický profil, že by žádný hráč neměnil svou strategii, kdyby znal strategie ostatních
- strategický profil $s$ $s$ Pareto dominuje profil $s'$ $s^{'}$ , pokud si změnou z $s'$ $s^{'}$ na $s$ $s$ žádný hráč nepohorší, ale aspoň jeden hráč si polepší
  - strategický profil je Pareto optimální, pokud neexistuje profil, který by ho Pareto dominoval
- další zajímavým typem ekvilibria je korelované ekvilibrium
vězňovo dilema
- dva hráči (vězni)
- vězeň může vypovídat (testify/defect) nebo odmítnout vypovídat (refuse/cooperate)
  - oba vypovídají → oba ztrácejí málo (užitek -5)
  - jeden vypovídá, druhý ne → jeden neztratí nic (užitek 0), druhý hodně ztratí (užitek -10)
  - oba odmítnou → oba ztrácejí velmi málo (užitek -1)
- vypovídat je čistá dominantní strategie
  - ale když vypovídají oba hráči, tak 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

Hry a teorie her

mechanism design (typy aukcí)

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_\text{min}$ , pokud je to nějaký zájemce ochotný zaplatit, tak se ptám na $b_\text{min}+d$
- strategie: přihazuju, dokud cena není vyšší než moje hodnota
  - dominantní strategie
holandská aukce
- začíná se vyšší cenou, snižuje se, dokud ji někdo nepřijme
obálková aukce
- největší nabídka vítězí
- neexistuje dominantní strategie
  - pokud věříš, že maximum ostatních 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, kdo nabídne nejvyšší cenu, platí druhou nejvyšší nabídnutou cenu
- dominantní strategie je tam dát svoji hodnotu
VCG mechanismus
- lze použít při obecnějších (víceparametrických) aukcích

Strojové učení

základní druhy učení (s učitelem, bez učitele, zpětnovazební)

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 podle toho, jak se chová v prostředí
učení s učitelem (supervised learning) – agent se učí funkci, která mapuje vstupy na výstupy

Strojové učení

rozhodovací stromy (definice, konstrukce)

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
  - k dělení se používá entropie
- každý list určuje hodnotu, kterou klasifikační funkce vrátí

Strojové učení

regrese, SVM (základní principy)

při regresi přiřazujeme položce $x$ $x$ vhodnou funkční hodnotu $y$ $y$
- je to jedna z úloh strojového učení s učitelem
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)

Strojové učení

Bayesovské učení, EM algoritmus

bayesovské učení
- máme několik hypotéz
- na základě pozorování upravujeme jejich pravděpodobnost
- maximálně věrohodná hypotéza
  - z množiny hypotéz je to ta, která přiřazuje naměřeným datům největší pravděpodobnost
  - $\mathrm{argmax}_h\,p(\mathrm{data}\mid h)$ nebo také $\mathrm{argmax}_h\,p_h(\mathrm{data})$
  - pokud je hypotéza parametrizovaná (hledáme parametr), tak můžeme hledat hodnotu parametru, pro níž je derivace logaritmu pravděpodobnosti nulová
    - tomu se říká maximum-likelihood parameter learning
- z $p(\mathrm{data}\mid h)$ $p (data ∣ h)$ můžeme získat $p(h\mid\mathrm{data})=\frac{p(\mathrm{data}\mid h)p(h)}{\sum_{h'} p(\mathrm{data}\mid h')p(h')}$ $p (h ∣ data) = \frac{p ( data ∣ h ) p ( h )}{\sum _{h^{'}} p ( data ∣ h ^{'} ) p ( h ^{'} )}$
  - pokud mají všechny hypotézy stejné apriorní pravděpodobnosti, stačí vzít $p(\mathrm{data}\mid h)$ a normalizovat je, jelikož $\frac{p(h)}{\sum_{h'} p(\mathrm{data}\mid h')p(h')}$ bude konstantní
- bayesovsky optimální predikce pravděpodobnosti pro vstupní data a konkrétní predikci $z$ $z$
  - $p(z\mid\mathrm{data})=\sum_h p(z\mid h)\cdot p(h\mid\mathrm{data})$
algoritmus expectation-maximization (EM)
- používá se k maximum-likelihood odhadu, pokud se nedá jednoduše spočítat
- předstíráme, že známe parametry modelu (na začátku je určíme náhodně)
- iterujeme dva kroky (dokud to nezkonverguje)
  - dopočteme střední hodnoty skrytých proměnných (E-step, expectation)
  - upravíme parametry, abychom maximalizovali likelihood modelu (M-step, maximization)
- příklad
  - chceme odhadnout průměrnou výšku mužů a žen
  - máme data o naměřených výškách, ale chybí nám údaje o pohlaví (zda je to výška muže nebo ženy)
    - třídy označíme jako 0 (muži), 1 (ženy)
  - začneme tak, že oba parametry (průměrná výška mužů $\mu_0$ , průměrná výška žen $\mu_1$ ) inicializujeme náhodně
  - v E-kroku spočítáme střední hodnoty skrytých proměnných
    - pohlaví je skrytá proměnná (pro každou naměřenou výšku)
    - střední hodnota bude odpovídat pravděpodobnosti, že konkrétní výška patří ženě
  - v M-kroku upravíme hodnoty $\mu_0,\mu_1$ $μ_{0}, μ_{1}$ , abychom maximalizovali likelihood modelu
    - tedy spočítáme vážený průměr výšek
    - váhy odpovídají pravděpodobnosti, že výška patří muži (u $\mu_0$ ) / ženě (u $\mu_1$ )
  - poznámka: může se jednoduše stát, že nám parametry $\mu_0,\mu_1$ vyjdou naopak (EM je metoda učení bez učitele, hledá vzory v datech, nezajišťuje jejich intepretaci)

Strojové učení

pasivní zpětnovazební učení (definice, metody ADP a TD)

uvažujeme agenta, který se účastní MDP (markovského rozhodovacího procesu)
pasivní učení – známe strategii $\pi$ (je pevně daná) a učíme se, jak je dobrá (učíme se utility funkci)
agent nezná přechodový model ani reward function
přímý odhad utility
- máme trace (běh) mezi stavy, z toho počítáme utility function
- odhadujeme užitky jednotlivých stavů
  - užitek stavu = reward-to-go (tedy odměna tohoto a všech budoucích stavů)
  - odměny z budoucích stavů bychom mohli zohleďnovat s discount factorem $\gamma$ (viz výše)
- užitky pro jednotlivé stavy prostě průměrujeme
- v podstatě učení s učitelem – na vstupu je stav, na výstupu užitek stavu (neboli reward-to-go)
- nevýhoda
  - 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
adaptivní dynamické programování (ADP)
- agent se učí přechodový model a odměny
- přechodový model odhaduje přímo z pozorovaných přechodů
- utilitu počítá z Bellmanových rovnic třeba pomocí value iteration
  - využíváme toho, že užitky nejsou nezávislé
- ADP zajišťuje, že jsou odhady užitků konzistentní
temporal-difference (TD) learning
- upravuje stav, aby odpovídal aktuálně pozorovanému následníkovi
- když dojde k přechodu ze stavu $s$ $s$ do stavu $s'$ $s^{'}$ , tak na $U^\pi(s)$ $U^{π} (s)$ použijeme update: $U^\pi(s)\leftarrow U^\pi(s)+\alpha\cdot (R(s)+\gamma\cdot U^\pi(s')-U^\pi(s))$ $U^{π} (s) \leftarrow U^{π} (s) + α \cdot (R (s) + γ \cdot U^{π} (s^{'}) - U^{π} (s))$
  - $\alpha$ je learning rate
- vlastnosti
  - nepotřebuju přechodový model (je to model-free metoda)
  - konverguje to pomaleji než ADP

Strojové učení

aktivní zpětnovazební učení (definice, explorace vs. exploitace, Q-učení, SARSA)

uvažujeme agenta, který se účastní MDP (markovského rozhodovacího procesu)
aktivní učení – agent se učí strategii (policy; jak se rozhodovat) a taky utility funkci
mohli bychom použít ADP, tím vznikne hladový agent, který opakuje zažité vzory (nezkouší nové věci)
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
- první možná exploration policy: agent si zvolí náhodnou akci s pravděpodobností $\frac1t$ $\frac{1}{t}$ (kde $t$ $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 ještě nevyzkoušel
- 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')$ $Q (s, a) = R (s) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) \cdot max_{a^{'}} Q (s^{'}, a^{'})$
    - tohle vyžaduje, aby se model naučil i $P(s'\mid s,a)$
  - Q-learning ale 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))$ $Q (s, a) \leftarrow Q (s, a) + α \cdot (R (s) + γ \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-learningu
  - $Q(s,a)\leftarrow Q(s,a)+\alpha\cdot (R(s)+\gamma\cdot Q(s',a')-Q(s,a))$ $Q (s, a) \leftarrow Q (s, a) + α \cdot (R (s) + γ \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$ $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
  - SARSA je on-policy – jeho strategie se upravuje přímo za běhu algoritmu
  - Q-learning je off-policy – algoritmus se učí optimální strategii, ale během učení se může používat úplně jiná strategie
při aktivním učení je výhodnější učit se q-hodnoty než užitkovou funkci
- abychom našli nejvýhodnější akci v daném stavu pomocí utility, museli bychom při výpočtu použít pravděpodobnost, že danou akcí přejdeme do určitého stavu
- q-hodnota nám dá přímo řekne, jak je užitečné provést danou akci – k volbě nejlepší akce nepotřebujeme přechodový model