Bayesovské sítě

(exaktní inference, přibližná inference)

Pozn.: toto není přímo uvedené v okruhu, ale je to takový základ, který je asi dobré znát.

• realita je nejistá, většinou nelze usuzování provádět exaktně
• využívá se tedy teorie pravděpodobnosti

• 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

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

<m>P(a|b) = {P(b|a)P(b)}/{P(a)}</m>, obdobně obecný zápis pro proměnné

• 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

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.

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ů.

Přesnost vypočítané pravděpodobnosti je závislá na počtu nagenerovaných vzorků.

Existuje několik variant generování vzorků:

• 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

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

• ve vzorcích generuje pouze hodnoty neznámých proměnných a přiřazuje vzorku váhu