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 <m>x</m> a pro false <m>not x</m> (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): <m>P(a|b) = {P(a wedge b)}/{P(b)}</m>

zapisuje se taky <m>P(a|b) = alpha P(a wedge b)</m>, kde <m>alpha = 1/{P(b)}</m>

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

<m>P(a|b) = {P(b|a)P(b)}/{P(a)}</m>, 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!