umělá inteligence – snažíme se, aby stroje zvládly činnosti, které od člověka vyžadují jistou inteligenci
historie ve stručnosti
v počátcích se hlavní důraz kladl na logické a pravděpodobnostní uvažování – symbolic AI
nyní jsme v éře hlubokého učení a neuronových sítí
logika
formalizace racionálního uvažování
Aristoteles – pravidla racionálního přemýšlení
sylogismus – deduktivní argumentační struktura, která nám dává správný výsledek, máme-li správné předpoklady
Sokrates je člověk ∧ lidé jsou smrtelní ⟹ Sokrates je smrtelný
René Descartes – porozumění světu skrze racionální uvažování
George Boole – formální logika
pravděpodobnost
někdy věci nejsou černobílé, máme určitou míru nejistoty
Gerolamo Cardamo – možné výsledky hazardních her
Thomas Bayes – dodatečné změny pravděpodobností na základě nových poznatků
ekonomie
jak správným rozhodováním maximalizovat užitek (zisk)
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
systémy na zpracování informací
stroj Antikythera – starověké Řecko, pro předvídání pohybů hvězd
Joseph Marie Jacquard – program pro tkalcovský stroj, pomocí děrných štítků
Charles Babbage – Difference Engine, Analytical Engine
Konrad Zuse – Z-3, první programovatelný počítač
Alan Turing – Colossus
kybernetika a teorie řízení
stroje se udržují při (správném) chodu
Ktesibios – regulátor vodního toku
James Watt – regulátor parního stroje
Norbert Wiener – kybernetika (autonomní stroje)
teorie řízení – návrh systémů, které postupně maximalizují cílovou funkci
psychologie – jak lidé a zvířata myslí a jednají
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í
Kenneth Craik – zavedl pojem znalostní (knowledge-based) agent
postupný převod vjemu na vnější akci
lingvistika – jak jazyk souvisí s myšlením
Noam Chomsky – formální teorie
porozumění jazyku vyžaduje porozumění obsahu (nestačí rozumět syntaxi)
neurověda – jak mozek zpracovává informace?
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í
Historický vývoj
před zrozením oboru umělé inteligence
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
zrod 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.
zlatá éra, první léto
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í
první zima
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
druhé léto
expertní systémy – zabývají se konkrétními obory lidské činnosti
druhá zima
systémy jsou křehké a drahé na údržbu
lispové počítače byly nahrazeny obecnými počítači (Apple, IBM)
třetí léto
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
co bude dál? může nám to naznačit Gartner Hype Cycle
innovation trigger
peak of inflated expectations
trough of disillusionment
slope of enlightenment
plateau of productivity
AI je o kontrukci racionálních agentů
racionální agent by měl zvolit akci, o které se očekává, že maximalizuje užitek
vševědoucí (omniscient) agent zná výsledek akce – vševědoucnost není reálně možná
záleží na prostředí, v němž agent operuje
všechno vidím / něco nevidím (fully observable / partially observable)
další stav prostředí je/není předem daný (deterministic / stochastic)
epizodické/sekvenční prostředí – „život“ agenta se může dělit na epizody (kde další epizoda nezávisí na akcích, které agent vykonal v předchozí epizodě)
statické/dynamické prostředí – podle toho, zda se mění během toho, co robot uvažuje
diskrétní/spojité prostředí
agentů může být více – můžou soutěžit nebo kooperovat
2. Řešení úloh prohledáváním (A* a spol.)
agent – vnímá prostředí pomocí senzorů, aktuátory mu umožňují jednat
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
jako model-based
kromě aktuální stavu bere v úvahu i cíl a podle toho provede akci
reprezentace stavů
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í problému prohledáváním grafu
problém převedeme na graf
vrcholy = stavy (kořen = výchozí stav)
hrany = akce
algoritmy prohledávání grafu: graph-search a tree-search
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
strategie neinformovaného prohledávání
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(bd+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
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(bm), 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) 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
tedy je to vlastně „konzistence orientovaných hran“
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 (Vi,Vj) je hranově konzistentní ≡ pro každé x∈Di existuje y∈Dj takové, že přiřazení Vi=x a Vj=y splní všechny binární podmínky pro Vi,Vj
může platit, že (Vi,Vj) je hranově konzistentní, ale (Vj,Vi) není
CSP je hranově konzistentní ≡ 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(cd3), kde c je počet podmínek, d je velikost domény
O(d2) … 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(cd2)
jak 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
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, kdežto strom stavů se větví exponenciálně
hranová konzistence je typ lokální konzistence, negarantuje globální konzistenci
silnější konzistence … k-konzistence
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
globální podmínky
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í
v jakém pořadí brát proměnné a hodnoty v backtrackingu
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
constraint programming je deklarativní přístup k řešení problémů
zkonstruujeme model
použijeme univerzální solver
kombinace prohledávání a odvozování přes podmínky
hranová konzistence a globální podmínky jsou nejčastěji používané inferenční techniky
4. Logické uvažování (dopředné a zpětné řetězení, rezoluce, SAT)
často lze u nějakého modelu (třeba CSP) prohodit proměnné a hodnoty → vznikne duální model
hodnoty se stávají proměnnými, proměnné hodnotami
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
používá se tree-search ke zkoušení hodnot proměnných
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
clever indexing – je potřeba chytře udržovat různé množiny, např. množinu jednotkových klauzulí
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
znalostní agenti
mají k dispozici znalostní bázi
můžeme jim poskytovat nové informace (operace tell) nebo se jich na něco ptát (operace ask)
agent používá inferenci – logicky odvozuje
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
příklad
agent v jeskyni
díry a Wumpus
hromada zlata
agent má šíp
dotaz α … 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í
α vyjádřím jako výrokovou formuli
KB vyjádřím jako teorii
zajímá mě, zda KB⊨α
tzv. entailment (KB entails α)
to platí, právě když KB∧¬α je nesplnitelné
lze použít rezoluci
použitím rezolučního pravidla z klauzulí φ∨p a ψ∨¬p dostaneme φ∨ψ
zkoušíme spolu rezolvovat postupně všechny dvojice klauzulí
pokud v průběhu dostaneme prázdnou klauzuli, máme rezoluční důkaz α z KB
pokud se dostaneme do stavu, kdy nelze použít rezoluční pravidlo na žádnou dvojici klauzulí, tak víme, že neplatí KB⊨α
pokud naše znalostní báze obsahuje pouze Hornovy klauzule
Hornova klauzule = disjunkce literálů, z nichž nejvýše jeden je pozitivní
forward chaining … data-driven reasoning
p∧q∧r⟹s
pokud vím, že platí p, pak převedu na q∧r⟹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
tohle se používá v Prologu
opět vlastně používám rezoluční pravidlo
to, co chci zjistit, rezolvuju s libovolnou klauzulí
konkrétní příklad: HaveArrowt+1⟺(HaveArrowt∧¬Shoott)
neexistuje akce, která by HaveArrow mohla nastavit z false na true, takže chybí levá část pravé strany
plánování
hybridní agent pomocí výrokové logiky odvodí stav světa, ale k plánování použije A*
k plánování však můžeme použít přímo logiku
SAT solveru předhodíme formuli: „Lze dosáhnout cíle v přesně t krocích?“
musíme definovat výchozí stav (nastavit hodnoty všem proměnným kromě těch „akčních“), dále pak successor-state axiomy pro všechny možné akce a také požadovaný cílový stav
z nalezeného modelu zjistíme konkrétní plán
zkoušíme pro t do 1 do Tmax (tomu se říká SATPlan)
potřebujeme také zadefinovat podmínky, kdy se akce dají použít
abychom např. nemohli střílet bez šípu
tzv. precondition axioms
Shoott⟹HaveArrowt
chceme-li v jednu chvíli provádět nejvýše jednu akci, použijeme action exclusion axioms: (∀t)(∀i=j)(¬Ait∨¬Ajt)
k plánování můžeme používat prohledávání nebo výrokové odvození
prohledávání vyžaduje dobrou doménově-specifickou heuristiku
odvození výrokovou logikou může být zahlcené, pokud máme 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 … s0
situace po aplikace akce a na situaci s … 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í: at(robot, location, s)
pro stálé relace takový argument není potřeba: connected(loc1, loc2)
podmínky (předpoklady) akcí jsou definovány possibility axiomem
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ů
skryté Markovovy modely
předpokládejme, že stav procesu je popsán jedinou diskrétní náhodnou proměnnou Xt (a máme jednu proměnnou Et odpovídající pozorování)
pak můžeme všechny základní algoritmy implementovat maticově
dynamická bayesovská síť
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
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ší
inference v DBN
můžeme použít existující algoritmy pro inferenci v bayesovských sítích
můžeme zkonstruovat celou bayesovskou síť tak, že přidáme vrstvy od začátku až po současnost – do nich dáme pozorování (měření)
tzv. unrolling
exact inference
můžeme si pamatovat jenom poslední dvě vrstvy
ale prostorová složitost bude exponenciální vzhledem k počtu stavových proměnných
approximate inference
samplujeme skryté proměnné v síti v topologickém pořadí pomocí likelihood weighting
vzorky se generují nezávisle na měření, takže jejich váhy klesají
abychom udrželi přesnost, musíme počet vzorků exponenciálně zvětšovat v závislosti na t
8. Markovské rozhodovací procesy
rozhodování
racionální agent se rozhoduje na základě svých informací o prostředí a svých cílů
potřebujeme měřit kvalitu výsledku
budeme dělat jednoduchá rozhodnutí (v epizodických prostředích) i posloupnosti mnoha rozhodnutí (v sekvenčních prostředích)
užitek (utility)
pro každý stav známe utility function (funkci užitku) … U(s)
očekávaný užitek (expected utility, EU) akce a, máme-li pozorování e
EU(a∣e)=∑sP(Result(a)=s∣a,e)⋅U(s)
maximální očekávaný užitek (maximum expected utility, MEU)
argmaxaEU(a∣e)
princip maximálního očekávaného užitku: racionální agent by si měl zvolit akci, která maximalizuje očekávaný užitek agenta,
teorie užitku
očekávaný užitek náhodné volby (loterie) … ∑ipiui
pi … pravděpodobnost i-té volby
ui … užitek i-té volby
často známe preference agenta spíše než přesné hodnoty utility funkce
A<B … agent preferuje B oproti A
A∼B … agent nerozlišuje mezi A a B (nemá favorita, je indiferentní)
z prefencí se dá dostat utility
U(A)<U(B)⟺A<B
U(A)=U(B)⟺A∼B
alternativní způsob – získáme normalizovanou utility funkci
nejlepšímu možnému stavu Smax přiřadíme U(Smax)=1
nejhorší možné katastrofě Smin přiřadíme U(Smin)=0
pro každý další stav S necháme agenta rozhodnout se mezi standardní loterií a stavem S
standardní loterie … Smax s pravděpodobností p a Smin s pravděpodobností 1−p
upravujeme pravděpodnost p, dokud agent není indiferentní mezi S a standardní loterií
pak U(S):=p
rozhodovací sítě (decision networks, influence diagrams) kombinují bayesovské sítě s dodatečnými typy vrcholů pro akce a utility
vyhodnocení rozhodovací sítě: nastavíme proměnné pozorování (evidence variables) na aktuální stav, pro všechna možná rozhodnutí spočítáme utility, vrátíme akci s největší utilitou
decision-theoretic expert systems
vytvoříme kauzální model – znázorníme příznaky, nemoci, léčbu, nakreslíme hrany
zjednodušíme ho na kvalitativní rozhodovací model – odstraníme proměnné, které se nepoužívají při rozhodování
přiřadíme pravděpodobnosti
přiřadíme užitky
ověříme a vyladíme model – porovnáme s týmem expertů
provedeme citlivostní analýzu – malé změny vedoucí k výrazně odlišným rozhnodnutím typicky indikují problémy
markovovský rozhodovací proces (MDP)
ř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′∣s,a) … pravděpodobnost dosažení stavu s′, když ve stavu s použiju akci a
odměna (reward) R(s) … získá ji agent ve stavu s, je krátkodobá
utility function U([s0,s1,s2,…])=R(s0)+γR(s1)+γ2R(s2)+…
kde γ je discount factor, číslo mezi 0 a 1
utility je „dlouhodobá lokální odměna“
hodnota utility funkce je konečná i pro nekonečnou posloupnost stavů, protože zjevně U([s0,…])≤1−γRmax
řešením MDP je policy (strategie) – funkce doporučující akci pro každý stav
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 ≡ strategie, která vrací největší očekávanou utilitu
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
opravdový užitek stavu je reward (odměna) stavu ve spojení s očekávaným užitkem následného stavu → to vede na Bellmanovu rovnici
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í)
U(s)=R(s)+γmaxa∑s′P(s′∣s,a)⋅U(s′)
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 ϵ, 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 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(n3)
algoritmus skončí, protože policies je jenom konečně mnoho a vždycky hledáme tu lepší
částečně pozorovatelný markovský rozhodovací proces (POMDP)
přibude nám sensor model P(s∣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
9. Hry a teorie her
více agentů
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, …)
nulový součet … zisk jednoho hráče je ekvivalentní ztrátě druhého
algoritmus minimax – předpokládá, že oba hráči hrají optimálně
minimax s α,β 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 pro šachy bude brát vážený počet figurek
někdy ve hrách hraje roli náhoda (tzv. stochastické hry)
např. házíme kostkou
algoritmus expected minimax
mezi vrcholy s tahy hráčů přidám vrstvy s pravděpodobnostmi
hodnota pravděpodobnostního vrcholu odpovídá ∑s∈Spsvs, kde S je množina všech synů vrcholu, ps je pravděpodobnost konkrétního jevu a vs je hodnota jevu (vrcholu s jevem)
vlastně to odpovídá tomu, jako bych při výpočtu min nebo max vrcholy vážil 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
hry na jeden tah
příklady her
kámen, nůžky, papír
dvouprstá Morra
hru tvoří: hráči (agenti), možné akce, payoff function
např. n bodů určuje polynom stupně n−1, ale pokud body leží na přímce, tak nejjednodušší hypotéze je prostě ta přímka
typy úloh
klasifikace – u nečíselných funkcí, data rozdělujeme do množin
regrese – u číselných funkcí
rozhodovací strom
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
každý list určuje hodnotu, kterou klasifikační funkce vrátí
zakončení větve (listy)
když jsou ve větvi výsledky jednoho druhu – není co řešit, zvolím daný druh
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
prostor hypotéz = množina rozhodovacích stromů
hledáme strom, který je konzistentní s příklady a zároveň je co nejmenší
snažím se vždy (hladově) 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é)
entropie náhodné proměnné V s hodnotami vk, kde každá má pravděpodobnost P(vk) se spočítá takto: H(V)=∑kP(vk)⋅log2P(vk)1
pro binární proměnnou je to B(p)=p⋅log2p1+(1−p)log21−p1
kde p je pravděpodobnost jedné z variant
dále použijeme information gain pro daný atribut – tedy očekávanou redukci entropie
Gain(A)=B(p+np)−∑kp+npk+nkB(pk+nkpk)
kde p jsou pozitivní případy, n jsou negativní případy, pk jsou pozitivní případy v k-té podmnožině
z toho levá část vzorce je entropie atributu vůči celé množině, pravá je očekávaná zbývající entropie
poznámky
entropie spravedlivé mince je 1
zjevně B(p+np)=B(p+nn)
logická formulace učení
hypotézy, příklady a klasifikaci budeme reprezentovat logickými formulemi
tzv. logická klasifikace
příklady (trénovací data)
atributy se stanou unárními predikáty
klasifikace se určí literálem s cílovým predikátem
hypotéza bude mít tvar ∀x:Goal(x)⟺Cj(x)
kde Cj je nějaká formule (mohla by popisovat rozhodovací strom)
Cj (na vstupních datech) definuje množinu dat klasifikovaných jako true
prostor hypotéz = množina všech hypotéz
učící algoritmus věří, že jedna hypotéza je správná, takže věří formuli h1∨h2∨⋯∨hn
hypotézy, které nejsou konzistentní s příklady, můžeme vyškrtnout
idea … udržujeme jednu hypotézu a upravujeme ji podle toho, jak přicházejí další příklady, abychom ji udržely konzistentní
pokud je příklad konzistentní, neměníme hypotézu
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
pro každou modifikaci musíme zkontrolovat konzistenci s předchozími příklady
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í)
G-set
na začátku True
pokud je příklad false positive pro Gi → nahradíme ho všemi jeho následnými specializacemi
false negative → vyhodíme Gi
dolní mez – specifické formule (specifičtější jsou nekonzistentní)
S-set
na začátku False
false positive → vyhodíme Si
false negative → nahradíme Si jeho následnými zobecněními
když je šum v datech, může dojít ke kolapsu version space
lineární modely
univariate linear function = přímka
y=w1x+w0
multivariate linear function = nadrovina
y=w0+∑iwixi
hledáme přímku (hypotézu), která bude nejlépe odpovídat datům
hypotézu značíme hw(x)
chybu měříme pomocí square loss function
chyba … ∑j(yj−hw(xj))2
→ lineární regrese
lze řešit dvěma způsoby
analyticky pomocí rovnic
∑j(yj−(w1xj+w0))2=0
derivujeme postupně podle w0,w1
pomocí metody gradient descent
wi←wi−α⋅∂wi∂∑j(yj−hw(xj))2
α … learning rate (step size)
lineární klasifikace
hledáme přímku (hypotézu), která bude oddělovat vstupy klasifikované jedním a druhým způsobem
hledáme lineární separátor
perceptronové pravidlo wi←wi+α(y−hw(x))⋅xi
kde y je cílová hodnota a hw(x) je výstup perceptronu pro vektor x
pro lineárně oddělitelné množiny konverguje
jinak „konvergenci“ zajistíme snižováním hodnoty α
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
pak můžeme k nalezení vah použít gradient descent
Umělé neuronové sítě
skládají se z propojených uzlů (jednotek)
každá jednotka nejdříve spočítá vážený součet vstupů
pak aplikuje aktivační funkci, čímž odvodí výstup
perceptron – schodová (step, hard treshold) aktivační funkce
sigmoid perceptron – aktivační funkce s logistickým tresholdem
struktury neuronových sítí
feed-forward network
spoje jenom v jednom směru (DAG)
reprezentuje funkci, která převádí vstup na výstup
žádný interní stav (paměť) kromě vah
recurrent network
výstup vrací zpátky do svých vstupů
reprezentuje dynamický systém, který může dojít do stabilního stavu, oscilovat, nebo se dokonce chovat chaoticky
může mít krátkodobou paměť
učení ve feed-forward vícevrstevných sítích
váhy upravujeme pomocí metody gradient descent
chyba na výstupové vrstvě se dá snadno spočítat – prostě porovnáme očekávaný výstup a výsledek neuronu
neznám však 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)
parametrický model
vezmeme data
zakódujeme je do parametrů neuronky (data „komprimujeme“, zajímá nás jenom část informace)
data zahodíme
neparametrický model
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
klasifikuju → lze zvolit nejčastější y
dělám regresi → spojím tečky nebo použiju průměr
vzdálenosti se typicky měří pomocí Minkowského metriky
Lp(a,b)=p∑i∣ai−bi∣p
pro p=1 … manhattanská vzdálenost
pro p=2 … euklidovská vzdálenost
máme-li boolovské hodnoty atributů, tak počet atributů, ve kterých se body liší, se nazývá Hammingova vzdálenost
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)
Bayesovské učení
někdy se neučíme úplně od nuly, už máme částečnou znalost, snažíme se naučit něco navrch – statistické učení
bayesovské učení
bereme v úvahu všechny hypotézy
vracíme vážený průměr všech hypotéz (váha = pravděpodobnost hypotézy)
další přístup – bereme v úvahu nejpravděpodobnější hypotézu
bayesovské sítě, parameter learning (učení se parametrů)
chceme se naučit hodnoty, které vyplníme do CPD tabulek
maximum-likelihood parameter learning
hledáme hypotézu, která nejlépe vysvětluje příklady
nejprve vyjádříme pravděpodobnost dat za podmínky dané hypotézy
pak derivujeme logaritmus téhle pravděpodobnosti postupně podle každého hladeného parametru
určíme hodnoty parametrů tak, aby byly derivace nulové
co když mám skryté proměnné (nejsou v datech)?
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 (E-step, expectation)
upravíme parametry, abychom maximalizovali likelihood modelu (M-step, maximization)
iterujeme (dokud to nezačne konvergovat)
Reinforcement learning (zpětnovazební učení)
základní myšlenka
nemusíme agentovi říkat y
agent se učí transition model pro své vlastní akce
vychází z markovských rozhodovacích procesů
agent dostává pozitivní nebo negativní zpětnou vazbu (ve formě reward/reinforcement)
aby zjistil, co je dobré a co je špatné
odměna (reward) je součástí input percept (vstupního vnímání), ale agent musí být hardwired, aby chápal, že je to odměna
cílem zpětnovazebního učení je, aby se agent pomocí odměn naučil optimální strategii pro prostředí
pasivní učení – známe strategii a učíme se, jak je dobrá (učíme se utility funkci)
strategie π je pevně daná
agent nezná přechodový model ani reward function
myšlenka: agent se řídí podle policy, vnímá současný stav a reward, z toho odvozuje utility
přímý odhad utility
máme trace (běh) mezi stavy, z toho (postupně) počítáme utility function
pokud stav potkáme víckrát, tak průměrujeme
idea: utilita stavu je očekávaný celkový reward z toho stavu v budoucnu (očekávaný reward-to-go)
nevýhody – 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
Uπ(s)←R(s)+γ∑s′P(s′∣s,π(s))⋅Uπ(s′)
adaptivní dynamické programování (ADP)
agent se učí přechodový model a odměny
utilitu počítá třeba z Bellmanových rovnic třeba pomocí value iteration
upravuje stav, aby odpovídal všem následníkům
temporal-difference (TD) learning
po každém kroku updatuju jedno číslo
nepotřebuju přechodový model (je to model-free metoda)
konverguje to pomaleji než ADP
upravuje stav, aby odpovídal aktuálně pozorovanému následníkovi
když dojde k přechodu ze stavu s do stavu s′, tak na Uπ(s) použijeme update: Uπ(s)←Uπ(s)+α⋅(R(s)+γ⋅Uπ(s′)−Uπ(s))
aktivní učení – agent zjišťuje, co má dělat (učíme se strategii a utility funkci)
agent neví, co má dělat
active ADP agent
agent se učí přechodovou funkci a odměny
používá Bellmanovy rovnice
Uπ(s)←R(s)+γmaxa∑s′P(s′∣s,a)⋅Uπ(s′)
můžeme použít value iteration
získáme utility funkci
ale nemusí se chovat úplně optimálně – opakuje zažité vzory
říká se tomu hladový (greedy) agent
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
agent si zvolí náhodnou akci v O(1/t) případech (kde 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 nezkusil příliš často, a vyhýbat se akcím, o kterých jsme přesvědčeni, že mají malou utilitu
přiřadíme vyšší odhad utility neprozkoumaným dvojicím (stav, akce)
opět použijeme value iteration
používáme optimistický odhad utility, aby se agent dostal i do vzdálenějších neprozkoumaných oblastí
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)=maxaQ(s,a)
můžeme napsat omezující podmínku Q(s,a)=R(s)+γ∑s′P(s′∣s,a)⋅maxa′Q(s′,a′)
tohle vyžaduje, aby se model naučil i P(s′∣s,a)
tenhle přístup nevyžaduje model přechodů – je to bezmodelová (model-free) metoda, potřebuje akorát q-hodnoty
Q(s,a)←Q(s,a)+α⋅(R(s)+γ⋅maxa′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-učení
Q(s,a)←Q(s,a)+α⋅(R(s)+γ⋅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) 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 (podle strategie – je to on-policy algoritmus, kdežto Q-learning je off-policy)
11. Filozofické a etické aspekty
přístup k AI
myslet lidsky – jako člověk
myslet racionálně – logicky
jednat lidsky – podle Turingova testu
jednat racionálně – jako racionální agent
lidská utility funkce jsou obvykle peníze
ale nedají se použít přímo – nejsou lineární (mezi milionem a dvěma miliony není takový rozdíl jako mezi nulou a milionem)
lidé jsou „předvídatelně iracionální“
preferují jistotu oproti nejistotě … certainity effect
preferují známou pravděpodobnost oproti té neznámé … ambiguity aversion
mohou stroje myslet?
weak AI … stroje můžou jednat, jako by byly inteligentní
to je zjevné
strong AI … stroje opravdu myslí
není jasné, zda je to vůbec možné
general AI … stroje můžou vyřešit libovolný problém
strong AI je v principu general AI
ale může být i weak AI general AI?
narrow AI … stroje můžou řešit problémy v konkrétní oblasti
určitě
Turingův test
počítač má pětiminutovou konverzaci s člověkem
člověk musí uhodnout, jestli to byl počítač nebo jiný člověk
pokud počítač napálí člověka v aspoň 30 % případů, tak prošel Turingovým testem
povedlo se to programům ELIZA, Eugene Goostman, Google Duplex, …
reverzní Turingův test – počítač se snaží zjistit, jestli komunikuje s počítačem nebo člověkem (např. captcha)
je Gödelova věta o neúplnosti problémem pro AI?
logická omezení se týkají i lidí
mind-body problem
dualistická teorie – tělo a mysl existují v oddělených sférách
jak může mysl ovládat tělo?
monistická teorie – mysl není oddělená od těla
mentální stavy jsou fyzické
tato teorie dnes převažuje
tedy by silná AI měla být možná
myšlenkové experimenty
brain in a vat – dá se poznat život v simulaci?
brain replacement – dají se neurony vyměnit jeden po druhém, aniž bychom přišli o vědomí?
čínský pokoj – poznáme, jestli člověk v pokoji rozumí čínštině?
etické problémy AI
falešné informace (ztráta důvěry)
dohled (ztráta práce)
automatizace (ztráta zaměstnání)
zabijácké stroje (ztráta životů)
konec lidské rasy (singularita)
technické problémy AI
vysvětlitelnost – člověk někdy potřebuje vědět, proč daný systém vrátil konkrétní výstup
křehkost – někdy se stává, že malá změna vstupu dramaticky změní výstup
předpojatost (bias) – může se stát, že systém upřednostňuje určitou skupinu uživatelů
sociální problémy AI
vojenské použití – může AI systém vystřelit?
zaměstnání – zautomatizují AI systémy každý lidský úkon?
dohled – mohou AI systémy nepřímo ovládat lidské životy?
rozhodování – měly by se AI systémy rozhodovat (nebo pouze doporučovat)?