# Ú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