| Title:
|
Rank of tensors of $\ell $-out-of-$k$ functions: An application in probabilistic inference (English) |
| Author:
|
Vomlel, Jiří |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
47 |
| Issue:
|
3 |
| Year:
|
2011 |
| Pages:
|
317-336 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Bayesian networks |
| Keyword:
|
probabilistic inference |
| Keyword:
|
uncertainty in artificial intelligence |
| Keyword:
|
tensor rank |
| Keyword:
|
symmetric rank |
| Keyword:
|
border rank |
| MSC:
|
15A69 |
| MSC:
|
62E15 |
| MSC:
|
68T37 |
| idZBL:
|
Zbl 1221.68243 |
| idMR:
|
MR2857193 |
| . |
| Date available:
|
2011-06-23T12:49:40Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141588 |
| . |
| Reference:
|
[1] Bini, D., Lotti, G., Romani, F.: Approximate solutions for the bilinear form computational problem.SIAM J. Comput. 9 (1980), 692–697. Zbl 0446.68035, MR 0592760, 10.1137/0209053 |
| Reference:
|
[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. Zbl 0202.19101, 10.1007/BF02310791 |
| Reference:
|
[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. |
| Reference:
|
[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. 10.1002/int.10080 |
| Reference:
|
[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. |
| Reference:
|
[6] Jensen, F. V.: Bayesian Networks and Decision Graphs.Springer-Verlag, New York 2001. Zbl 0973.62005, MR 1876880 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0939.68848, MR 1724104, 10.1016/S0004-3702(99)00062-4 |
| Reference:
|
[10] Olmsted, S. M.: On Representing and Solving Decision Problems.PhD. Thesis, Stanford University 1983. |
| Reference:
|
[11] Team, R Development Core: R: A Language and Environment for Statistical Computing.R Foundation for Statistical Computing, Vienna 2008. |
| Reference:
|
[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. Zbl 0266.65028, MR 0341833 |
| Reference:
|
[13] Savický, P., Vomlel, J.: Exploiting tensor rank-one decomposition in probabilistic inference.Kybernetika 43 (2007), 5, 747–764. Zbl 1148.68539, MR 2376335 |
| Reference:
|
[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. Zbl 1245.62019, MR 2893316 |
| Reference:
|
[15] Shafer, G. R., Shenoy, P. P.: Probability propagation.Ann. Math. Artif. Intell. 2 (1990), 1–4, 327–351. Zbl 0875.68676, MR 1215075, 10.1007/BF01531015 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[19]
: Wikipedia: Minesweeper (Computer game).http://en.wikipedia.org/wiki/Minesweeper_(computer_game). |
| . |
