EM算法是什么？什么是E（Epectation）？什么是M（Maximization）？什么又是公式里面出现的Q函数？这些公式都是怎么推导的？

极大似然和EM(Expectation Maximization)算法，与其说是一种算法，不如说是一种解决问题的思想，解决一类问题的框架，是很多具体算法的基础。

一、EM算法的背景和推导

EM算法主要是用在概率图中参数学习上面，如果具有完整观测数据集（指概率图中的所有变量都能观测到，即观测集中每条样本都包含了图中所有变量的观测值），直接用极大似然估计就能解决；但如果我们无法观测到图中所有的变量的，观测样本数据只包含图中部分变量的观测值， 这时我们称为不完整观测(Partial Observations)。所以这篇文章通过图模型的不完整观测的参数学习来理解EM算法。

1. 隐变量

我们把模型中无法观测到的变量称为隐变量或者潜在变量(Latent variable)。 潜变量是不能直接观测到的, 包含潜变量的模型称为潜变量模型 (latent variable models, LVM)。 此时可以把模型中的变量分为两类，一类是可以观测（有观测样本）到的变量集合，称为可观测变量或显变量， 用符号表示； 另一类是不可观测（没有观测样本）到的变量集合，称为不可观测变量或隐变量，用符号表示。 注意，这里和分别表示多个变量的集合，因为一个模型中变量可以有许多个。 完整的图模型联合概率分布记作。 依据概率图的知识，模型中观测变量集合的边缘概率分布需要通过边际化的方法得到：

观测数据的对数似然函数也就变成了如下形式：

由于包含隐变量，对数操作里面有求和符号，导致里面的内容无法继续拆解成独立的子项，导致对参数求偏导变得十分困难。

2. Jensen不等式

因为存在求和符号，所以可以转化成求平均，所以我们可以用Jensen不等式来改变对数似然函数的形式，如果函数是个上凹函数：，因为是上凹函数，所以可以将上式变成

我们为对数似然函数找到了一个下界函数，且无论这个是什么形式这个不等式都成立；

我们令为的后验概率分布，则可以发现下界函数与对数似然函数是等价的：

所以我们可以进行迭代，通过上一轮的参数值和观测数据得到隐变量的后验概率分布，通过对替换成后验概率的下界函数进行极大化，进而来极大化，来获得这一轮估计的和隐变量的后验概率分布。

我们使用一个辅助函数来代表有后验概率的下界函数：

这个辅助函数中对数的内部就是模型的联合概率，这个与完整数据观测的对数似然函数一样了， 可以方便的进行因子分解后求参数的偏导， 只需要极大化这个辅助函数得到本轮的参数值即可。

由于极大化的辅助函数是一个关于隐变量后验分布的期望形式，因此被称为期望最大化(Expectation-Maximization)算法，一般简称为EM算法。

3. EM算法

我们整理一下算法的执行过程，EM算法是一个迭代式的算法， 每次迭代有两个过程：E(Expectation)步骤和M(Maximization)步骤， 交替的执行这两个过程，直到参数收敛。

• 初始： 初始化模型的参数，可以选择随机初始化赋值，也可以使用一些复杂的参数初始化方法。

• E步骤： 计算隐变量集合 的后验概率分布，也可以看做是为了得到辅助函数。

• M步骤： 极大化辅助函数  得到本轮迭代的参数值。

这里就和正常的极大似然估计是一样的了，可以通过梯度法得到最优的参数值。

• 迭代： 交替执行E步骤和M步骤，直到参数收敛。

EM算法有两个特点：

1. EM算法得到的是局部最优解，不保证得到全局最优，这取决于似然函数是否是凸函数(或者凹函数)。
2. 通常EM算法前几次迭代收敛较快，在之后收敛速度回急剧下降。

EM算法是一个伟大的发明，它是解决潜变量模型的常用算法，应用十分的广泛。

4. EM算法就一种局部下限构造

我们通过Jensen不等式得到概率图模型的对数似然函数的下界函数：

从上式可以看出下界函数分为两部分，第一部分可以看做完整数据对数似然（模型联合概率）的期望。 第二部分是的熵，记作。另一种形式：

下界函数可以分为观测数据对数似然函数减去，构造出来的与的KL散度。因为我们想让下界函数最大，那就是说第二项的KL散度尽可能小，也就是要让构造出来的尽可能和真实的隐函数分布接近，这时候，KL散度为零。

所以之前让构造的函数取隐变量的后验概率分布后，Jensen不等式就能取等号，然后再对似然函数最大化更新，迭代过程如下：

这个也是所谓的九层境界里面的第二层（EM算法的九层境界：Hinton和Jordan理解的EM算法）

二、抛硬币的例子

我们接下来从一个简单的例子来理解EM算法；来源：Do, C. B., & Batzoglou, S. (2008). What is the expectation maximization algorithm? Nature Biotechnology, 26(8), 897–899. https://doi.org/10.1038/nbt1406

上面这篇著名的EM入门论文里面有一张很好的图例，利用抛硬币来说明EM，可是对于某些初学者来讲缺乏解读可能还是有点难理解思路。

下面尝试拆解一下分步骤解读

1、问题定义

已知： - 手上有两种不同的硬币，分别称为A和B

实验： - 随机抛硬币十次为一组，记录正面朝上（H）和反面朝上（T）的数据 - 换硬币重复试验

问题： - 分别求这两个硬币正面朝上的概率和

2、 完全信息 vs 包含隐函数的不完全信息

上图的实验过程中如果记录了当时抛的是A或者B哪种硬币，统计推断的时候知道了每一组是属于哪一种硬币的情况下那当然很好算，这种情况叫完全信息。

假如实验中根本不知道抛的时候究竟是哪一种硬币，或者就不告诉你的话，我们就没办法直接计算两种硬币正面朝上的概率了，这种情况叫不完全信息。例如上图的数据是和完全信息的情况一样的，区别在于左边的标签是问号，不知道是什么硬币。这个时候就用到了EM算法。

3、完全信息下的求解

每次抛硬币都是独立的，通过极大似然估计可以推导；

• 对于A来说，一共抛了三组共三十次，共24次向上6次向下，那么A硬币朝上的概率是。
• 对于B来说，一共抛了两组共二十次，共9次向上11次向下，那么B硬币朝上的概率是。

4、不完全信息下的初级EM求解

不完全信息情况呢？我们根本不知道每一组的结果是属于哪种硬币的，没办法用极大似然估计的方法算。这个时候硬币是否属于A的隐变量是未知的。

那怎么办？

想一下就发现，一组抛多次，不同硬币的抛出不同结果的概率是相当不同的。比如说：

• 一个的硬币抛出4H6T的概率是
• 而的硬币抛出4H6T的概率是

也就是说，倒过来说，看到4H6T的结果的时候，这个硬币本身朝上的概率更有可能是而不是0.3。可以通过观察抛出来的结果来推测原来硬币究竟是属于A还是B的方法叫做最大似然估计。

可是我们现在不知道和怎么办呢？这不是要求解的参数吗？面对这个蛋生鸡还是鸡生蛋的cul-de-sac（死胡同），我们的做法是：先蒙一个！然后再不停互相更新修改。

具体步骤

（1）先给和随便赋值。比如和 。

（2）然后算出

• A硬币抛出第一组的似然函数是。
• B硬币抛出第一组的似然函数是。

这个例子先按照比例来把第一组数据划分给A和B，这一步就类似于计算隐变量集合 的后验概率分布

• 划分给A的比例是。
• 同理划分给B的比例是。

对其他组也进行推算，得到。

（3）接下来得到了新的划分后的数据，可以更新参数了，计算每次结果中属于A和B的H和T的加权次数；

• 对于A来说，一共有21.3次向上8.6次向下，那么A硬币朝上的概率是。
• 对于B来说，一共有11.7次向上8.4次向下，那么B硬币朝上的概率是。

这一步就类似于极大化辅助函数得到本轮迭代的参数值。

（4）重复步骤（2）和（3），直到收敛，可以算得第十次循环之后，。

可以看到这个结果也跟之前完全信息算出来的比较接近。

三、混合模型的参数学习

在实际应用中，经常会遇到观测数据并不是从某个单一的总体分布中采样得到， 而是来源于多个拥有不同参数的相同分布。 这里首先给出一个概念：参数分布族(parametric family of distributions)。

参数分布族(parametric family of distributions)：参数分布族是指，属于同一种概率分布仅仅参数值不同的一类分布的集合， 比如拥有不同均值和方差的高斯分布组成的分布集合。

假设有一份某地小学生的身高数据，已知身高数据可以看做近似服从高斯分布， 这份数据中含有全部六个年级的学生，并且男生女生都有。 按照过去一般的处理逻辑，可以用一个高斯分布去拟合这份数据， 然而由于不同年龄段的孩子身高差异较大，用一个单一的高斯模型并不能很好的拟合数据， 此时可以用多个高斯分布去分别拟合不同年龄段不同性别的身高数据， 这些高斯分布拥有不同的均值和方差参数，但他们都是高斯分布，而不是什么其它的分布。 这就是一个典型的混合分布的例子，数据来源于一个参数分布族， 即不同参数的同一种分布。

1. 混合模型的有向图表示

现在我们用概率图的语言来描述混合模型， 首先定义一个离散类别变量，记作 ，随机变量  用于表示当前数据来源于哪一个具体的分布。 假设数据来源于  个不同参数的分布， 则类别变量  有  个取值，  表示第 i 条观测样本来源于第 k 个分布。 用  表示观测变量， 观测变量  一共有  个分量， 每个分量  有不同的参数。 混合模型的有向图可以用下图所示，其中 表示类别变量  的参数，  表示观测变量  的参数。

在混合模型中，一条观测样本的生成（采样）由两个变量控制，样本的生成过程为：

1. 首先，从变量  进行采样，假设采样值为  。
2. 然后，从变量  第  个分量（记作 ）中采样得到 x 。

模型的联合概率分布可以写为

其中变量是一个类别变量，它的边缘概率分布可以写为

响应变量有个分量，所有分量都属于同一种概率分布，只是参数不同。条件概率分布就表示每个分量的概率分布，可以写为

分量的具体分布取决于你的实际场景（数据）， 当是高斯分布时就被称为高斯混合模型， 这里我们暂时不关心它的具体形式，下一节再讨论高斯混合模型。

2. 不完整观测数据的参数估计

如果观测数据完整，变量不是隐变量，可以直接使用极大似然估计；然而在实际应用场景中，类别变量通常是不可观测的， 即我们并不知道样本是从的哪个分量取得的， 通常把模型中不可观测的变量称为隐变量或者潜在变量。 此时观测样本只有的值， 似然函数（所有样本的联合概率）为

根据图模型的推断理论，需要在联合概率的基础上通过边际化（消元）的方法得到边缘概率，

此时对数似然函数为

可以看到上式中对数ln内部存在一个求和符号， 这使得无法对公式进一步的拆解，这种情况下很难对其求偏导， 给参数估计带来了极大的困难。 在含有隐变量的模型中，需要对隐变量进行消元，以便得到观测变量的边缘概率， 而这个消元操作（求和或者积分）会出现在对数似然函数的对数内部， 最终导致对数似然函数无法分解，使得参数估计无比困难。 EM算法就是对这一问题的有效解决，通过 Jensen 不等式的理论， 可以在等价的情况下，把对数内部的求和操作转换到对数外部。

3. 使用EM算法

EM算法的具体推导过程看上文， 这里仅给出E步和M步的具体内容。

E-步骤： 得到隐变量的后验概率分布

用 表示 的后验概率分布的概率质量函数， 根据贝叶斯公式有

具体的为

其中都是已知量，其值使用上一轮迭代得到的估计值。 这一步的结果， 就是为每一条样本计算一个后验概率分布，其表示样本来自于各个分量的概率， 也可以认为是各个分量对样本的”贡献”。

M-步骤： 极大化期望，得到参数的解。

极大化的目标函数记作 ，其形式为

令，上式的一个简洁表示为

可以看到在上式中，对数内的联合概率项已经可以分解开，和完整观测的对数似然函数一样， 可以独立的估计每一项局部条件概率的参数。 稍微有点区别的是，每一项前面多了一个系数，并且需要对这个系数进行求和。可以看做是一个权重，可以理解成每一个分量对观测样本的”贡献” ，事实上，它含义就是在取得观测样本的条件下，观测样本i来自于第k个分量的概率。

4.高斯混合模型

当观测变量  是高斯分布时，就称为高斯混合模型（Gaussian mixture model,GMM） ，高斯混合模型是应用最广的混合模型。 此时构成  的每个分量都是一个高斯变量， 通常在高斯混合模型中， 的每个分量是一个多元高斯分布， 为了以示区分，我们用粗体符号，观测变量整体记作  ，第 k 个分量记作，粗体表示变量是一个多元高斯分布, 记作 。隐变量  仍然是一个服从类别分布的单变量， 记作 。

后续的不完整观测数据的参数学习类似。

参考

不完整观测的学习-张振虎

EM Algorithm 从直观到数学理解

EM算法的九层境界

---

• ← Previous Post
• Next Post →