May  2017, 37(5): 2717-2743. doi: 10.3934/dcds.2017117

Diagonal stationary points of the bethe functional

1. 

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

2. 

Faculty of Mathematics and Information Science, Warsaw University of Technology, Koszykowa 75, PL-00-662 Warsaw, Poland

* Corresponding author: g.swiatek@mini.pw.edu.pl

Received  March 2016 Revised  December 2016 Published  February 2017

Fund Project: Both authors supported in part by Narodowe Centrum Nauki - grant 2015/17/B/ST1/00091.

We investigate stationary points of the Bethe functional for the Ising model on a $2$-dimensional lattice. Such stationary points are also fixed points of message passing algorithms. In the absence of an external field, by symmetry reasons one expects the fixed points to have constant means at all sites. This is shown not to be the case. There is a critical value of the coupling parameter which is equal to the phase transition parameter on the computation tree, see [13], above which fixed points appear with means that are variable though constant on diagonals of the lattice and hence the term “diagonal stationary points”. A rigorous analytic proof of their existence is presented. Furthermore, computer-obtained examples of diagonal stationary points which are local maxima of the Bethe functional and hence stable equilibria for message passing are shown. The smallest such example was found on the $100× 100$ lattice.

Citation: Grzegorz Siudem, Grzegorz Świątek. Diagonal stationary points of the bethe functional. Discrete & Continuous Dynamical Systems - A, 2017, 37 (5) : 2717-2743. doi: 10.3934/dcds.2017117
References:
[1]

R. J. Baxter, Exactly solved models in statistical mechanics, Integrable Systems in Statistical Mechanics, 1 (1985), 5-63.  doi: 10.1142/9789814415255_0002.  Google Scholar

[2]

H. A. Bethe, Statistical theory of superlattices, Selected Works of Hans A Bethe, 18 (1997), 245-270.  doi: 10.1142/9789812795755_0010.  Google Scholar

[3]

S. DorogovtsevA. Goltsev and J. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys., 80 (2008), 1275-1335.  doi: 10.1103/RevModPhys.80.1275.  Google Scholar

[4]

C. FortuinP. Kasteleyn and J. Ginibre, Correlation inequalities on some partially ordered sets, Commun. Math. Phys., 22 (1971), 89-103.  doi: 10.1007/BF01651330.  Google Scholar

[5]

T. Heskes, Stable fixed points of loopy belief propagation are local minima of the Bethe free energy, In S. Thrun S. Becker and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, MIT Press, Cambridge, MA, (2003), 343-350.   Google Scholar

[6]

J. M. Mooij and H. J. Kappen, On the properties of the Bethe approximation and loopy belief propagation on binary networks J. Stat. Mech. Theor. Exp. 11 (2005), P11012. doi: 10.1088/1742-5468/2005/11/P11012.  Google Scholar

[7]

J. M. Mooij and H. J. Kappen, Sufficient conditions for convergence of the sum-product algorithm, IEEE Transactions on Information Theory, 53 (2007), 4422-4437.  doi: 10.1109/TIT.2007.909166.  Google Scholar

[8]

S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology, 13 (1974), 9-18.  doi: 10.1016/0040-9383(74)90034-2.  Google Scholar

[9]

J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, Proceedings of the Second National Conference on Artificial Intelligence, (1982), 133-136.   Google Scholar

[10]

T. G. Roosta and M. J. Wainwright snd S. S. Sastry, Convergence analysis of reweighted sum-product algorithms, IEEE Transactions on Signal Processing, 56 (2008), 4293-4305.  doi: 10.1109/ICASSP.2007.366292.  Google Scholar

[11]

J. Shin, The complexity of approximating a bethe equilibrium, IEEE Transactions on Information Theory, 60 (2014), 3959-3969.  doi: 10.1109/TIT.2014.2317487.  Google Scholar

[12]

G. Siudem and G. Świątek, Dynamics of the belief propagation for the ising model, Acta Physica Polonica A, 127 (2015), 3A145-3A149.  doi: 10.12693/APhysPolA.127.A-145.  Google Scholar

[13]

S. Tatikonda and M. Jordan, Loopy belief propagation and Gibbs measures, in Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, San Francisco, (2002), 493-500, Google Scholar

[14]

M. J. Wainwright and M. I. Jordan, Graphical models, exponential families, and variational inference, Foundations and Trends in Machine Learning, 1 (2008), 1-305.  doi: 10.1561/2200000001.  Google Scholar

[15]

A. Weller and T. Jebara, Bethe bounds and approximating the global optimum, Journal of Machine Learning Research W& CP, 31 (2013), 618-631.   Google Scholar

[16]

M. Welling and Y. -W. Teh, Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation in Proc. 17th Conference on Uncertainty in Artificial Intelligence (UAI), 2001. Google Scholar

[17]

J. YedidiaW. Freeman and Y. Weiss, Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Trans. on Information Theory, 51 (2005), 2282-2312.  doi: 10.1109/TIT.2005.850085.  Google Scholar

show all references

References:
[1]

R. J. Baxter, Exactly solved models in statistical mechanics, Integrable Systems in Statistical Mechanics, 1 (1985), 5-63.  doi: 10.1142/9789814415255_0002.  Google Scholar

[2]

H. A. Bethe, Statistical theory of superlattices, Selected Works of Hans A Bethe, 18 (1997), 245-270.  doi: 10.1142/9789812795755_0010.  Google Scholar

[3]

S. DorogovtsevA. Goltsev and J. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys., 80 (2008), 1275-1335.  doi: 10.1103/RevModPhys.80.1275.  Google Scholar

[4]

C. FortuinP. Kasteleyn and J. Ginibre, Correlation inequalities on some partially ordered sets, Commun. Math. Phys., 22 (1971), 89-103.  doi: 10.1007/BF01651330.  Google Scholar

[5]

T. Heskes, Stable fixed points of loopy belief propagation are local minima of the Bethe free energy, In S. Thrun S. Becker and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, MIT Press, Cambridge, MA, (2003), 343-350.   Google Scholar

[6]

J. M. Mooij and H. J. Kappen, On the properties of the Bethe approximation and loopy belief propagation on binary networks J. Stat. Mech. Theor. Exp. 11 (2005), P11012. doi: 10.1088/1742-5468/2005/11/P11012.  Google Scholar

[7]

J. M. Mooij and H. J. Kappen, Sufficient conditions for convergence of the sum-product algorithm, IEEE Transactions on Information Theory, 53 (2007), 4422-4437.  doi: 10.1109/TIT.2007.909166.  Google Scholar

[8]

S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology, 13 (1974), 9-18.  doi: 10.1016/0040-9383(74)90034-2.  Google Scholar

[9]

J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, Proceedings of the Second National Conference on Artificial Intelligence, (1982), 133-136.   Google Scholar

[10]

T. G. Roosta and M. J. Wainwright snd S. S. Sastry, Convergence analysis of reweighted sum-product algorithms, IEEE Transactions on Signal Processing, 56 (2008), 4293-4305.  doi: 10.1109/ICASSP.2007.366292.  Google Scholar

[11]

J. Shin, The complexity of approximating a bethe equilibrium, IEEE Transactions on Information Theory, 60 (2014), 3959-3969.  doi: 10.1109/TIT.2014.2317487.  Google Scholar

[12]

G. Siudem and G. Świątek, Dynamics of the belief propagation for the ising model, Acta Physica Polonica A, 127 (2015), 3A145-3A149.  doi: 10.12693/APhysPolA.127.A-145.  Google Scholar

[13]

S. Tatikonda and M. Jordan, Loopy belief propagation and Gibbs measures, in Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, San Francisco, (2002), 493-500, Google Scholar

[14]

M. J. Wainwright and M. I. Jordan, Graphical models, exponential families, and variational inference, Foundations and Trends in Machine Learning, 1 (2008), 1-305.  doi: 10.1561/2200000001.  Google Scholar

[15]

A. Weller and T. Jebara, Bethe bounds and approximating the global optimum, Journal of Machine Learning Research W& CP, 31 (2013), 618-631.   Google Scholar

[16]

M. Welling and Y. -W. Teh, Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation in Proc. 17th Conference on Uncertainty in Artificial Intelligence (UAI), 2001. Google Scholar

[17]

J. YedidiaW. Freeman and Y. Weiss, Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Trans. on Information Theory, 51 (2005), 2282-2312.  doi: 10.1109/TIT.2005.850085.  Google Scholar

Figure 1.  Illustration of the diagonal matrix which can be obtained from means given by Eq. (11).
Figure 2.  Numerical evidence that the means (from Eq. (11), visualized on Fig. 1) in fact define a stationary point of the Bethe functional. The dots on the graph show values of the negative Bethe functional computed for the means given by vector $B_{\eta}$ given by formula (12) with $\eta$ shown on the horizontal axis and various randomly chosen $(X_{\ell})$.
Figure 3.  Values of the negative Bethe functional for the diagonal stationary point $\mathcal{B}_0$ perturbed in the direction of $P$ according to formula (12).
Figure 5.  The stability test algorithm.
Figure 4.  Stable fixed point given by Eq. (13).
[1]

Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems & Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066

[2]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067

[3]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065

[4]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389

[5]

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

[6]

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

[7]

Bilal Al Taki, Khawla Msheik, Jacques Sainte-Marie. On the rigid-lid approximation of shallow water Bingham. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 875-905. doi: 10.3934/dcdsb.2020146

[8]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178

[9]

Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048

[10]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322

[11]

Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168

[12]

Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213

[13]

Michiyuki Watanabe. Inverse $N$-body scattering with the time-dependent hartree-fock approximation. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021002

[14]

Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350

[15]

Xiaoli Lu, Pengzhan Huang, Yinnian He. Fully discrete finite element approximation of the 2D/3D unsteady incompressible magnetohydrodynamic-Voigt regularization flows. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 815-845. doi: 10.3934/dcdsb.2020143

[16]

Simone Göttlich, Elisa Iacomini, Thomas Jung. Properties of the LWR model with time delay. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020032

[17]

Ténan Yeo. Stochastic and deterministic SIS patch model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021012

[18]

M. Dambrine, B. Puig, G. Vallet. A mathematical model for marine dinoflagellates blooms. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 615-633. doi: 10.3934/dcdss.2020424

[19]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457

[20]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (75)
  • HTML views (52)
  • Cited by (0)

Other articles
by authors

[Back to Top]