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.

[2]

A. Azuma and Y. Matsumoto, A generalization of forward-backward algorithm,, in, (2009), 99. doi: 10.1007/978-3-642-04180-8_24.

[3]

C. M. Bishop, "Pattern Recognition and Machine Learning (Information Science and Statistics),'', Springer-Verlag, (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.

[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).

[6]

R. Gallager, Low-density parity-check codes,, IRE Trans. Inform. Theory, 8 (1962), 21. 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. 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. 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. 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. doi: 10.1109/18.910572.

[11]

A. Kulesza and B. Taskar, Structured determinantal point processes,, in, (2011).

[12]

Z. Li and J. Eisner, First- and second-order expectation semirings with applications to minimum-risk training on translation forests,, in, (2009), 40.

[13]

D. MacKay, Good error-correcting codes based on very sparse matrices,, IEEE Trans. Inform. Theory, 45 (1999), 399. 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, (1999), 467.

[16]

M. Protter, "Basic Elements of Real Analysis,'', Springer, (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. 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. 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. doi: 10.1109/18.825794.

[2]

A. Azuma and Y. Matsumoto, A generalization of forward-backward algorithm,, in, (2009), 99. doi: 10.1007/978-3-642-04180-8_24.

[3]

C. M. Bishop, "Pattern Recognition and Machine Learning (Information Science and Statistics),'', Springer-Verlag, (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.

[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).

[6]

R. Gallager, Low-density parity-check codes,, IRE Trans. Inform. Theory, 8 (1962), 21. 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. 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. 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. 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. doi: 10.1109/18.910572.

[11]

A. Kulesza and B. Taskar, Structured determinantal point processes,, in, (2011).

[12]

Z. Li and J. Eisner, First- and second-order expectation semirings with applications to minimum-risk training on translation forests,, in, (2009), 40.

[13]

D. MacKay, Good error-correcting codes based on very sparse matrices,, IEEE Trans. Inform. Theory, 45 (1999), 399. 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, (1999), 467.

[16]

M. Protter, "Basic Elements of Real Analysis,'', Springer, (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. 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. doi: 10.1109/TIT.2005.850085.

[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]

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

[3]

Sho Matsumoto, Jonathan Novak. A moment method for invariant ensembles. Electronic Research Announcements, 2018, 25: 60-71. doi: 10.3934/era.2018.25.007

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Jessy Mallet, Stéphane Brull, Bruno Dubroca. General moment system for plasma physics based on minimum entropy principle. Kinetic & Related Models, 2015, 8 (3) : 533-558. doi: 10.3934/krm.2015.8.533

2018 Impact Factor: 0.879

Metrics

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

[Back to Top]