Question

2.1 观测变量和隐变量

1. 令 $ MathJax-Element-108 $ 表示观测随机变量， $ MathJax-Element-832 $ 表示对应的数据序列；令 $ MathJax-Element-173 $ 表示隐随机变量， $ MathJax-Element-834 $ 表示对应的数据序列。

   $ MathJax-Element-852 $ 和 $ MathJax-Element-854 $ 连在一起称作完全数据，观测数据 $ MathJax-Element-852 $ 又称作不完全数据。

2. 假设给定观测随机变量 $ MathJax-Element-108 $ ，其概率分布为 $ MathJax-Element-95 $ ，其中 $ MathJax-Element-353 $ 是需要估计的模型参数，则不完全数据 $ MathJax-Element-852 $ 的似然函数是 $ MathJax-Element-860 $ ， 对数似然函数为 $ MathJax-Element-863 $ 。

   假定 $ MathJax-Element-108 $ 和 $ MathJax-Element-173 $ 的联合概率分布是 $ MathJax-Element-102 $ ，完全数据的对数似然函数是 $ MathJax-Element-867 $ ，则根据每次观测之间相互独立，有：

   $ \log P(\mathbb Y;\theta)=\sum_i \log P(Y=y_i;\theta)\\ \log P(\mathbb Y,\mathbb Z;\theta)=\sum_i \log P(Y=y_i,Z=z_i;\theta) $

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

   $ L(\theta)=\log P(\mathbb Y;\theta)=\sum_{i=1}\log P(Y=y_i;\theta) =\sum_{i=1}\log\sum_Z P(Y=y_i, Z;\theta)\\ =\sum_{i=1}\log\left[\sum_Z P(Y=y_i \mid Z;\theta)P(Z;\theta)\right] $

   的极大值。其中 $ MathJax-Element-118 $ 表示对所有可能的 $ MathJax-Element-173 $ 求和，因为边缘分布 $ MathJax-Element-120 $ 。

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

2.2 EM算法

2.2.1 原理

1. EM 算法通过迭代逐步近似极大化 $ MathJax-Element-320 $ 。

   假设在第 $ MathJax-Element-157 $ 次迭代后， $ MathJax-Element-353 $ 的估计值为： $ MathJax-Element-352 $ 。则希望 $ MathJax-Element-353 $ 新的估计值能够使得 $ MathJax-Element-320 $ 增加，即： $ MathJax-Element-127 $ 。

   为此考虑两者的差： $ MathJax-Element-898 $ 。

   这里 $ MathJax-Element-352 $ 已知，所以 $ MathJax-Element-901 $ 可以直接计算得出。

2. Jensen 不等式：如果 $ MathJax-Element-132 $ 是凸函数， $ MathJax-Element-133 $ 为随机变量，则有： $ MathJax-Element-1236 $ 。

   • 如果 $ MathJax-Element-132 $ 是严格凸函数，当且仅当 $ MathJax-Element-133 $ 是常量时，等号成立。

     

   • 当 $ MathJax-Element-907 $ 满足 $ MathJax-Element-912 $ 时，将 $ MathJax-Element-1131 $ 视作概率分布。

     设随机变量 $ MathJax-Element-55 $ 满足概率分布 $ MathJax-Element-992 $ ，则有： $ MathJax-Element-1000 $ 。

3. 考虑到条件概率的性质，则有 $ MathJax-Element-134 $ 。因此有：

   $ L(\theta) - L(\theta^{})=\sum_{j}\log\sum_Z P(Y=y_j, Z;\theta) - \sum_{j}\log P(Y=y_j; \theta^{})\\ =\sum_{j}\left[\log\sum_ZP(Z\mid Y=y_j;\theta^{})\frac{P(Y=y_j, Z;\theta)}{P(Z\mid Y=y_j;\theta^{})} - \log P(Y=y_j;\theta^{}) \right]\\ \ge\sum_{j}\left[\sum_Z P(Z\mid Y=y_j;\theta^{})\log\frac{P(Y=y_j, Z;\theta)}{P(Z\mid Y=y_j;\theta^{})} - \log P(Y=y_j;\theta^{}) \right]\\ =\sum_{j}\left[\sum_Z P(Z\mid Y=y_j;\theta^{})\log\frac{P(Y=y_j\mid Z;\theta)P(Z;\theta)}{P(Z\mid Y=y_j;\theta^{})} - \log P(Y=y_i;\theta^{})\times 1 \right]\\ =\sum_{j}\left[\sum_Z P(Z\mid Y=y_j;\theta^{})\log\frac{P(Y=y_j\mid Z;\theta)P(Z;\theta)}{P(Z\mid Y=y_j;\theta^{})} \\ - \log P(Y=y_j;\theta^{})\times \sum_Z P(Z\mid Y=y_j;\theta^{}) \right]\\ =\sum_{j}\left[\sum_Z P(Z\mid Y=y_j;\theta^{})\log\frac{P(Y=y_j\mid Z;\theta)P(Z;\theta)}{P(Z\mid Y=y_j;\theta^{}) P(Y=y_j;\theta^{})} \right] $

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

   $ P(Z\mid Y=y_j;\theta^{})=\frac 1 {n_Z}\\ \frac{P(Y=y_j, Z;\theta)}{P(Z\mid Y=y_j;\theta^{})}=\text{const} $

   其中 $ MathJax-Element-137 $ 为随机变量 $ MathJax-Element-173 $ 的取值个数。

4. 令 ：

   则有： $ MathJax-Element-139 $ ，因此 $ MathJax-Element-147 $ 是 $ MathJax-Element-141 $ 的一个下界。

   • 根据定义有： $ MathJax-Element-142 $ 。因为此时有：

     $ \frac{P( Y=y_j\mid Z ;\theta^{})P( Z ;\theta^{})}{P( Z \mid Y=y_j;\theta^{})P(Y=y_j;\theta^{})}=\frac{P( Y=y_j, Z ;\theta^{})}{P(Y=y_j,Z ;\theta^{})} =1 $

   • 任何可以使得 $ MathJax-Element-147 $ 增大的 $ MathJax-Element-353 $ ，也可以使 $ MathJax-Element-320 $ 增大。

     为了使得 $ MathJax-Element-320 $ 尽可能增大，则选择使得 $ MathJax-Element-147 $ 取极大值的 $ MathJax-Element-353 $ ： $ MathJax-Element-1198 $ 。

5. 求极大值：

   其中： $ MathJax-Element-1113 $ 与 $ MathJax-Element-353 $ 无关，因此省略。

2.2.2 算法

1. EM 算法：

   • 输入：

     • 观测变量数据 $ MathJax-Element-1211 $
     • 联合分布 $ MathJax-Element-152 $ ，以及条件分布 $ MathJax-Element-153 $

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

   • 输出：模型参数 $ MathJax-Element-353 $

   • 算法步骤：

     • 选择参数的初值 $ MathJax-Element-155 $ ，开始迭代。

     • E步：记 $ MathJax-Element-352 $ 为第 $ MathJax-Element-157 $ 次迭代参数 $ MathJax-Element-353 $ 的估计值，在第 $ MathJax-Element-360 $ 步迭代的 E 步，计算：

       $ Q(\theta,\theta^{})=\sum_{j=1}^N \mathbb E_{P(Z\mid Y=y_j;\theta^{})}\log P(Y=y_j,Z ;\theta)\\ =\sum_{j=1}^N\left(\sum_Z P(Z\mid Y=y_j;\theta^{})\log P(Y=y_j,Z;\theta) \right) $

       其中 $ MathJax-Element-1289 $ 表示：对于观测点 $ MathJax-Element-79 $ ， $ MathJax-Element-1303 $ 关于后验概率 $ MathJax-Element-1312 $ 的期望。

     • M步：求使得 $ MathJax-Element-368 $ 最大化的 $ MathJax-Element-353 $ ，确定 $ MathJax-Element-360 $ 次迭代的参数的估计值 $ MathJax-Element-357 $

       $ \theta^{}=\arg\max_\theta Q(\theta,\theta^{}) $

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

2. 通常收敛的条件是：给定较小的正数 $ MathJax-Element-178 $ ，满足： $ MathJax-Element-179 $ 或者 $ MathJax-Element-180 $ 。

3. $ MathJax-Element-368 $ 是算法的核心，称作 $ MathJax-Element-358 $ 函数。其中：

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

4. EM算法的直观理解：EM算法的目标是最大化对数似然函数 $ MathJax-Element-1317 $ 。

   • 直接求解这个目标是有问题的。因为要求解该目标，首先要得到未观测数据的分布 $ MathJax-Element-1324 $ 。如：身高抽样问题中，已知身高，需要知道该身高对应的是男生还是女生。

     但是未观测数据的分布就是待求目标参数 $ MathJax-Element-353 $ 的解的函数。这是一个“鸡生蛋-蛋生鸡” 的问题。

   • EM算法试图多次猜测这个未观测数据的分布 $ MathJax-Element-1327 $ 。

     每一轮迭代都猜测一个参数值 $ MathJax-Element-352 $ ，该参数值都对应着一个未观测数据的分布 $ MathJax-Element-1331 $ 。如：已知身高分布的条件下，男生/女生的分布。

   • 然后通过最大化某个变量来求解参数值。这个变量就是 $ MathJax-Element-192 $ 变量，它是真实的似然函数的下界 。
     

     • 如果猜测正确，则 $ MathJax-Element-194 $ 就是真实的似然函数。
     • 如果猜测不正确，则 $ MathJax-Element-194 $ 就是真实似然函数的一个下界。

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

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

2.2.3 收敛性定理

1. 定理一：设 $ MathJax-Element-860 $ 为观测数据的似然函数， $ MathJax-Element-352 $ 为EM算法得到的参数估计序列， $ MathJax-Element-1343 $ 为对应的似然函数序列，其中 $ MathJax-Element-1355 $ 。

   则： $ MathJax-Element-1343 $ 是单调递增的，即： $ MathJax-Element-1361 $ 。

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

   • 如果 $ MathJax-Element-860 $ 有上界，则 $ MathJax-Element-141 $ 会收敛到某一个值 $ MathJax-Element-210 $ 。

   • 在函数 $ MathJax-Element-368 $ 与 $ MathJax-Element-320 $ 满足一定条件下，由 EM 算法得到的参数估计序列 $ MathJax-Element-352 $ 的收敛值 $ MathJax-Element-321 $ 是 $ MathJax-Element-320 $ 的稳定点。

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

3. 定理二只能保证参数估计序列收敛到对数似然函数序列的稳定点 $ MathJax-Element-210 $ ，不能保证收敛到极大值点。

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

   • 关于对数似然函数序列 $ MathJax-Element-141 $ 的收敛。
   • 关于参数估计序列 $ MathJax-Element-352 $ 的收敛。

   前者并不蕴含后者。

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

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

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