《自旋玻璃与消息传递算法Spin Glass and Message Passing 概要课件.ppt》由会员分享，可在线阅读，更多相关《自旋玻璃与消息传递算法Spin Glass and Message Passing 概要课件.ppt（47页珍藏版）》请在三一办公上搜索。
1、自旋玻璃与消息传递算法Spin Glass and Message-Passing Algorithms,周海军http:/,2,提纲,1。自旋玻璃理论基本图像与平衡自由能分布空腔方法,2。消息传递算法Vertex-Cover 问题, 3-SAT 问题 Survey Propagation算法,3,部分参考文献,Mezard, Parisi, Virasoro, “Spin Glass Theory and Beyond” (World Scientific, 1987）Mezard, Parisi, “The Bethe lattice spin glass revisited”, Euro
2、pean Physics Journal B 20: 217-233 (2001) Mezard, Parisi, Zecchina, “Analytic and algorithmic solution of random satisfiability problems”, Science 297: 812-815 (2002),如果对报告中所涉及的具体模型的计算细节感兴趣，请参考http:/,自旋玻璃理论：自由能分,5,Statistical mechanics of a (simple) system in equilibrium is well-established.,Partiti
3、on function, free energy, .Mean-field treatment. Phase transitions. Correlation length, scaling exponents, . Renormalization flow.,6, but non-equilibrium dynamics of even a simple system may be difficult to understand,Formal framework.Connection with equilibrium.Glassy dynamics. Why relaxation becom
4、es so low and non-exponential?,7,Equilibrium (static) and dynamical properties of complex systems are both difficult and interesting,Quenched randomness, frustration, non-self averaging, , broken ergodicity.NP-complete combinatorial optimizations, message-passing algorithms for information science (
5、CDMA, for example!), econo-physics, , biological systems.,8,自旋玻璃：无序与阻错系统的简单模型,3D regular lattice (Edwards-Anderson, 1975)Complete graph (Sherrington-Kirkpatrick 1975)Random Poisson graph (Viana-Bray, 1985),9,What we learned from an equilibrium statistical mechanics course?,10,What we learned from an
6、 equilibrium statistical mechanics course? (contl.),11,What we learned from an equilibrium statistical mechanics course? (contl.),12,ergodic vs non-ergodic,?,13,repeated heatingannealing and the equilibrium Gibbs measure,Complexity （复杂度）,14,distribution of equilibrium free-energies,1,15,distribution
7、 of equilibrium free-energies (contl.),2,16,17,Which thermodynamic states contribute to the equilibrium properties?,If,If,Excited macrostates matter!,Macrostates of minimal free energy density matter!,18,3-spin-Interaction Ising model on a complete graph,19,the mean free energy density,20,Overlap Di
8、stribution,自旋玻璃理论：空腔方法（cavity method),22,Lets define an artificial system!,23,Some examples of the grand free energy：2-body interactions,Beta=+infinity The max-2-SAT problem,Beta=1.25The +/- J spin-glassmodel on a randomregular graph ofdegree K=6,24,How to calculate the grand free energy? The cavity
9、 approach,25,26,N,N+2,27,Population Dynamics Simulation,28,Message-Passing Algorithms,30,3-SAT 问题,31,顶点覆盖问题,32,This graph is covered, but not optimally covered.,33,Minimal Vertex Cover Problem,A vertex cover of the global minimal size.Is a NP-hard optimization problem.Efficient algorithms for constr
10、ucting near-optimal solutions for a given graph.,34,There are many optimal solutions for a given graph,35,Three types of vertices： vertices that are always covered (frozen vertices, ) vertices that are always uncovered(frozen vertices, ) vertices that are covered in somesolutions and uncovered in th
11、eremaining solutions(unfrozen vertices, ),36,Mean-field analysis of the minimal vertex cover problemon a random graph,37,自洽的空穴场方法,覆盖还是不覆盖?,The vertex cover problem,38,=,always uncovered,always covered,unfrozen,Weigt, Hartmann, PRL (2000), PRE (2001),39,New vertex un-covered,New vertex partially cove
12、red,New vertex always covered,40,Mean-field theory result is lower than experimental values for c e=2.7183,2.7183,41,假定的相空间结构,42,引入参数 y,43,44,45,46,同样的消息传递的算法可以用于解决神经网络，信息系统，满足性问题，中的许多计算困难,47,Program and School in Beijing 2008,ICTP-ITP Spring School on “Statistical Physics and Interdisciplinary Applications” March 03-14, 2008KITPC Program “Collective Dynamics in Information Systems” March 01-April 15, 2008,
