Úvod do AI – cvičení

A*

• u Dijkstra v nekonečném grafu použijeme hashovací tabulku
• v A* heuristice nevybíráme vrcholy u podle vzdálenosti od startu, ale přičteme k ní heuristiku vzdálenosti od cíle
  • v domácím úkolu to vrací heuristiku nula (tzn. je to Dijkstra)
  • chceme, aby byla heuristika nezáporná
  • heuristika by neměla přestřelovat skutečnou vzdálenost
    • tzn. měla by být přípustná
    • pokud přestřelí, může se stát, že nalezená cesta nebude nejkratší
  • v reálném světě je vhodná heuristika vzdálenost vzdušnou čarou
• heuristika
  • přípustnost $0\leq h(u)\leq c^*(u)$
  • monotonie $0\leq h(u)\leq h(v)+c(u,v)$
• příklady metrik, jejich vlastnosti pro silniční síť
  • Euklidovská – je přípustná, je i monotónní
    • $h(u,t)\leq h(u,v)+h(v,t)\leq c(u,v)+h(v,t)$
      • z trojúhelníkové nerovnosti a přípustnosti
      • přičemž $h(x,t)=h(x)$
  • Manhattanská – přestřeluje (kdyby cesta vedla diagonálně), takže není přípustná, tudíž není ani monotónní
  • maximová (Chebyshevova) – je přípustná (maximum je menší rovno Euklidovi)
• k důkazu monotonie metriky potřebujeme trojúhelníkovou nerovnost dané metriky a její přípustnost
• monotonie implikuje přípustnost
• existují nemonotónní přípustné heuristiky
• monotonii potřebujeme, abychom se při prohledávání posouvali ve směru cíle
• Sokoban
  • nepříliš dobrá (ale monotónní) heuristika – pro každou krabici vzdálenost od nejbližšího cíle, přes to součet
    • monotónní je, protože v každém kroku se sníží nejvýš o jedna
  • chtěli bychom najít přiřazení krabic, které má nejmenší celkovou cenu
    • hledáme minimální vážené perfektní párování – to jde v lineárním čase
  • chceme řešit vzdálenost panáčka, takže do heuristiky započteme vzdálenost panáčka od nejbližší krabice minus jedna
  • když je krabice v rohu, tak se nemůžeme dostat nikam dál
    • takže je to nepřípustný stav
    • můžeme algoritmu o tom stavu vůbec neříkat
    • můžeme nastavit heuristiku na „nekonečno“
• vlastnosti A*
  • $f(u)=h(u)+g(u)$, kde $h$ je heuristika, $g$ je vzdálenost ze startu do $u$
  • uvažujme monotónní heuristiku
  • hodnoty $f(u)$ jsou neklesající na všech nejkratších cestách ze startu
    • $h(u)+g(u)\leq h(v)+g(v)$
    • $h(u)\leq h(v)+g(v)-g(u)$
    • pro $u,v$ na nejkratší cestě
      • $h(u)\leq h(v)+c(u,v)$
  • A* prozkoumává stavy v pořadí, ve kterém hodnoty $f(u)$ neklesají
• kombinování heuristik
  • afinní kombinace $\alpha h_1+(1-\alpha)h_2$, kde $\alpha\in[0,1]$
  • maximová kombinace $\max\set{h_1,h_2}$
  • přípustnost je jednoduché ukázat
  • jsou-li heuristiky monotónní, je monotónní jejich kombinace?
    • afinní
      • máme
        • $h_1(u)\leq h_1(v)+c(u,v)$
        • $h_2(u)\leq h_2(v)+c(u,v)$
      • chceme $\alpha h_1(u)+(1-\alpha)h_2(u)\leq c(u,v)+\alpha h_1(v)+(1-\alpha)h_2(v)$
      • stačí přenásobit ty dvě rovnosti $\alpha$ a $(1-\alpha)$ a sečíst
    • maximová
      • $\max\set{h_1(u),h_2(u)}$ se BÚNO rovná $h_1(u)\leq c(u,v)+h_1(u)$
      • $\leq c(u,v)+\max\set{h_1(v),h_2(v)}$
  • maximum je vždycky větší (blíž reálné hodnotě) než afinní
  • typicky nechceme strávit hodně času výpočtem heuristiky
  • dává smysl vymyslet několik heuristik a pak použít jejich maximum
  • k domácímu úkolu
    • je fajn se podívat do zdrojáků
    • kratší řešení jsou typicky lepší

CSP

• NP-úplný problém
• na vstupu
  • proměnné
  • domény (pro každou proměnnou jedna)
  • podmínky
• typické podmínky
  • nerovnost
  • all_different(…)
  • logické spojky
  • aritmetika
• dva hlavní problémy
  • solving
    • algoritmy: backtracking, forward check, look ahead
    • backtracking
      • zkusím ohodnotit proměnnou
      • zkontroluju constraints
      • když constraints jsou splněny, ohodnotím další proměnnou
        • jinak zkusím jiné ohodnocení
        • když žádné ohodnocení nefunguje, vrátím fail
    • forward check
      • při backtrackingu začínám v proměnné A
      • přiřadím jí hodnotu, ostatní prvky z domény vyškrtnu
      • přejdu do proměnné B
      • podívám se na všechny hrany (constraints), které vedou z B do již přiřazených proměnných (?)
        • proškrtám prvky v doméně B, které constraints nemůžou splnit
    • look ahead
      • jako forward check
      • pokud zmenším doménu, zkontroluju hrany, které do ní vedou (?)
  • modelování
• jak najít chromatické číslo?
  • binární vyhledávání?
  • pro náš úkol je lepší po jednom zvyšovat $k$ (počet barev)
  • začít u hodnoty o jedno vyšší než nejvyšší stupeň vrcholu
• tvorba SAT klauzulí
  • aspoň jeden … disjunkce
  • nejvýš jeden … konjunkce přes disjunkce všech dvojic negací
  • nejvýš $k$ … konjunkce disjunkcí negací všech $k+1$-tic
  • alespoň $k$ … převedeme na nejvýše $n-k$ negací
• jakmile máme k CSP úloze k dispozici testy, je jasné, co máme dát do constraints

Automatické plánování

• v domácím úkolů nepoužívat typování objektů – „typovat“ klasicky unárními predikáty
• v SISu jsou nahrávky přednášek
• PDDL robot s chapadly
  • neexistenční kvantifikátor nemůžeme použít, tak tam dáme pomocný predikát free (chapadlo je prázdné)
  • při move nechceme přesouvat všechny věci, které robot drží – místo toho je zrušíme z místnosti a dáme mu je do ruky
  • predikáty definujeme tak, aby se úloha zapisovala co nejjednodušeji
• u neorientovaného grafu je potřeba vyjmenovat oba směry hran
• PDDL v základní verzi neumí negace předpokladů
• hanojské věže
  • při přesunu potřebujeme znát disk nahoře na cílové tyči – přidáme si další argument
  • typové predikáty nepotřebujeme, protože relaci „menší“ definujeme jenom pro disky a stůl (a nic není větší než stůl, takže ho nemůžeme přesouvat)
• v domácím úkolu je potřeba akce nazvat správně a mít správné pořadí argumentů kvůli testu

Pravděpodobnost

• výsledek akce nemusí být deterministický, nemáme kompletní informaci o stavu apod.
• v bayesovské síti … $P(X_1,\dots,X_n)=P(X_1|\text{parents}(X_1))\cdot\ldots\cdot P(X_n|\text{parents}(X_n))$
  • kde parents jsou přímí předci vrcholu (vrcholy, z nichž do něj vedou šipky)
• eliminace proměnných
• minesweeper – korektní postup
  • rozdělíme na komponenty souvislosti podle závislosti pravděpodobností
  • pak už to můžu dát solveru
  • dvě miny, jedna nemina
    • $p^2(1-p)$
  • jedna mina, dvě neminy
    • $(1-p)^2p$
• lokalizace robota
  • $M_t$ nemá informace o tom, co robot viděl dřív
  • našim cílem je časově oddělené informace $M_t$ spojit, abychom zjistili, kde robot může být
• deterministická varianta – máme přesnou informaci o senzorech a pohybu robota
  • filtering
    • zjevně $A_1=M_1$
    • $A_t=t(A_{t-1})\cap M_t$
  • predikce
    • $B_t=A_t$
    • $B_k=t(B_{k-1})$
  • smoothing/vyhlazování
    • $C_t=A_t$
    • $C_k=t^{-1}(C_{k+1})\cup A_k$
• pravděpodobnostní varianta
  • velká písmena označují náhodné proměnné, malá jejich konkrétní hodnoty
  • $P(X_{t+1}=v|e_{1:t})=\sum_{u}P(X_t=u|e_{1:t})\cdot P(X_{t+1}=v|X_t=u)$
    • to, kam se robot dostane, nezáleží na tom, co dříve naměřil, proto lze použít tento vzorec (místo podmíněné marginalizace)
• lokalizace v domácím úkolu
  • filtering
  • z přednášky $P(X_{t+1}|e_{1:t+1})=\alpha P(e_{t+1}|X_{t+1})\sum_{x_t}P(X_{t+1}|x_t)P(x_t|e_{1:t})$
  • z cvičení $P(X_{t+1}|e_{1:t+1})=P(e_{t+1}|X_{t+1})\cdot \frac{P(X_{t+1}|e_{1:t})}{P(e_{t+1}|e_{1:t})}$
    • $P(e_{t+1}|e_{1:t})=P(e_{t+1})=0.5$ (asi?)
    • $P(X_{t+1}|e_{1:t})=\sum_{x_t} P(X_{t+1}|x_t)P(x_t|e_{1:t})$
    • zjevně jako předchozí políčko přichází v úvahu právě jedno
      • $P(X_{t+1}|e_{1:t})=P(X_t|e_{1:t})$
  • tudíž snad $P(X_{t+1}|e_{1:t+1})=P(e_{t+1}|X_{t+1})\cdot \frac{P(X_{t}|e_{1:t})}{0.5}$
• jiný přístup k plánování
  • dostaneme odměnu $R(s)$ za navštívení stavu $s$
  • stejnou odměnu dostaneme i při opakovaném navštívení
  • máme funkci popisující akumulaci odměn
  • Bellmanova rovnice $U(s)=R(s)+\gamma\sum_{s'} P(s'|s,a)U(s')$
    • $R(s)$ … odměna konkrétního jevu
    • kam se přesuneme – to je náhodný jev
      • takže marginalizujeme
    • pokud neznáme správnou akci, tak vybereme tu, pro kterou bude suma maximální
      • $U(s)=R(s)+\max_a\sum_{s'} P(s'|s,a)U(s')$
    • $\gamma$ … „faktor zapomnění“
      • je tam proto, aby existoval algoritmus, který najde řešení
      • pro gamma rovno jedné by to nemuselo konvergovat
  • zjednodušená varianta robota z přednášky
    • $U(5,5)=10$
    • $U(5,4)=-0.1+1\cdot10=9.9$
    • $U(4,3)=-0.1+0.8\cdot 9.8+0.2\cdot1$
    • $U(3,4)=-0.1+0.8\cdot6.9+0.2\cdot 1$
      • kde $6.9$ je $U(3,5)$
    • obecně budeme počítat maximum z akcí
  • pokud tam budou cykly
    • budeme iterovat
    • začneme s $\forall s:U(s)=0$
    • jak dlouho iterovat?
      • dokud maximální delta hodnot není menší než $\epsilon(1-\gamma)/\gamma$
  • z akcí můžeme spočítat užitek pomocí soustavy lineárních rovnic
  • takže jsou dva přístupy – value iteration a policy iteration
• v domácím úkol
  • máme torus → pozor na modulo
  • podívat se do zdrojáku
  • soustředit se na pomocné testy

Teorie her

• hra Nim s Fibonacciho čísly
  • vyhráváme tehdy, když protihráče umíme dostat do prohrávajícího stavu
  • stačí nám jednoduchá dynamika, zpětné prohledávání
  • může to být náročné na paměť
  • pokud má každý hráč jiná pravidla, stačí nám k tomu dvě pole místo jednoho
• dopředné prohledávání
  • je paměťově úspornější
  • některé stavy prohledáváme vícekrát
  • u netriviální her hodně časově složité
  • pokud má každý hráč jiná pravidla, použijeme dvě rekurzivní funkce místo jedné
  • máme volnost v tom, v jakém pořadí stavy procházíme
    • u Nimu funguje dobře procházet čísla od největšího
  • když chceme prokázat, že je stav prohrávající, musíme projít všechny jeho podstavy
• úkol
  • první tah nemusíme řešit, ten má speciální pravidla
  • musí to vracet správné výsledky
  • musí to fungovat obecně

Strojové učení

• nevýhody neuronových sítí
  • vyžadují vysoký výpočetní výkon
  • nejsme schopni vysvětlit, proč to vrací konkrétní výsledek
  • nejsme schopni zaručit (dokázat), že bude neuronka v konkrétních situacích vracet správné výsledky
• klasifikace
  • true positive, true negative, false positive, false negative
  • měření kvality binární klasifikace
    • accuracy … správnost odpovědí ze všech testů
      • $TP+TN\over TP+TN+FP+FN$
    • precision … správnost odpovědí ze všech pozitivních testů
      • $TP\over TP+FP$
    • recall … správnost odpovědí ze všecch nemocných jedinců
      • $TP\over TP+FN$
  • proč nestačí jedno měřítko kvality
    • mějme nemoc, kterou má 1 % obyvatel
    • test, který je vždy negativní
      • accuracy 99 %
      • precision není definována
      • recall 0
    • test, který z nemocných pozná 1 %
      • accuracy cca 99 %
      • precision 100 %
      • recall 1 %
    • test, který je vždy pozitivní
      • accuracy 1 %
      • precision 1 %
      • recall 100 %
  • Simpsonův paradox
• neuronové sítě
  • lineární klasifikace
    • hledáme nadrovinu rozdělující A a B
    • začneme s nějakou nadrovinou, tu postupně posouváme
  • XOR klasifikujeme pomocí dvou nadrovin
    • tím nám přibudou dimenze/souřadnice (podle toho, jestli je bod vlevo nebo vpravo od nadroviny)
      • pak už můžeme najít nadrovinu
      • každá nadrovina nám vlastně reprezentujeme jeden neuron, jejich výstupy spojíme ve třetím neuronu
    • support vector machines
  • aktivační funkce
    • step (hard treshold) – je těžké ji naučit, protože nemá derivaci v jednom bodě a všude jinde jsou derivace nulové
    • logistická funkce
    • spousta dalších
  • cílem je najít lokální minimum funkce
    • použijeme gradient
  • algoritmus zpětné propagace
    • v prezentaci chyba – inicializace vah má být před repeatem