Dynamics of the Belief Propagation for the Ising Model

• Authors: G. Siudem , G. Świątek
• Languages of publication: EN

Abstracts

EN

The Belief Propagation algorithm is a popular technique of solving inference problems for different graph-like structures. We present a discussion of the dynamics of that algorithm for the Ising model on the square lattice. Our main goal was to describe limit fixed points for that algorithm, which are strictly connected with the marginal probabilities and stationary points of the Bethe Free Energy. Analytical considerations provide an exact analysis of a class of symmetrical points while numerical simulations confirm that for small lattices there are no non-symmetrical points. Notwithstanding the prevalent use of the Belief Propagation as an inference tool we present a sociophysical interpretation of its dynamics. In that case our considerations may be viewed as an investigation of the possible fixed points of the social dynamics.

Keywords

EN

05.10.-a; 05.45.-a; 89.65.-s

Discipline

• 89.65.-s: Social and economic systems
• 05.45.-a: Nonlinear dynamics and chaos(see also section 45 Classical mechanics of discrete systems; for chaos in fluid dynamics, see 47.52.+j; for chaos in superconductivity, see 74.40.De)
• 05.10.-a: Computational methods in statistical physics and nonlinear dynamics(see also 02.70.-c in mathematical methods in physics)

• Journal: Acta Physica Polonica A
• Year: 2015
• Volume: 127
• Issue: 3A
• Pages: A-145-A-149

Dates

published

2015-03

Contributors

author

G. Siudem

• Faculty of Physics, Warsaw University of Technology, Koszykowa 75, PL-00662 Warsaw, Poland
• Faculty of Mathematics and Information Science, Warsaw University of Technology, Koszykowa 75, PL-00662 Warsaw, Poland

author

G. Świątek

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Koszykowa 75, PL-00662 Warsaw, Poland

References

• [1] J. Pearl, Proceedings of the Second National Conference on Artificial Intelligence, 1982, p. 133
• [2] J.S. Yedidia, W.T. Freeman, Y. Weiss, Exploring Artificial Intelligence in the New Millennium, Eds. G. Lakemeyer, B. Nebel, Morgan Kaufmann Publishers, San Francisco 2003, Ch. 8, p. 239
• [3] G. Winkler, Image Analysis, Random Fields and Dynamic Monte Carlo Methods. A Mathematical Introduction, Springer-Verlag, New York 1991
• [4] P. Brémaud, Markov Chains, Gibbs Fields, Monte Carlo Simulation, And Queues, Springer-Verlag, New York 1999
• [5] B.M. McCoy, Advanced Statistical Mechanics, Oxford Univ. Press, Oxford 2010
• [6] R.J. Baxter Exactly Solved Models in Statistical Mechanics, Academic Press, London 1989
• [7] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Fransisco, 1988
• [8] C. Castellano, S. Fortunato, V. Loreto, Rev. Mod. Phys. 81, 591 (2009), doi: 10.1103/revmodphys.81.591
• [9] M.J. Krawczyk, K. Malarz, R. Korff, K. Kułakowski, Lect. Notes Artif. Int. 6421, 90 (2010), doi: 10.1007/978-3-642-16693-8_10
• [10] J. Sienkiewicz, G. Siudem, J.A. Hołyst, Phys. Rev. E 82, 057101, (2010), doi: 10.1103/PhysRevE.82.057101
• [11] A. Czaplicka, A. Chmiel, J.A. Hołyst, Acta Phys. Pol. A 117, 688 (2010)
• [12] K. Malarz, K. Kułakowski, Acta Phys. Pol. A 121, B86 (2012)
• [13] P. Nyczka, K. Sznajd-Weron, J. Cislo, Phys. Rev. E 86, 011105 (2012), doi: 10.1103/PhysRevE.86.011105
• [14] P. Nyczka, K. Sznajd-Weron, J. Stat. Phys., 151, 174 (2013), doi: 10.1007/s10955-013-0701-4
• [15] P. Sobkowicz, J. Artif. Soc. Soc. Simulat. 12, 11 (2009)
• [16] S. Yoon, A.V. Goltsev, S.N. Dorogovtsev, J.F.F. Mendes, Phys. Rev. E 84, 041144, (2011), doi: 10.1103/PhysRevE.84.041144
• [17] J. Ohkubo, M. Yasuda, K. Tanaka, Phys. Rev. E 72, 046135 (2005), doi: 10.1103/PhysRevE.72.046135
• [18] S. Dorogovtsev, A. Goltsev, J. Mendes, Rev. Mod. Phys. 80, 1275 (2008), doi: 10.1103/RevModPhys.80.1275
• [19] J.M. Mooij, H.J. Kappen, J. Stat. Mech. Theor. Exp. 11, P11012 (2005), doi: 10.1088/1742-5468/2005/11/P11012
• [20] G. Siudem, G. Świątek, Diagonal Stationary Points of Bethe's Free Energy, in preparation

Identifiers

DOI

10.12693/APhysPolA.127.A-145