Úvod do umělé inteligence

• Aristoteles – sylogismy, formalizace logiky
  • sylogismus – pokud dostane správné předpoklady, vrátí správné důsledky
• Descartes, Boole

• počítání s nejistotou a neúplností – pravděpodobnost
• Cardamo, Bayes

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

• automaty
  • stroj Antikythera – starověké Řecko, pro předvídání pohybů hvězd
• Jacquard – program pro tkalcovský stroj, pomocí děrných štítků
• Babbage – Difference Engine, Analytical Engine
• Zuse, Turing

• Ktesibios – regulátor vodního toku
• Watt – regulátor parního stroje
• Wiener – kybernetika (autonomní stroje)
• teorie řízení

• 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í
• Craik – zavedl pojem znalostní (knowledge-based) agent
  • postupný převod vjemu na vnější akci

• 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

• Gartner Hype Cycle
  • 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šechno vidím / něco nevidím (fully observable / partially observable)
• další stav prostředí je/není předem daný (deterministic / stochartic)
• …

• 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

• atomic – stav je blackbox
• factored – stav je vektor
• structured – stav je sada objektů, ty jsou propojeny

• akce jsou reprezentovány pomocí přechodové funkce
• cílem je najít posloupnost akcí, kterými se dostaneme z výchozího do cílového stavu
  • cílových stavů může být víc
• očekáváme, že prostředí je plně pozorovatelné, diskrétní, statické a deterministické

ne všechny stavy jsou dosažitelné – zachovává se parita permutace

• 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

• výchozí stav
• přechodový model (state, action) -> state
• goal test (funkce, která odpoví true/false podle toho, zda je daný stav cílový)

• algoritmy na prohledávání grafů
• graph-search si pamatuje, které vrcholy už expandoval (takže ho cyklus nerozháže)
• i tree-search lze použít k prohledávání grafů s cykly, ale může se chovat divně

• BFS (fronta)
  • ú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)
  • úplný pro graph-search
  • neúplný pro tree-search
    • pokud algoritmus pustíme na grafu, který není strom
  • suboptimální
  • časová složitost $O(b^m)$, kde $m$ je maximální hloubka libovolného vrcholu
  • prostorová složitost $O(bm)$

• 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

• pro vrchol máme ohodnocovací funkci $f(n)$
• $f(n)$ použijeme v Dijkstrově algoritmu místo $g(n)$
• 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

• 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
  • mějme vrchol $n$ a jeho souseda $n'$
  • $c(n,a,n')$ je cena přechodu z $n$ do $n'$
  • heuristika je monotónní, když $h(n)\leq c(n,a,n')+h(n')$
• tvrzení: monotónní heuristika je přípustná
• tvrzení: pro monotónní heuristiku jsou hodnoty $f(n)$ neklesající po libovolné cestě
• tvrzení: pokud je $h(n)$ přípustná, pak je A* u tree search optimální
• tvrzení: pokud je $h(n)$ přípustná, pak je A* u graph search optimální

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$

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

• možný model
  • stavy – (částečná) rozmístění královen na šachovnici
  • úvodní stav – prázdná šachovnice
  • cíl – neznámý stav
  • 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
  • …
• 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
  • forward checking
  • stav pro nás není černá skříňka
  • jak to zobecnit?

• královny i sudoku jsou constraint satisfaction problem (CSP)
• relace = podmnožina kartézského součinu

• 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
  • constraint arity = počet proměnných, které podmínka omezuje
• chceme přípustné řešení (feasible solution)

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

• arc = orientovaná hrana
• edge = neorientovaná 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á podmínka odpovídá orientované hraně v síti podmínek
• 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 $V_i,V_j$
• CSP je hranově konzistentní $\equiv$ každá hrana je hranově konzistentní (v obou směrech)
• algoritmus AC-3
  • jakmile odstraním prvky domény, musím opakovat kontrolu v sousedech (ale stačí kontrolovat jen jednu ze dvou hran)
  • složitost $O(ed^3)$, kde $e$ je počet podmínek, $d$ je velikost domény
  • optimální algoritmus má složitost $O(ed^2)$

• 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 (strom se větví exponenciálně)
• hranová konzistence je typ lokální konzistence
  • takže 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

• např. u královen jsou jednotlivá políčka proměnné, které nabývají hodnot 0 nebo 1 podle toho, zda tam je královna
• podmínky vyjádříme logickými formulemi – lze je zapsat v CNF
• k nalezení splňujícího ohodnocení se nejčastěji používá algoritmus DPLL
  • 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
• další optimalizace SATu
  • 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
  • jak hledat jednotkové klauzule – clever indexing (?)
    • 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 nebo se jich na něco ptát
• agent používá inferenci – logicky odvozuje
• agent v jeskyni – díry a Wumpus; má šíp
  • 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
  • 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$
      • to platí, právě když $KB\land\neg\alpha$ je nesplnitelné
    • lze použít rezoluci
    • Hornova klauzule
      • 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
      • backward chaining … goal-driven reasoning
        • něco mě zajímá – pokouším se to odvodit
        • tohle se používá v Prologu

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

• částečná pozorovatelnost – nelze snadno zjistit současný stav
• nedeterminismus – není jisté, jak akce dopadne

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

• 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, Earthquakce
  • 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|e)=\alpha P(X,e)=\alpha\sum_y P(X,e,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))$
• 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 s faktory mezi sebou můžeme násobit

• transition model
  • určuje pravděpodobnostní rozložení přes proměnné posledního stavu, když známe předchozí hodnoty
  • zjednodušující předpoklady
    • další stav závisí jen na předchozím stavu
    • všechny přechodové tabulky jsou identické přes všechna $t$
• sensor (observation) model
  • popisuje, jak se pozorované proměnné mění
  • …

• filtrování
• predikce
• vyhlazování
• nejpravděpodobnější vysvětlení

• stavy světa jsou neznámé → proto jsou proměnné skryté
• mezi stavy existují pravděpodobnostní přechody
  • předpoklad: nový stav (jeho pravděpodobnost) závisí jen na tom předchozím
• máme pozorované proměnné
  • předpoklad: pozorování záleží jenom na současném stavu, ne na těch předchozích
• základní inferenční úlohy
  • filtering
  • prediction
  • smoothing
  • most likely explanation

• máme matici stavů a měření
• algoritmy lze formulovat pomocí maticových operací

• sekvenční rozhodovací problém
• pro plně pozorovatelné stochastické prostředí
• máme Markovovův přechodový model a reward
• řešením MDP je policy (strategie) – funkce doporučující akci pro každý stav
• 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í)
• 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 uižtkem a užitkem strategie
    • můžeme iterativně zlepšovat policy, dokud se nepřestane zlepšovat
    • z rovnic nám zmizí maximum → máme lineární rovnice
    • → policy iteration
    • gaussovka je $O(n^3)$

• místo reálný 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 a dostaneme dynamickou rozhodovací síť
• generujeme si stromeček
  • „co kdyby pozorování bylo takové?“ „co kdyby bylo jiné?“
• používá se algoritmus ExpectedMiniMax

• 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, …)
• algoritmus minimax
• 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 bude brát vážený počet figurek

• např. házíme kostkou
• algoritmus expected minimax
• mezi uzly s tahy hráčů přidám vrstvy s pravděpodobnostmi
• při výpočtu min nebo max je vážím 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

• kámen, nůžky, papír
• dvouprstá Morra
• vězňovo dilema
  • dominantní čistá strategie – testify (defect)
  • ale vyhrála policie – lepší by bylo, kdyby oba odmítli vypovídat (= refuse/cooperate)
  • našli jsme Nashovo ekvilibrium – nikdo neprofituje ze změny strategie, pokud druhý hráč zůstane u stejné strategie
  • definice dominance a čistoty strategie
• dvouprstá Morra nemá čistou strategii
• jak najít optimální smíšenou strategii?
  • technika maximin
• opakované hry
• strategie pro opakované vězňovo dilema
  • pokud víme, která hra je poslední, vede to na podobnou situaci jako u jedné hry
  • tit-for-tat

• k návrhu agentů
• k návrhu mechanismů (pravidel)
  • inverzní teorie her
  • aukce
    • anglická aukce
      • strategie: přihazuju, dokud cena není vyšší než moje hodnota
      • 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
    • obálková aukce
      • největší nabídka vítězí
      • neexistuje jednoduchá dominantní strategie
    • 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í
  • „tragedy of commons“
  • mechanismus Vickeray-Clarke-Groves
    • zdanění společného zboží
    • problém – je nezbytné mít centrální autoritu

• 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

• scénáře, na které programátor nemyslel
• změny v prostředí
• někdy není jasné, jak agenta naprogramovat

• učení bez učitele (unsupervised learning) – agent se učí vzory ve vstupu
• 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 z prostoru hypotéz
  • princip Occamovy břitvy
  • typy úloh – klasifikace (u nečíselných funkcí) nebo regrese (u číselných funkcí)
  • nekonzistence s příkladem – příklad neodpovídá naučené funkci

• přijímá vektor hodnot atributů, vrací výslednou hodnotu
• na základě tabulky příkladů se dá postavit strom, vnitřní uzly jsou jednotlivé atributy
• dá se zjistit odůvodnění konkrétního rozhodnutí
• strom se dá postavit hladovou metodou rozděl a panuj
• zakončení větve
  • když jsou ve větvi výsledky jednoho druhu
  • 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
• snažím se vždy 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é)

• agent má inferenční mechanismus
• přihodíme mu axiom, aby toho mohl odvozovat víc
• z větví v rozhodovacím stromu můžeme udělat logické formule
• 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
• 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í)
    • dolní mez – specifické formule (specifičtější jsou nekonzistentní)
• když je šum v datech, může dojít ke kolapsu version space

• vzorečky viz prezentace
• můžeme ji použít pro klasifikaci – nakreslíme přímku, která bude oddělovat vstupy klasifikované jedním a druhým způsobem
• perceptronové pravidlo
• 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

• znám chybu u výstupních neuronů
• neznám 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
    • lze zvolit nejčastější $y$
    • lze použít regresi nebo průměr
• vzdálenosti se typicky měří pomocí Minkowského metriky

• stojí na lineární regresi
• pokud lze třídy oddělit nadrovinou, zvolí takovou, která je nejdál od všech dat (příkladů)
• pokud nejde použít nadrovinu, provede mapování do vícedimenzionálního prostoru, 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

• bayesovské učení
  • bereme v úvahu všechny hypotézy
  • vracíme vážený průměr všech hypotéz
• další přístup – bereme v úvahu nejpravděpodobnější hypotézu

• chceme se naučit hodnoty, které vyplníme do CPD tabulek
• hledáme hypotézu, která nejlépe vysvětluje příklady
• derivuju postupně podle každého hledaného parametru a derivaci položím rovnou nule
• co když mám skryté uzly v síti
  • 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
    • upravíme parametry, abychom maximalizovali likelihood modelu
    • iterujeme (dokud to nezačne konvergovat)

• nemusíme agentovi říkat $y$
• agent dostává pozitivní nebo negativní zpětnou vazbu (ve formě reward/reinforcement)
• vychází z markovských rozhodovacích procesů
• pasivní učení – známe strategii a učíme se, jak je dobrá (učíme se utility funkci)
• aktivní učení – agent zjišťuje, co má dělat
• pasivní učení
  • agent nezná přechodový model ani reward function
  • přímý odhad utility
    • máme trace (běh) mezi stavy, z toho (postupně) počítáme utility function
    • nevýhody – utilities nejsou nezávislé, ale řídí se Bellmanovými rovnicemi
  • adaptivní dynamické programování (ADP)
    • používá Bellmanovy rovnice
  • temporal-difference learning
    • po každém kroku updatuju jedno číslo
    • nepotřebuju přechodový model
    • konverguje to pomaleji než ADP
• aktivní učení
  • agent neví, co má dělat
  • active adaptive dynamic programming agent
    • používá Bellmanovy rovnice
    • ale nemusí se chovat úplně optimálně – opakuje zažité vzory
    • říká se tomu hladový (greedy) agent
  • je potřeba najít optimum mezi exploration a exploitation
    • k tomu se dá použít temporální diference a Q funkce – říká se tomu Q učení
    • variantou Q učení je SARSA (state-action-reward-state-action)