变分消息传播模型与算法

Variational Message Passing

Posted by huajh7 on March 23, 2013

关键词 Variational Message Passing, Bayesian networksExponential Family, Sufficient Statistics.

传统的变分贝叶斯方法对模型的推导是繁琐而复杂的。J. Winn, Bishop [1] [2] 考虑了贝叶斯网络中的共轭指数网络 (conjugate-exponential networks) 提出变分消息传播 (VMP, Variational Message Passing) 。这种方法使得充分统计量与自然参数都有一个标准形式,现在该方法已经取代了手工推导, 成为标准的变分贝叶斯推断方法。而对于非共轭指数网络 (比如混合模型) ,也能通过进一步的近似转化为标准形式。


理论基础

Bayesian networks

变分信息传播方法是建立在贝叶斯网络[3]上的,如图所示,对于一个节点,它的父节点为,子节点为, 子节点的父节点为。所有节点统称为的马尔科夫毯,对于变分贝叶斯推理, 我们只需要关心这个模型,为参数或潜在变量,其父节点为它的超参数,子节点为数据样本, co-parents为其他参数或潜在变量。

贝叶斯网络 (马尔科夫毯)

图-1 贝叶斯网络 (马尔科夫毯)

Exponential Family

是可控参数统计结构,其密度函数可表示为如下形式:

并且它的支撑不依赖于θ,则称此结构为指数型的统计结构,简称指数结构,其中的分布族为指数分布族。 都与θ无关,且取有限值的B可测函数,k为正整数,,常见指数分布族,如二项分布,二元正态分布,伽马分布。

对于一个条件分布,如果它能写成如下形式,则称它属于指数分布族,

其中称为自然参数 (natural parameter) 向量,称为自然统计 (natural statistic) 向量。作为归一化函数使得对于任意的Y都能整合到统一的形式。指数分布族的好处是它的对数形式是可计算的并且它的状态可以用自然参数向量所概括。

Conjugate-Exponential Model

当变量X关于父节点Y的条件概率分布P(X|Y)为指数分布族,且为父节点分布P(Y)的共轭先验,那么称这样的模型是共轭指数模 (Conjugate-Exponential Model) 。 考虑共轭指数模型,其后验的每个因子与它的先验都有相同的形式,因而只需要关心参数的变化,而无需整个函数。所谓相同的形式是指属于同样的分布, 比如都属于正态分布,伽马分布,多项式分布等。

Sufficient Statistics

如果知道自然参数向量,那么就能找到自然统计量的期望。重写指数分布族,用作为参数,重新参数化为则,

积分有,

然后对微分,

得自然统计量的期望,


变分消息传播模型

变分分布Q在共轭指数模型下的最优化

不失一般性,考虑变分分布的一个因子, 为马尔科夫毯上一个节点,子节点为,如图-2所示

马尔科夫毯

图-2 马尔科夫毯

根据指数族条件分布的一般形式,则变量Y关于父节点的条件概率为,

为了更新Q(Y),需要找到(2),(3)关于除Y外其他因子的期望。对任何指数族的自然统计量u的期望都可以用自然参数向量ϕ带入 (2-19) 式得到。即对于任何变量A,都可以找到。特别的,当A为被观测量时,我们能直接计算得

从(3),(4)式可以看出分布成线性关系。而共轭要求对数条件分布也会与所有的成线性,。因而看得出是一个关于u的多线性函数。

考虑Y的变分更新方程,

其中,

正如以上所解释的,的期望都是相应的自然统计向量期望的多线性函数。因而有可能将以上期望重新参数化为

举例

如果X服从,那么

其中,,

可以重参数化为

其中分别表示的第一个元素。

变分消息传播模型

在贝叶斯网络中,由于Q可因式分解,则有

被分解为每一个节点上的贡献值 ,如节点的贡献值为

注意到在求的后验分布时就已经计算了;传出消息的时候也已经计算了,这样降低了下界的计算成本。

特别地,对于每个观测变量对下界的贡献值则更简单,


变分消息传播算法

变分消息的定义

来自父节点的消息 (Message from parents) :父节点传播给子节点的消息只是自然统计量的期望:

 

消息传播给父节点 (Message to parents) :依赖于X之前从Y的co-parents接收到的消息;对任何节点A,如果A是被观测量,那么,

用Y接收来自父节点与子节点的所有消息来计算,然后我们就能通过计算更新后的自然参数向量来找到Y的更新后的后验分布的计算公式如下,

.

该式与 (2) 式一致。从 (1) 式可以看出自然统计量的期望的单一函数,这样我们就可以用它来计算期望的新值。变分消息传播算法通过迭代的消息传播来最优化变分分布Q.

算法描述

Step1. 通过初始化相关的矩向量来初始化每个因子分布.
Step2. 对于每一个节点
1) 从父节点和子节点接收 (3),(4) 式所定义的消息。 前提是子节点已经从的co-parents接收到消息。
2) 使用 (5) 式更新自然参数向量
3) 根据新的参数向量更新距向量
Step3. 计算新的下界;
Step4. 如果经过数次迭代已经无法增加下界值,或者各边缘分布达到稳定值,则结束;否则回到Step2

举例:对于单一高斯模型消息传播过程如下图

消息传播过程

图-3 单一高斯模型消息传播过程

混合模型

到目前为止只考虑了来自指数族的分布。而通常来讲,混合模型并非来自指数族,比如高斯混合模型,通常需要将混合分布转化为指数族分布形式。

考虑高斯混合模型,通常有如下形式,

可以引入一个离散型潜在变量λ,表示每个观测点是属于哪个单高斯分布。重写分布函数为:

加入该λ变量后该分布属于指数分布族,可写成

如果X有子节点Z,那么共轭条件要求每一个成分都有相同的自然统计向量, 统一定义为。 另外,我们可能要使模型的其他部分也有相同的形式,虽然不要求共轭,即。 在这种情况下,混合模型的每个成分都有相同的形式,可写成,

其中定义。这样对于每个成分来说条件分布都有了 与指数分布族一样的形式,便可以应用变分消息传播算法。

从某个节点X传播个子节点的消息为,而这是通过混合参数向量计算的。 相似地,节点X到父亲节点的消息是那些以它为父节点的子节点发出的,而节点X中哪些属于是由指标变量的后验确定的。最后,从X到的消息是一个K维向量,其中第k个元素为.


算法分析

VB算法与EM算法比较

EM算法计算随机变量 (或归类于参数) 后验分布的点估计,但估计隐变量的真实后验分布。用这些参数的众数作为点估计,无任何其他信息。 而在VB算法作为一个分布估计 (Distributional Approximation) 方法,计算所有变量的真实后验分布的估计,包括参数和隐变量。 在贝叶斯推断中,计算点估计一般使用常用的均值而非众数。与此同时,应该注意的是计算参数在VB中与EM有不同的意义。 EM算法计算贝叶斯网络本身的参数的最优值。而VB计算用于近似参数和隐变量的贝叶斯网络的参数最佳值,VB会先找一个合适的参数分布, 通常是一个先验分布的形式,然后计算这个分布的参数值,更准确说是超参数,最后得到联合分布的各参数的分布。

算法复杂性

变分贝叶斯估计方法是众多概率函数估计技术之一。还有许多其他被广泛使用的估计算法,一般分为确定性 (deterministic) 和随机性 (stochastic) 的方法,比如基于点估计的极大似然估计、极大后验概率估计,基于局部估计的Laplace估计,基于spline估计的B-样条估计,还有经验性估计,利用随机采用的如MCMC方法。变分贝叶斯方法作为平均场估计,能够在计算复杂度和精度之间保持一个良好的关系,如图-4所示。变分贝叶斯方法主要的计算压力在于它的IVB算法——一系列为求取变分边缘概率相关的矩估计而进行的迭代。如果只关心计算代价而对精度要求不高,那么可以用简单的估计方法来代替变分边缘概率,或者减少估计迭代的次数,这样变分估计的路径将沿着虚线往下。

VB方法的精度与复杂性之间的关系

图-4 VB方法的精度与复杂性之间的关系

小结

本文对基于贝叶斯网络的变分消息传播方法从理论基础到算法流程展开论述。 特别地与EM算法进行比较,分析了变分贝叶斯方法的算法复杂性。 下一篇将给出高斯混合模型的例子,以及MATLAB实现源代码。

参考文献

[1] John M. Winn, M. Bishop, Variational Message Passing, Journal of Machine Learning Research, 2004

[2] John M. Winn, Variational Message Passing and its Applications, University of Cambridge, 2003

[3] Michael I. Jordan, An Introduction to Variational Methods for Graphical Models, Machine Learning, 1999

完整文章下载: [pdf]