吉布斯采样

吉布斯采样(英语:Gibbs sampling)是统计学中用于马尔科夫蒙特卡洛(MCMC)的一种算法,用于在难以直接采样时从某一多变量概率分布中近似抽取样本序列。该序列可用于近似联合分布、部分变量的边缘分布或计算积分(如某一变量的期望值)。某些变量可能为已知变量,故对这些变量并不需要采样。

来源:维基百科
简介

吉布斯采样是一种简单且广泛适用的马尔可夫链蒙特卡洛(MCMC)算法,可以看作是MetropolisHastings算法的一个特例。吉布斯采样适用于联合分布未明确知道或难以直接抽样但每个变量的条件分布是已知的并且很容易(或者至少更容易)从中抽样的情况。

考虑我们希望从中抽样的分布p(z)= p(z_1,...,z_M),并假设我们已经为马尔可夫链选择了一些初始状态。 吉布斯采样程序的每一步都涉及用某个变量相对于其他变量的条件概率分布中抽样得出的值代替该变量的值。即,我们用从分布p(z_i | z_{ \ i})绘制的值替换z_i,其中z_i表示z的第i个分量,并且z_{\ i}表示除z_i以外的z_1,...,z_M。如何我们通过以某种特定顺序循环变量或者通过从某个分布中随机选择每个步骤要更新的变量来重复该过程。请注意在符号表示上的区别,z表示一个单独的变量,而z则表示一个向量。

举例来说,假设我们有三个变量的联合分布p(z_1,z_2,z_3),并且在算法的第τ步中,我们已经抽取了z_1^(τ),z_2^(τ)和z_3^(τ)。 我们首先将z_1^(τ)替换为从条件分布中抽取的新值z_1^(τ+ 1),所使用的条件概率如下:

同理,我们将z_2^(τ)替换为从条件分布中抽取的值z_^(τ+ 1):

注意到在后续采样步骤中我们立即使用z_1的新值。 然后我们用从中抽取的样本z_3^(τ+ 1)更新z_3:

这样依次循环三个变量,直到采样过程收敛,或达到循环次数上限。

正式的吉布斯采样算法框架给定如下:

吉布斯采样之所以被看作是Metropolis Hastings算法的一个特例,是因为它总是以1的概率接受抽样出的值,而Metropolis Hastings算法则以一定的概率拒绝或接受。

【描述及图片来源:Bishop C. M. (2006). Pattern Recognition and Machine Learning. Springer.

发展历史

吉布斯采样是以物理学家Josiah Willard Gibbs的名字命名的,他提到了采样算法和统计物理学之间的类比。Gibbs逝世后约八十年,Stuart和Donald Geman兄弟于1984年描述了该算法,这是我们目前熟悉的版本。1990年Alan E. Gelfand和 Adrian F. M. Smith对随机替换(Stochastic substitution),吉布斯采样(Gibbs sampler)和采样重要性重采样算法(sampling-importance-resampling algorithm)这三种重要的抽样算法进行了回顾和对比。

由于EM算法是特别为了缺失数据而设计的,其与吉布斯采样之间有着天然的联系。1994年Jean Diebolt和Christian P. Robert提出了用于EM算法中M步的近似方法,其依赖于混合模型的缺失数据结构,通过吉布斯采样来评估后验分布和贝叶斯估计。

吉布斯采样特别适合采样贝叶斯网络的后验分布,因为贝叶斯网络通常被指定为一组条件分布。

在深度学习领域,Yoshua Bengio 等研究者最近提出了 GibbsNet,旨在通过匹配模型期望的联合分布和数据驱动的联合分布直接定义和学习转换算子(transition operator),然后使用转换算子训练图模型。这与无向图模型类似,也受到其启发,期望跃迁算子(对应成块吉布斯采样)沿着已定义能量流形移动,这样我们就可以在公式中建立该连接。

主要事件

年份事件相关论文/Reference
1984Stuart和Donald Geman兄弟描述了Gibbs抽样算法Geman, S.; Geman, D.(1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images.IEEE Transactions on Pattern Analysis and Machine Intelligence. 6 (6): 721–741.
1990Alan E. Gelfand和 Adrian F. M. Smith对随机替换(Stochastic substitution),吉布斯采样(Gibbs sampler)和采样重要性重采样算法(sampling-importance-resampling algorithm)这三种重要的抽样算法进行了回顾和对比Gelfand, A. E. and Smith, A. F. M. (1990). Sampling-based approaches to calculating marginal densities. J. Amer. Statist. Assoc. 85 398–409.
1994Jean Diebolt和Christian P. Robert提出了用于EM算法中M步的近似方法Diebolt, J. and Robert, C. P. (1994). Estimation of finite mixture distributions through Bayesian sampling. J. Roy. Statist. Soc. Ser. B 56 363–375.
2017Yoshua Bengio 等研究者最近提出了 GibbsNetLamb, A. et al. (2017).GibbsNet: Iterative Adversarial Inference for Deep Graphical Models.arXiv:1712.04120.

发展分析

瓶颈

吉布斯采样仅要求使用者知道完全条件分布(full conditionals),但知道完全条件分布是非常重要的前提。如果使用者不知道完全条件分布或者不能有效地从该分布抽样,那么吉布斯采样要么不适用要么其表现不能与其他MCMC方法相比较。因此,吉布斯采样使用的范围是有限的,虽然在实际应用中许多使用者并不遵循这一点。

未来发展方向

吉布斯采样在许多领域都有应用,如主题模型、受限玻尔兹曼机(RBM),贝叶斯网络等,此外,Yoshua Bengio等学者提出了GibbsNet显示了即使在吉布斯采样还没有被应用的领域中,通过精巧的设计也可以将吉布斯采样算法融合,取得良好的效果。

Contributor:Yuanyuan Li

相关人物
斯图尔特·格曼
斯图尔特·格曼
生于1949年,美国数学家,以对计算机视觉、统计学、概率论、机器学习和神经科学有影响的贡献而闻名。他和他的兄弟Donald Geman因提出吉布斯采样器以及首次证明模拟退火算法的收敛性而闻名。
阿兰·格尔凡德
阿兰·格尔凡德
Alan E. Gelfand是美国统计学家,目前是杜克大学统计与决策科学的James B. Duke教授。 Gelfand的研究领域包括对贝叶斯统计、空间统计和层次建模。
简介
相关人物