《统计学习方法》EM 算法的部分读书笔记
1. 引入 · 三硬币模型
假设有三枚硬币，分别记作A、B、C。这三枚硬币正面朝上的概率分别为 $\pi$、$p$ 和 $q$。进行如下掷硬币实验：先掷硬币 A，如果 A 为正面则下一个掷 B，反面掷 C；以第二枚硬币的结果为最终结果。进行独立重复实验。
我们将独立重复实验得到的结果记作 “观测结果”；将每次硬币 A 的结果记为 “不可观测数据（隐变量）”。假设我们只能知道观测结果，如何去估计隐变量？这就是 EM 算法解决的问题。（用于含有隐变量的概率模型参数的极大似然估计）
2. EM 算法的导出
算法：（EM算法）
输入：模型参数 $\theta$
选择参数的初值 $\theta^{(0)}$，开始迭代。
E 步（求期望）：记 $\theta^{(i)}$ 为第 i 次迭代参数 $\theta$ 的估计值，在第 i+1 次迭代的 E 步，计算：
$Q(\theta,\theta^{(i)})=E_Z[logP(Y,Z|\theta)|Y, \theta^{(i)}]$
$=\sum_ZlogP(Y,Z|\theta)P(Z|Y,\theta^{(i)})$
此处，$P(Z|Y,\theta^{(i)})$ 是给定观测数据 Y 和当前的参数估计 $\theta^{(i)}$ 下隐变量数据 Z 的条件概率分布。
M 步（求极大）：求使 $Q(\theta,\theta^{(i)})$ 极大化的 $\theta$，确定第 i+1 次迭代的参数的估计值 $\theta^{(i+1)}$
$\theta^{(i+1)}=arg\ max_{\theta}Q(\theta, \theta^{(i)})$
重复第二步和第三步，直到收敛。
接下来对 EM 算法进行推导：
我们的目标是极大化观测数据 Y 关于参数 $\theta$ 的对数似然函数，也就是 $L(\theta)=log P(Y|\theta)$
将上面的不等式进行整理：
为了使 $L(\theta)$ 有尽可能大的增长，选择 $\theta^{(i+1)}$ 使 $B(\theta, \theta^{(i)})$ 达到极大：$\theta^{(i+1)}=arg\ max_{\theta}B(\theta, \theta^{(i)})$
对这个表达式进行化简：
EM 算法就是通过不断对 Q 函数（下界）求极大，逼近求解对数似然函数极大化。
将上述算法步骤进行总结：
3. EM 算法的收敛性
在第二章中，我们并未对以下两个问题进行分析：
EM 算法的估计序列是否收敛？
如果收敛，是否收敛到全局最大值或者局部最大值？
我们将通过以下两个定理进行介绍。
3.1 递增性
定理：设 $P(Y|\theta)$ 为观测数据的似然函数，$\theta^{(i)}$ 为 EM 算法得到的参数估计序列，$P(Y|\theta^{(i)})$ 为对应的似然函数序列，则 $P(Y|\theta^{(i)})$ 是单调递增的。
接下来我们进行证明：
若要证明 $P(Y|\theta)$ 是单调递增的，只需证明上式大于等于 0。
至此， $P(Y|\theta)$ 是单调递增得证。
3.2 收敛到极大值
定理：设 $L(\theta)=logP(Y|\theta)$ 为观测数据的对数似然函数，$\theta^{(i)}$ 为 EM 算法得到的参数估计序列，$L(\theta^{(i)})$ 为对应的对数似然函数序列。
- 如果 $P(Y|\theta)$ 有上界，则 $L(\theta^{(i)})=logP(Y|\theta^{(i)})$ 收敛到某一值 $L^*$
由 $L(\theta)=logP(Y|\theta^{(i)})$ 的单调性及 $P(Y|\theta)$ 的有界性可以立即得到。
4. EM 算法在高斯混合模型学习中的应用
4.1 高斯分布
先简单介绍一下高斯分布
$\phi(y|\theta)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$
其中，$\mu$ 决定分布的位置；$\sigma^2$ 为方差，决定分布的幅度。
4.2 高斯混合模型
高斯混合模型可以理解为由多个高斯分布叠加得到，具有如下概率分布：
$P(y|\theta)=\sum_{k=1}^K\alpha_k\phi(y|\theta_k)$
其中 K 为 K 个叠加的高斯模型，$\alpha_k$ 为每个高斯模型的权重，$\phi(y|\theta_k)$ 为每个高斯模型。
4.3 高斯混合模型参数估计的 EM 算法
步骤一：明确隐变量
设想观测数据 $y_j$ 的产生方式为：首先依据概率 $\alpha_k$ 选择 k 个高斯分布模型 $\phi(y|\theta_k)$；然后依第 k 个分模型的概率分布 $\phi(y|\theta_k)$ 生成观测数据 $y_j$。
其中，反映观测数据 $y_j$ 来自第 k 个分模型的数据是未知的，记作隐变量 $\gamma_{jk}$。
$\gamma_{jk}=\begin{cases} 1 &\text{第 j 个观测来自第 k 个模型} \\ 0 &\text{否则} \end{cases}$
通过观测数据 $y_j$ 和未观测数据 $\gamma_{jk}$，得到完全数据 $(y_j,\gamma_{j1},\gamma_{j2},…,\gamma_{jK})$
因此可以写出完全数据的似然函数：
令 $n_k=\sum_{j=1}^N\gamma_{jk}$ 可得：
则完全数据的对数似然函数为：
步骤二：（E）确定 Q 函数
此处需要计算 $E(\gamma_{jk},\theta)$，记作 $\hat{\gamma_{jk}}$
步骤三：（M）迭代求 Q 函数对 $\theta$ 的最大值（即求新一轮迭代的参数）
求 Q 函数的极大值，仅需对各参数（$\mu_k$，$\sigma_k^2$）求偏导并令其为 0（拉格朗日参数法）
求 $\hat{\alpha_k}$ 是在 $\sum_{k=1}^K\alpha_k=1$ 下求偏导数并令其为 0（拉格朗日参数法）
可以得到如下结果
重复步骤二和步骤三，直到对数似然函数值不再有明显的变化。
4.5 高斯混合模型参数估计 EM 算法总结
输入：观测数据 $y_1$，$y_2$，…，$y_N$；高斯混合模型
输出：高斯混合模型参数
取参数的初始值开始迭代
E 步：依据当前参数模型，计算分模型 k 对观测数据 $y_j$ 的响应度
$\hat{\gamma_{jk}}=\frac{\alpha_k\phi(y_j|\theta_k)}{\sum_{k=1}^K\alpha_k\phi(y_j|\theta_k)}$
M 步：计算新一轮迭代的模型参数
重复步骤（2）和（3），直至收敛
5. 总结
本章主要介绍了 EM 算法，其本质就是通过不断迭代参数逼近似然函数的极大值
在第二章我们介绍了 EM 算法，EM 算法顾名思义分为两步：
E 步，求 Q 函数的期望（对数似然函数的期望）。
M 步，求使 Q 函数极大化的参数，确定下一次迭代的参数的估计值
$\theta^{(i+1)}=arg\ max_{\theta}Q(\theta,\theta^{(i)})$
在第三章我们对 EM 算法进行了推导：
- 我们的目的是极大化对数似然函数 $L(\theta)$，因此找到对数似然函数的下限 $B(\theta,\theta^{(i)})$ ,将待解决的问题转换为 “寻找合适的参数使 $B(\theta,\theta^{(i)})$ 极大”。
- 通过对 $B(\theta,\theta^{(i)})$ 进行化简，我们可以得到 Q 函数，因此问题转化为 “寻找合适的参数使 Q 函数极大”，并且极大值为下一次迭代的参数。
- 使用新的参数重新计算 Q 函数，并继续求极大，直至收敛。
在第四章我们证明了 EM 算法得到的似然函数关于 $\theta^{(i)}$ 单调递增且有界。因此似然函数 $L(\theta)$ 收敛有上界，因此 EM 算法在理论上可行。
在第五章我们介绍了 EM 算法在解决高斯混合模型中的应用，主要分为三步：
取参数初始值开始迭代
E 步：计算对数似然函数的期望
特别地，需要计算分模型 k 对观测数据 $y_k$ 的响应度（当前模型参属下第 j 个观测数据来自第 k 个分模型的概率）
M 步：计算新一轮的模型参数
重复第二步和第三步，直至收敛