Geodesic
Rank of tensors of $\ell $-out-of-$k$ functions: An application in probabilistic inference
Kybernetika, Tome 47 (2011) no. 3, pp. 317-336 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 15A69, 62E15, 68T37
Keywords: Bayesian networks; probabilistic inference; uncertainty in artificial intelligence; tensor rank; symmetric rank; border rank 
@article{KYB_2011_47_3_a1,
     author = {Vomlel, Ji\v{r}{\'\i}},
     title = {Rank of tensors of $\ell $-out-of-$k$ functions: {An} application in probabilistic inference},
     journal = {Kybernetika},
     pages = {317--336},
     year = {2011},
     volume = {47},
     number = {3},
     mrnumber = {2857193},
     zbl = {1221.68243},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2011_47_3_a1/}
}
TY  - JOUR
AU  - Vomlel, Jiří
TI  - Rank of tensors of $\ell $-out-of-$k$ functions: An application in probabilistic inference
JO  - Kybernetika
PY  - 2011
SP  - 317
EP  - 336
VL  - 47
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/KYB_2011_47_3_a1/
LA  - en
ID  - KYB_2011_47_3_a1
ER  - 
%0 Journal Article
%A Vomlel, Jiří
%T Rank of tensors of $\ell $-out-of-$k$ functions: An application in probabilistic inference
%J Kybernetika
%D 2011
%P 317-336
%V 47
%N 3
%U http://geodesic.mathdoc.fr/item/KYB_2011_47_3_a1/
%G en
%F KYB_2011_47_3_a1
Vomlel, Jiří. Rank of tensors of $\ell $-out-of-$k$ functions: An application in probabilistic inference. Kybernetika, Tome 47 (2011) no. 3, pp. 317-336. http://geodesic.mathdoc.fr/item/KYB_2011_47_3_a1/

[1] Bini, D., Lotti, G., Romani, F.: Approximate solutions for the bilinear form computational problem. SIAM J. Comput. 9 (1980), 692–697. | DOI | MR | Zbl

[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 | Zbl

[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

[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 | Zbl

[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

[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

[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 | MR | Zbl

[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 | Zbl

[13] Savický, P., Vomlel, J.: Exploiting tensor rank-one decomposition in probabilistic inference. Kybernetika 43 (2007), 5, 747–764. | MR | Zbl

[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 | Zbl

[15] Shafer, G. R., Shenoy, P. P.: Probability propagation. Ann. Math. Artif. Intell. 2 (1990), 1–4, 327–351. | DOI | MR | Zbl

[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)