Název: An experimental comparison of triangulation heuristics on transformed BN2O networks
Překlad názvu: Experimentální srovnání triangulačních heuristik na transformovaných sítích BN2O
Autoři: Vomlel, Jiří ; Savický, Petr
Typ dokumentu: Příspěvky z konference
Konference/Akce: WUPES 2009, Liblice (CZ), 2009-09-19 / 2009-09-23
Rok: 2009
Jazyk: eng
Abstrakt: [eng] [cze]
In this paper we present results of experimental comparisons of several triangulation heuristics on bipartite graphs. Our motivation for testing heuristics on the family of bipartite graphs is the rank-one decomposition of BN2O networks. A BN2O network is a Bayesian network having the structure of a bipartite graph with all edges directed from the top level toward the bottom level and where all conditional probability tables are noisy-or gates. After applying the rank-one decomposition, which adds an extra level of auxiliary nodes in between the top and bottom levels, and after removing simplicial nodes of the bottom level we get so called BROD graph. This is an undirected bipartite graph. It is desirable for efficiency of the inference to find a triangulation of the BROD graph having the sum of table sizes for all cliques of the triangulated graph as small as possible. From this point of view, the minfill heuristics perform in average better than other tested heuristics (minwidth, h1, and mcs). V článku jsou prezentovány výsledky provnání různých heuristik pro triangulaci bipartitních grafů. Motivací pro testování heuristik na rodině bipartitních grafů je rozklad na tensory ranku jedna použitý na sítě typu BN2O.
Klíčová slova: Bayesian networks; bipartite graphs; graph triangulation
Číslo projektu: CEZ:AV0Z10750506 (CEP), CEZ:AV0Z10300504 (CEP), 1M0572 (CEP), 1M0545 (CEP), 1ET100300517 (CEP), GA201/09/1891 (CEP), GEICC/08/E010 (CEP), 2C06019 (CEP)
Poskytovatel projektu: GA MŠk, GA MŠk, GA AV ČR, GA ČR, GA ČR, GA MŠk
Zdrojový dokument: Proceedings of the 8th Workshop on Uncertainty Processing, ISBN 978-80-245-1543-4

Instituce: Ústav teorie informace a automatizace AV ČR (web)
Informace o dostupnosti dokumentu: Dokument je dostupný na externích webových stránkách.
Externí umístění souboru: http://library.utia.cas.cz/separaty/2009/MTR/vomlel-an experimental comparison of triangulation heuristics on transformed bn2o networks.pdf
Původní záznam: http://hdl.handle.net/11104/0175891

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-40520


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Ústav teorie informace a automatizace
Konferenční materiály > Příspěvky z konference