【李航统计学习笔记】第九章：EM算法

9.1 导论

三硬币模型

注：如果觉得文字太密集，请适当缩进阅读

• 若z_1=1, y_1 \sim b(1, p)
• 若z_1=0, y_1 \sim b(1, q)

如果(z, y)是完全数据，则有p(y, z)=p(z) \cdot p(y \mid z)。

当观测变量Y为不完全数据时，则其概率表达式可表示为：

p(Y|\theta) = \prod_{i=1}^{N}\sum_z p(Y_i,Z_i|\theta) = \prod_{i=1}^{N}\left[\pi p^{Y_i}(1-p)^{1-Y_i} + (1-\pi)q^{Y_i}(1-q)^{1-Y_i}\right]

其中推导关系表明：

p(Y,Z|\theta),\quad 并求取其对数似然函数的最大值即为：

\max(\ln p(Y,Z|\theta))

在EM算法中

算法的引入

EM算法步骤

观测型数据Y与潜在型数据Z共同构成了联合概率分布在参数\theta下的表现；同时，在给定观测值的情况下，潜在型数据的概率模型由条件概率模型P(Z|Y,\theta)来描述。

输出 : 模型参数 \theta 。

(1) 选择参数的初值 \theta^{(0)}, 开始迭代 ;

设\hat{\Theta}^{(t)}=\{\hat{\Theta}_{k}^{(t)}, k=1,\dots,K\}表示模型参数集合在t-th
迭代时的状态，在模型训练过程中采用逐点更新策略，在每一轮训练中，
首先初始化模型参数为当前状态；然后依次对每个样本进行数据增强，
并将其添加到训练集中；接着在整个训练集中基于当前模型参数完成一次全
量级的数据集上的优化计算。

在第M步中，请确定使得Q(theta, theta^{(i))达到其最大值的参数θ，并将其作为第(i+1)次迭代中的参数估计值θ}(i+1)

步骤 (4) 依次执行步骤 (2) 和步骤 (3)，直至收敛。 Q\left(\theta^{(i+1)}, \theta^{(i)}\right) \leftarrow Q \left(\theta^{(i)}, \theta^{(i-1)}\right)

第9.9式中的函数被称为 Q\left(\theta, \theta^{(i)}\right) ，它是EM算法的关键组成部分，并以其命名。

定理9.1

定义观测样本数据Y关于模型参数θ的概率分布函数为 P(Y | θ) ，其中参数估计序列 \{θ_{est}^{(1)}, θ_{est}^{(2)}, ...\} 是由EM算法生成的一系列估计值；相应地其对应条件概率分布序列为 \{P(Y | θ_{est}^{(1)}), P(Y | θ_{est}^{(2)}), ...\} 。根据EM算法的基本性质则该条件概率值序列 \{P(Y | θ_{est}^{(t)})\}_{t=1,2,...} 是严格单调递增的；具体而言有 P(Y | θ_{est}^{(t+1)}) ≥ P(Y | θ_{est}^{(t)}) 对所有 t 成立。

定理2

设 L(\theta)=\log P(Y \mid \theta) 为观测数据的对数似然函数， \theta^{(i)}(i=1,2, \ldots) 为
E M 算法得到的参数估计序列， L\left(\theta^{(i)}\right)(i=1,2, \ldots) 为对应的对数似然函数序列。
(1) 如果 P(Y \mid \theta) 有上界，则 L\left(\theta^{(i)}\right)=\log P\left(Y \mid \theta^{(i)}\right) 收敛到某一值 L ；
(2) 在函数 Q\left(\theta, \theta^{\prime}\right) 与 L(\theta) 满足一定条件下，由 E M 算法得到的参数估计序列 \theta^{(i)} 的收敛值 \theta 是 L(\theta) 的稳定点。

总结

1. 基于迭代的方法用于最大化观测数据对应的完全数据空间中的对数可能性函数以完成最大可能性估计。
2. 在最大可能性估计的过程中包含了两部分运算：首先计算条件期望值（E步），然后最大化完全数据空间中的可能性（M步）。
3. 该算法每经过一次迭代计算后都能提升观测数据的可能性值。

9.2 EM算法的导出

$\begin{aligned}
L(\theta)=\ln P(Y \mid \theta) &=\ln \sum_{Z} P(Y, Z \mid \theta)=\ln \left(\sum_{Z} P(Z \mid \theta) P(Y \mid Z, \theta)\right) \
\Delta L(\theta, \theta^{(i)}) &=\ln \left(\sum_{Z} P(Z \mid \theta) P(Y \mid Z, \theta)\right)-\ln P\left(Y \mid \theta^{(i)}\right) \
&=\ln \left(\sum_{Z} P\left(Z \mid Y, \theta^{(i)}\right) \frac{P(Z \mid \theta) P(Y \mid Z, θ)}{P\left(Z ∣ Y, θ^{(i)}\right)}\right)-\ln P\left(Y ∣ θ^{(i)}\right) \
&=∑{Z} P(Z ∣ Y, θ^{(i)}) ln⁡[ (P(Z ∣ θ)P(Y ∣ Z, θ)) / (P(Z ∣ Y, θ^{(i)})P(Y ∣ θ^{(i)})) ] −∑{Z} P(Z ∣ Y, θ^{(i)}) ln⁡P(Y ∣ θ^{(i)})
\
&=∑_{Z} P(Z ∣ Y, θ^{(i)}) ln⁡[ (P(Z ∣ θ)P(Y ∣ Z, θ)) / (P(Z ∣ Y, θ^{(i)})P(Y ∣ θ^{(i)})) ]
\end{aligned}

随后我们展开 ##### 总结 1. EM算法经过迭代运算逐步逼近$L$的最大值。 2. 为了使每一次都能使$L$增大，在每一步中必须满足$L(\theta)-L\left(\theta^{(i)}\right) > 0$。 3. 确定当前阶段的$L(\theta)-L\left(\theta^{(i)}\right)$下界后，并通过不断抬高这一下界来优化模型。 #### 9.3 高斯混合模型 (to be continue )