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]

Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[2]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[3]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364

[4]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[5]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345

[6]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010

[7]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[8]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

[9]

Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256

[10]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[11]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[12]

Annegret Glitzky, Matthias Liero, Grigor Nika. Dimension reduction of thermistor models for large-area organic light-emitting diodes. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020460

2019 Impact Factor: 0.734

Metrics

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

[Back to Top]