EM算法

Jensen 不等式

要学习 EM 算法，需要先了解 Jensen 不等式：

假设 ff 为凸函数，XX 为随机变量，则有 E[f(X)]≥f(EX)E[f(X)]≥f(EX)，若假设 ff 为严格凸函数，则 E[f(X)]=f(EX)E[f(X)]=f(EX) 当且仅当 X≡E[X]X≡E[X]，即 XX 是一个常量。

EM 算法的一般形式

假设我们有一个数据集 x(1),x(2),⋯,x(m)x(1),x(2),⋯,x(m)，我们要用一个模型去拟合数据，模型为 p(x(i),z(i))p(x(i),z(i))。这里我们不会像高斯混合模型那样假设 zz 服从多项式分布，并假设 xx 服从正态分布。我们只假设 zz 和 xx 服从某一分布。从这也可以看出高斯混合模型是 EM 算法的一个特例。

利用 Jensen 不等式得到对数似然函数的下界

在一个有隐含变量的模型中，对数似然函数的形式通常为以下形式，在下式中 zz 就是隐含变量。
l(θ)=m∑i=1logp(x(i);θ) =m∑i=1log∑z(i)p(x(i),z(i);θ)l(θ)=∑i=1mlogp(x(i);θ)=∑i=1mlog∑z(i)p(x(i),z(i);θ)

我们进一步处理上面的式子：
m∑i=1logp(x(i);θ)=m∑i=1log∑z(i)p(x(i),z(i);θ) =m∑i=1log∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))∑i=1mlogp(x(i);θ)=∑i=1mlog∑z(i)p(x(i),z(i);θ)=∑i=1mlog∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))

其中 ∑zQi(z)=1∑zQi(z)=1 并且 Qi(z)≥0Qi(z)≥0，我们分析一下上述式子，其中 p(x(i),z(i);θ)Qi(z(i))p(x(i),z(i);θ)Qi(z(i)) 可以看成 z(i)z(i) 的函数，QiQi 则是 z(i)z(i) 的概率分布，那么 ∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i)) 就是对 z(i)z(i) 的函数求期望，再因为 loglog 函数为凹函数（相对于凸函数，Jensen 不等式的符号要翻转一下，即 E[log(X)]≤log(EX)E[log(X)]≤log(EX)，接下来我们使用 Jensen 不等式得到下面的不等式：
log∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))≥∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))log∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))≥∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))

也就可以得到：
m∑i=1log∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))≥m∑i=1∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))∑i=1mlog∑z(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))≥∑i=1m∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))

综合上面的所有的推导过程，我们可以得到以下不等式：
l(θ)≥m∑i=1∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))l(θ)≥∑i=1m∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))

利用得到的下界进行极大似然估计

我们在上述的推导过程中得到了对数似然函数的一个下界，为了能在这个下界上进行极大似然估计，我们再次看一下 Jensen 不等式的性质，若假设 ff 为严格凸函数，则 E[f(X)]=f(EX)E[f(X)]=f(EX) 当且仅当 X≡E[X]X≡E[X]，即 XX 是一个常量。我们想在下界上进行极大似然估计，就得让不等式取等号，即：
l(θ)=m∑i=1∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))l(θ)=∑i=1m∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))

下面我们就推导出什么情况下等号成立，要想等号成立，当且仅当 X≡E[X]X≡E[X]，也就是让 XX 为一个常数，假设这个常数为 cc，也就是：
p(x(i),z(i);θ)Qi(z(i))≡cp(x(i),z(i);θ)Qi(z(i))≡c

这也很容做到，只要我们保证：
Qi(z(i))∝p(x(i),z(i);θ)Qi(z(i))∝p(x(i),z(i);θ)

也就是让分子分母成比例，这样分式将会是一个常数。另外，我们知道有以下等式：
∑zQi(z(i))=1∑zQi(z(i))=1

我们可以如下选择 Q：
Qi(z(i))=p(x(i),z(i);θ)∑z(i)p(x(i),z(i);θ)=p(z(i)|x(i);θ)Qi(z(i))=p(x(i),z(i);θ)∑z(i)p(x(i),z(i);θ)=p(z(i)|x(i);θ)

我们验证一下是不是符合条件：
p(x(i),z(i);θ)Qi(z(i))≡1∑z(i)p(x(i),z(i);θ)p(x(i),z(i);θ)Qi(z(i))≡1∑z(i)p(x(i),z(i);θ)
∑zQi(z(i))=1∑zQi(z(i))=1

我们经过一系列推导最终得出，如果我们要利用通过 Jensen 不等式得到的下界进行极大似然估计，那么我们需要如下设置 Q 分布，对于一个具体的问题，我们假设 zz 属于某一分布并假设 xx 属于某一分布，同时我们先对所有分布初始化一个参数，那么我们就可以计算出 p(z(i)|x(i);θ)p(z(i)|x(i);θ)，也就是计算出样本 x(i)x(i) 在参数为 θθ 时，属于各个分布的概率。计算出所有样本的 Qi(z(i))Qi(z(i)) 后，带入到对数似然函数中，再求导，让导数为 0，进行极大似然估计，然后更新参数，迭代，直到收敛即可。
Qi(z(i))=p(z(i)|x(i);θ)Qi(z(i))=p(z(i)|x(i);θ)

得到 EM 的一般形式

1. 首先我们要初始化参数 θθ
2. 重复以下步骤直到收敛：
   （1）E-Step：对于当前参数 θθ，找到使 l(θ)=∑mi=1∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))l(θ)=∑i=1m∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i)) 成立的 Q 分布，即让 Qi(z(i))=p(z(i)|x(i);θ)Qi(z(i))=p(z(i)|x(i);θ)
   （2）M-step：在 M-step 中对对数似然函数进行极大似然估计，得到新的参数 θθ，形式化表述为 θ:=argmaxθ∑mi=1∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))θ:=argmaxθ∑i=1m∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))

EM 算法中的坐标上升过程

如果我们将 EM 算法的优化目标看成：
J(Q,θ)=m∑i=1∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))J(Q,θ)=∑i=1m∑z(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))
那么 EM 算法就可以看做是对目标函数的坐标上升过程，在 E-step 中，θθ 不变，调整 Q 使函数变大，在 M-step 中，Q 不变，调整 θθ 使目标函数变大。

EM 算法的直观图示

1. 斯坦福机器学习公开课 —— 吴恩达
2. 斯坦福ML机器学习公开课笔记 —— 张雨石
3. 图片来自网络，如有侵权，麻烦联系我删除。

文章标题:EM算法

文章字数:1,456

本文作者:ylhao

发布时间:2018-05-15, 23:44:09

最后更新:2019-06-07, 11:50:53

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。