# 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. doi: 10.1109/18.825794. Google Scholar [2] A. Azuma and Y. Matsumoto, A generalization of forward-backward algorithm,, in, (2009), 99. doi: 10.1007/978-3-642-04180-8_24. Google Scholar [3] C. M. Bishop, "Pattern Recognition and Machine Learning (Information Science and Statistics),'', Springer-Verlag, (2006). Google Scholar [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. Google Scholar [5] R. G. Cowell, P. A. Dawid, S. L. Lauritzen and D. J. Spiegelhalter, "Probabilistic Networks and Expert Systems (Information Science and Statistics),'', Springer, (2003). Google Scholar [6] R. Gallager, Low-density parity-check codes,, IRE Trans. Inform. Theory, 8 (1962), 21. doi: 10.1109/TIT.1962.1057683. Google Scholar [7] S. Golomb, The information generating function of a probability distribution (corresp.),, IEEE Trans. Inform. Theory, 12 (1966), 75. doi: 10.1109/TIT.1966.1053843. Google Scholar [8] A. Heim, V. Sidorenko and U. Sorger, Computation of distributions and their moments in the trellis,, Adv. Math. Commun., 2 (2008), 373. doi: 10.3934/amc.2008.2.373. Google Scholar [9] V. M. Ilic, M. S. Stankovic and B. T. Todorovic, Entropy message passing,, IEEE Trans. Inform. Theory, 57 (2011), 219. doi: 10.1109/TIT.2010.2090235. Google Scholar [10] F. Kschischang, B. Frey and H.-A. Loeliger, Factor graphs and the sum-product algorithm,, IEEE Trans. Inform. Theory, 47 (2001), 498. doi: 10.1109/18.910572. Google Scholar [11] A. Kulesza and B. Taskar, Structured determinantal point processes,, in, (2011). Google Scholar [12] Z. Li and J. Eisner, First- and second-order expectation semirings with applications to minimum-risk training on translation forests,, in, (2009), 40. Google Scholar [13] D. MacKay, Good error-correcting codes based on very sparse matrices,, IEEE Trans. Inform. Theory, 45 (1999), 399. doi: 10.1109/18.748992. Google Scholar [14] D. J. C. MacKay, "Information Theory, Inference, and Learning Algorithms,'', Cambridge University Press, (2003). Google Scholar [15] K. P. Murphy, Y. Weiss and M. I. Jordan, Loopy belief propagation for approximate inference: an empirical study,, in, (1999), 467. Google Scholar [16] M. Protter, "Basic Elements of Real Analysis,'', Springer, (1998). Google Scholar [17] T. Richardson and R. Urbanke, "Modern Coding Theory,'', Cambridge University Press, (2008). doi: 10.1017/CBO9780511791338. Google Scholar [18] Y. Weiss, Correctness of local probability propagation in graphical models with loops,, Neural Computation, 12 (2000), 1. doi: 10.1162/089976600300015880. Google Scholar [19] J. Yedidia, W. Freeman and Y. Weiss, Constructing free-energy approximations and generalized belief propagation algorithms,, IEEE Trans. Inform. Theory, 51 (2005), 2282. doi: 10.1109/TIT.2005.850085. Google Scholar

show all references

##### References:
 [1] S. Aji and R. McEliece, The generalized distributive law,, IEEE Trans. Inform. Theory, 46 (2000), 325. doi: 10.1109/18.825794. Google Scholar [2] A. Azuma and Y. Matsumoto, A generalization of forward-backward algorithm,, in, (2009), 99. doi: 10.1007/978-3-642-04180-8_24. Google Scholar [3] C. M. Bishop, "Pattern Recognition and Machine Learning (Information Science and Statistics),'', Springer-Verlag, (2006). Google Scholar [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. Google Scholar [5] R. G. Cowell, P. A. Dawid, S. L. Lauritzen and D. J. Spiegelhalter, "Probabilistic Networks and Expert Systems (Information Science and Statistics),'', Springer, (2003). Google Scholar [6] R. Gallager, Low-density parity-check codes,, IRE Trans. Inform. Theory, 8 (1962), 21. doi: 10.1109/TIT.1962.1057683. Google Scholar [7] S. Golomb, The information generating function of a probability distribution (corresp.),, IEEE Trans. Inform. Theory, 12 (1966), 75. doi: 10.1109/TIT.1966.1053843. Google Scholar [8] A. Heim, V. Sidorenko and U. Sorger, Computation of distributions and their moments in the trellis,, Adv. Math. Commun., 2 (2008), 373. doi: 10.3934/amc.2008.2.373. Google Scholar [9] V. M. Ilic, M. S. Stankovic and B. T. Todorovic, Entropy message passing,, IEEE Trans. Inform. Theory, 57 (2011), 219. doi: 10.1109/TIT.2010.2090235. Google Scholar [10] F. Kschischang, B. Frey and H.-A. Loeliger, Factor graphs and the sum-product algorithm,, IEEE Trans. Inform. Theory, 47 (2001), 498. doi: 10.1109/18.910572. Google Scholar [11] A. Kulesza and B. Taskar, Structured determinantal point processes,, in, (2011). Google Scholar [12] Z. Li and J. Eisner, First- and second-order expectation semirings with applications to minimum-risk training on translation forests,, in, (2009), 40. Google Scholar [13] D. MacKay, Good error-correcting codes based on very sparse matrices,, IEEE Trans. Inform. Theory, 45 (1999), 399. doi: 10.1109/18.748992. Google Scholar [14] D. J. C. MacKay, "Information Theory, Inference, and Learning Algorithms,'', Cambridge University Press, (2003). Google Scholar [15] K. P. Murphy, Y. Weiss and M. I. Jordan, Loopy belief propagation for approximate inference: an empirical study,, in, (1999), 467. Google Scholar [16] M. Protter, "Basic Elements of Real Analysis,'', Springer, (1998). Google Scholar [17] T. Richardson and R. Urbanke, "Modern Coding Theory,'', Cambridge University Press, (2008). doi: 10.1017/CBO9780511791338. Google Scholar [18] Y. Weiss, Correctness of local probability propagation in graphical models with loops,, Neural Computation, 12 (2000), 1. doi: 10.1162/089976600300015880. Google Scholar [19] J. Yedidia, W. Freeman and Y. Weiss, Constructing free-energy approximations and generalized belief propagation algorithms,, IEEE Trans. Inform. Theory, 51 (2005), 2282. doi: 10.1109/TIT.2005.850085. Google Scholar
 [1] Peter Bella, Arianna Giunti. Green's function for elliptic systems: Moment bounds. Networks & 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 & Continuous Dynamical Systems - B, 2008, 10 (1) : 73-90. doi: 10.3934/dcdsb.2008.10.73 [4] Sho Matsumoto, Jonathan Novak. A moment method for invariant ensembles. Electronic Research Announcements, 2018, 25: 60-71. doi: 10.3934/era.2018.25.007 [5] Florian Schneider. Second-order mixed-moment model with differentiable ansatz function in slab geometry. Kinetic & Related Models, 2018, 11 (5) : 1255-1276. doi: 10.3934/krm.2018049 [6] 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 [7] Zhenning Cai, Yuwei Fan, Ruo Li. On hyperbolicity of 13-moment system. Kinetic & Related Models, 2014, 7 (3) : 415-432. doi: 10.3934/krm.2014.7.415 [8] Gilberto M. Kremer, Wilson Marques Jr.. Fourteen moment theory for granular gases. Kinetic & Related Models, 2011, 4 (1) : 317-331. doi: 10.3934/krm.2011.4.317 [9] Henning Struchtrup. Unique moment set from the order of magnitude method. Kinetic & Related Models, 2012, 5 (2) : 417-440. doi: 10.3934/krm.2012.5.417 [10] 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 [11] Miroslava Růžičková, Irada Dzhalladova, Jitka Laitochová, Josef Diblík. Solution to a stochastic pursuit model using moment equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 473-485. doi: 10.3934/dcdsb.2018032 [12] Florian Méhats, Olivier Pinaud. A problem of moment realizability in quantum statistical physics. Kinetic & Related Models, 2011, 4 (4) : 1143-1158. doi: 10.3934/krm.2011.4.1143 [13] Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic & Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291 [14] Laurent Baratchart, Sylvain Chevillard, Douglas Hardin, Juliette Leblond, Eduardo Andrade Lima, Jean-Paul Marmorat. Magnetic moment estimation and bounded extremal problems. Inverse Problems & Imaging, 2019, 13 (1) : 39-67. doi: 10.3934/ipi.2019003 [15] Swann Marx, Tillmann Weisser, Didier Henrion, Jean Bernard Lasserre. A moment approach for entropy solutions to nonlinear hyperbolic PDEs. Mathematical Control & Related Fields, 2019, 0 (0) : 0-0. doi: 10.3934/mcrf.2019032 [16] Henri Schurz. Moment attractivity, stability and contractivity exponents of stochastic dynamical systems. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 487-515. doi: 10.3934/dcds.2001.7.487 [17] YunKyong Hyon. Hysteretic behavior of a moment-closure approximation for FENE model. Kinetic & Related Models, 2014, 7 (3) : 493-507. doi: 10.3934/krm.2014.7.493 [18] Youngae Lee. Topological solutions in the Maxwell-Chern-Simons model with anomalous magnetic moment. Discrete & Continuous Dynamical Systems - A, 2018, 38 (3) : 1293-1314. doi: 10.3934/dcds.2018053 [19] Luciano Pandolfi. Riesz systems and moment method in the study of viscoelasticity in one space dimension. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1487-1510. doi: 10.3934/dcdsb.2010.14.1487 [20] T. Hillen. On the $L^2$-moment closure of transport equations: The general case. Discrete & Continuous Dynamical Systems - B, 2005, 5 (2) : 299-318. doi: 10.3934/dcdsb.2005.5.299

2018 Impact Factor: 0.879

## Metrics

• PDF downloads (6)
• HTML views (0)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]