4.3.1. 基本模型与算法介绍

4.3.1.1. Ising 模型 与 Potts 模型

Ising 模型,是物理学家研究磁性材料的模型,在统计物理中已经被广泛的研究过了。一个相近的模型是 Potts 模型 。与Ising模型类似,Potts 模型也是定义在晶格空间 \(\mathcal{L}\) 上的 \(x=(x_l,x\in \mathcal{L})\)

\[\mathcal{L}=\{ l=(l_1,l_2)\ for\ l_1,l_2 = 1,\dots,N\}.\]

与Ising模型不同,在Potts 模型里面每一个 \(x_l\) 可以取 \(q:{1,\dots,q}\) 。能量势可以取为:

\[H(x)=-J\sum_{i\sim j}\delta_{x_ix_j}-\sum_{j}h_j(x_j)\]

这里 \(i\sim j\) 表示i和j在晶格空间里面是相邻的。于是我们关心的分布就是Bolzmann分布:

\[\pi(x) \propto exp\{-\beta H(x)\}\]

\(\beta=(kT)^{-1}\)\(k\) 是Bolzmann常数,T是绝对温度。当 \(q=2\) 时,Potts模型就是Ising模型:

\[H(x)=-\frac{1}{2}J\sum_{i\sim j}2(\delta_{x_ix_j}-\frac{1}{2})-\sum_{i\sim j}\frac{1}{2}J-\sum_{j}h_j(x_j)\]

为了简单起见,我们假设 \(h_j\equiv 0\)

关于这个模型的一个重要的问题是相变现象:当温度高的时候,可以观察到所有的spin几乎是独立变化的;而当温度低到一个特定的温度 \(c_0\) 以后,所有的spin就趋于保持一致。

标准的 Metropolis算法正好方便的应用于模拟这个模型:第一步,随机选一个spin将他的取值 \(x_l\) 取为 \(-x_l\) ; 第二步,计算 Metropolis 比例来决定是否接受这个变化。但是当温度接近或者低于 \(c_0\) 的时候,这个算法变的非常的慢。

4.3.1.2. 算法介绍

4.3.1.2.1. The Swendsen-Wang Algorithm as Data Augmentation

概念上,我们可以将 Swendsen-wang 算法视为一种“数据增强”(data augmentation scheme)。我们用一个连接变量 \(u=(u_{l\sim l'})\) 来增强数据。每一个 \(u_{l \sim l'}\) 在晶格的边界上,取值范围为: \([0,e^{2 \beta J}]\)

\[\begin{split}\pi(x)& \propto exp\{\beta J \sum_{l\sim l'}x_l x_{l'}\} \\ &\propto \prod_{l\sim l'}exp\{\beta J(1+ \sum_{l\sim l'}x_l x_{l'})\} \\\end{split}\]

注意到 \(1+x_l x_{l'}\) 等于 0 或者2。所以,如果我们引入辅助变量 \(u\) 使得:

\[\pi(x,u) \propto \prod_{l \sim l'} I[0 \leq u_{l,l'} \leq exp{\beta J(1+x_lx_{l'})}],\]

于是 x 的边界分布就是我们想要的分布。 显然,在这个联合分布中,条件分布 \([u|x]\) 是各个基于两个相邻的spin的平均分布的乘积。反过来,给定u,x的条件分布也容易得到:如果 \(u_{l,l'}>1\) ,则 \(x_l=x_{l'}\) ;否则对 \(x_l\) 没有限制。 于是,u 只有在 \(I[u_{l,l'}>1\) 时,对 x 起作用。基于u的作用,我们将这些晶格根据相互直接有没有连接来分成组(cluster)。然后,所有属于同一组的 \(x_l\) 必须保持相同的值。在这样的分组的前提下,没一种情况出现的概率都是相同的。

所以,我们还可以做另一种数据增强,只用一个 连接变量 \(b =(b_{l\sim l'}\) ,来表示 \(u(l,l')>1\) 是否成立。也就是说,我们定义:
\[\begin{split}b_{l,l'}= I[u_{l,l'}>1]\end{split}\]

于是,相应的增强模型是:

\[\pi(x,b) \propto \prod_{x_l=x_{l'}}\{1+b_{l,l'}(e^{2 \beta J} - 1)\},\]

\(b_{l,l'}\) 如果 \(x_l\neq x_{l'}\) 。 spin的分组(clustering)可以通过将连接为1的邻居相连。分组之间的spin方向相互独立。

Swendsen-Wang 算法:

  • 对于一个给定的spin情况,以概率 \(1-e^{-2\beta J}\) 建立每一个相等晶格之间的边界的连接变量 \(\langle l,l' \rangle\) 取值为1 ,否则取值0。
  • 在连接变量 b 前提下,通过 \(p(x|b)\) 更新 spin变量x ,即在所有可能情况下的平均分布。也就是说,每一个组以概率 0.5 翻转。

4.3.1.2.2. The Modification by Wolff

Wolff的修正使得算法的效率得到了很大的改善:

Wolff 算法:

  • 对于给定的一个情况x,随机选取一个晶格 \(x_l\) ,然后从一个连接集 \(C\) 递归的生长:
  • 检查 \(C^{old}\) 所有未检查的邻居;并且按照 SW算法中的规则建立连接。
  • 将新连接到 \(C^{old}\) 上的单元添加到 \(C^{old}\) 中生成 \(C^{new}\)
  • 停止上诉递归过程直到没有未检查的邻居可以添加。将最后的集合称为 \(C\)
  • 将 集合 C 中的所有元素翻转,(不带随机性)。

4.3.1.2.3. Further Generalization

Niedermayer 提出允许连接取值不同的邻居。设 \(p_a\) 为连接相等邻居的概率, \(p_b\) 为连接相反邻居的概率。生长完一个组 \(C\) (Cluster)之后,反转整个 \(C\) 。 选取适当的 \(p_a,p_b\) 使得:

\[\frac{1-p_a}{1-p_b}=e^{2\beta J}\]