Geodesic
The sum-product algorithm: algebraic independence and computational aspects
Kybernetika, Tome 49 (2013) no. 1, pp. 4-22.

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

The sum-product algorithm is a well-known procedure for marginalizing an “acyclic” product function whose range is the ground set of a commutative semiring. The algorithm is general enough to include as special cases several classical algorithms developed in information theory and probability theory. We present four results. First, using the sum-product algorithm we show that the variable sets involved in an acyclic factorization satisfy a relation that is a natural generalization of probability-theoretic independence. Second, we show that for the Boolean semiring the sum-product algorithm reduces to a classical algorithm of database theory. Third, we present some methods to reduce the amount of computation required by the sum-product algorithm. Fourth, we show that with a slight modification the sum-product algorithm can be used to evaluate a general sum-product expression.
Classification : 47A67, 62-09, 62C10, 68P15, 68W30
Keywords: sum-product algorithm; distributive law; acyclic set system; junction tree 
@article{KYB_2013__49_1_a1,
     author = {Malvestuto, Francesco M.},
     title = {The sum-product algorithm: algebraic independence and computational aspects},
     journal = {Kybernetika},
     pages = {4--22},
     publisher = {mathdoc},
     volume = {49},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2013__49_1_a1/}
}
TY  - JOUR
AU  - Malvestuto, Francesco M.
TI  - The sum-product algorithm: algebraic independence and computational aspects
JO  - Kybernetika
PY  - 2013
SP  - 4
EP  - 22
VL  - 49
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2013__49_1_a1/
LA  - en
ID  - KYB_2013__49_1_a1
ER  - 
%0 Journal Article
%A Malvestuto, Francesco M.
%T The sum-product algorithm: algebraic independence and computational aspects
%J Kybernetika
%D 2013
%P 4-22
%V 49
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2013__49_1_a1/
%G en
%F KYB_2013__49_1_a1
Malvestuto, Francesco M. The sum-product algorithm: algebraic independence and computational aspects. Kybernetika, Tome 49 (2013) no. 1, pp. 4-22. http://geodesic.mathdoc.fr/item/KYB_2013__49_1_a1/