====== Bayesovské sítě ====== (exaktní inference, přibližná inference) ---- ===== Základy (podmíněné) pravěpodobnosti ===== Pozn.: toto není přímo uvedené v okruhu, ale je to takový základ, který je asi dobré znát. ==== Motivace ==== * realita je nejistá, většinou nelze usuzování provádět exaktně * využívá se tedy teorie pravděpodobnosti ==== Pravděpodobnost ==== * zavádí se termín //míra důvěry// v platnost daného výroku * míra důvěry 0.8 znamená, že v 8/10 případů je výrok pravdivý * proměnné * píšou velkýma písmenama a nabývají hodnot diskrétních, spojitých nebo booleovských * pokud víme u booleovské proměnné X, jakou má hodnotu, tak pro true se píše x a pro false not x (nenašel jsem jak se píše v téhle wikině negace) * nepodmíněná //apriorní// pravděpodobnost - nezávisí na ničem jiném * podmíněná //aposteriorní// pravděpodobnost - je závislá na jiném jevu (jev a je závislý na jevu b): P(a|b) = {P(a wedge b)}/{P(b)} * zapisuje se taky P(a|b) = alpha P(a wedge b), kde alpha = 1/{P(b)} * obecně pro pravděpodobnostní proměnné (nikoli konkrétní jevy = hodnoty těchto proměnných) se zavádí stejná notace s tučným **P**, která vyjadřuje soustavu rovnic pro všechny možné varianty jednotlivých proměnných === Inference === * výpočet podmíněné pravděpodobnosti * pro exaktní inferenci je nutné znát pravděpodobnost všech kombinací všech možných hodnot všech jevů * to je pro malé systémy proměnných v pořádku, ale potřebný prostor i časová složitost inference narůstají exponenciálně === Bayesovo pravidlo === P(a|b) = {P(b|a)P(b)}/{P(a)}, obdobně obecný zápis pro proměnné doplnit, rozsirit, nebo to uplne flipnout? ===== Bayesovská síť ===== * acyklický orientovaný graf * uzly = pravděpodobnostní proměnné * hrana z A do B vyjadřuje fakt, že proměnná B je závislá na proměnné A * uzly obsahují tabulky s pravděpodobnostmi výskytu hodnot uzlové proměnné v závislosti na hodnotách rodičovských proměnných * také jinak: obsahují podmíněnou pravděpodobnost vzhledem ke všem rodičovským proměnným * tabulky popisují úplné sdružené rozložení pravděpodobnosti, tedy výpočet pravděpodobnosti pro konkrétní hodnoty jednotlivých jevů se počítá jako **násobek** patřičných hodnot v jednotlivých tabulkách ==== Exaktní inference v Bayesovských sítích ==== Definice úlohy inferenčního systému: Cílem je spočítat podmíněnou pravděpodobnost proměnných **X** na základě známých hodnot proměnných **E** (evidences) pro všechny možné varianty proměnných **Y**, u kterých hodnoty známé nejsou. Postup je následující: * pro každou možnou kombinaci hodnot proměnných v množině **X** se spočítá pravděpodobnost: * provede se výše popsaný výpočet pravděpodobnosti (násobením hodnot z tabulek) pro všechny varianty proměnných z množiny **Y** * pravděpodobnosti těchto variant se sečtou * pozor: výsledné pravděpodobnosti pro každou proměnnou je nutné nakonec normovat, aby byl součet 1 Problém exaktní inference je v exponenciální časové složitosti výpočtu. Určité zlepšení přináší zavedení faktoru, který je mezivýsledkem výpočtu pro kombinace neznámých proměnných a tak zamezuje opakovanému výpočtu některých hodnot. ==== Přibližná inference ==== Pokud je síť příliš velká pro použití exaktní inference, využívá se přibližné. Místo vyčíslování všech variant hodnot proměnných je použita metoda Monte Carlo na generování vzorků. Myslím, že výsledné pravděpodobnosti se jednoduše sčítají a normují. Přesnost vypočítané pravděpodobnosti je závislá na počtu nagenerovaných vzorků. === Varianty === Existuje několik variant generování vzorků: == Direct Sampling == * generují se náhodné vzorky, nepočítá se s žádnými známými okolnostmi (evidences) * většinou nevhodné, protože nějaké okolnosti jsou vstupem úlohy == Rejection Sampling == * Monte Carlo - vygenerovaný vzorek je odmítnut, pokud hodnoty proměnných nesouhlasí se známými okolnostmi * nevýhoda: velký počet odmítnutých vzorků == Weighted Sampling == * ve vzorcích generuje pouze hodnoty neznámých proměnných a přiřazuje vzorku váhu tohle moc nechápu, dodělat!