EM算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计，或极大后验概率估计。
EM算法的每次迭代由两步组成：E步，求期望；M步，求极大。所以这一算法称为期望极大算法，简称EM算法。

EM算法的引入

EM算法

EM算法与初值的选择有关，选择不同的初值可能得到不同的参数估计值。
一般地，用Y表示观测随机变量的数据，Z表示隐随机变量的数据。Y和Z连在一起称为完全数据，观测数据Y又称为不完全数据。
EM算法

输入：观测变量数据Y，隐变量数据Z，联合分布 <nobr> P(Y,Z|θ) </nobr>，条件分布 <nobr> P(Z|Y,θ) </nobr>；
输出：模型参数 <nobr> θ </nobr>
（1）选择参数的初始值 <nobr> θ(0) </nobr>，开始迭代
（2）E步：记 <nobr> θ(i) </nobr>为第i此迭代参数 <nobr> θ </nobr>的估计值，在第i+1此迭代的E步，计算

<nobr> Q(θ,θ(i))=Ez[logP(Y,Z|θ)|Y,θ(i)]=∑ZlogP(Y,Z|θ)P(Z|Y,θ(i))(9.9) </nobr>

这里， <nobr> P(Z|Y,θ(i)) </nobr> 是在给定观测数据Y和当前的参数估计 <nobr> θ(i) </nobr> 下隐变量数据Z的条件概率分布；
（3）M步：求使得 <nobr> Q(θ,θ(i)) </nobr> 极大化的 <nobr> θ </nobr> ，确定第i+1次迭代的参数的估计值 <nobr> θ(i+1) </nobr>
<nobr> θ(i+1)=argmaxθQ(θ,θ(i)) </nobr>
（4）重复第(2)步和第(3)步，直到收敛。

式(9.9)的函数 <nobr> Q(θ,θ(i)) </nobr>是EM算法的核心，称为Q函数(Q function)。

EM算法（二）

极大似然估计

我们可将对数据建模的方法分为两大类，概率模型和非概率模型
概率模型：
1. 贝叶斯分类器
2. 逻辑回归
3. 最小二乘法回归和岭回归（使用ML和MAP解释）
4. 贝叶斯线性回归
非概率模型：
1. 感知机
2. 支持向量机
3. 决策树
4. K-means
在上述每一种方法中，我们都有一个想要优化的目标函数（贪婪或非贪婪，局部或全局）

一种概率的目标函数是极大化（对数）似然函数。对于一些模型，可以找到参数 <nobr> θML </nobr>的极大似然估计值得解析解，然后代入数据求解。
但是对于更加复杂的模型，可能将参数分为两组 <nobr> θ1,θ2 </nobr>，然后求解关于两个组参数的极大似然估计
<nobr> θ1,ML,θ2,ML=argmaxθ1,θ2∑ni=1lnp(xi|θ1,θ2) </nobr>
尽管可以在给定一个参数的条件下求得另一个参数，但是不能同时求解两者。

坐标上升

K-means使用的就是一种坐标上升方法。

第三种情况

我们想要获得
<nobr> θ1,ML=argmaxθ1∑ni=1lnp(xi|θ1) </nobr>
但是这个函数很难直接进行优化。但是，我们发现我们可以添加第二个变量 <nobr> θ2 </nobr>使得
<nobr> ∑ni=1lnp(xi,θ2|θ1)(Function 2) </nobr>
容易处理。
注意

• 第二个函数中， <nobr> θ2 </nobr>在条件符的左侧，这意味着 <nobr> θ2 </nobr>上存在着先验。
• 接下来使用EM算法通过Function 2求解 <nobr> θ1,ML </nobr>

EM算法的目标函数

首先需要定义一个较通用的目标函数使得能够：
1. 易于优化给定 <nobr> θ1 </nobr>的关于x的边缘分布 <nobr> p(x|θ1) </nobr>
2. 仅出于计算方便的考虑，使用 <nobr> p(x,θ2|θ1) </nobr>来计算
EM目标函数
<nobr> lnp(x|θ1)=∫q(θ2)lnp(x,θ2|θ1)q(θ2)dθ2+∫q(θ2)lnq(θ2)p(θ2|x,θ1)dθ2 </nobr>
注意
1. <nobr> q(θ2) </nobr>可以是任意概率分布
2. 假设我们知道 <nobr> p(θ2|x,θ1) </nobr>。即，给定数据x和固定的 <nobr> θ1 </nobr>，我们可以解出关于 <nobr> θ2 </nobr>的条件后验分布(存在解析解)。

EM算法的推导

注意

• 对于第一项，希望关于完全数据的似然函数的期望是可以计算的（存在解析形式）
• 对于第二项，希望关于辅助变量（隐变量）的条件后验存在解析形式。
  
  总结
• E步相当于利用隐变量的条件后验更新隐变量分布，然后计算完全数据关于隐变量的的期望。
• M步相当于求上述期望关于模型变量的极大。

EM算法（三）

琴声不等式和KL散度

对于凹函数（如log x）有
<nobr> f(Ep(t)t)≥Ep(t)f(t) </nobr>

KL散度用于衡量两个分布之间的差异，不具有对称性，不是一种距离度量。
<nobr> KL(q||p)=∫q(x)logq(x)p(x)dx </nobr>
具有一下性质
1. <nobr> KL(q||p)≠KL(p||q) </nobr>
2. <nobr> KL(q||q)=0 </nobr>
3. <nobr> KL(q||p)≥0 </nobr>

推导

设观测变量X受到隐变量T和参数 <nobr> θ </nobr>影响。

想要极大化观测变量X关于参数的对数似然函数

由于完全变量关于参数的对数似然函数不易直接优化，考虑利用琴声不等式找到一个下届函数进行优化。

1. 给定参数 <nobr> θk </nobr>情况下，找到使得 <nobr> L(θk,q) </nobr>最大的 <nobr> qk+1 </nobr>

2.给定参数 <nobr> qk+1 </nobr>情况下，找到使得 <nobr> L(θ,qk+1) </nobr>最大的 <nobr> θk+1 </nobr>

E步，求期望细节

M步，求极大细节

EM算法的导出

EM算法是通过不断求解下界的极大化逼近对数似然函数极大化的算法。
EM算法不能保证找到全局最优值。

EM算法在非监督学习中的应用

待补充

EM算法的收敛性

EM算法提供一种近似计算含有隐变量概率模型的极大似然估计方法。
问题
1. EM算法得到的估计序列是否收敛
2. 若收敛，收敛的全局最大还是局部极大值？

定理9.1
设 <nobr> P(Y|θ) </nobr>是观测数据的似然函数， <nobr> θ(i)(i=1,2,...) </nobr>为EM算法得到的参数估计序列， <nobr> P(Y|θ(i))(i=1,2,...) </nobr>为对应的似然函数序列，则 <nobr> P(Y|θ(i)) </nobr>是单调递增的，即
<nobr> P(Y|θ(i+1))≥P(Y|θ(i)) </nobr>

单调有界定理

定理9.2

EM算法在高斯混合模型中的应用

请参阅高斯混合模型GMM

EM算法的推广

待补充

总结

参考资料

《统计学习方法》第9章
《Machine Learning》ColumbiaX: CSMM.102x Lecture 15
《Bayesian Methods for Machine Learning》