Vzhledem k mal´e efektivitˇe algoritm˚u pro exaktn´ı odvozov´an´ı ve velk´ych a sloˇzitˇe propo-jen´ych s´ıt´ıch, je tˇreba zamˇeˇrit se na stochastick´e aproximaˇcn´ı metody, zaloˇzen´e na n´ahodn´em vzorkov´an´ı. Z´akladn´ı aproximaˇcn´ı metody patˇr´ı do skupiny pˇr´ım´eho vzorkov´an´ı a jsou toprior sample arejection sampling. Jsou postaveny na gener´atoru n´ahodn´ych ˇc´ısel, kter´y vrac´ı hodnotu v intervalu [0,1]. Bayesovsk´a s´ıt’ je v topologick´em poˇrad´ı vyhodnocena s pouˇzit´ım vygenerovan´eho ˇc´ısla a s ohledem na jiˇz urˇcen´e hodnoty pˇredk˚u dan´eho uzlu.
Druh´a metoda vyuˇz´ıv´a stejn´eho principu, ale hled´a pouze vzorky splˇnuj´ıc´ı poˇzadovan´a fakta, ostatn´ı vzorky ignoruje. Pod´ıl vzork˚u vyhovuj´ıc´ım fakt˚um exponenci´alnˇe kles´a s nar˚ustaj´ıc´ım poˇctem faktick´ych promˇenn´ych, algoritmus tud´ıˇz nen´ı vhodn´y pro sloˇzit´e probl´emy. Metoda likelihood weighting eliminuje probl´em zahazov´an´ı nevhodn´ych vzork˚u t´ım, ˇze generuje pouze ty vhodn´e. Pˇri postupn´em proch´azen´ı s´ıt´ı se generuj´ı hodnoty tˇech promˇenn´ych, kter´e nejsou pevnˇe nastaveny jako fakta, v opaˇcn´em pˇr´ıpadˇe je hodnota pˇr´ımo nastavena a z´aroven uloˇzena podm´ınˇen´a pravdˇepodobnost t´eto hodnoty pro tuto promˇennou jako koeficient pro dan´y vzorek. Kaˇzd´y vzorek je nakonec upraven t´ımto koeficientem, kter´y zaruˇc´ı pˇrimˇeˇrenou v´ahu jednotliv´ym vzork˚um v z´avislosti na pravdˇepodobnosti jejich v´yskytu. Posledn´ım algoritmem pro aproximaˇcn´ı vyhodnocen´ı bayesovsk´e s´ıtˇe je Markov chain Monte Carlo. Tato metoda, narozd´ıl od pˇredeˇsl´ych, nevytv´aˇr´ı nov´e vzorky ´uplnˇe od zaˇc´atku, n´ybrˇz vˇzdy z pˇredch´azej´ıc´ıho vzorku, zmˇenou hodnoty jedn´e z promˇenn´ych, kter´a se nevyskytuje v zadan´ych faktech.
6.4 Implementace
6.4.1 Tˇr´ıda EnumerateJointAsk
Tato tˇr´ıda implementuje stejnojmennou metodu pro v´ypoˇcet podm´ınˇen´e pravdˇepodobnosti urˇcit´eho jevu bez pouˇzit´ı bayesovsk´ych s´ıt´ı. Pˇred pouˇzit´ım t´eto metody je nutn´e naplnit tzv. ´upln´e spojen´e pravdˇepodobnostn´ı rozloˇzen´ı, kter´e je reprezentov´ano tˇr´ıdou
ProbabilityDistribution. Konstruktoru t´eto tˇr´ıdy se pˇred´avaj´ı promˇenn´e prostˇred´ı, a to bud’ jako jednotliv´e parametry nebo jejich kolekce (existuj´ı metody with:, with:with:,
with:with:with:,with:with:with:with: awithAll:). Jednotliv´e ˇr´adky tabulky rozloˇzen´ı jsou in-stance tˇr´ıdyRow a obsahuj´ı zadanou pravdˇepodobnost aModel, coˇz je kolekce promˇenn´ych a jejich hodnot pro dan´y ˇr´adek. Tyto ˇr´adky se zad´avaj´ı vol´an´ım zpr´avy set:probability: ob-jektu ProbabilityDistribution. Nakonec je nutn´e poloˇzit ot´azku, co vlastnˇe chceme zjistit a za jak´ych podm´ınek. To zajiˇst’uje tˇr´ıda Query, kter´a obsahuje dotazovanou promˇennou a kolekci nastaven´ych promˇenn´ych. To cel´e je n´aslednˇe zpracov´ano v metodˇe tˇr´ıdy Enumer-ateJointAsk ask:probabilityDistribution: a v´ysledek nakonec jeˇstˇe znormalizov´an. Uk´azka pouˇzit´ı t´eto metody jeProbabilityDemo enumerationJointAskDemo.
6.4.2 Tˇr´ıda BayesNetNode
Z´akladn´ımi elementy bayesovsk´e s´ıtˇe jsou jej´ı uzly, kter´e zastupuje tˇr´ıda BayesNetNode.
Kaˇzd´y uzel obsahuje kolekci sv´ych pˇredk˚u i potomk˚u, n´azev sv´e promˇenn´e a tabulku pravdˇepodobnostn´ıho rozloˇzen´ı. Pˇredek nebo pˇredkov´e uzlu se nastavuj´ı vol´an´ım zpr´avy influencedBy:, kter´a nejen dopln´ı vz´ajemn´e vazby mezi uzly, ale napln´ı i tabulku ro-zloˇzen´ı (ve formˇe instance ProbabilityDistribution) podle pˇredk˚u uzlu. Samotn´a hod-nota pravdˇepodobnosti v z´avislosti na hodnotˇe pˇredka je nastavena metodou setProba-bility:val:, kter´a dopln´ı tabulku rozloˇzen´ı dan´eho uzlu. Kaˇzd´y uzel m´a tedy tuto tabulku s poˇctem promˇenn´ych odpov´ıdaj´ıc´ım poˇctu pˇredk˚u uzlu a s nastavenou pravdˇepodobnost´ı v´yskytu pro kaˇzdou kombinaci hodnot promˇenn´ych. Vlastn´ı hodnotu promˇenn´e uzlu poˇc´ıt´a metoda isTrueFor:model:, kter´e je pˇred´ana hodnota pravdˇepodobnosti a kolekce jiˇz nas-taven´ych uzl˚u, podle kter´e je spoˇc´ıt´ana pravdˇepodobnost aktu´aln´ıho uzlu, ta je porovn´ana se zadan´ym parametrem a podle v´ysledku vr´acena hodnota uzlu. Koˇrenov´y uzel takto vytvoˇren´e s´ıtˇe je pˇred´an konstruktoru tˇr´ıdy BayesNet. Vytvoˇren´ı bayesovsk´e s´ıtˇe podle knihy AIMA str. 510 ukazuje metoda ProbabilityDemo createWetGrassNetwork.
6.4.3 Tˇr´ıda BayesNet
Jak vypov´ıd´a z n´azvu, tato tˇr´ıda reprezentuje bayesovskou s´ıt’ a implementuje metody pro pr´aci s n´ı. Z´akladn´ı metoda pro spoˇc´ıt´an´ı podm´ınˇen´e pravdˇepodobnosti je enumerateAsk:, kter´a, podobnˇe jako tˇr´ıdaEnumerateJointAsk, spoˇc´ıt´a pravdˇepodobnosti podle tabulky ro-zloˇzen´ı a je tedy z´astupcem exaktn´ıch v´ypoˇcetn´ıch metod pro bayesovsk´e s´ıtˇe. Postupn´e rekurzivn´ı proch´azen´ı s´ıtˇe pˇri v´ypoˇctu zajiˇst’uje metoda enumerateAll:evidence:. N´ahodn´y vzorek stavu s´ıtˇe lze z´ıskat vol´an´ım metody getPriorSample, kter´a vygeneruje n´ahodn´y stav pro kaˇzd´y uzel s´ıtˇe s ohledem na vz´ajemn´e z´avislosti. Tuto metodu vyuˇz´ıv´a algo-ritmus rejection sampling, kter´y na z´akladˇe hledan´e promˇenn´e, poˇzadovan´eho stavu s´ıtˇe a poˇctu pokus˚u statisticky urˇc´ı pravdˇepodobnost v´yskytu poˇzadovan´eho stavu. Vzorky, kter´e nevyhovuj´ı zadan´ym podm´ınk´am, jsou zahozeny. Spouˇst´ı se vol´an´ım zpr´avy re-jectionSample:evidence:numSamples. Na podobn´em principu funguje metoda likelihood-Weighting:evidence:numSamples:, kter´a ovˇsem ˇz´adn´e vzorky nezahazuje, ale upravuje tak, aby splˇnovaly zadan´e podm´ınky, a m´ısto pˇriˇcten´ı 1 za kaˇzd´y vzorek obsahuj´ıc´ı hledanou promˇennou ve stavu true resp. false je pˇriˇcten koeficient, kter´y je n´asobkem pravdˇepodobost´ı zadan´ych podm´ınek, aby bylo statisticky vyv´aˇzeno upravov´an´ı vzork˚u.
Posledn´ı zm´ınˇenou metodou t´eto tˇr´ıdy jemcmcAsk:evidence:numSamples:, coˇz je implemen-tace algoritmu Markov chain Monte Carlo. Tento algoritmus nejprve vygeneruje n´ahodn´y prvn´ı vzorek, vytvoˇr´ı mnoˇzinu uzl˚u, kter´e nejsou zad´any (non-evidence), a pro kaˇzd´y takov´y uzel spoˇc´ıt´aMarkov blanket, coˇz je mnoˇzina vˇsech pˇr´ım´ych pˇredk˚u, potomk˚u a pˇredk˚u po-tomk˚u, a pouˇzije jej jako poˇc´ateˇcn´ı podm´ınky pro generov´an´ı nov´e hodnoty tohoto uzlu.
T´ım postupnˇe obmˇenuje hodnoty v mnoˇzinˇenon-evidence a vytv´aˇr´ı tak nov´y stav ze stavu pˇredchoz´ıho. Pro proveden´ın iterac´ı vrac´ı normalizovan´y pomˇer hodnottrue afalse.
Pˇr´ıklady pouˇzit´ı tˇechto algoritm˚u obsahuje tˇr´ıda ProbabilityDemo, jej´ıˇz tˇr´ıdn´ı metody priorSampleDemo, rejectionSamplingDemo, likelihoodWeightingDemo a mcmcAskDemo pouˇz´ıvaj´ı pˇreddefinovanou bayesovskou s´ıt’ vytvoˇrenou metodou createWetGrassNetwork a vyhodnocuj´ı zadan´y dotaz pomoc´ı v´yˇse popsan´ych algoritm˚u.
Kapitola 7
Uˇ cen´ı
Tato kapitola se zab´yv´a uˇcen´ım, jehoˇz podstata spoˇc´ıv´a ve zpracov´an´ı vjem˚u a jejich vyuˇzit´ı v budoucnu. To vede ke zlepˇsen´ı schopnosti jednat ´uˇcelnˇe a efektivnˇe. Uˇcen´ı m´a mnoho podob, od prost´eho zapamatov´an´ı zkuˇsenost´ı aˇz po vytv´aˇren´ı sloˇzit´ych teori´ı. V z´asadˇe m˚uˇzeme rozdˇelit uˇcen´ı do tˇrech skupin, a to podle dostupn´e odezvy. Uˇcen´ı s dohledem (supervised learning) obn´aˇs´ı hled´an´ı urˇcit´e funkce podle mnoˇziny pˇr´ıklad˚u jej´ıch vstup˚u a v´ystup˚u. Tyto pˇr´ıklady mohou b´yt zad´any bud’ jako ˇskolic´ı mnoˇzina, nebo v pˇr´ıpadˇe plnˇe pozorovateln´eho prostˇred´ı m˚uˇze agent s´am vn´ımat n´asledky sv´ych akc´ı a nauˇcit se tak tyto n´asledky pˇredv´ıdat v budoucnu. Uˇcen´ı bez dohledu (unsupervised learning) znamen´a vyuˇzit´ı metod uˇcen´ı pro zadan´e vstupy, aˇckoli nejsou pˇresnˇe definov´any v´ystupy funkce.
Takto m˚uˇzeme nauˇcit agenta rozliˇsit r˚uzn´e jevy, aniˇz bychom pˇredem znali jejich definici.
Posledn´ı a nejobecnˇejˇs´ı skupinou je tzv. zpˇetnovazebn´ı uˇcen´ı (reinforcement learning), pˇri kter´em agentovi nen´ı pˇr´ımo sdˇeleno co m´a dˇelat, pouze je na konci ohodnocen (odmˇenou nebo pokutou). D˚uleˇzitou roli hraje tak´e vyj´adˇren´ı nauˇcen´ych informac´ı, napˇr. jako formule v´yrokov´e ˇci predik´atov´e logiky, nebo pravdˇepodobnostn´ı popis ve formˇe bayesovsk´e s´ıtˇe.
7.1 Princip uˇ cen´ı
Algoritmus pro deterministick´e ˇr´ızen´e uˇcen´ı m´a za ´ukol pomoc´ı indukce naj´ıt funkci h, kter´a je aproximac´ı nezn´am´e funkce f. Protoˇze je to uˇcen´ı s dohledem, jsou algortimu pˇred´any pˇr´ıklady, coˇz jsou dvojice (x, f(x)), kde x je vstup a f(x) v´ystup hledan´e funkce.
Funkce h se naz´yv´a hypot´eza, konzistentn´ı hypot´eza je takov´a, kter´a spr´avnˇe spoˇc´ıt´a vˇsechny zadan´e pˇr´ıklady. Sloˇzitost uˇcen´ı spoˇc´ıv´a v tom, ˇze nen´ı moˇzn´e dost dobˇre ˇr´ıci, zda h je dobr´a hypot´eza, tj. jestli je schopn´a spr´avnˇe aproximovat f i pro dalˇs´ı (pro ni nezn´am´e) pˇr´ıklady. Pokud existuje v´ıce konzistentn´ıch hypot´ez pro jednu mnoˇzinu pˇr´ıklad˚u, je vhodn´e (podle Ockhamova pravidla) preferovat tu nejjednoduˇsˇs´ı hypot´ezu konzistentn´ı s daty. Nalezen´ı jednoduch´e a spr´avn´e hypot´ezy z´avis´ı pˇredevˇs´ım na volbˇe prostoru hy-pot´ez, kter´y vyjadˇruje urˇcitou mnoˇzinu funkc´ı, napˇr. polynomick´e k-t´eho stupnˇe. Pokud se skuteˇcn´a hledan´a funkce f nenach´az´ı v tomto zvolen´em prostoru, nen´ı dan´y probl´em uˇcen´ı splniteln´y. Jako ˇreˇsen´ı bychom mohli zvolit co nejobecnˇejˇs´ı prostor hypot´ez, kter´ym bezesporu je tˇr´ıda vˇsech Turingov´ych stroj˚u, nebot’ kaˇzd´a spoˇcitateln´a funkce m˚uˇze b´yt vyj´adˇrena nˇejak´ym Turingov´ym strojem, to ale bohuˇzel nen´ı moˇzn´e, protoˇze by t´ımto doˇslo k obrovsk´emu n´ar˚ustu v´ypoˇcetn´ı sloˇzitosti uˇcic´ıho algorimu. Druh´ym d˚uvodem proˇc volit jednoduch´y prostor hypot´ez je n´asledn´e pouˇz´ıv´an´ı nalezen´e hypot´ezy, v´ypoˇceth(x) je mno-hem rychlejˇs´ı v pˇr´ıpadˇe line´arn´ı funkce neˇz v pˇr´ıpadˇe programu Turingova stroje. Z tˇechto
d˚uvod˚u pracuj´ı n´asleduj´ıc´ı algoritmy s jednoduˇse vyj´adˇren´ymi funkcemi, a to konkr´etnˇe ve formˇe klauzul´ı v´yrokov´e logiky. Efektivitu uˇcic´ıho algoritmu m˚uˇzeme zmˇeˇrit pomoc´ı tzv. uˇcic´ı kˇrivky, kter´a ukazuje procentu´aln´ı pˇresnost pˇredpovˇedi pro testovac´ı mnoˇzinu v z´avislosti na velikosti tr´enovac´ı mnoˇziny.