机器学习（十九）EM:期望最大算法

1 EM算法简介

最大期望算法(Expectation Maximization Algorithm，又译期望最大化算法)，是一种迭代算法，用于含有隐变量(hidden variable)的概率参数模型的最大似然估计或极大后验概率估计。

在统计计算中，最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。

未观测变量的学名是“隐变量”（latent variable）。EM算法是常用的估计参数隐变量的利器，它是一种迭代式的方法，其基本思想是：若参数θ已知，则可根据训练数据推断出最优隐变量Z的值(E步)；反之，若Z的值已知，则可以方便地对参数θ做极大似然估计(M步)。

于是，以初始值θ⁰为起点，可迭代执行以下步骤直至收敛：

• 基于θ^t推断隐变量Z的期望，记为Z^t;
• 基于已观测变量X和Z^t对参数θ做极大似然估计，记为θ^t+1

2  抛硬币例子

我们现在考虑两个抛硬币的例子：

"给定两个硬币A和B，随机抛掷后正面朝上概率分别记为 p'和'q'。每次随机选择一个硬币并投掷。有以下观察序列：H _A H _A T _B T _A T _B H _B H _B T _A H _B H _A T _A T _A H _A H _B H _A T _B，从给定数据估计出'p'和'q'的值"。

我们很容易计算出p：

相似地可以计算出q:

这很容易，因为计算未知参数所需的所有信息都是可获得的。但是，如果硬币上的标签(A和B)被隐藏起来,不知道每次投掷哪个硬币。鉴于A和B硬币同样可能被选中，那我们如何估计未知参数'p'和'q'?

我们将尝试通过多次迭代计算来解决问题。在每次迭代中，我们有两个步骤，'E'步骤和'M'步骤。

“E”步骤（期望）：

1. 首先初始化p和q的值(初始猜测)。
2. 我们不是说掷硬币来自特定的硬币，而是说它以概率为'x'来自硬币A，来自硬币B概率'1-x'。
3. 计算每枚硬币的正反面期望数量。

“M”步骤（最大化）：

1. 从“E”步骤计算步骤3中每个硬币的正反面期望的对数似然，类似于MLE计算。
2. 最大似然估计出隐变量，并重新估计p和q的新值
3. 使用新的p和q值重复“E”步骤，直到它收敛为止。

让我们举一个例子，其中进行了5次实验并且在每次实验中进行了10次抛掷。（使用两个硬币）。

我们从对未知参数进行初始化猜测，假设p = 0.6和q = 0.5。让我们进行第一轮实验。将此观察序列称为'S'，我们想要估计观察'S'来自硬币A的可能性是多少，即P（A | S）。回想贝叶斯定理：

P(A)是选择硬币A的概率，它是0.5（因此是P(B)），因为我们知道每个硬币具有相同的被选择的概率。P(S|A)是观察的概率，因为它来自硬币A，即使用二项分布，我们推断它是：

同样地有，

P(S)是观察序列的概率。由于观察可以来自硬币A或硬币B或两者，因此：

然后可以得到：

将初始猜测的值代入p = 0.6和q = 0.5，得到P（A | S）= 0.45，因此P（B | S）= 1-P（A | S）= 0.55。

因此，给定观察序列S，它来自硬币A的概率是0.45并且来自硬币B的概率是0.55。因此，来自硬币A正面期望数量 = 5 * 0.45并且反面期望数量= 5 * 0.45，类似地，来自硬币B的正面的期望数量= 5 * 0.55并且反面期望数量= 5 * 0.55。对其他四个实验重复相同的期望（E）步骤，我们得到硬币A 正面期望总数= 21.3和反面期望总数= 8.6，类似于硬币B，正面期望总数= 11.7，反面期望总数= 8.4

因此，对未知参数p和q的新估计是：

和

上一步是“M”步骤或最大化步骤。我们重复上述EM步骤，直到'p'和'q'的值收敛。在这个例子中，'p'和'q'的值在大约10步中收敛到最终值p = 0.8和q = 0.52。

以上是EM算法应用的一个非常简单的例子。它用于表明给定具有缺失数据(含有隐变量)的参数估计问题，EM算法可以通过生成对丢失数据的可能猜测来迭代地解决该问题，然后通过使用这些猜测来最大化观察的可能性。除了简单的投掷硬币示例之外，EM已成功用于训练隐藏状态的HMM，EM也用于  聚类应用  和  半监督学习

3 EM算法推导

上面是EM算法的一个简单感性的例子，下面我们看看如何用数学推导EM算法。在引入EM算法之前，我们先了解一些基础知识。

3.1 凸函数(Convex Functions)

定义1  假设f是在区间I = [a, b]的一个实数函数，当满足以下条件时，可以说f在区间是凸函数，

此时，∀x1, x2 ∈ I, λ ∈ [0, 1]

定义2 如果-f是凸函数，那么f是凹函数.

定理1 如果f(x)在区间[a,b]上二阶可导，并且f''(x) ≥0，那么f(x)在[a,b]上是凸函数

证明

结论1 在(0, ∞)，-ln(x)为凸函数，ln(x)为凹函数

证明

3.2 Jensen’s 不等式

在区间I上，f是一个凸函数，有x1, x2, . . . , xn∈I，λ1, λ2, . . . , λn ≥ 0，

并且

那么有

证明

因为ln(x)为凹函数，那么有

结论2 Jensen's不等式同时也证明了算数平均要大于等于几何平均

证明

3.3 EM推导

假设X是一个随机样本集，用来估计θ，我们希望找到一个θ使得P(X|θ) 最大，这就是称作为θ的最大似然估计。为了估计θ，通常是需要引入对数似然函数，定义为如下：

这个似然函数可以看作为给定样本集X上的关于θ的函数。因为ln(x)是一个严格单调递增函数，所以使P(X|θ)达到最大也会使L(θ)最大化。

EM算法是一个最大化L(θ)(或者说是极大似然估计)的迭代过程。假设在经过n^th迭代之后，由θ_n得到当前估计θ，那么我们的目标是最大化L(θ)，所以我们希望更新后的θ满足如下：

相应地，我们就是想最大化下面的差值：

EM算法是常用的估计参数隐变量的利器。到目前为止，我们还没有考虑任何不能观察到的变量或者缺失变量，对于上述情况，由于存在隐含变量，不能直接最大化l(θ)，所以只能不断地建立l的下界（E-step），再优化下界（M-step），依次迭代，直至算法收敛到局部最优解。这就是EM算法的核心思想，简单的归纳一下：

EM算法通过引入隐含变量,使用MLE（极大似然估计）进行迭代求解参数。通常引入隐含变量后会有两个参数，EM算法首先会固定其中的第一个参数，然后使用MLE计算第二个变量值；接着通过固定第二个变量，再使用MLE估测第一个变量值，依次迭代，直至收敛到局部最优解。

E-Step和M-Step:

• E-Step：通过observed data和现有模型估计参数估计值 missing data；
• M-Step：假设missing data已知的情况下，最大化似然函数。

现在我们引入隐含变量的集合为Z,具体值记为z,那么P(X|θ) 可以写成：

带入之前的差值公式可以得到：

我们这里引入Jensen's不等式，

继续推导之前的公式：

从式子(12)到式子(13)我们用到了：

所以有：

为了方便，做如下变换：

我们有如下函数图像：

可以推导出：

我们发现l(θn|θn)始终在L(θ)之下，并且在θ时会相等，因此假如一个θ使得l(θn|θn)变大，那么L(θ)也会变大，所以求解转化为如下：

4 参考资料

• EM_algorithm
• Expectation Maximization with an Example
• EM-最大期望算法