Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
sum-product algorithm; distributive law; acyclic set system; junction tree
sum-product algorithm; distributive law; acyclic set system; junction tree
Summary:
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.
References:
[1] Aji, S. M., McEliece, R. J.: The generalized distributive law. IEEE Trans. Inform. Theory 46 (2000), 325-343. DOI 10.1109/18.825794 | MR 1748973 | Zbl 0998.65146
[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 10.1145/2402.322389 | MR 0709830 | Zbl 0624.68087
[3] Bernstein, P. A., Goodman, N.: The power of natural semijoins. SIAM J. Comput. 10 (1981), 751-771. DOI 10.1137/0210059 | MR 0635434
[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 0970828
[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 10.1016/0022-0000(84)90004-7 | MR 0769592
[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 10.1109/18.910572 | MR 1820474
[7] Maier, D., Ullman, J. D.: Connections in acyclic hypergraphs. Theoret. Comput. Sci. 32 (1984), 185-199. DOI 10.1016/0304-3975(84)90030-6 | MR 0761167 | Zbl 0557.05054
[8] Malvestuto, F. M.: Existence of extensions and product extensions for discrete probability distributions. Discrete Math. 69 (1988), 61-77. DOI 10.1016/0012-365X(88)90178-1 | MR 0935028 | Zbl 0637.60021
[9] Malvestuto, F. M.: From conditional independences to factorization constraints with discrete random variables. Ann. Math. Artif. Intel. 35 (2002), 253-285. DOI 10.1023/A:1014551721406 | MR 1899954 | Zbl 1001.68033
[10] Mezzini, M.: Fast minimal triangulation algorithm using minimum degree criterion. Theoret. Comput. Sci. 412 (2011), 3775-3787. DOI 10.1016/j.tcs.2011.04.022 | MR 2839718 | Zbl 1220.05121
[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 10.1137/0213035 | MR 0749707 | Zbl 0562.68055
Search
Partner of
