数据科学 | 算法工程师必备的机器学习--EM

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

• EM 算法是一种迭代算法。
• EM 算法专门用于含有隐变量的概率模型参数的极大似然估计，或者极大后验概率估计。

• E步求期望。
• M步求极大。所以EM算法也称为期望极大算法。

1 示例

1.1 身高抽样问题

1. 假设学校所有学生中，男生身高服从正态分布 ， 女生身高服从正态分布 。现在随机抽取200名学生，得到这些学生的身高 ，求参数 的估计。

2. 定义隐变量为 ，其取值为 ，分别表示男生、女生 。

   (1) 如果隐变量是已知的，即已知每个学生是男生还是女生 ，则问题很好解决：

   (1.1) 统计所有男生的身高的均值和方差，得到 ：

   其中 表示满足 的 构成的集合。 分别表示平均值和方差。

   
   

   (1.2) 统计所有女生的身高的均值和方差，得到 ：

   其中 表示满足 的 构成的集合。 分别表示平均值和方差。

   
   

   (2) 如果已知参数 ，则任意给出一个学生的身高 ，可以知道该学生分别为男生/女生的概率。

   则有：

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

   
   

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

3. 为解决该问题，通常采取下面步骤：

   (1) 先假定参数的初始值：

   
   

   (2) 迭代 ：

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

   (2.2) 根据上一步的划分，统计所有男生的身高的均值和方差，得到 ；统计所有女生的身高的均值和方差，得到 。这一步为 M 步（Maximization ），用于通过最大似然函数求解正态分布的参数。

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

1.2 三硬币模型

1. 已知三枚硬币 A，B，C ，这些硬币正面出现的概率分别为 。进行如下试验：

• 先投掷硬币 A，若是正面则选硬币 B；若是反面则选硬币 C 。
• 然后投掷被选出来的硬币，投掷的结果如果是正面则记作 1；投掷的结果如果是反面则记作0 。
• 独立重复地 次试验，观测结果为：1,1,0,1,0,...0,1。现在只能观测到投掷硬币的结果，无法观测投掷硬币的过程，求估计三硬币正面出现的概率。

• 随机变量 是观测变量，表示一次试验观察到的结果，取值为 1 或者0
• 随机变量 是隐变量，表示未观测到的投掷A硬币的结果，取值为 1 或者 0
• 是模型参数 则：

• 第一个式子：通过后验概率 估计值的均值作为先验概率 的估计。
• 第二个式子：通过条件概率 的估计来求解先验概率 的估计。
• 第三个式子：通过条件概率 的估计来求解先验概率 的估计。

• E步：计算模型在参数 下，观测数据 来自于投掷硬币 B 的概率：

  它其实就是 ，即：已知观测变量 的条件下，观测数据 来自于投掷硬币 B 的概率。

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

• 初始化：随机选择三枚硬币 A，B，C 正面出现的概率 的初始值 。

• E 步：在已知概率 的情况下，求出每个观测数据 是来自于投掷硬币 B 的概率。即： 。于是对于 次实验，就知道哪些观测数据是由硬币 B 产生，哪些是由硬币 C 产生。

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

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

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

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

2 EM算法原理

2.1 观测变量和隐变量

1. 令 表示观测随机变量， 表示对应的数据序列；令 表示隐随机变量， 表示对应的数据序列。 和 连在一起称作完全数据，观测数据 又称作不完全数据。

2. 假设给定观测随机变量 ，其概率分布为 ，其中 是需要估计的模型参数，则不完全数据 的似然函数是 ， 对数似然函数为 。假定 和 的联合概率分布是 ，完全数据的对数似然函数是 ，则根据每次观测之间相互独立，有：

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

   的极大值。其中 表示对所有可能的Z 求和，因为边缘分布 。该问题的困难在于：该目标函数包含了未观测数据的的分布的积分和对数。

2.2 算法

2.2.1 原理

1. EM 算法通过迭代逐步近似极大化 。假设在第 次迭代后， 的估计值为：。则希望 新的估计值能够使得 增加，即： 。为此考虑两者的差：

   
   

   这里 已知，所以 可以直接计算得出。

2. Jensen 不等式：如果 是凸函数，x 为随机变量，则有： 。

• 如果 是严格凸函数，当且仅当 是常量时，等号成立。

  

• 当 满足 时，将 视作概率分布。设随机变量 满足概率分布 ，则有： 。

• 任何可以使得 增大的 ，也可以使 增大。为了使得 尽可能增大，则选择使得 取极大值的 ： 。
• 根据定义有： 。因为此时有：

2.2.2 算法

1. EM 算法：

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

• 输出：模型参数

• 算法步骤：

  (1) 选择参数的初值 ，开始迭代。

  (2) E步：记 为第 次迭代参数 的估计值，在第 步迭代的 E 步，计算：

  其中

  表示：对于观测点 ， 关于后验概率 的期望。

  
  

  (3) M步：求使得 最大化的 ，确定 次迭代的参数的估计值 $\theta^{(i+1)}

  (4) 重复上面两步，直到收敛。

• 输入：

  (1) 观测变量数据

  (2) 联合分布 ，以及条件分布

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

• 直接求解这个目标是有问题的。因为要求解该目标，首先要得到未观测数据的分布 。如：身高抽样问题中，已知身高，需要知道该身高对应的是男生还是女生。但是未观测数据的分布就是待求目标参数 的解的函数。这是一个“鸡生蛋-蛋生鸡” 的问题。
• EM算法试图多次猜测这个未观测数据的分布 。每一轮迭代都猜测一个参数值 ，该参数值都对应着一个未观测数据的分布 。如：已知身高分布的条件下，男生/女生的分布。
• 然后通过最大化某个变量来求解参数值。这个变量就是 变量，它是真实的似然函数的下界 。
  (1) 如果猜测正确，则 就是真实的似然函数。(2) 如果猜测不正确，则 就是真实似然函数的一个下界。

• EM算法可以视作一个非梯度优化算法。
• 无论是梯度下降法，还是EM 算法，都容易陷入局部极小值。

2.2.3 收敛性定理

1. 定理一：设 为观测数据的似然函数， 为EM算法得到的参数估计序列， 为对应的似然函数序列，其中 。则： 是单调递增的，即：

   
   

2. 定理二：设 为观测数据的对数似然函数， 为EM算法得到的参数估计序列， 为对应的对数似然函数序列，其中 。

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

• 如果 有上界，则 会收敛到某一个值 。
• 在函数 与 满足一定条件下，由 EM 算法得到的参数估计序列 的收敛值 是 的稳定点。

• 关于对数似然函数序列 的收敛。
• 关于参数估计序列 的收敛。前者并不蕴含后者。

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

3 EM算法与高斯混合模型

3.1 高斯混合模型

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

   其中 是系数，满足 ：

• 。
• 是高斯分布密度函数，称作第 个分模型，

3.2 参数估计

1. 假设观察数据

   由高斯混合模型

   生成，其中

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

   
   

2. 可以设想观察数据 是这样产生的：

• 首先以概率 选择第 个分模型 。
• 然后以第 个分模型的概率分布 生成观察数据 。 这样，观察数据 是已知的，观测数据 来自哪个分模型是未知的。 对观察变量 ，定义隐变量 ，其中 。

• 输入：

  (1) 观察数据

  (2) 高斯混合模型的分量数 K

• 输出：高斯混合模型参数

  
  

• 算法步骤：

  (1) 随机初始化参数 。

  (2) 根据 迭代求解 ，停止条件为：对数似然函数值或者参数估计值收敛。

  其中：

  (2.1)

  其物理意义为：所有的观测数据 中，产生自第 个分模型的观测数据的数量。

  
  

  (2.2)

  其物理意义为：所有的观测数据 中，产生自第 个分模型的观测数据的总和。

  (2.3)

  其物理意义为：所有的观测数据 中，产生自第 个分模型的观测数据，偏离第 个模型的均值（）的平方和。

4 EM 算法与 模型

1. kmeans算法：给定样本集

   针对聚类所得簇划分

    最小化平方误差：

   
   

   其中 是簇 的均值向量。

2. 定义观测随机变量为 ，观测数据为 。定义隐变量为 ，它表示 所属的簇的编号。设参数 ， 则考虑如下的生成模型：

   其中 表示距离 最近的中心点所在的簇编号。即：

• 若 最近的簇就是 代表的簇，则生成概率为 。
• 若 最近的簇不是 代表的簇，则生成概率等于 0 。

• 若 最近的簇就是 代表的簇，则后验概率为 1 。
• 若 最近的簇不是 代表的簇，则后验概率为 0 。

5.1 函数

1. F函数：假设隐变量 的概率分布为 ，定义分布 与参数 的函数 为：

   其中 是分布 的熵。 通常假定 是 的连续函数，因此 为 和 的连续函数。

2. 函数 有下列重要性质：

• 对固定的 ，存在唯一的分布 使得极大化 。此时 ，并且 随着 连续变化。
• 若 ， 则 。

• 如果 在 和 有局部极大值，那么 也在 有局部极大值。
• 如果 在 和 有全局极大值，那么 也在 有全局极大值。