EM算法

1 简介

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

E步：求期望；M步，求极大。

1.1 例子

P176三硬币模型：

$$p_{(y/\theta)}=\sum_{\mathcal{Z}} P(y, z | \theta)=\sum_{\mathcal{Z}} P(z | \theta) P(y | z, \theta)$$ $$= \pi p^y(1-p)^{(1-y)} + (1-\pi)q^y (1-q)^{(1-y)}$$

y是观测变量，表示一次试验结果是1或0；

z（随机变量）是隐变量，表示未观测到的抛硬币A的结果

$\theta = (\pi,p,q)$ 是模型参数。

这个模型是以上数据的生成模型

1.2 模型

观测数据是$Y=\left(Y_{1}, Y_{2}, \cdots, Y_{n}\right)^{\mathrm{T}}$，未观测数据表示为$Z=(Z_1,Z_2…Z_n)^{\mathrm{T}}$，则观测数据的似然函数是：

$$P(Y | \theta)=\sum_{Z} P(Z | \theta) P(Y | Z, \theta)$$

即：

$$P(Y | \theta)=\prod_{j=1}^{n}\left[\pi p^{y_{j}}(1-p)^{1-y_{j}}+(1-\pi) q^{y_{j}}(1-q)^{1-y_{j}}\right]$$

求模型参数 $\theta = (\pi,p,q)$的极大似然估计是：

$$\hat{\theta} = argmax_{\theta} log(P(Y|\theta))$$

1.3 迭代算法

这个问题只能通过迭代的方法求解，EM算法就是用于求解这个问题的一种迭代算法。

1，选取参数的初值，记作 $\theta^0 = (\pi^0,p^0,q^0)$，然后迭代计算参数的估计值，直至收敛为止。第i次迭代的参数估计值是 $\theta^i = (\pi^i,p^i,q^i)$

2, E步，计算在模型参数$\theta^i$下观测数据$y_i$来自硬币B的概率：

$$\mu_{j}^{(i+1)}=\frac{\pi^{(i)}\left(p^{(i)}\right)^{y_{j}}\left(1-p^{(i)}\right)^{1-y_{j}}}{\pi^{(i)}\left(p^{(i)}\right)^{y_{j}}\left(1-p^{(i)}\right)^{1-y_{j}}+\left(1-\pi^{(i)}\right)\left(q^{(i)}\right)^{y_{j}}\left(1-q^{(i)}\right)^{1-y_{j}}}$$

M步计算模型参数的新估计值(n是独立重复n次实验)：

$$\pi^{i+1} = \frac{1}{n}\sum_{j=1}^n \mu_j^{i+1}$$ $$p^{(i+1)}=\frac{\sum_{j=1}^{n} \mu_{j}^{(i+1)} y_{j}}{\sum_{j=1}^{n} \mu_{j}^{(i+1)}}$$ $$q^{(i+1)}=\frac{\sum_{j=1}^{n}\left(1-\mu_{j}^{(i+1)}\right) y_{j}}{\sum_{j=1}^{n}\left(1-\mu_{j}^{(i+1)}\right)}$$

P177的计算例子，不同的初值得到不同的参数估计值。

2 EM算法

Y表示观测随机变量的数据，Z表示隐随机变量的数据。Y和Z连到一起称为完全数据。不完全数据Y的似然函数是$P(Y|\theta)$，Y和Z的联合概率分布是$P(Y,Z|\theta)$，完全数据的对数似然函数是$logP(Y,Z|\theta)$，EM算法通过迭代求$L(\theta) = logP(Y|\theta)$

(1) 选择参数初始值$\theta^{(0)}$，开始迭代。

(2) E步，记$\theta^i$是第i次迭代参数$\theta$的估计值，在第i+1次迭代的E步，计算：

$$Q\left(\theta, \theta^{(i)}\right)=E_{Z}\left[\log P(Y, Z | \theta) | Y, \theta^{(i)}\right] = \sum_{Z} \log P(Y, Z | \theta) P\left(Z | Y, \theta^{(i)}\right)$$

这离的$P(Z|Y,\theta^{(i)})$是在给定观测数据Y和当前参数估计$\theta^{(i)}$下隐变量数据Z的条件分布。

(3) M步，求使得$Q\left(\theta, \theta^{(i)}\right)$ 极大化的$\theta$，确定第i+1次迭代的参数估计值$\theta^{(i+1)}$。

$$\theta^{(i+1)}=\arg \max _{\theta} Q\left(\theta, \theta^{(i)}\right)$$

(4) 重复2、3步直到收敛。Q函数是EM算法的核心。

EM算法也是要先假设数据分布的。EM算法就是当抽取得到的每个样本都不知道是从哪个分布来的时候，通过迭代计算的方法来近似实现对观测数据的极大似然估计。EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。

3 Reference

1，知乎 EM算法

2，《李航 统计学习方法》