Triangulation heuristics for BN2O networks. (English) Zbl 1245.62019
Sossai, Claudio (ed.) et al., Symbolic and quantitative approaches to reasoning with uncertainty. 10th European conference, ECSQARU 2009, Verona, Italy, July 1–3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02905-9/pbk). Lecture Notes in Computer Science 5590. Lecture Notes in Artificial Intelligence, 566-577 (2009).
Summary: 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.
For the entire collection see [Zbl 1165.68020].
For the entire collection see [Zbl 1165.68020].
MSC:
| 62F15 | Bayesian inference |
| 05C90 | Applications of graph theory |
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
References:
| [1] | 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 · doi:10.1080/08839518908949933 |
| [2] | Díez, F.J., Galán, S.F.: An efficient factorization for the noisy MAX. International Journal of Intelligent Systems 18, 165–177 (2003) · Zbl 1028.68164 · doi:10.1002/int.10080 |
| [3] | 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) |
| [4] | Savicky, P., Vomlel, J.: Exploiting tensor rank-one decomposition in probabilistic inference. Kybernetika 43(5), 747–764 (2007) · Zbl 1148.68539 |
| [5] | Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic and Discrete Methods 2, 77–79 (1981) · Zbl 0496.68033 · doi:10.1137/0602010 |
| [6] | 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) |
| [7] | 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) · doi:10.1111/j.1467-8640.2005.00274.x |
| [8] | Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209(1-2), 1–45 (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4 |
| [9] | 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 · Zbl 1245.62019 |
| [10] | 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) |
| [11] | 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) · Zbl 0545.68062 · doi:10.1137/0213035 |
| [12] | 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) · doi:10.1007/BFb0035941 |
| [13] | Ace: A Bayesian network compiler (2008), http://reasoning.cs.ucla.edu/ace/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
