# American Institute of Mathematical Sciences

August  2012, 6(3): 363-384. doi: 10.3934/amc.2012.6.363

## 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, Serbia 2 University of Niš, Faculty of Occupational Safety, Čarnojevića 10a, 18000 Niš, Serbia, Serbia

Received  November 2011 Revised  May 2012 Published  August 2012

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.
Citation: Velimir M. Ilić, Miomir S. Stanković, Branimir T. Todorović. Computation of cross-moments using message passing over factor graphs. Advances in Mathematics of Communications, 2012, 6 (3) : 363-384. doi: 10.3934/amc.2012.6.363
##### 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.

show all references

##### 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.
 [1] Peter Bella, Arianna Giunti. Green's function for elliptic systems: Moment bounds. Networks and Heterogeneous Media, 2018, 13 (1) : 155-176. doi: 10.3934/nhm.2018007 [2] Armin Eftekhari, Michael B. Wakin, Ping Li, Paul G. Constantine. Randomized learning of the second-moment matrix of a smooth function. Foundations of Data Science, 2019, 1 (3) : 329-387. doi: 10.3934/fods.2019015 [3] Josephus Hulshof, Pascal Noble. Travelling waves for a combustion model coupled with hyperbolic radiation moment models. Discrete and Continuous Dynamical Systems - B, 2008, 10 (1) : 73-90. doi: 10.3934/dcdsb.2008.10.73 [4] Pierre Degond, Amic Frouvelle, Jian-Guo Liu. From kinetic to fluid models of liquid crystals by the moment method. Kinetic and Related Models, 2022, 15 (3) : 417-465. doi: 10.3934/krm.2021047 [5] Sho Matsumoto, Jonathan Novak. A moment method for invariant ensembles. Electronic Research Announcements, 2018, 25: 60-71. doi: 10.3934/era.2018.25.007 [6] Florian Schneider. Second-order mixed-moment model with differentiable ansatz function in slab geometry. Kinetic and Related Models, 2018, 11 (5) : 1255-1276. doi: 10.3934/krm.2018049 [7] Cruz Vargas-De-León, Alberto d'Onofrio. Global stability of infectious disease models with contact rate as a function of prevalence index. Mathematical Biosciences & Engineering, 2017, 14 (4) : 1019-1033. doi: 10.3934/mbe.2017053 [8] Zhenning Cai, Yuwei Fan, Ruo Li. On hyperbolicity of 13-moment system. Kinetic and Related Models, 2014, 7 (3) : 415-432. doi: 10.3934/krm.2014.7.415 [9] Gilberto M. Kremer, Wilson Marques Jr.. Fourteen moment theory for granular gases. Kinetic and Related Models, 2011, 4 (1) : 317-331. doi: 10.3934/krm.2011.4.317 [10] Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete and Continuous Dynamical Systems - S, 2021, 14 (10) : 3803-3819. doi: 10.3934/dcdss.2021019 [11] Swann Marx, Tillmann Weisser, Didier Henrion, Jean Bernard Lasserre. A moment approach for entropy solutions to nonlinear hyperbolic PDEs. Mathematical Control and Related Fields, 2020, 10 (1) : 113-140. doi: 10.3934/mcrf.2019032 [12] Laurent Baratchart, Sylvain Chevillard, Douglas Hardin, Juliette Leblond, Eduardo Andrade Lima, Jean-Paul Marmorat. Magnetic moment estimation and bounded extremal problems. Inverse Problems and Imaging, 2019, 13 (1) : 39-67. doi: 10.3934/ipi.2019003 [13] Henning Struchtrup. Unique moment set from the order of magnitude method. Kinetic and Related Models, 2012, 5 (2) : 417-440. doi: 10.3934/krm.2012.5.417 [14] Darryl D. Holm, Cesare Tronci. Geodesic Vlasov equations and their integrable moment closures. Journal of Geometric Mechanics, 2009, 1 (2) : 181-208. doi: 10.3934/jgm.2009.1.181 [15] Miroslava Růžičková, Irada Dzhalladova, Jitka Laitochová, Josef Diblík. Solution to a stochastic pursuit model using moment equations. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 473-485. doi: 10.3934/dcdsb.2018032 [16] Florian Méhats, Olivier Pinaud. A problem of moment realizability in quantum statistical physics. Kinetic and Related Models, 2011, 4 (4) : 1143-1158. doi: 10.3934/krm.2011.4.1143 [17] Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic and Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291 [18] Julian Koellermeier, Giovanni Samaey. Projective integration schemes for hyperbolic moment equations. Kinetic and Related Models, 2021, 14 (2) : 353-387. doi: 10.3934/krm.2021008 [19] Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021151 [20] Henri Schurz. Moment attractivity, stability and contractivity exponents of stochastic dynamical systems. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 487-515. doi: 10.3934/dcds.2001.7.487

2021 Impact Factor: 1.015