EM 算法

1. 如果概率模型的变量都是观测变量，则给定数据之后，可以直接用极大似然估计法或者贝叶斯估计法来估计模型参数。 但是当模型含有隐变量时，就不能简单的使用这些估计方法。此时需要使用EM 算法。
   • EM 算法是一种迭代算法。
   • EM 算法专门用于含有隐变量的概率模型参数的极大似然估计，或者极大后验概率估计。

2. EM算法的每次迭代由两步组成：
   • E步求期望。
   • M步求极大。

   所以EM算法也称为期望极大算法。

一、示例

1.1 身高抽样问题

1. 假设学校所有学生中，男生身高服从正态分布

， 女生身高服从正态分布

。 现在随机抽取200名学生，得到这些学生的身高

，求参数

的估计。

1. 定义隐变量为

，其取值为

，分别表示男生、女生 。

• 如果隐变量是已知的，即已知每个学生是男生还是女生

，则问题很好解决：

• 统计所有男生的身高的均值和方差，得到

：

其中

表示满足

的

构成的集合。

分别表示平均值和方差。

• 统计所有女生的身高的均值和方差，得到

：

其中

表示满足

的

构成的集合。

分别表示平均值和方差。

• 如果已知参数

，则任意给出一个学生的身高

，可以知道该学生分别为男生/女生的概率。

则有：

。因此也就知道该学生更可能为男生，还是更可能为女生。

因此：参数

学生是男生/女生，这两个问题是相互依赖，相互纠缠的。

1. 为解决该问题，通常采取下面步骤：
   • 先假定参数的初始值：

   。

   • 迭代 ：
   • 根据

   来计算每个学生更可能是属于男生，还是属于女生。 这一步为E 步（Expectation），用于计算隐变量的后验分布

   。

   • 根据上一步的划分，统计所有男生的身高的均值和方差，得到

   ；统计所有女生的身高的均值和方差，得到

   。 这一步为 M 步（Maximization ），用于通过最大似然函数求解正态分布的参数。

   • 当前后两次迭代的参数变化不大时，迭代终止。

1.2 三硬币模型

1. 已知三枚硬币 A，B，C ，这些硬币正面出现的概率分别为

。进行如下试验：

• 先投掷硬币 A，若是正面则选硬币 B；若是反面则选硬币 C 。
• 然后投掷被选出来的硬币，投掷的结果如果是正面则记作 1；投掷的结果如果是反面则记作0 。
• 独立重复地

次试验，观测结果为： 1,1,0,1,0,...0,1 。

现在只能观测到投掷硬币的结果，无法观测投掷硬币的过程，求估计三硬币正面出现的概率。

1. 设：
   • 随机变量

   是观测变量，表示一次试验观察到的结果，取值为 1 或者0

   • 随机变量

   是隐变量，表示未观测到的投掷A硬币的结果，取值为 1 或者 0

   是模型参数

   则：

注意：随机变量

的数据可以观测，随机变量

的数据不可观测

1. 将观测数据表示为

，未观测数据表示为

。 由于每次试验之间都是独立的，则有：

1. 考虑求模型参数

的极大似然估计，即：

这个问题没有解析解，只有通过迭代的方法求解，EM算法就是可以用于求解该问题的一种迭代算法。

1. EM算法求解： 首先选取参数的初值，记作

，然后通过下面的步骤迭代计算参数的估计值，直到收敛为止： 设第

次迭代参数的估计值为：

， 则EM算法的第

次迭代如下：

• E步：计算模型在参数

下，观测数据

来自于投掷硬币 B 的概率：

它其实就是

，即：已知观测变量

的条件下，观测数据

来自于投掷硬币 B 的概率。

• M 步：计算模型参数的新估计值：

• 第一个式子：通过后验概率

估计值的均值作为先验概率

的估计。

• 第二个式子：通过条件概率

的估计来求解先验概率

的估计。

• 第三个式子：通过条件概率

的估计来求解先验概率

的估计。

1. EM 算法的解释：
   • 初始化：随机选择三枚硬币 A，B，C 正面出现的概率

   的初始值

   。

   • E 步：在已知概率

   的情况下，求出每个观测数据

   是来自于投掷硬币 B 的概率。即：

   。 于是对于

   次实验，就知道哪些观测数据是由硬币 B 产生，哪些是由硬币 C 产生。

   • M 步：在已知哪些观测数据是由硬币 B 产生，哪些是由硬币 C 产生的情况下：

     就等于硬币 B 产生的次数的频率。

     就等于硬币B 产生的数据中，正面向上的频率。

     就等于硬币 C 产生的数据中，正面向上的频率。

二、EM算法原理

2.1 观测变量和隐变量

1. 令

表示观测随机变量，

表示对应的数据序列；令

表示隐随机变量，

表示对应的数据序列。

和

连在一起称作完全数据，观测数据

又称作不完全数据。

1. 假设给定观测随机变量

，其概率分布为

，其中

是需要估计的模型参数，则不完全数据

的似然函数是

， 对数似然函数为

。 假定

和

的联合概率分布是

，完全数据的对数似然函数是

，则根据每次观测之间相互独立，有：

1. 由于

发生，根据最大似然估计，则需要求解对数似然函数：

的极大值。其中

表示对所有可能的

求和，因为边缘分布

。 该问题的困难在于：该目标函数包含了未观测数据的的分布的积分和对数。

2.2 EM算法

2.2.1 原理

1. EM 算法通过迭代逐步近似极大化

。 假设在第

次迭代后，

的估计值为：

。则希望

新的估计值能够使得

增加，即：

。 为此考虑两者的差：

。 这里

已知，所以

可以直接计算得出。

1. Jensen 不等式：如果

是凸函数，

为随机变量，则有：

。

• 如果

是严格凸函数，当且仅当

是常量时，等号成立。

• 当

满足

时，将

视作概率分布。 设随机变量

满足概率分布

，则有：

。

1. 考虑到条件概率的性质，则有

。因此有：

等号成立时，需要满足条件：

其中

为随机变量

的取值个数。

1. 令 ：

则有：

，因此

是

的一个下界。

• 根据定义有：

。因为此时有：

• 任何可以使得

增大的

，也可以使

增大。 为了使得

尽可能增大，则选择使得

取极大值的

：

。

1. 求极大值：

其中：

与

无关，因此省略。

2.2.2 算法

1. EM 算法：
   • 输入：
     • 观测变量数据
     • 联合分布

     ，以及条件分布

     联合分布和条件分布的形式已知（比如说高斯分布等），但是参数未知（比如均值、方差）

   • 输出：模型参数
   • 算法步骤：
     • 选择参数的初值

     ，开始迭代。

     • E步：记

     为第

     次迭代参数

     的估计值，在第

     步迭代的 E 步，计算：

     其中

     表示：对于观测点

     ，

     关于后验概率

     的期望。

     • M步：求使得

     最大化的

     ，确定

     次迭代的参数的估计值

     • 重复上面两步，直到收敛。

2. 通常收敛的条件是：给定较小的正数

，满足：

或者

。

是算法的核心，称作

函数。其中：

• 第一个符号表示要极大化的参数（未知量）。
• 第二个符号表示参数的当前估计值（已知量）。

1. EM算法的直观理解：EM算法的目标是最大化对数似然函数

。

• 直接求解这个目标是有问题的。因为要求解该目标，首先要得到未观测数据的分布

。如：身高抽样问题中，已知身高，需要知道该身高对应的是男生还是女生。 但是未观测数据的分布就是待求目标参数

的解的函数。这是一个“鸡生蛋-蛋生鸡” 的问题。

• EM算法试图多次猜测这个未观测数据的分布

。 每一轮迭代都猜测一个参数值

，该参数值都对应着一个未观测数据的分布

。如：已知身高分布的条件下，男生/女生的分布。

• 然后通过最大化某个变量来求解参数值。这个变量就是

变量，它是真实的似然函数的下界 。

• 如果猜测正确，则

就是真实的似然函数。

• 如果猜测不正确，则

就是真实似然函数的一个下界。

1. 隐变量估计问题也可以通过梯度下降法等算法求解，但由于求和的项数随着隐变量的数目以指数级上升，因此代价太大。
   • EM算法可以视作一个非梯度优化算法。
   • 无论是梯度下降法，还是EM 算法，都容易陷入局部极小值。

2.2.3 收敛性定理

1. 定理一：设

为观测数据的似然函数，

为EM算法得到的参数估计序列，

为对应的似然函数序列，其中

。 则：

是单调递增的，即：

。

1. 定理二：设

为观测数据的对数似然函数，

为EM算法得到的参数估计序列，

为对应的对数似然函数序列，其中

。

• 如果

有上界，则

会收敛到某一个值

。

• 在函数

与

满足一定条件下，由 EM 算法得到的参数估计序列

的收敛值

是

的稳定点。 关于“满足一定条件”：大多数条件下其实都是满足的。

1. 定理二只能保证参数估计序列收敛到对数似然函数序列的稳定点

，不能保证收敛到极大值点。

1. EM算法的收敛性包含两重意义：
   • 关于对数似然函数序列

   的收敛。

   • 关于参数估计序列

   的收敛。

   前者并不蕴含后者。

2. 实际应用中，EM 算法的参数的初值选择非常重要。
   • 参数的初始值可以任意选择，但是 EM 算法对初值是敏感的，选择不同的初始值可能得到不同的参数估计值。
   • 常用的办法是从几个不同的初值中进行迭代，然后对得到的各个估计值加以比较，从中选择最好的（对数似然函数最大的那个）。

3. EM 算法可以保证收敛到一个稳定点，不能保证得到全局最优点。其优点在于：简单性、普适性。

三、EM算法与高斯混合模型

3.1 高斯混合模型

1. 高斯混合模型(Gaussian mixture model,GMM)：指的是具有下列形式的概率分布模型：

其中

是系数，满足 ：

。

是高斯分布密度函数，称作第

个分模型，

：

1. 如果用其他的概率分布密度函数代替上式中的高斯分布密度函数，则称为一般混合模型。

3.2 参数估计

1. 假设观察数据

由高斯混合模型

生成，其中

。 可以通过EM算法估计高斯混合模型的参数

。

1. 可以设想观察数据

是这样产生的：

• 首先以概率

选择第

个分模型

。

• 然后以第

个分模型的概率分布

生成观察数据

。

这样，观察数据

是已知的，观测数据

来自哪个分模型是未知的。 对观察变量

，定义隐变量

，其中

。

1. 完全数据的对数似然函数为：

其对数为：

后验概率为：

即：

。 则

函数为：

求极大值：

。 根据偏导数为 0，以及

得到：

：

其中：

，其物理意义为：所有的观测数据

中，产生自第

个分模型的观测数据的数量。

：

其中：

，其物理意义为：所有的观测数据

中，产生自第

个分模型的观测数据的总和。

：

其中：

，其物理意义为：所有的观测数据

中，产生自第

个分模型的观测数据，偏离第

个模型的均值（

）的平方和。

1. 高斯混合模型参数估计的EM算法：
   • 输入：
     • 观察数据
     • 高斯混合模型的分量数

   • 输出：高斯混合模型参数
   • 算法步骤：
     • 随机初始化参数

     。

     • 根据

     迭代求解

     ，停止条件为：对数似然函数值或者参数估计值收敛。

     其中：

     。 其物理意义为：所有的观测数据

     中，产生自第

     个分模型的观测数据的数量。

     。 其物理意义为：所有的观测数据

     中，产生自第

     个分模型的观测数据的总和。

     。 其物理意义为：所有的观测数据

     中，产生自第

     个分模型的观测数据，偏离第

     个模型的均值（

     ）的平方和。

四、EM 算法与 kmeans 模型

1. kmeans算法：给定样本集

， 针对聚类所得簇划分

， 最小化平方误差：

其中

是簇

的均值向量。

1. 定义观测随机变量为

，观测数据为

。定义隐变量为

，它表示

所属的簇的编号。设参数

， 则考虑如下的生成模型：

其中

表示距离

最近的中心点所在的簇编号。即：

• 若

最近的簇就是

代表的簇，则生成概率为

。

• 若

最近的簇不是

代表的簇，则生成概率等于 0 。

1. 计算后验概率：

即：

• 若

最近的簇就是

代表的簇，则后验概率为 1 。

• 若

最近的簇不是

代表的簇，则后验概率为 0 。

1. 计算

函数：

设距离

最近的聚类中心为

，即它属于簇

，则有：

则有：

定义集合

，它表示属于簇

的样本的下标集合。则有：

则有：

这刚好就是 k-means 算法的目标：最小化平方误差。

1. 由于求和的每一项都是非负的，则当每一个内层求和

都最小时，总和最小。即：

得到：

，其中

表示集合

的大小。 这就是求平均值来更新簇中心。

五、EM 算法的推广

5.1 F 函数

1. F函数：假设隐变量

的概率分布为

，定义分布

与参数

的函数

为：

其中

是分布

的熵。 通常假定

是

的连续函数，因此

为

和

的连续函数。

1. 函数

有下列重要性质：

• 对固定的

，存在唯一的分布

使得极大化

。此时

，并且

随着

连续变化。

• 若

， 则

。

1. 定理一：设

为观测数据的对数似然函数，

为 EM 算法得到的参数估计序列，函数

，则：

• 如果

在

和

有局部极大值，那么

也在

有局部极大值。

• 如果

在

和

有全局极大值，那么

也在

有全局极大值。

1. 定理二：EM算法的一次迭代可由 F 函数的极大-极大算法实现：设

为第

次迭代参数

的估计，

为第

次迭代函数

的估计。在第

次迭代的两步为：

• 对固定的

，求

使得

极大化。

• 对固定的

，求

使得

极大化。

5.2 GEM算法1

1. GEM算法1（EM算法的推广形式）：
   • 输入：
     • 观测数据

     函数

   • 输出：模型参数
   • 算法步骤：
     • 初始化参数

     ，开始迭代。

     • 第

     次迭代：

     • 记

     为参数

     的估计值，

     为函数

     的估计值。求

     使得

     极大化。

     • 求

     使得

     极大化。

     • 重复上面两步直到收敛。

2. 该算法的问题是，有时候求

极大化很困难。

5.3 GEM算法2

1. GEM算法2（EM算法的推广形式）：
   • 输入：
     • 观测数据

     函数

   • 输出：模型参数
   • 算法步骤：
     • 初始化参数

     ，开始迭代。

     • 第

     次迭代：

     • 记

     为参数

     的估计值， 计算

     • 求

     使得

     • 重复上面两步，直到收敛。

2. 此算法不需要求

的极大值，只需要求解使它增加的

即可。

5.4 GEM算法3

1. GEM算法3（EM算法的推广形式）：
   • 输入：
     • 观测数据

     函数

   • 输出：模型参数
   • 算法步骤：
     • 初始化参数

     ，开始迭代

     • 第

     次迭代：

     • 记

     为参数

     的估计值， 计算

     • 进行

     次条件极大化：

     • 首先在

     保持不变的条件下求使得

     达到极大的

     • 然后在

     的条件下求使得

     达到极大的

     • 如此继续，经过

     次条件极大化，得到

     ，使得

     • 重复上面两步，直到收敛。

2. 该算法将 EM 算法的 M 步分解为

次条件极大化，每次只需要改变参数向量的一个分量，其余分量不改变。