论文标题
关于Metropolis算法与多元二进制概率分布的固定顺序更新的收敛性
On the convergence of the Metropolis algorithm with fixed-order updates for multivariate binary probability distributions
论文作者
论文摘要
大都市算法可以说是马尔可夫链蒙特卡洛（MCMC）方法最基本的。但是，如果变量（站点或神经元）以固定顺序更新，则不能保证在多元二进制分布（例如，ISING模型或随机神经网络（例如Boltzmann机器））的情况下，该算法不能收敛到所需的分布（例如，ISING模型或随机神经网络（例如Boltzmann机器））。原因是相应的马尔可夫链可能不可还原。我们提出了一个修改后的大都市过渡运算符，该运算符几乎总是与标准都市运营商相同的行为，并证明它确保了具有固定顺序更新的多元二进制案例中的限制性和融合到限制分布。结果为大都会MCMC在这种情况下的行为提供了解释，并缩小了长期的理论差距。我们通过实验研究了模型的标准和修改的大都市操作员的行为实际上不同。如果标准算法也收敛，则修改后的操作员在收敛速度方面表现出相似的性能（如果不是更好）。
The Metropolis algorithm is arguably the most fundamental Markov chain Monte Carlo (MCMC) method. But the algorithm is not guaranteed to converge to the desired distribution in the case of multivariate binary distributions (e.g., Ising models or stochastic neural networks such as Boltzmann machines) if the variables (sites or neurons) are updated in a fixed order, a setting commonly used in practice. The reason is that the corresponding Markov chain may not be irreducible. We propose a modified Metropolis transition operator that behaves almost always identically to the standard Metropolis operator and prove that it ensures irreducibility and convergence to the limiting distribution in the multivariate binary case with fixed-order updates. The result provides an explanation for the behaviour of Metropolis MCMC in that setting and closes a long-standing theoretical gap. We experimentally studied the standard and modified Metropolis operator for models were they actually behave differently. If the standard algorithm also converges, the modified operator exhibits similar (if not better) performance in terms of convergence speed.
