二、EM算法原理

2.1 观测变量和隐变量

  1. 令 二、EM算法原理 - 图1 表示观测随机变量，二、EM算法原理 - 图2 表示对应的数据序列；令 二、EM算法原理 - 图3 表示隐随机变量， 二、EM算法原理 - 图4 表示对应的数据序列。

    二、EM算法原理 - 图5 和 二、EM算法原理 - 图6 连在一起称作完全数据，观测数据 二、EM算法原理 - 图7 又称作不完全数据。

  2. 假设给定观测随机变量 二、EM算法原理 - 图8 ，其概率分布为 二、EM算法原理 - 图9，其中 二、EM算法原理 - 图10 是需要估计的模型参数，则不完全数据 二、EM算法原理 - 图11 的似然函数是 二、EM算法原理 - 图12， 对数似然函数为 二、EM算法原理 - 图13 。

    假定 二、EM算法原理 - 图14 和 二、EM算法原理 - 图15 的联合概率分布是 二、EM算法原理 - 图16，完全数据的对数似然函数是 二、EM算法原理 - 图17，则根据每次观测之间相互独立，有：

    二、EM算法原理 - 图18

  3. 由于 二、EM算法原理 - 图19 发生，根据最大似然估计，则需要求解对数似然函数：

    二、EM算法原理 - 图20

    的极大值。其中 二、EM算法原理 - 图21 表示对所有可能的二、EM算法原理 - 图22 求和，因为边缘分布 二、EM算法原理 - 图23 。

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

2.2 EM算法

2.2.1 原理

  1. EM 算法通过迭代逐步近似极大化 二、EM算法原理 - 图24 。

    假设在第 二、EM算法原理 - 图25 次迭代后，二、EM算法原理 - 图26 的估计值为： 二、EM算法原理 - 图27。则希望 二、EM算法原理 - 图28 新的估计值能够使得 二、EM算法原理 - 图29 增加，即： 二、EM算法原理 - 图30 。

    为此考虑两者的差：二、EM算法原理 - 图31 。

    这里 二、EM算法原理 - 图32 已知，所以 二、EM算法原理 - 图33 可以直接计算得出。

  2. Jensen 不等式：如果 二、EM算法原理 - 图34 是凸函数，二、EM算法原理 - 图35 为随机变量，则有：二、EM算法原理 - 图36 。

    • 如果 二、EM算法原理 - 图37 是严格凸函数，当且仅当 二、EM算法原理 - 图38 是常量时，等号成立。

      jensen

    • 当 二、EM算法原理 - 图40 满足 二、EM算法原理 - 图41 时，将 二、EM算法原理 - 图42 视作概率分布。

      设随机变量 二、EM算法原理 - 图43 满足概率分布 二、EM算法原理 - 图44 ，则有：二、EM算法原理 - 图45 。

  3. 考虑到条件概率的性质，则有 二、EM算法原理 - 图46 。因此有：

    二、EM算法原理 - 图47

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

    二、EM算法原理 - 图48

    其中 二、EM算法原理 - 图49 为随机变量 二、EM算法原理 - 图50 的取值个数。

  4. 令 ：

    二、EM算法原理 - 图51

    则有： 二、EM算法原理 - 图52，因此 二、EM算法原理 - 图53 是 二、EM算法原理 - 图54 的一个下界。

    • 根据定义有： 二、EM算法原理 - 图55 。因为此时有：

      二、EM算法原理 - 图56

    • 任何可以使得 二、EM算法原理 - 图57 增大的 二、EM算法原理 - 图58 ，也可以使 二、EM算法原理 - 图59 增大。

      为了使得 二、EM算法原理 - 图60 尽可能增大，则选择使得 二、EM算法原理 - 图61 取极大值的 二、EM算法原理 - 图62 ：二、EM算法原理 - 图63 。

  5. 求极大值：

    二、EM算法原理 - 图64

    其中： 二、EM算法原理 - 图65 与 二、EM算法原理 - 图66 无关，因此省略。

2.2.2 算法

  1. EM 算法：

    • 输入：

      • 观测变量数据 二、EM算法原理 - 图67
      • 联合分布 二、EM算法原理 - 图68，以及条件分布 二、EM算法原理 - 图69

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

    • 输出：模型参数 二、EM算法原理 - 图70

    • 算法步骤：

      • 选择参数的初值 二、EM算法原理 - 图71 ，开始迭代。

      • E步：记 二、EM算法原理 - 图72 为第 二、EM算法原理 - 图73 次迭代参数 二、EM算法原理 - 图74 的估计值，在第 二、EM算法原理 - 图75 步迭代的 E 步，计算：

        二、EM算法原理 - 图76

        其中二、EM算法原理 - 图77 表示：对于观测点 二、EM算法原理 - 图78 ， 二、EM算法原理 - 图79 关于后验概率 二、EM算法原理 - 图80 的期望。

      • M步：求使得 二、EM算法原理 - 图81 最大化的 二、EM算法原理 - 图82，确定 二、EM算法原理 - 图83 次迭代的参数的估计值 二、EM算法原理 - 图84

        二、EM算法原理 - 图85

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

  2. 通常收敛的条件是：给定较小的正数 二、EM算法原理 - 图86，满足：二、EM算法原理 - 图87 或者 二、EM算法原理 - 图88 。

  3. 二、EM算法原理 - 图89是算法的核心，称作 二、EM算法原理 - 图90 函数。其中：

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

  4. EM算法的直观理解：EM算法的目标是最大化对数似然函数 二、EM算法原理 - 图91 。

    • 直接求解这个目标是有问题的。因为要求解该目标，首先要得到未观测数据的分布 二、EM算法原理 - 图92 。如：身高抽样问题中，已知身高，需要知道该身高对应的是男生还是女生。

      但是未观测数据的分布就是待求目标参数 二、EM算法原理 - 图93 的解的函数。这是一个“鸡生蛋-蛋生鸡” 的问题。

    • EM算法试图多次猜测这个未观测数据的分布 二、EM算法原理 - 图94 。

      每一轮迭代都猜测一个参数值 二、EM算法原理 - 图95，该参数值都对应着一个未观测数据的分布 二、EM算法原理 - 图96 。如：已知身高分布的条件下，男生/女生的分布。

    • 然后通过最大化某个变量来求解参数值。这个变量就是 二、EM算法原理 - 图97 变量，它是真实的似然函数的下界 。

      • 如果猜测正确，则 二、EM算法原理 - 图98 就是真实的似然函数。
      • 如果猜测不正确，则 二、EM算法原理 - 图99 就是真实似然函数的一个下界。

  5. 隐变量估计问题也可以通过梯度下降法等算法求解，但由于求和的项数随着隐变量的数目以指数级上升，因此代价太大。

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

2.2.3 收敛性定理

  1. 定理一：设 二、EM算法原理 - 图100 为观测数据的似然函数，二、EM算法原理 - 图101 为EM算法得到的参数估计序列， 二、EM算法原理 - 图102 为对应的似然函数序列，其中 二、EM算法原理 - 图103 。

    则： 二、EM算法原理 - 图104 是单调递增的，即：二、EM算法原理 - 图105 。

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

    • 如果 二、EM算法原理 - 图110 有上界，则 二、EM算法原理 - 图111 会收敛到某一个值 二、EM算法原理 - 图112 。

    • 在函数 二、EM算法原理 - 图113 与 二、EM算法原理 - 图114 满足一定条件下，由 EM 算法得到的参数估计序列 二、EM算法原理 - 图115 的收敛值 二、EM算法原理 - 图116 是 二、EM算法原理 - 图117 的稳定点。

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

  3. 定理二只能保证参数估计序列收敛到对数似然函数序列的稳定点 二、EM算法原理 - 图118 ，不能保证收敛到极大值点。

  4. EM算法的收敛性包含两重意义：

    • 关于对数似然函数序列 二、EM算法原理 - 图119 的收敛。
    • 关于参数估计序列 二、EM算法原理 - 图120 的收敛。

    前者并不蕴含后者。

  5. 实际应用中，EM 算法的参数的初值选择非常重要。

    • 参数的初始值可以任意选择，但是 EM 算法对初值是敏感的，选择不同的初始值可能得到不同的参数估计值。
    • 常用的办法是从几个不同的初值中进行迭代，然后对得到的各个估计值加以比较，从中选择最好的（对数似然函数最大的那个）。
  6. EM 算法可以保证收敛到一个稳定点，不能保证得到全局最优点。其优点在于：简单性、普适性。