| Title:
|
The sum-product algorithm: algebraic independence and computational aspects (English) |
| Author:
|
Malvestuto, Francesco M. |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
49 |
| Issue:
|
1 |
| Year:
|
2013 |
| Pages:
|
4-22 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
sum-product algorithm |
| Keyword:
|
distributive law |
| Keyword:
|
acyclic set system |
| Keyword:
|
junction tree |
| MSC:
|
47A67 |
| MSC:
|
62-09 |
| MSC:
|
62C10 |
| MSC:
|
68P15 |
| MSC:
|
68W30 |
| . |
| Date available:
|
2013-03-05T15:02:23Z |
| Last updated:
|
2013-07-31 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143237 |
| . |
| Reference:
|
[1] Aji, S. M., McEliece, R. J.: The generalized distributive law..IEEE Trans. Inform. Theory 46 (2000), 325-343. Zbl 0998.65146, MR 1748973, 10.1109/18.825794 |
| Reference:
|
[2] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes..J. Assoc. Comput. Mach. 30 (1983), 479-513. Zbl 0624.68087, MR 0709830, 10.1145/2402.322389 |
| Reference:
|
[3] Bernstein, P. A., Goodman, N.: The power of natural semijoins..SIAM J. Comput. 10 (1981), 751-771. MR 0635434, 10.1137/0210059 |
| Reference:
|
[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 |
| Reference:
|
[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. MR 0769592, 10.1016/0022-0000(84)90004-7 |
| Reference:
|
[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. MR 1820474, 10.1109/18.910572 |
| Reference:
|
[7] Maier, D., Ullman, J. D.: Connections in acyclic hypergraphs..Theoret. Comput. Sci. 32 (1984), 185-199. Zbl 0557.05054, MR 0761167, 10.1016/0304-3975(84)90030-6 |
| Reference:
|
[8] Malvestuto, F. M.: Existence of extensions and product extensions for discrete probability distributions..Discrete Math. 69 (1988), 61-77. Zbl 0637.60021, MR 0935028, 10.1016/0012-365X(88)90178-1 |
| Reference:
|
[9] Malvestuto, F. M.: From conditional independences to factorization constraints with discrete random variables..Ann. Math. Artif. Intel. 35 (2002), 253-285. Zbl 1001.68033, MR 1899954, 10.1023/A:1014551721406 |
| Reference:
|
[10] Mezzini, M.: Fast minimal triangulation algorithm using minimum degree criterion..Theoret. Comput. Sci. 412 (2011), 3775-3787. Zbl 1220.05121, MR 2839718, 10.1016/j.tcs.2011.04.022 |
| Reference:
|
[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. Zbl 0562.68055, MR 0749707, 10.1137/0213035 |
| . |
