Geodesic
Rank of tensors of $\ell $-out-of-$k$ functions: An application in probabilistic inference
Kybernetika, Tome 47 (2011) no. 3, pp. 317-336.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {47},
     number = {3},
     year = {2011},
     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
PB  - mathdoc
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
%I mathdoc
%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/