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

EM算法的引入

EM算法

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

输入：观测变量数据Y，隐变量数据Z，联合分布P(Y,Z|θ)，条件分布P(Z|Y,θ)；
输出：模型参数θ
（1）选择参数的初始值θ(0)，开始迭代
（2）E步：记θ(i)为第i此迭代参数θ的估计值，在第i+1此迭代的E步，计算
$Q (θ, θ (i)) = E z [log P (Y, Z | θ) | Y, θ (i)] = \sum Z log P (Y, Z | θ) P (Z | Y, θ (i)) (9.9)$
这里，P(Z|Y,θ(i))是在给定观测数据Y和当前的参数估计θ(i)下隐变量数据Z的条件概率分布；
（3）M步：求使得Q(θ,θ(i))极大化的θ，确定第i+1次迭代的参数的估计值θ(i+1)
θ(i+1)=argmaxθQ(θ,θ(i))
（4）重复第(2)步和第(3)步，直到收敛。

式(9.9)的函数Q(θ,θ(i))是EM算法的核心，称为Q函数(Q function)。
EM算法及其推广

EM算法（二）

极大似然估计

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

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

坐标上升

K-means使用的就是一种坐标上升方法。
EM算法及其推广

第三种情况

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

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

EM算法的目标函数

EM算法的推导

EM算法及其推广

注意

对于第一项，希望关于完全数据的似然函数的期望是可以计算的（存在解析形式）
对于第二项，希望关于辅助变量（隐变量）的条件后验存在解析形式。

总结
E步相当于利用隐变量的条件后验更新隐变量分布，然后计算完全数据关于隐变量的的期望。
M步相当于求上述期望关于模型变量的极大。

EM算法（三）

琴声不等式和KL散度

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

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

推导

设观测变量X受到隐变量T和参数θ影响。
EM算法及其推广
想要极大化观测变量X关于参数的对数似然函数

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

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

2.给定参数qk+1情况下，找到使得L(θ,qk+1)最大的θk+1
EM算法及其推广