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.

junction tree, sum-product algorithm, distributive law, acyclic set system

47A67, 62-09, 62c10, 68P15, 68W30

- S. M. Aji and R. J. McEliece: The generalized distributive law. IEEE Trans. Inform. Theory 46 (2000), 325-343. CrossRef
- C. Beeri, R. Fagin, D. Maier and M. Yannakakis: On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30 (1983), 479-513. CrossRef
- P. A. Bernstein and N. Goodman: The power of natural semijoins. SIAM J. Comput. 10 (1981), 751-771. CrossRef
- S. A. Goldman and R. L. Rivest: 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. CrossRef
- N. Goodman, O. Shmueli and T. Tay: GYO reductions, canonical connections, tree and cyclic schema, and tree projections. J. Comput. and System Sci. 29 (1984), 338-358. CrossRef
- F. R. Kschinschang, B. J. Frey and H.-A. Loeliger: Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory 47 (2001), 498-519. CrossRef
- D. Maier and J. D. Ullman: Connections in acyclic hypergraphs. Theoret. Comput. Sci. 32 (1984), 185-199. CrossRef
- F. M. Malvestuto: Existence of extensions and product extensions for discrete probability distributions. Discrete Math. 69 (1988), 61-77. CrossRef
- F. M. Malvestuto: From conditional independences to factorization constraints with discrete random variables. Ann. Math. Artif. Intel. 35 (2002), 253-285. CrossRef
- M. Mezzini: Fast minimal triangulation algorithm using minimum degree criterion. Theoret. Comput. Sci. 412 (2011), 3775-3787. CrossRef
- R. E. Tarjan and M. Yannakakis: 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. CrossRef