Úvod do AI – cvičení

• 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

• přípustnost $0\leq h(u)\leq c^*(u)$
• monotonie $0\leq h(u)\leq h(v)+c(u,v)$

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

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

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

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

• proměnné
• domény (pro každou proměnnou jedna)
• podmínky

• nerovnost
• all_different(…)
• logické spojky
• aritmetika

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

• 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

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

• 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

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

kde parents jsou přímí předci vrcholu (vrcholy, z nichž do něj vedou šipky)

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

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

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

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

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

• 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

• máme torus → pozor na modulo
• podívat se do zdrojáku
• soustředit se na pomocné testy

• 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

• 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

• první tah nemusíme řešit, ten má speciální pravidla
• musí to vracet správné výsledky
• musí to fungovat obecně

• 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

• 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

• 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