【原理】期望最大算法EM——含有隐变量的概率参数模型的最大似然估计或极大后验概率估计_期望最大化算法的原理
赞
踩
EM 算法，全称 Expectation Maximization Algorithm。期望最大算法是一种迭代算法，用于含有隐变量（Hidden Variable）的概率参数模型的最大似然估计或极大后验概率估计。
本文思路大致如下：先简要介绍其思想，然后举两个例子帮助大家理解，有了感性的认识后再进行严格的数学公式推导。
1. 思想
EM 算法的核心思想非常简单，分为两步：Expection-Step 和 Maximization-Step。E-Step 主要通过观察数据和现有模型来估计参数，然后用这个估计的参数值来计算似然函数的期望值；而 M-Step 是寻找似然函数最大化时对应的参数。由于算法会保证在每次迭代之后似然函数都会增加，所以函数最终会收敛。
2. 举例
我们举两个例子来直观的感受下 EM 算法。
2.1 例子 A
第一个例子我们将引用 Nature Biotech 的 EM tutorial 文章中的例子。
2.1.1 背景
假设有两枚硬币 A 和 B，他们的随机抛掷的结果如下图所示：
我们很容易估计出两枚硬币抛出正面的概率：
现在我们加入隐变量，抹去每轮投掷的硬币标记：
碰到这种情况，我们该如何估计 θ A \theta _A θA和 θ B \theta _B θB的值？
我们多了一个隐变量 Z = ( z 1 , z 2 , z 3 , z 4 , z 5 ) Z=(z_1,z_2,z_3,z_4,z_5) Z=(z1,z2,z3,z4,z5) ，代表每一轮所使用的硬币，我们需要知道每一轮抛掷所使用的硬币这样才能估计 θ A \theta _A θA和 θ B \theta _B θB的值，但是估计隐变量 Z Z Z 我们又需要知道 θ A \theta _A θA和 θ B \theta _B θB 的值，才能用极大似然估计法去估计出 Z。这就陷入了一个鸡生蛋和蛋生鸡的问题。
其解决方法就是先随机初始化 θ A \theta _A θA和 θ B \theta _B θB，然后用去估计 Z， 然后基于 Z 按照最大似然概率去估计新的 θ A \theta _A θA和 θ B \theta _B θB，循环至收敛。
2.1.2 计算
随机初始化
θ
A
=
0.6
\theta _A=0.6
θA=0.6和
θ
B
=
0.5
\theta _B=0.5
θB=0.5
对于第一轮来说，如果是硬币 A，得出的 5 正 5 反的概率为：
0.
6
5
∗
0.
4
5
0.6^5*0.4^5
0.65∗0.45；如果是硬币 B，得出的 5 正 5 反的概率为：
0.
5
5
∗
0.
5
5
0.5^5*0.5^5
0.55∗0.55 。我们可以算出使用是硬币 A 和硬币 B 的概率分别为：
从期望的角度来看，对于第一轮抛掷，使用硬币 A 的概率是 0.45，使用硬币 B 的概率是 0.55。同理其他轮。这一步我们实际上是估计出了 Z 的概率分布，这部就是 E-Step。
>>> a= 0.6**9*0.4
>>>> b = 0.5**10
>>>> a/(a+b)
>0.804985517232276
> >>> b/(a+b)
> 0.19501448276772407
- 1
- 2
- 3
- 4
- 5
- 6
结合硬币 A 的概率和上一张投掷结果，我们利用期望可以求出硬币 A 和硬币 B 的贡献。
以第二轮硬币 A 为例子，计算方式为：
于是我们可以得到：
然后用极大似然估计来估计新的
θ
A
\theta _A
θA和
θ
B
\theta _B
θB 。
这步就对应了 M-Step，重新估计出了参数值。
如此反复迭代10次，我们就可以算出最终的参数值。
2.2 例子 B
如果说例子 A 需要计算你可能没那么直观，那就举更一个简单的例子：
现在一个班里有 50 个男生和 50 个女生，且男女生分开。我们假定男生的身高服从正态分布： N ( u 1 , p 1 ) N(u_1,p_1) N(u1,p1)，女生的身高则服从另一个正态分布： N ( u 2 , p 2 ) N(u_2,p_2) N(u2,p2)。这时候我们可以用极大似然法（MLE），分别通过这 50 个男生和 50 个女生的样本来估计这两个正态分布的参数。
但现在我们让情况复杂一点，就是这 50 个男生和 50 个女生混在一起了。我们拥有 100 个人的身高数据，却不知道这 100 个人每一个是男生还是女生。
这时候情况就有点尴尬，因为通常来说，我们只有知道了精确的男女身高的正态分布参数我们才能知道每一个人更有可能是男生还是女生。但从另一方面去考量，我们只有知道了每个人是男生还是女生才能尽可能准确地估计男女各自身高的正态分布的参数。
这个时候有人就想到我们必须从某一点开始，并用迭代的办法去解决这个问题：我们先设定男生身高和女生身高分布的几个参数（初始值），然后根据这些参数去判断每一个样本（人）是男生还是女生，之后根据标注后的样本再反过来重新估计参数。之后再多次重复这个过程，直至稳定。这个算法也就是 EM 算法。
3. 推导
给定数据集，假设样本间相互独立，我们想要拟合模型
p
(
x
;
θ
)
p(x;\theta)
p(x;θ) 到数据的参数。根据分布我们可以得到如下似然函数：
第一步是对极大似然函数取对数，第二步是对每个样本的每个可能的类别 z 求联合概率分布之和。如果这个 z 是已知的数，那么使用极大似然法会很容易。但如果 z 是隐变量，我们就需要用 EM 算法来求。
事实上，隐变量估计问题也可以通过梯度下降等优化算法，但事实由于求和项将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；而 EM 算法则可看作一种非梯度优化方法。
上面式子中，第一步是求和每个样本的所有可能的类别 z 的联合概率密度函数，但是这一步直接求导非常困难，所以将其分母都乘以函数 Q i ( z ) Q_i(z) Qi(z) ，转换到第二步。从第二步到第三步是利用 Jensen 不等式。
通过上面我们得到了： L ( θ ) > = J ( z , Q ) L(\theta)>=J(z,Q) L(θ)>=J(z,Q) 的形式（z 为隐变量），那么我们就可以通过不断最大化 J ( z , Q ) J(z,Q) J(z,Q) 的下界来使 L ( θ ) L(\theta) L(θ)得 不断提高。下图更加形象：
也就是说，EM 算法通过引入隐含变量，使用 MLE（极大似然估计）进行迭代求解参数。通常引入隐含变量后会有两个参数，EM 算法首先会固定其中的第一个参数，然后使用 MLE 计算第二个变量值；接着通过固定第二个变量，再使用 MLE 估测第一个变量值，依次迭代，直至收敛到局部最优解。
3.1 两个问题
- 什么时候下界 J ( z , Q ) J(z,Q) J(z,Q)与 L ( θ ) L(\theta) L(θ)相等？
- 为什么一定会收敛？
对于第二个问题，为什么一定会收敛？
这边简单说一下，因为每次
更新时（每次 θ \theta θ迭代时），都可以得到更大的似然函数，也就是说极大似然函数时单调递增，那么我们最终就会得到极大似然估计的最大值。
但是要注意，迭代一定会收敛，但不一定会收敛到真实的参数值，因为可能会陷入局部最优。所以 EM 算法的结果很受初始值的影响。
4 . EM算法另一种理解
坐标上升法（Coordinate ascent）：
图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。
这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步：固定θ，优化Q；M步：固定Q，优化θ；交替将极值推向最大。
5. EM的应用
EM算法有很多的应用，最广泛的就是GMM混合高斯模型、聚类、HMM等等。具体可以参考JerryLead的cnblog中的Machine Learning专栏：
混合高斯模型（Mixtures of Gaussians）和EM算法
K-means聚类算法
6.cite
【机器学习】EM——期望最大（非常详细）
Do, C. B., & Batzoglou, S. (2008). What is the expectation maximization algorithm?. Nature biotechnology, 26(8), 897.
从最大似然到EM算法浅解
怎么通俗易懂地解释EM算法并且举个例子?
(EM算法）The EM Algorithm
Andrew Ng《The EM algorithm》
7. other
求最大似然函数估计值的一般步骤：
（1）写出似然函数；
（2）对似然函数取对数，并整理；
（3）求导数，令导数为0，得到似然方程；
（4）解似然方程，得到的参数即为所求；
8. EM 与 meanshift
