# American Institute of Mathematical Sciences

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 and Continuous Dynamical Systems, 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. [2] H. A. Bethe, Statistical theory of superlattices, Selected Works of Hans A Bethe, 18 (1997), 245-270.  doi: 10.1142/9789812795755_0010. [3] S. Dorogovtsev, A. Goltsev and J. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys., 80 (2008), 1275-1335.  doi: 10.1103/RevModPhys.80.1275. [4] C. Fortuin, P. Kasteleyn and J. Ginibre, Correlation inequalities on some partially ordered sets, Commun. Math. Phys., 22 (1971), 89-103.  doi: 10.1007/BF01651330. [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. [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. [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. [8] S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology, 13 (1974), 9-18.  doi: 10.1016/0040-9383(74)90034-2. [9] J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, Proceedings of the Second National Conference on Artificial Intelligence, (1982), 133-136. [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. [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. [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. [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, [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. [15] A. Weller and T. Jebara, Bethe bounds and approximating the global optimum, Journal of Machine Learning Research W& CP, 31 (2013), 618-631. [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. [17] J. Yedidia, W. 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.

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. [2] H. A. Bethe, Statistical theory of superlattices, Selected Works of Hans A Bethe, 18 (1997), 245-270.  doi: 10.1142/9789812795755_0010. [3] S. Dorogovtsev, A. Goltsev and J. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys., 80 (2008), 1275-1335.  doi: 10.1103/RevModPhys.80.1275. [4] C. Fortuin, P. Kasteleyn and J. Ginibre, Correlation inequalities on some partially ordered sets, Commun. Math. Phys., 22 (1971), 89-103.  doi: 10.1007/BF01651330. [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. [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. [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. [8] S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology, 13 (1974), 9-18.  doi: 10.1016/0040-9383(74)90034-2. [9] J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, Proceedings of the Second National Conference on Artificial Intelligence, (1982), 133-136. [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. [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. [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. [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, [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. [15] A. Weller and T. Jebara, Bethe bounds and approximating the global optimum, Journal of Machine Learning Research W& CP, 31 (2013), 618-631. [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. [17] J. Yedidia, W. 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.
Illustration of the diagonal matrix which can be obtained from means given by Eq. (11).
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})$.
Values of the negative Bethe functional for the diagonal stationary point $\mathcal{B}_0$ perturbed in the direction of $P$ according to formula (12).
The stability test algorithm.
Stable fixed point given by Eq. (13).
 [1] 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 [2] Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427 [3] Michele Gianfelice, Marco Isopi. On the location of the 1-particle branch of the spectrum of the disordered stochastic Ising model. Networks and Heterogeneous Media, 2011, 6 (1) : 127-144. doi: 10.3934/nhm.2011.6.127 [4] Robert Baier, Matthias Gerdts, Ilaria Xausa. Approximation of reachable sets using optimal control algorithms. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 519-548. doi: 10.3934/naco.2013.3.519 [5] Manuel González-Navarrete. Type-dependent stochastic Ising model describing the dynamics of a non-symmetric feedback module. Mathematical Biosciences & Engineering, 2016, 13 (5) : 981-998. doi: 10.3934/mbe.2016026 [6] Lori Badea, Marius Cocou. Approximation results and subspace correction algorithms for implicit variational inequalities. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1507-1524. doi: 10.3934/dcdss.2013.6.1507 [7] Fanghua Lin, Juncheng Wei. Superfluids passing an obstacle and vortex nucleation. Discrete and Continuous Dynamical Systems, 2019, 39 (12) : 6801-6824. doi: 10.3934/dcds.2019232 [8] Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91 [9] Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040 [10] Farrukh Mukhamedov, Otabek Khakimov. Chaotic behavior of the P-adic Potts-Bethe mapping. Discrete and Continuous Dynamical Systems, 2018, 38 (1) : 231-245. doi: 10.3934/dcds.2018011 [11] Bernard Bonnard, Thierry Combot, Lionel Jassionnesse. Integrability methods in the time minimal coherence transfer for Ising chains of three spins. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4095-4114. doi: 10.3934/dcds.2015.35.4095 [12] Gonzalo Galiano, Julián Velasco. Finite element approximation of a population spatial adaptation model. Mathematical Biosciences & Engineering, 2013, 10 (3) : 637-647. doi: 10.3934/mbe.2013.10.637 [13] Jishan Fan, Tohru Ozawa. An approximation model for the density-dependent magnetohydrodynamic equations. Conference Publications, 2013, 2013 (special) : 207-216. doi: 10.3934/proc.2013.2013.207 [14] Stephen Thompson, Thomas I. Seidman. Approximation of a semigroup model of anomalous diffusion in a bounded set. Evolution Equations and Control Theory, 2013, 2 (1) : 173-192. doi: 10.3934/eect.2013.2.173 [15] Tong Zhang, Jinyun Yuan. Two novel decoupling algorithms for the steady Stokes-Darcy model based on two-grid discretizations. Discrete and Continuous Dynamical Systems - B, 2014, 19 (3) : 849-865. doi: 10.3934/dcdsb.2014.19.849 [16] Luís Tiago Paiva, Fernando A. C. C. Fontes. Sampled–data model predictive control: Adaptive time–mesh refinement algorithms and guarantees of stability. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2335-2364. doi: 10.3934/dcdsb.2019098 [17] Lin Lu, Qi Wang, Yongzhong Song, Yushun Wang. Local structure-preserving algorithms for the molecular beam epitaxy model with slope selection. Discrete and Continuous Dynamical Systems - B, 2021, 26 (9) : 4745-4765. doi: 10.3934/dcdsb.2020311 [18] Xin Du, M. Monir Uddin, A. Mostakim Fony, Md. Tanzim Hossain, Md. Nazmul Islam Shuzan. Iterative Rational Krylov Algorithms for model reduction of a class of constrained structural dynamic system with Engineering applications. Numerical Algebra, Control and Optimization, 2022, 12 (3) : 481-493. doi: 10.3934/naco.2021016 [19] Gilles Carbou, Bernard Hanouzet. Relaxation approximation of the Kerr model for the impedance initial-boundary value problem. Conference Publications, 2007, 2007 (Special) : 212-220. doi: 10.3934/proc.2007.2007.212 [20] Pierre Degond, Maximilian Engel. Numerical approximation of a coagulation-fragmentation model for animal group size statistics. Networks and Heterogeneous Media, 2017, 12 (2) : 217-243. doi: 10.3934/nhm.2017009

2021 Impact Factor: 1.588