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.
In probability theory, Bayesian statistics, artificial intelligence and database theory the minimum cross-entropy principle is often used to estimate a distribution with a given set P of marginal distributions under the proportionality assumption with respect to a given "prior'' distribution q. Such an estimation problem admits a solution if and only if there exists an extension of P that is dominated by q. In this paper we consider the case that q is not given explicitly, but is specified as the maximum-entropy extension of an auxiliary set Q of distributions. There are three problems that naturally arise: (1) the existence of an extension of a distribution set (such as P and Q), (2) the existence of an extension of P that is dominated by the maximum entropy extension of Q, (3) the numeric computation of the minimum cross-entropy extension of P with respect to the maximum entropy extension of Q. In the spirit of a divide-and-conquer approach, we prove that, for each of the three above-mentioned problems, the global solution can be easily obtained by combining the solutions to subproblems defined at node level of a suitable tree.