Efektivní metody výpočtu v bayesovských sítích typu BN2O

BN2O je bayesovská síť, která má strukturu bipartitního grafu se všemi hranami orientovanými z jedné hladiny do druhé. Všechny podmíněné pravděpodobnostní tabulky jsou tzv. zašuměné OR funkce (angl. noisy-or gates). Příkladem BN2O sítě z praxe je rozsáhlý medicínský model Quick Medical Reference vyvinutý na univerzitě v Pittsburghu. Model obsahuje celkem 570 nemocí a 4075 možných pozorování či testů pacienta.

Aby bylo možné provádět výpočty v BN2O sítích efektivně používají se různé grafové transformace. Složitost výpočtu pak závisí na celkové velikosti všech tabulek odpovídajících klikám triangulovaného grafu. Proto je žádoucí dosáhnout co nejmenší velikost klik triangulovaného grafu.

V naší předchozí práci jsme navrhli metodu transformace založenou na rozkladu pravděpodobnostních tabulek na tensory ranku jedna. Nyní jsme teoreticky ukázali, že tato transformace nemůže dát horší výsledky než doposud používaná metoda rozvádění rodičů (angl. parent divorcing). Provedli jsme také experimenty na různě velkých sítích typu BN2O, které potvrdily, že i při použití heuristických triangulačních metod dosahuje rozkladu na tensory ranku jedna lepších výsledků.

Protože výsledky závisí na použitých triangulačních metodách, studovali jsme také vliv triangulačních heuristik na celkovou velikost všech tabulek triangulovaného grafu. Ukázalo se, že pro většinu testovaných modelů dává nejlepší výsledky metoda minimálního počtu doplňovaných hran (angl. min-fill).

Inovační aspekty

Pro sítě typu BN2O se nám podařilo teoreticky dokázat a prakticky ověřit dominanci námi navržené metody rozkladu pravděpodobnostních tabulek na tensory ranku jedna nad doposavad používanou metodou parent divorcnig.

Přínosy

Uživatel pravděpodobnostních modelů typu BN2O má díky novým výsledkům k dispozici výpočetně efektivnější metodu. Ta umožňuje rychlejší práci i s rozsáhlejšími modely.

Dokumentace

  • Savický, Petr ; Vomlel, Jiří. Triangulation Heuristics for BN2O Networks. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Berlin : Springer, 2009. S. 566-577. ISBN 978-3-642-02905-9. [ECSQARU 2009. European Conference /10./, Verona, 01.07.2009-03.07. 2009, IT].
  • Vomlel, Jiří ; Savický, Petr. An experimental comparison of triangulation heuristics on transformed BN2O networks. In Proceedings of the 8th Workshop on Uncertainty Processing. Praha : University of Economics, 2009. S. 251-260. ISBN 978-80-245-1543-4. [WUPES 2009, Liblice, 19.09.2009-23.09.2009, CZ]. Dostupný z: <http://library.utia.cas.cz/separaty/2009/MTR/vomlel-an experimental comparison of triangulation heuristics on transformed bn2o networks.pdf http://library.utia.cas.cz/separaty/2009/MTR/vomlel-an experimental comparison of triangulation heuristics on transformed bn2o networks.pdf>.
Design downloaded from Free Templates - your source for free web templates