Abstract
A BN2O network is a Bayesian network having the structure of a bipartite graph with all edges directed from one part (the top level) toward the other (the bottom level) and where all conditional probability tables are noisy-or gates. In order to perform efficient inference, graphical transformations of these networks are performed. The efficiency of inference is proportional to the total table size of tables corresponding to the cliques of the triangulated graph. Therefore in order to get efficient inference it is desirable to have small cliques in the triangulated graph. We analyze existing heuristic triangulation methods applicable to BN2O networks after transformations using parent divorcing and tensor rank-one decomposition and suggest several modifications. Both theoretical and experimental results confirm that tensor rank-one decomposition yields better results than parent divorcing in randomly generated BN2O networks that we tested.
P. Savicky was supported by grants number 1M0545 (MŠMT ČR), 1ET100300517 (Information Society), and by Institutional Research Plan AV0Z10300504. J. Vomlel was supported by grants number 1M0572 and 2C06019 (MŠMT ČR), ICC/08/E010 (Eurocores LogICCC), and 201/09/1891 (GA ČR).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Olesen, K.G., Kjærulff, U., Jensen, F., Jensen, F.V., Falck, B., Andreassen, S., Andersen, S.K.: A MUNIN network for the median nerve — a case study on loops. Applied Artificial Intelligence 3, 384–403 (1989); Special issue: Towards Causal AI Models in Practice
Díez, F.J., Galán, S.F.: An efficient factorization for the noisy MAX. International Journal of Intelligent Systems 18, 165–177 (2003)
Vomlel, J.: Exploiting functional dependence in Bayesian network inference. In: Proceedings of the 18th Conference on Uncertainty in AI (UAI), pp. 528–535. Morgan Kaufmann, San Francisco (2002)
Savicky, P., Vomlel, J.: Exploiting tensor rank-one decomposition in probabilistic inference. Kybernetika 43(5), 747–764 (2007)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic and Discrete Methods 2, 77–79 (1981)
Vomlel, J., Savicky, P.: Arithmetic circuits of the noisy-or models. In: Proceedings of the Fourth European Workshop on Probabilistic Graphical Models (PGM 2008), Hirtshals, Denmark, pp. 297–304 (2008)
Bodlaender, H.L., Koster, A.M.C.A., Eijkhof, F.V.D.: Preprocessing rules for triangulation of probabilistic networks. Computational Intelligence 21(3), 286–305 (2005)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209(1-2), 1–45 (1998)
Savicky, P., Vomlel, J.: Triangulation heuristics for BN2O networks. Technical report, Institute of Information Theory and Automation of the AS CR (2009), http://www.utia.cas.cz/vomlel/ecsqaru2009-full-version.pdf
Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory and Computing, 183–217 (1972)
Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566–579 (1984)
Cano, A., Moral, S.: Heuristic algorithms for the triangulation of graphs. In: Bouchon-Meunier, B., Yager, R.R., Zadeh, L.A. (eds.) IPMU 1994. LNCS, vol. 945, pp. 98–107. Springer, Heidelberg (1995)
Ace: A Bayesian network compiler (2008), http://reasoning.cs.ucla.edu/ace/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Savicky, P., Vomlel, J. (2009). Triangulation Heuristics for BN2O Networks. In: Sossai, C., Chemello, G. (eds) Symbolic and Quantitative Approaches to Reasoning with Uncertainty. ECSQARU 2009. Lecture Notes in Computer Science(), vol 5590. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02906-6_49
Download citation
DOI: https://doi.org/10.1007/978-3-642-02906-6_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02905-9
Online ISBN: 978-3-642-02906-6
eBook Packages: Computer ScienceComputer Science (R0)