Computation of cross-moments using message passing over factor graphs

Velimir M. Ilić; Miomir S. Stanković; Branimir T. Todorović

doi:10.3934/amc.2012.6.363

Article Contents

2012, Volume 6, Issue 3: 363-384. Doi: 10.3934/amc.2012.6.363

This issue Previous Article Cycle structure of permutation functions over finite fields and their applications Next Article

Computation of cross-moments using message passing over factor graphs

1.
Mathematical Institute of the Serbian Academy of Sciences and Arts, Kneza Mihaila 36, 11000 Beograd
2.
University of Niš, Faculty of Occupational Safety, Čarnojevića 10a, 18000 Niš

Received: November 2011

Revised: May 2012

Published online: August 2012

Abstract / Introduction Related Papers Cited by

Abstract

This paper considers the problem of cross-moments computation for functions which decompose according to cycle-free factor graphs. Two algorithms are derived, both based on message passing computation of a corresponding moment-generating function ($MGF$). The first one is realized as message passing algorithm over a polynomial semiring and represents a computation of the $MGF$ Taylor coefficients, while the second one represents message passing algorithm over a binomial semiring and a computation of the $MGF$ partial derivatives. We found that some previously developed algorithms can be seen as special cases of our algorithms and we consider the time and memory complexities.

Keywords:

Mathematics Subject Classification: Primary: 68W05, 94A15; Secondary: 68R01.

Citation:

Related Papers

Cited by

References

[1]	S. Aji and R. McEliece, The generalized distributive law, IEEE Trans. Inform. Theory, 46 (2000), 325-343.doi: 10.1109/18.825794.
[2]	A. Azuma and Y. Matsumoto, A generalization of forward-backward algorithm, in "Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases: Part I,'' Springer-Verlag, Berlin, Heidelberg, (2009), 99-114.doi: 10.1007/978-3-642-04180-8_24.
[3]	C. M. Bishop, "Pattern Recognition and Machine Learning (Information Science and Statistics),'' Springer-Verlag, New York, 2006.
[4]	C. Cortes, M. Mohri, A. Rastogi and M. Riley, On the computation of the relative entropy of probabilistic automata, Int. J. Found. Comput. Sci., 19 (2008), 219-242.
[5]	R. G. Cowell, P. A. Dawid, S. L. Lauritzen and D. J. Spiegelhalter, "Probabilistic Networks and Expert Systems (Information Science and Statistics),'' Springer, New York, 2003.
[6]	R. Gallager, Low-density parity-check codes, IRE Trans. Inform. Theory, 8 (1962), 21-28.doi: 10.1109/TIT.1962.1057683.
[7]	S. Golomb, The information generating function of a probability distribution (corresp.), IEEE Trans. Inform. Theory, 12 (1966), 75-77.doi: 10.1109/TIT.1966.1053843.
[8]	A. Heim, V. Sidorenko and U. Sorger, Computation of distributions and their moments in the trellis, Adv. Math. Commun., 2 (2008), 373-391.doi: 10.3934/amc.2008.2.373.
[9]	V. M. Ilic, M. S. Stankovic and B. T. Todorovic, Entropy message passing, IEEE Trans. Inform. Theory, 57 (2011), 219-242.doi: 10.1109/TIT.2010.2090235.
[10]	F. Kschischang, B. Frey and H.-A. Loeliger, Factor graphs and the sum-product algorithm, IEEE Trans. Inform. Theory, 47 (2001), 498-519.doi: 10.1109/18.910572.
[11]	A. Kulesza and B. Taskar, Structured determinantal point processes, in "Advances in Neural Information Processing Systems 23,'' 2011.
[12]	Z. Li and J. Eisner, First- and second-order expectation semirings with applications to minimum-risk training on translation forests, in "Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 1,'' Association for Computational Linguistics, Stroudsburg, PA, (2009), 40-51.
[13]	D. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, 45 (1999), 399-431.doi: 10.1109/18.748992.
[14]	D. J. C. MacKay, "Information Theory, Inference, and Learning Algorithms,'' Cambridge University Press, 2003.
[15]	K. P. Murphy, Y. Weiss and M. I. Jordan, Loopy belief propagation for approximate inference: an empirical study, in "Proceedings of Uncertainty in AI,'' (1999), 467-475.
[16]	M. Protter, "Basic Elements of Real Analysis,'' Springer, New York, 1998.
[17]	T. Richardson and R. Urbanke, "Modern Coding Theory,'' Cambridge University Press, 2008.doi: 10.1017/CBO9780511791338.
[18]	Y. Weiss, Correctness of local probability propagation in graphical models with loops, Neural Computation, 12 (2000), 1-41.doi: 10.1162/089976600300015880.
[19]	J. Yedidia, W. Freeman and Y. Weiss, Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Trans. Inform. Theory, 51 (2005), 2282-2312.doi: 10.1109/TIT.2005.850085.