EM算法

EM算法是含有隐变量的概率模型参数的极大似然估计法。

一、三硬币模型

假设有3枚硬币，分别记作 $A,B,C$ 。这些硬币正面出现的概率分别是 $\pi,p和q$ 。进行如下抛硬币试验：
先掷硬币 $A$ ，根据其结果选出硬币 $B$ 或硬币 $C$ ，正面选硬币 $B$ ，反面选硬币 $C$ ；然后掷选出的硬币，掷硬币的结果，出现正面记作1，出现反面记作0；独立地重复 $n$ 次试验（这里， $n$ =10）,观测结果如下：
　　　　　　　　　　　　1,1,0,1,0,0,1,0,1,1
假设只能观测到掷硬币的结果，不能观测到掷硬币的过程，问如何估计三硬币正面出现的概率，即三硬币模型的参数。

设 $y$ 是观测变量，表示观测结果 $0$ 或 $1$ ； $Z$ 是隐变量，表示未观测到的掷硬币 $A$ 的结果； $\theta=(\pi,p,q)$ 是模型参数。

示意图

y为可观测变量，取值为{0,1}，观测结果取决于Z的取值，y,Z均服从0-1分布。
三硬币模型可以写作：

P(y|\theta)=\sum_{z}P(y,z|\theta)=\sum_{z}P(z|\theta)P(y|z,\theta)

因此：

P(y=1|\theta)=\pi p+(1-\pi)q

P(y=0|\theta)=\pi (1-p)+(1-\pi)(1-q)

等价于

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

将观测数据表示为 $Y=(Y_1,Y_2...Y_n)^{T}$ ，未观测数据表示为 $Z=(Z_1,Z_2...Z_n)^{T}$ ，则观测数据的似然函数为：
$P(Y|\theta)=\prod_{i=1}^n[\pi p^{y_i}(1-p)^{1-y_i}+(1-\pi)q^{y_i}(1-q)^{1-y_i}]$

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

$\hat{\theta}$ = $\mathop{argmax}\limits_{\theta} 　logP(Y|\theta)$

二、EM算法

E步：基于 $\Theta^t$ 推断隐变量Z的期望，记为 $Z^t$
M步：基于已观测变量 $X$ 和 $Z^t$ 对参数 $\Theta$ 做极大似然估计，记为 $\Theta^{t+1}$

对于一个含有隐变量的概率模型，目标是极大化观测数据 $Y$ 关于参数 $\theta$ 的极大似然函数 $L(\theta)$ ：
$L(\theta)$ = $logP(Y|\theta)$ = $logE_zP(Y,Z|\theta)$ = $log\sum_zP(Z|\theta)P(Y|Z,\theta)$

EM算法通过逐步迭代近似极大化 $L(\theta)$ ，假设第 $i$ 次迭代后 $\theta$ 的估计值是 $\theta^{(i)}$ ，则有 $L(\theta)>L(\theta^{(i)})$ 。

由Jensen不等式： $E[f(X)]>f[E(X)]$

因此：

$L(\theta)-L(\theta^{(i)})$

= $log[\sum_zP(Z|\theta)P(Y|Z,\theta)]-logP(Y|\theta^{(i)})$

= $log[\sum_zP(Y|Z,\theta^{(i)})\frac{P(Z|\theta)P(Y|Z,\theta)}{P(Y|Z,\theta^{(i)})}]-logP(Y|\theta^{(i)})$

$>=\sum_zP(Z|Y,\theta^{(i)})log\frac{P(Z|\theta)P(Y|Z,\theta)}{P(Z|Y,\theta^{(i)})}-logP(Y|\theta^{(i)})$

= $\sum_zP(Z|Y,\theta^{(i)})log\frac{P(Z|\theta)P(Y|Z,\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}$

EM算法是不断求解下界的极大化逼近求解对数似然函数极大化。

因此：

$Q$ 函数：
$Q(\theta,\theta^{(i)})$ = $E_z[logP(Y,Z|\theta)|Y,\theta^{(i)}]$

EM算法：

选取参数初值： $\theta^{(0)}$

E步：计算 $Q(\theta,\theta^{(i)})$

M步：求使 $Q(\theta,\theta^{(i)})$ 极大化的 $\theta$ ，确定第 $i+1$ 次参数迭代的估计值 $\theta^{(i+1)}$ ：
　　　　　　　 $\theta^{(i+1)}=\mathop{argmax}\limits_{\theta}Q(\theta,\theta^{(i)})$
重复E步和M步直到收敛。

停止条件：

$||\theta^{(i+1)}-\theta^{(i)}||<\varepsilon_1$ 或 $||Q(\theta,\theta^{(i+1)})-Q(\theta,\theta^{(i)})||<\varepsilon_2$

三、EM求解三硬币模型

E步：

$\mu_j^{(i+1)}= P(Z=1|Y,\theta^{(i)})=\frac{P(Y,Z|\theta^{(i)})}{P(Y|\theta^{(i)})}=\frac{P(Y|Z,\theta^{(i)})P(Z))}{P(Y|\theta^{(i)})}$
　　　　　　　 $=\frac{\pi^{(i)} (p^{(i)})^{y_j}(1-p^{(i)})^{1-y_j}}{\pi^{(i)} (p^{(i)})^{y_j}(1-p^{(i)})^{1-y_j}+(1-\pi^{(i)})(q^{(i)})^{y_j}(1-q^{(i)})^{(1-y_j)} }$