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

Metrics

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

[Back to Top]