Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
Bayesian networks; probabilistic inference; uncertainty in artificial intelligence; tensor rank; symmetric rank; border rank
Bayesian networks; probabilistic inference; uncertainty in artificial intelligence; tensor rank; symmetric rank; border rank
Summary:
Bayesian networks are a popular model for reasoning under uncertainty. We study the problem of efficient probabilistic inference with these models when some of the conditional probability tables represent deterministic or noisy $\ell$-out-of-$k$ functions. These tables appear naturally in real-world applications when we observe a state of a variable that depends on its parents via an addition or noisy addition relation. We provide a lower bound of the rank and an upper bound for the symmetric border rank of tensors representing $\ell$-out-of-$k$ functions. We propose an approximation of tensors representing noisy $\ell$-out-of-$k$ functions by a sum of $r$ tensors of rank one, where $r$ is an upper bound of the symmetric border rank of the approximated tensor. We applied the suggested approximation to probabilistic inference in probabilistic graphical models. Numerical experiments reveal that we can get a gain in the order of two magnitudes but at the expense of a certain loss of precision.
References:
[1] Bini, D., Lotti, G., Romani, F.: Approximate solutions for the bilinear form computational problem. SIAM J. Comput. 9 (1980), 692–697. DOI 10.1137/0209053 | MR 0592760 | Zbl 0446.68035
[2] Carroll, J. D., Chang, J. J.: Analysis of individual differences in multidimensional scaling via an n-way generalization of Eckart–Young decomposition. Psychometrika 35 (1970), 283–319. DOI 10.1007/BF02310791 | Zbl 0202.19101
[3] Lathauwer, L. De, Moor, B. De: From matrix to tensor: multilinear algebra and signal processing. In: 4th Internat. Conf. on Mathematics in Signal Processing, Part I, Warwick 1996, IMA Conf. Series, pp. 1–11.
[4] Díez, F. J., Galán, S. F.: An efficient factorization for the noisy MAX. Internat. J. Intell. Systems 18 (2003), 2, 165–177. DOI 10.1002/int.10080
[5] Harshman, R. A.: Foundations of the PARAFAC procedure: Models and conditions for an “explanatory" multi-mode factor analysis. UCLA Working Papers in Phonetics 16 (1970), 1–84.
[6] Jensen, F. V.: Bayesian Networks and Decision Graphs. Springer-Verlag, New York 2001. MR 1876880 | Zbl 0973.62005
[7] Jensen, F. V., Lauritzen, S. L., Olesen, K. G.: Bayesian updating in recursive graphical models by local computation. omputational Statistics Quarterly 4 (1990), 269–282. MR 1073446
[8] Lauritzen, S. L., Spiegelhalter, D. J.: Local computations with probabilities on graphical structures and their application to expert systems (with discussion). J. Roy. Statist. Soc., Ser. B 50 (1988), 157–224. MR 0964177
[9] Madsen, A. L., Jensen, F. V.: Lazy propagation: A junction tree inference algorithm based on lazy evaluation. Artificial Intelligence 113 (1999), 1–2, 203–245. DOI 10.1016/S0004-3702(99)00062-4 | MR 1724104 | Zbl 0939.68848
[10] Olmsted, S. M.: On Representing and Solving Decision Problems. PhD. Thesis, Stanford University 1983.
[11] Team, R Development Core: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna 2008.
[12] Rose, D. J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory Comput. (1972), 183–217. MR 0341833 | Zbl 0266.65028
[13] Savický, P., Vomlel, J.: Exploiting tensor rank-one decomposition in probabilistic inference. Kybernetika 43 (2007), 5, 747–764. MR 2376335 | Zbl 1148.68539
[14] Savický, P., Vomlel, J.: Triangulation heuristics for BN2O networks. In: Tenth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2009, Lecture Notes in Comput. Sci. 5590, Springer, Berlin – Heidelberg 2009, pp. 566–577. MR 2893316 | Zbl 1245.62019
[15] Shafer, G. R., Shenoy, P. P.: Probability propagation. Ann. Math. Artif. Intell. 2 (1990), 1–4, 327–351. DOI 10.1007/BF01531015 | MR 1215075 | Zbl 0875.68676
[16] Vomlel, J.: Exploiting functional dependence in Bayesian network inference. In: Proc. 18th Conference on Uncertainty in AI (UAI), Morgan Kaufmann Publ. 2002, pp. 528–535.
[17] Vomlel, J., Savický, P.: Arithmetic circuits of the noisy-or models. In: Prof. Fourth European Workshop on Probabilistic Graphical Models (PGM’08), Hirtshals 2005, pp. 297–304.
[18] Wiegerinck, W., Kappen, B., Burgers, W.: Bayesian Networks for Expert Systems: Theory and Practical Applications. In: Interactive Collaborative Information Systems – Studies in Computational Intelligence (R. Babuška and F. C. A. Groen, eds.), Springer-Verlag, Berlin – Heidelberg 2010, pp. 547–578.
[19]
Wikipedia: Minesweeper (Computer game). http://en.wikipedia.org/wiki/Minesweeper_(computer_game)
Search
Partner of
