Kybernetika 49 no. 1, 4-22, 2013

The sum-product algorithm: algebraic independence and computational aspects

Francesco M. Malvestuto

Abstract:

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.

Keywords:

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

Classification:

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

References:

  1. S. M. Aji and R. J. McEliece: The generalized distributive law. IEEE Trans. Inform. Theory 46 (2000), 325-343.   CrossRef
  2. 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
  3. P. A. Bernstein and N. Goodman: The power of natural semijoins. SIAM J. Comput. 10 (1981), 751-771.   CrossRef
  4. 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
  5. 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
  6. 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
  7. D. Maier and J. D. Ullman: Connections in acyclic hypergraphs. Theoret. Comput. Sci. 32 (1984), 185-199.   CrossRef
  8. F. M. Malvestuto: Existence of extensions and product extensions for discrete probability distributions. Discrete Math. 69 (1988), 61-77.   CrossRef
  9. F. M. Malvestuto: From conditional independences to factorization constraints with discrete random variables. Ann. Math. Artif. Intel. 35 (2002), 253-285.   CrossRef
  10. M. Mezzini: Fast minimal triangulation algorithm using minimum degree criterion. Theoret. Comput. Sci. 412 (2011), 3775-3787.   CrossRef
  11. 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