「expectation」Expectation-Maximum（EM算法）

expectation

EM算法原理：

这里写图片描述

不作过多引言专注推导，先打个比方，一个袋子有10个球，但不清楚里面有些什么颜色的球，但是又不能打开袋子看，所以我们尝试通过大量的抽样，使用观察数据来估计。比如抽样结果是0.6概率是红球，0.4概率是蓝球，于是可以认为10个球里面有6个红球与4个蓝球。

所以首先EM算法是解决含隐变量（latent variable）情况下的参数估计问题，而求模型的参数时一般采用最大似然估计，由于含有了隐含变量（如例子中不清楚颜色却又不能打开袋子看），所以对似然函数参数求导是求不出来的，虽然通过梯度下降等优化方法也可以求解，但如果隐变量个数太多，将会带来指数级的运算。不过我们能知道在隐变量能观察到的情况下，最大似然法很简单，或者在知道参数的情况下，计算它的期望值也很容易。那么自然而然可以想到：

1.固定一组参数，计算该参数下的隐变量的期望值（E步）

2.结合E步求出的隐含变量条件概率，用最大似然法来估计参数（M步）。

重复上面2步直至收敛。其实可以从上面开篇的图片上快速理解，即如何反复构造出最大下界，从而不断的逼近最优点。

公式如下所示：

这里写图片描述

一起来推导一遍吧：

首先是jensen不等式： $如果 f (x) 是凸函数，则有： E (f (x)) \geq f (E (x)) 如果f(x) 是凸函数，则有：E(f(x)) \geq f(E(x))\;\;$ 如果f(x)是凸函数，则有：E(f(x))≥f(E(x))

在这里插入图片描述

简单来说如果只有两个变量x1和x2，自然成立，再使用数学归纳法易证该不等式。

然后求对于m个数据x的参数 $θ \theta$ θ的极大对数似然有： $θ = a r g \max_{} \sum_{i = 1}^{m} l o g P (x^{(i)} ∣ θ) \theta = arg \max \ limit s_{\theta}\sum\limits_{i=1}^m logP(x^{(i)}|\theta)$ θ=argθmaxi=1∑mlogP(x(i)∣θ)

因为存在隐变量z，似然函数可改写为： $θ = a r g \max_{} \sum_{i = 1}^{m} l o g \sum_{z^{(i)}} P (x^{(i)} ， z^{(i)} ∣ θ) \theta = arg \max \limits_{\theta}\sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}P(x^{(i)}， z^{(i)}|\theta)$ θ=argθmaxi=1∑mlogz(i)∑P(x(i)，z(i)∣θ)

引入 $Q_{i} (z^{(i)} Q_i(z^{(i)}$ Qi(z(i)表示隐含变量z的某种分布，它自然也满足概率分布的条件 $\sum_{z} Q_{i} (z^{(i)}) = 1 ， Q_{i} (z^{(i)}) \geq 0 \sum\limits_{z}Q_i(z^{(i)}) =1，Q_i(z^{(i)})\geq0$ z∑Qi(z(i))=1，Qi(z(i))≥0

那么上面的似然函数可变换为：

$\sum_{i = 1}^{m} l o g \sum_{z^{(i)}} P (x^{(i)} ， z^{(i)} ∣ θ) = \sum_{i = 1}^{m} l o g \sum_{z^{(i)}} Q_{i} (z^{(i)}) \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})))} \sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}P(x^{(i)}， z^{(i)}|\theta) =\sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})))}$ i=1∑mlogz(i)∑P(x(i)，z(i)∣θ)=i=1∑mlogz(i)∑Qi(z(i))Qi(z(i))))P(x(i)，z(i)∣θ)

观察到 $\sum_{z^{(i)}} Q_{i} (z^{(i)}) \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} 就是 P (z^{(i)} ∣ x^{(i)} ， θ)) 的期望 \sum\limits_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})} 就是P( z^{(i)}|x^{(i)}，\theta))的期望$ z(i)∑Qi(z(i))Qi(z(i))P(x(i)，z(i)∣θ)就是P(z(i)∣x(i)，θ))的期望，所以利用Jensen不等式可得：

$\sum_{i = 1}^{m} l o g \sum_{z^{(i)}} P (x^{(i)} ， z^{(i)} ∣ θ) = \sum_{i = 1}^{m} l o g \sum_{z^{(i)}} Q_{i} (z^{(i)}) \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} \geq \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} \sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}P(x^{(i)}， z^{(i)}|\theta) = \sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})} \\ \geq \sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})}$ i=1∑mlogz(i)∑P(x(i)，z(i)∣θ)=i=1∑mlogz(i)∑Qi(z(i))Qi(z(i))P(x(i)，z(i)∣θ)≥i=1∑mz(i)∑Qi(z(i))logQi(z(i))P(x(i)，z(i)∣θ)

到这里，相当于求出了一个下界，但是 $Q_{i} (z^{(i)} Q_i(z^{(i)}$ Qi(z(i)的选择可能会有多种，怎么样才算是最好的下界呢？凸函数的好处就在于一定存在唯一的全局最优值，而且存在于当且仅当不等式大于等于变成了等于的时候！根据Jensen不等式，想要等式成立需要满足条件： $\frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} = c, c 为常数 \frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})} =c, c为常数$ Qi(z(i))P(x(i)，z(i)∣θ)=c,c为常数

考虑到 $Q_{i} (z^{(i)} Q_i(z^{(i)}$ Qi(z(i)本身的分布性质，可得： $Q_{i} (z^{(i)}) = \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{\sum_{z} P (x^{(i)} ， z^{(i)} ∣ θ)} = \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{P (x^{(i)} ∣ θ)} = P (z^{(i)} ∣ x^{(i)} ， θ)) Q_i(z^{(i)}) = \frac{P(x^{(i)}， z^{(i)}|\theta)}{\sum\limits_{z}P(x^{(i)}， z^{(i)}|\theta)} = \frac{P(x^{(i)}， z^{(i)}|\theta)}{P(x^{(i)}|\theta)} = P( z^{(i)}|x^{(i)}，\theta))$ Qi(z(i))=z∑P(x(i)，z(i)∣θ)P(x(i)，z(i)∣θ)=P(x(i)∣θ)P(x(i)，z(i)∣θ)=P(z(i)∣x(i)，θ))

所以可以看出在固定了参数 $θ \theta$ θ后， $Q_{i} (z^{(i)} Q_i(z^{(i)}$ Qi(z(i)求出后验概率，解决它的选择问题，确定了下界，即E步。然后那么如果能极大化这个下界，不就极大化了对数似然，解决了问题吗？即M步求解下式：

$a r g \max_{} \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g P (x^{(i)} ， z^{(i)} ∣ θ) arg \max \limits_{\theta} \sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log{P(x^{(i)}， z^{(i)}|\theta)}$ argθmaxi=1∑mz(i)∑Qi(z(i))logP(x(i)，z(i)∣θ)

EM算法能保证收敛吗？

证明极大似然单调增加就行了。再次的一起推导吧，即要证明： $\sum_{i = 1}^{m} l o g P (x^{(i)} ∣ θ^{j + 1}) \geq \sum_{i = 1}^{m} l o g P (x^{(i)} ∣ θ^{j}) \sum\limits_{i=1}^m logP(x^{(i)}|\theta^{j+1}) \geq \sum\limits_{i=1}^m logP(x^{(i)}|\theta^{j})$ i=1∑mlogP(x(i)∣θj+1)≥i=1∑mlogP(x(i)∣θj)

因为： $\sum_{i = 1}^{m} l o g P (x^{(i)} ∣ θ) = \sum_{i = 1}^{m} \sum_{z^{(i)}} P (z^{(i)} ∣ x^{(i)} ， θ^{j})) l o g P (x^{(i)} ， z^{(i)} ∣ θ) - \sum_{i = 1}^{m} \sum_{z^{(i)}} P (z^{(i)} ∣ x^{(i)} ， θ^{j})) l o g P (z^{(i)} ∣ x^{(i)} ， θ)) \sum\limits_{i=1}^m logP(x^{(i)}|\theta) =\sum\limits_{i=1}^m\sum\limits_{z^{(i)}}P( z^{(i)}|x^{(i)}，\theta^{j}))log{P(x^{(i)}， z^{(i)}|\theta)} - \sum\limits_{i=1}^m\sum\limits_{z^{(i)}}P( z^{(i)}|x^{(i)}，\theta^{j}))log{P( z^{(i)}|x^{(i)}，\theta)})$ i=1∑mlogP(x(i)∣θ)=i=1∑mz(i)∑P(z(i)∣x(i)，θj))logP(x(i)，z(i)∣θ)−i=1∑mz(i)∑P(z(i)∣x(i)，θj))logP(z(i)∣x(i)，θ))

然后对上式取 $θ^{j} \theta^j$ θj和 $θ^{j} + 1 \theta^j+1$ θj+1再相减，对于前半函数 $\sum_{i = 1}^{m} \sum_{z^{(i)}} P (z^{(i)} ∣ x^{(i)} ， θ^{j})) l o g P (x^{(i)} ， z^{(i)} ∣ θ) \sum\limits_{i=1}^m\sum\limits_{z^{(i)}}P( z^{(i)}|x^{(i)}，\theta^{j}))log{P(x^{(i)}， z^{(i)}|\theta)}$ i=1∑mz(i)∑P(z(i)∣x(i)，θj))logP(x(i)，z(i)∣θ)是我们M步要优化的部分，一定是增大的。后半部分相减可得：

$\sum_{i = 1}^{m} \sum_{z^{(i)}} P (z^{(i)} ∣ x^{(i)} ， θ^{j}) l o g \frac{P (z^{(i)} ∣ x^{(i)} ， θ^{j + 1})}{P (z^{(i)} ∣ x^{(i)} ， θ^{j})} \sum\limits_{i=1}^m\sum\limits_{z^{(i)}}P( z^{(i)}|x^{(i)}，\theta^{j})log\frac{P( z^{(i)}|x^{(i)}，\theta^{j+1})}{P( z^{(i)}|x^{(i)}，\theta^j)}$ i=1∑mz(i)∑P(z(i)∣x(i)，θj)logP(z(i)∣x(i)，θj)P(z(i)∣x(i)，θj+1)

在此利用Jensen不等式，该式 $\leq \sum_{i = 1}^{m} l o g (\sum_{z^{(i)}} P (z^{(i)} ∣ x^{(i)} ， θ^{j}) \frac{P (z^{(i)} ∣ x^{(i)} ， θ^{j + 1})}{P (z^{(i)} ∣ x^{(i)} ， θ^{j})}) \leq \sum\limits_{i=1}^mlog(\sum\limits_{z^{(i)}}P( z^{(i)}|x^{(i)}，\theta^{j})\frac{P( z^{(i)}|x^{(i)}，\theta^{j+1})}{P( z^{(i)}|x^{(i)}，\theta^j)})$ ≤i=1∑mlog(z(i)∑P(z(i)∣x(i)，θj)P(z(i)∣x(i)，θj)P(z(i)∣x(i)，θj+1)) $= \sum_{i = 1}^{m} l o g (\sum_{z^{(i)}} P (z^{(i)} ∣ x^{(i)} ， θ^{j + 1})) = 0 = \sum\limits_{i=1}^mlog(\sum\limits_{z^{(i)}}P( z^{(i)}|x^{(i)}，\theta^{j+1})) = 0$ =i=1∑mlog(z(i)∑P(z(i)∣x(i)，θj+1))=0

至此得证。不过正因为EM算法是自收敛的分类算法，所以既不需要事先设定类别也不需要数据见的两两比较合并等操作。只不过缺点是当所要优化的函数不是凸函数时，EM算法容易给出局部最佳解，而不是最优解。

采用EM算法求解的模型有哪些，为什么不用牛顿法或梯度下降法？

蒙特卡罗算法，混合高斯、协同过滤、k-means。

因为梯度下降虽然算法一定会收敛，但是可能会收敛到局部最优，而且求和的项数会随着隐变量的数目指数上升，会给梯度计算带来麻烦。相对来说，EM算法是一种非梯度优化算法。

如何判断函数凸或非凸？

为了得到全局最优，函数的凹凸性很重要。但可惜这是一个NP难问题。

可以通过Disciplined Convex Programming（DCP）：基本的凸函数原子库（atom library）和凸性演算规则（convexity calculus rules）

非凸优化问题转化为凸优化问题的方法：

1）修改目标函数，使之转化为凸函数

2）抛弃一些约束条件，使新的可行域为凸集并且包含原可行域

3）狭义的和广义的蒙特卡罗，在足够多的尝试后，几乎一定返回的是全局最优，或至少离全局最优“不那么远”。

用EM算法推导解释Kmeans

k-means是两个步骤交替进行:确定中心点，对每个样本选择最近中心点–> E步和M步。

E步中将每个点选择最近的类优化目标函数，分给中心距它最近的类(硬分配)，可以看成是EM算法中E步(软分配)的近似。
*M步中更新每个类的中心点，可以认为是在「各类分布均为单位方差的高斯分布」的假设下，最大化似然值。

实际上k-means是hard EM算法，而普通上一般说的EM算法是soft EM。所谓hard就是0-1二分抉择（即袋子里的球要么全红要么全蓝）。而Soft是一个概率，从这里可以再次看出为什么EM用于隐变量说明隐变量是服从某种存在的分布（隐分布）的。

广义EM算法

在上面求下界的推导中，通过观察到 $\sum_{z^{(i)}} Q_{i} (z^{(i)}) \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} 就是 P (z^{(i)} ∣ x^{(i)} ， θ)) 的期望 \sum\limits_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})} 就是P( z^{(i)}|x^{(i)}，\theta))的期望$ z(i)∑Qi(z(i))Qi(z(i))P(x(i)，z(i)∣θ)就是P(z(i)∣x(i)，θ))的期望，所以利用Jensen不等式可得的： $\sum_{i = 1}^{m} l o g \sum_{z^{(i)}} P (x^{(i)} ， z^{(i)} ∣ θ) = \sum_{i = 1}^{m} l o g \sum_{z^{(i)}} Q_{i} (z^{(i)}) \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} \geq \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} = \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g (P (x^{(i)} ， z^{(i)} ∣ θ)) - \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g (Q_{i} (z^{(i)}) = \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g (P (x^{(i)} ， z^{(i)} ∣ θ)) + H (Q_{i}) \sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}P(x^{(i)}， z^{(i)}|\theta) = \sum\limits_{i=1}^m log\sum\limits_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})} \\ \geq \sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})} \\ =\sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log(P(x^{(i)}， z^{(i)}|\theta))-\sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log(Q_i(z^{(i)})\\ =\sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log(P(x^{(i)}， z^{(i)}|\theta))+H(Q_i)$ i=1∑mlogz(i)∑P(x(i)，z(i)∣θ)=i=1∑mlogz(i)∑Qi(z(i))Qi(z(i))P(x(i)，z(i)∣θ)≥i=1∑mz(i)∑Qi(z(i))logQi(z(i))P(x(i)，z(i)∣θ)=i=1∑mz(i)∑Qi(z(i))log(P(x(i)，z(i)∣θ))−i=1∑mz(i)∑Qi(z(i))log(Qi(z(i))=i=1∑mz(i)∑Qi(z(i))log(P(x(i)，z(i)∣θ))+H(Qi)

这样不等式的右边就变成了自由能！那么E步的理解可以变为固定参数，优化隐分布， M步是固定隐分布，优化参数，即广义EM算法。

上面的式子当然还可以换种变化: $\geq \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g \frac{P (x^{(i)} ， z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} \geq \sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)}， z^{(i)}|\theta)}{Q_i(z^{(i)})}$ ≥i=1∑mz(i)∑Qi(z(i))logQi(z(i))P(x(i)，z(i)∣θ) $= \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g \frac{P (x^{(i)} ∣ z^{(i)}, θ) P (z^{(i)} ∣ θ)}{Q_{i} (z^{(i)})} =\sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)}| z^{(i)},\theta)P( z^{(i)}|\theta)}{Q_i(z^{(i)})}$ =i=1∑mz(i)∑Qi(z(i))logQi(z(i))P(x(i)∣z(i),θ)P(z(i)∣θ) $= \sum_{i = 1}^{m} \sum_{z^{(i)}} Q_{i} (z^{(i)}) l o g P (z^{(i)} ∣ θ) - K L [Q_{i} (x^{i}) ∣ ∣ P (x^{i} ∣ z^{i} ， θ)] =\sum\limits_{i=1}^m \sum\limits_{z^{(i)}}Q_i(z^{(i)})log P( z^{(i)}|\theta)-KL[Q_i(x^{i})||P(x^{i}|z^{i}，\theta)]$ =i=1∑mz(i)∑Qi(z(i))logP(z(i)∣θ)−KL[Qi(xi)∣∣P(xi∣zi，θ)]

没错，可以发现自由能于KL距离的关系，所以固定参数的情况下最优化KL距离，可以知道引入 $Q_{i} (z^{(i)} Q_i(z^{(i)}$ Qi(z(i)满足的条件只能是 $\sum_{z} Q_{i} (z^{(i)}) = 1 ， Q_{i} (z^{(i)}) \geq 0 的 P (x^{i} ∣ z^{i}, θ^{k - 1}) 分布 \sum\limits_{z}Q_i(z^{(i)}) =1，Q_i(z^{(i)})\geq0的P(x^{i}|z^{i},\theta^{k-1})分布$ z∑Qi(z(i))=1，Qi(z(i))≥0的P(xi∣zi,θk−1)分布，而这是最初推导时给出的隐函数条件。即可以知道广义EM的最优分布情况就是EM算法！！

广义EM的引申特例–VBEM算法

隐分布可不是那么好算的！有限制的隐分布情况。如果隐分布有了先验分布，计算限制等的时候，E步不可能做到无限制的最优，也就是说KL距离是无法为0。此时引入变分思想，即VBEM。

广义EM的引申特例–Wake-Sleep算法

在这里插入图片描述

即认知阶段与生成阶段。

广义EM的引申特例–Gibbs Sampling

在这里插入图片描述

某种程度上它不也是无限求最优下界嘛！

WS算法是VAE和GAN组合的简化版

KL距离的统一

Expectation-Maximum（EM算法）

expectation

相关阅读

栏目导航

推荐阅读

热门阅读