树上自旋系统的快速采样算法  

Fast Sampling Algorithms for Spin Systems on Trees

作　　者：白宗磊 王捍贫[1,2] 曹永知 王璐璐 BAI Zong-Lei;WANG Han-Pin;CAO Yong-Zhi;WANG Lu-Lu(Key Laboratory of High Confidence Software Technologies(MOE),School of Computer Science,Peking University,Beijing100871;School of Computer Science and Cyber Engineering,Guangzhou University,Guangzhou 510006)

机构地区：[1]北京大学计算机学院高可信软件技术教育部重点实验室,北京100871 [2]广州大学计算机科学与网络工程学院,广州510006

出　　处：《计算机学报》2022年第10期2093-2116,共24页Chinese Journal of Computers

基　　金：国家自然科学基金(61972005,61932001,62172016)资助.

摘　　要：自旋系统是统计物理学中用来描述微观粒子相互作用的重要框架,其可以描述伊辛模型,硬核模型,玻茨模型等统计物理学中的重要模型;通过求解自旋系统的配分函数可以得出物质的能量、磁矩等物理性质.作为一种重要的图模型,自旋系统在理论计算机、人工智能、概率论等领域中被称作马尔可夫随机场而广泛应用,其可以描述着色问题、图同态问题等图论中的重要问题.对图中的点和边赋予非负权重,自旋系统可以诱导出著名的吉布斯分布;配分函数的近似计算可以归约到对应的吉布斯采样问题,通过吉布斯采样可以求解系统的相关物理性质和统计规律.作为模型的简化,树上的自旋系统受到广泛研究;本文研究树上自旋系统的采样算法,并将其推广到树宽较小的图上.我们的主要工作可以列举如下:对于无外场的伊辛模型,基于节点的两种状态的对称性,可以直接计算出任意节点对应的边缘分布,然后通过简单变量的组合来模拟吉布斯分布.类似地,着色问题和玻茨模型也可以基于状态的对称性用简单变量来模拟吉布斯分布.对于一般的自旋系统,无法保证状态的对称性,我们先递归地计算出所有节点的边缘分布,然后基于这些边缘分布进行采样,并通过简单变量的组合来模拟吉布斯分布.对于普通图,我们引入树宽的概念来度量图与树的相似性,并且基于节点间的独立性将算法推广到树宽为2的伪森林和仙人掌图中.我们的算法仅需要线性时间来得到吉布斯分布中的一个样本,在时间复杂度上优于基于马尔可夫链蒙特卡洛模拟的采样算法.Spin systems model the interactions between microscopic particles in statistical physics,and provide a framework for many important statistical physical models,such as the Ising model,hard-core model,and Potts model.The partition function of spin systems captures the mean magnetic moment and the mean energy of the systems.The spin systems are also widely used as Markov random field in theoretical computer science,artificial intelligence,and probability theory.They provide a framework for many important models in graph theory,such as colorings,graph homomorphisms,etc.The spin systems induce the famous Gibbs measures when the vertices and edges are assigned with non-negative weights.The approximation of partition function can be reduced to Gibbs samplings,so the physical properties can be obtained from Gibbs samplings.The spin systems on trees are widely studied as a simplification of the systems.In this paper,we study the sampling algorithms for the Gibbs measures on trees,and our contributions can be enumerated as follows:for the Ising model without external fields,the two spins are symmetric,and we simulate the Gibbs measure via the combinations of simple Bernoulli variables.The same result is valid for colorings and the Potts model due to the symmetry of spins.For general spin systems,the symmetry of spins is not valid,so we need to calculate the marginal distributions of the vertices recursively at first.Then based on the distributions,we perform samplings on some simple variables,and simulate the Gibbs measure via delicate combinations of the variables.For general graph,we introduce the treewidth of graph to measure the distance of the graph from tree.Based on the independence of vertices,we extend our algorithms to some graphs with treewidth 2,including pseudo-forest and cactus graphs.Our algorithms only need linear time to obtain a sample from the Gibbs measures on trees,and exhibit better in running time than the algorithms based on Markov chain Monte Carlo method.

关 键 词：着色问题 吉布斯分布 伊辛模型 采样算法 自旋系统 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]