The sum-product algorithm: algebraic independence and computational aspects

Francesco M. Malvestuto

Kybernetika (2013)

  • Volume: 49, Issue: 1, page 4-22
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Malvestuto, Francesco M.. "The sum-product algorithm: algebraic independence and computational aspects." Kybernetika 49.1 (2013): 4-22. <http://eudml.org/doc/252525>.

@article{Malvestuto2013,
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.},
author = {Malvestuto, Francesco M.},
journal = {Kybernetika},
keywords = {sum-product algorithm; distributive law; acyclic set system; junction tree; sum-product algorithm; belief propagation; graphical model; Bayesian network; junction tree},
language = {eng},
number = {1},
pages = {4-22},
publisher = {Institute of Information Theory and Automation AS CR},
title = {The sum-product algorithm: algebraic independence and computational aspects},
url = {http://eudml.org/doc/252525},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Malvestuto, Francesco M.
TI - The sum-product algorithm: algebraic independence and computational aspects
JO - Kybernetika
PY - 2013
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 1
SP - 4
EP - 22
AB - 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.
LA - eng
KW - sum-product algorithm; distributive law; acyclic set system; junction tree; sum-product algorithm; belief propagation; graphical model; Bayesian network; junction tree
UR - http://eudml.org/doc/252525
ER -

References

top
  1. Aji, S. M., McEliece, R. J., 10.1109/18.825794, IEEE Trans. Inform. Theory 46 (2000), 325-343. Zbl0998.65146MR1748973DOI10.1109/18.825794
  2. Beeri, C., Fagin, R., Maier, D., Yannakakis, M., 10.1145/2402.322389, J. Assoc. Comput. Mach. 30 (1983), 479-513. Zbl0624.68087MR0709830DOI10.1145/2402.322389
  3. Bernstein, P. A., Goodman, N., 10.1137/0210059, SIAM J. Comput. 10 (1981), 751-771. MR0635434DOI10.1137/0210059
  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. MR0970828
  5. Goodman, N., Shmueli, O., Tay, T., 10.1016/0022-0000(84)90004-7, J. Comput. and System Sci. 29 (1984), 338-358. MR0769592DOI10.1016/0022-0000(84)90004-7
  6. Kschinschang, F. R., Frey, B. J., Loeliger, H.-A., 10.1109/18.910572, IEEE Trans. Inform. Theory 47 (2001), 498-519. MR1820474DOI10.1109/18.910572
  7. Maier, D., Ullman, J. D., 10.1016/0304-3975(84)90030-6, Theoret. Comput. Sci. 32 (1984), 185-199. Zbl0557.05054MR0761167DOI10.1016/0304-3975(84)90030-6
  8. Malvestuto, F. M., 10.1016/0012-365X(88)90178-1, Discrete Math. 69 (1988), 61-77. Zbl0637.60021MR0935028DOI10.1016/0012-365X(88)90178-1
  9. Malvestuto, F. M., 10.1023/A:1014551721406, Ann. Math. Artif. Intel. 35 (2002), 253-285. Zbl1001.68033MR1899954DOI10.1023/A:1014551721406
  10. Mezzini, M., 10.1016/j.tcs.2011.04.022, Theoret. Comput. Sci. 412 (2011), 3775-3787. Zbl1220.05121MR2839718DOI10.1016/j.tcs.2011.04.022
  11. Tarjan, R. E., Yannakakis, M., 10.1137/0213035, SIAM J. Comput. 13 (1984), 566-579. Zbl0562.68055MR0749707DOI10.1137/0213035

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.