Geodesic
The sum-product algorithm: algebraic independence and computational aspects
Kybernetika, Tome 49 (2013) no. 1, pp. 4-22 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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},
     year = {2013},
     volume = {49},
     number = {1},
     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
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
%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/

[1] Aji, S. M., McEliece, R. J.: The generalized distributive law. IEEE Trans. Inform. Theory 46 (2000), 325-343. | DOI | MR | Zbl

[2] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30 (1983), 479-513. | DOI | MR | Zbl

[3] Bernstein, P. A., Goodman, N.: The power of natural semijoins. SIAM J. Comput. 10 (1981), 751-771. | DOI | MR

[4] Goldman, S. A., Rivest, R. L.: Making maximum-entropy computations easier by adding extra constraints. In: Maximum-Entropy and Bayesian Methods in Science and Engineering 2 (G. J. Erikson and C. R. Smith, eds.), Kluwer Academic Pub. 1988, pp. 323-340. | MR

[5] Goodman, N., Shmueli, O., Tay, T.: GYO reductions, canonical connections, tree and cyclic schema, and tree projections. J. Comput. and System Sci. 29 (1984), 338-358. | DOI | MR

[6] Kschinschang, F. R., Frey, B. J., Loeliger, H.-A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory 47 (2001), 498-519. | DOI | MR

[7] Maier, D., Ullman, J. D.: Connections in acyclic hypergraphs. Theoret. Comput. Sci. 32 (1984), 185-199. | DOI | MR | Zbl

[8] Malvestuto, F. M.: Existence of extensions and product extensions for discrete probability distributions. Discrete Math. 69 (1988), 61-77. | DOI | MR | Zbl

[9] Malvestuto, F. M.: From conditional independences to factorization constraints with discrete random variables. Ann. Math. Artif. Intel. 35 (2002), 253-285. | DOI | MR | Zbl

[10] Mezzini, M.: Fast minimal triangulation algorithm using minimum degree criterion. Theoret. Comput. Sci. 412 (2011), 3775-3787. | DOI | MR | Zbl

[11] Tarjan, R. E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13 (1984), 566-579. | DOI | MR | Zbl