前言: 本文主要是关于期望传播, 这是一种用指数族分布去近似复杂目标分布的方法, 其本质上为变分推断逆过来, 主要参考了Thomas P Minka的博士论文A family of algorithms for approximate Bayesian inference、维基百科及PRML一书10.7节.
指数族分布
首先来看一个重要概念指数族分布, 称\(X\)为指数族分布, 若其密度函数:\[f(x\mid \theta )=h(x)\exp \left(\eta (\theta )^TT(x)-A(\theta )\right), \theta\in\Theta\]其中:
- \(T(x)\)为\(X\)的充分统计量. 样本\(x=\{x_1,..,x_m\}\), \(x_i\sim f(x\mid \theta)\), 统计量(比方说)\[T(x)=(\bar{x}, \frac{1}{m}\sum_{i=1}^n (x_i-x)^2)\]可理解为对样本\(x\)的粗加工, 其将对样本的信息量由\(m\)维降至\(2\)维; 而充分统计量\(T(x)\)则是那些能够充分说明原样本的统计量, 定义为: 若\(x\mid T(x)\)的条件分布与未知参数\(\theta\)无关, 则称\(T(x)\)为充分统计量. \((\bar{x}, \frac{1}{m}\sum_{i=1}^n (x_i-\bar{x})^2)\)就是正态分布的一个充分统计量(充分统计量不唯一).
- 当\(\eta (\theta )=\theta\)取实值, 此时指数族分布称为是自然形式的指数族分布.
- \(A(\theta)\)称为是归一化因子\[A(\theta )=\ln \left(\int h(x)\exp(\theta ^T T(x))\,\mathrm {d} x\right)\]它的存在保证了这个函数是个密度函数. 有时这个归一化因子会写在外面, 因此指数族分布的密度函数有如下等价形式:\[f(x\mid \theta )=h(x)g(\theta )\exp \left(\theta ^T T(x)\right)\]此时\(g(\theta)\)满足\(g(\theta)^{-1}=\int h(x)\exp \left(\theta ^T T(x)\right)dx\).
- 参数空间\(\Theta\)中的每一个元\(\theta\)都应当使得归一化因子为正数: \(A(\theta)\in(0,+\infty)\); 而所使得归一化因子为正数的\(\theta\)构成的参数空间\(\Theta\)称为是自然参数空间, 且自然形式下的指数族分布的自然参数空间为欧式空间中的凸集.
指数族分布是一大类分布的集合, 包括正态分布, 指数分布, 二项分布, 泊松分布, Beta分布, Gamma分布, 狄利克雷分布等, 具体见维基百科上的总结, 有兴趣的读者不妨拿一个验证一下. 以密度函数的第二个形式为例, 归一化因子满足条件的等式的两边对参数\(\theta\)求导可以得到自然形式指数族分布的一个重要性质, 能轻易表示出\(T(x)\)的各阶矩: \[g(\theta)^{-2}\frac{dg(\theta)}{d\theta} = \int h(x)\exp \left(\theta ^T T(x)\right)T(x)dx \]两边同乘\(g(\theta)\)得:\[-\nabla\ln g(\theta)=\mathbb{E}_{f(x\mid \theta )}T(x)\]再次对\(\theta\)求导可得:\[-\nabla^2 \ln g(\theta)=\mathbb{E}_{f(x\mid \theta )}T^2(x)\]当然如果此时密度函数取第一个形式, 形式会更简单: \[\nabla A(\theta)=\mathbb{E}_{f(x\mid \theta )}T(x), \nabla^2 A(\theta)=\mathbb{E}_{f(x\mid \theta )}T^2(x)\]关于更多指数族分布或是统计量可参考数理统计的教材, 比如韦博成的参数统计教程, 陈希孺的高等数理统计学.
期望传播
下面来看期望传播:
- 首先简单回顾变分推断, 变分推断做的是通过最小化KL散度(以EM算法中E步为例, 详见贝叶斯方法的3.1节.):\[\mathcal{KL}(q(T)\Vert P(T\mid X, \theta))\] \(\mathcal{KL}\)散度的定义见维基百科, 这里的\(X\)为机器学习中的样本矩阵, 已给定, 不同于变量\(x\); \(\theta\)为未知参数; \(T\)本为隐变量, 这里为了不和上文\(T\)重名, 简记为\[\mathcal{KL}(q(x)\Vert P(x\mid X, \theta))\]这里做的事情就是从一个相对简单的单分布族\(Q\)中找到一个\(q(x)\)去逼近复杂分布\(P(x\mid X, \theta)\). 和下文的期望传播以示区别, 这里我们称之为\(q(x)\)从左逼近\(P(x\mid X, \theta)\), 这种从左逼近的方法的最大的好处就是不必去考虑关于\(X, \theta\)的分布, 即不必计算\(P(X, \theta)\).
- 期望传播(Expectation Propagation: EP)做的则是最小化逆过来的KL散度:\[\mathcal{KL}( P(x\mid X, \theta)\Vert q(x))\]这里我们称之为\(q(x)\)从右逼近\(P(x\mid X, \theta)\), 这种从右逼近的方法的好处就是, 若这里的\(q(x)\)限定在指数族分布的范围内, 即\(q(x\mid\tilde{\theta})=h(x)g(\tilde{\theta} )\exp \left(\tilde{\theta} ^T T(x)\right)\)(\(\tilde{\theta}\)与\(\theta\)是不同的未知参数), 此时最小化上述\(\mathcal{KL}\)散度就等价于充分统计量\(T(x)\)关于两个分布\(q(x)\)和\(P(x\mid X, \theta)\)的期望相等: \[\begin{aligned} \mathcal{KL}( P(x\mid X, \theta)\Vert q(x)) & = \int P(x\mid X, \theta)\ln\frac{P(x\mid X, \theta)}{q(x)}dx\\\
& = \int P(x\mid X, \theta)\ln\frac{P(x\mid X, \theta)}{h(x)g(\tilde{\theta} )\exp \left(\tilde{\theta} ^T T(x)\right)}dx\\\
(let \, P=P(x\mid X, \theta)) \,& = \int P\ln Pdx - \int P\ln h(x)dx-\int P\ln g(\tilde{\theta})dx- \int P\tilde{\theta} ^T T(x)dx\\\
& = \int P\ln Pdx - \int P\ln h(x)dx-\ln g(\tilde{\theta})- \tilde{\theta} ^T \mathbb{E}_{P}T(x) \end{aligned}\] 此时令关于未知参数 \(\tilde{\theta}\) 的梯度为\(0\)就可以得到\[-\nabla\ln g(\tilde{\theta})=\mathbb{E}_{P(x\mid X, \theta)}T(x)\]再利用上节中能轻易表示出\(T(x)\)各接矩的性质, 这里仅用一阶矩: \[-\nabla\ln g(\tilde{\theta})=\mathbb{E}_{q(x\mid\tilde{\theta})}T(x)\]得到结论: \[\mathbb{E}_{P(x\mid X, \theta)}T(x)=\mathbb{E}_{q(x\mid\tilde{\theta})}T(x)\]即\(T(x)\)关于目标分布\(P(x\mid X, \theta)\)期望的信息能够传递下去. 以正态分布为例, \(q(x\mid \mu, \Sigma)=N(\mu, \Sigma)\):
\[\begin{aligned} q(x\mid \mu, \Sigma) & = {\frac {\exp \left(-{\frac {1}{2}}(x- \mu )^{T }\Sigma ^{-1}(x-\mu)\right)}{\sqrt {(2\pi )^{k}|\Sigma|}}}\\\
& = {\frac {\exp \left(-{\frac {1}{2}}x^{ T }\Sigma ^{-1}x+x^{ T }\Sigma ^{-1}\mu-{\frac {1}{2}}\mu^{ T }\Sigma ^{-1}\mu\right)}{\sqrt {(2\pi )^{k}|\Sigma|}}} \end{aligned}\]
& = {} \end{aligned}只需考虑\(x\)与参数\(\mu, \Sigma\)分不开的那些项, 得\(T(x)=(x, xx^T)\)(
p.s.这里笔者并不是很明白怎么去算, 希望知道多元正态分布充分统计量详细推导的朋友的朋友能给我解惑, 联系方式见关于我 :) )必然是其中一个充分统计量, 用上述结论即为\[\begin{aligned} \mathbb{E}_{P(x\mid X, \theta)}x & = \mathbb{E}_{q(x\mid \mu, \Sigma)}x=\mu\\\ \mathbb{E}_{P(x\mid X, \theta)}xx^T& = \mathbb{E}_{q(x\mid \mu, \Sigma)}xx^T=\Sigma + \mu\mu^T\end{aligned}\]上述思路其实是Assumed Density Filtering(ADF)(或者说在线贝叶斯学习online bayesian leaning, 矩匹配moment matching)的主要思路, 至于在线学习则体现在初始化\(q=1\)后对每个样本序列地用上述式子去更新, 详细可见Thomas P Minka的博士论文A family of algorithms for approximate Bayesian inference(百度学术, 谷歌学术均可达)的3.1节.
p.s.这篇论文其实是期望方法传播的提出之作, 其可视为ADF的拓展, 或者说ADF是期望传播的online版本, 两者相同点在于每次都只对一个样本进行更新; 区别则在于逼近目标为batch还是依次来样本; 且期望方法会一直更新直到收敛, 因此很可能每个样本点更新多次, 而ADF对每个样本点只更新一次. 有兴趣的朋友可见Thomas P Minka的那篇论文, 或者见PRML一书p510, 但本质上两者的核心更新式子还是出于期望的传播这样一个想法.