Nové metody triangularizace grafů

Je všeobecně známo, že nejefektivnější výpočty v bayesovských sítích jsou prováděny tak, že uvažovaná bayesovská síť (tj. pravděpodobnostní distribuce reprezentovaná touto sítí) je konvertována do tvaru rozložitelného modelu. Nejkritičtějším krokem této konverze je proces triangularizace grafu, o kterémžto kroku je teoreticky dokázáno, že se jedná o NP úplný problém. To znamená, že všechny známé optimální postupy jsou exponenciálně složité, a tedy proveditelné jen pro malé rozsahy původní bayesovské sítě a jsou tedy z praktického hlediska nezajímavé. Proto byla navržena celá řada heuristických (suboptimálních) postupů pro řešení triangularizace grafů. Námi navržené postupy jsou dosud nejlepší známé, které jsou speciálně upraveny pro bayesovské sítě modelující "zašuměné relace nebo" (noisy or relations).

Inovační aspekty

V prvním z uvedených článků je popsána poměrně jednoduchá, ale překvapivě výkonná metoda pro hledání klik v dynamicky se měnících grafech. Postup je založen na méně známém Bron-Kerboschově algoritmu, který je výhodnější než častěji používaný Stixův přístup. Druhý z uvedených článků je popisem metody, která inovativně používá klasické postupy prohledávání, tzv. prohledávání do hloubky (depth-first search) a řízené prohledávání (best-first search) pro nalezení prostorové složitosti výsledného triangulovaného grafu. V publikaci bylo experimentálně prokázáno, že námi navržený postup je rychlejší než běžně používané metody vycházející z principů dynamického programování.

Přínosy

Zařazení námi navržených postupů do systémů pro provádění výpočtů s bayesovskými sítěmi umožní pracovat se sítěmi s zašuměnými relacemi nebo (noisy or relations), jejichž velikost přesahuje možnosti stávajících programových systémů.

Dokumentace

Design downloaded from Free Templates - your source for free web templates