机器学习算法深度总结(9)-EM算法

概率模型有时既有观测变量, 又有隐变量, 当存在隐变量时, 直接的最大似然估计无法直接搞定。
EM算法是一种迭代算法, 对于含有隐变量(hidden variable)的概率模型参数的极大似然估计或极大后验概率估计.
EM算法每次迭代分两步: E步, 求期望; M步, 求极大; 因此EM算法称为期望极大算法.

最经典的例子就是抛3个硬币:

假设三枚硬币, 分别记作A,B,C，正面出现的概率分别为 $\pi, p, q$ . ,抛A硬币决定B和C(A正面, 选B; A反面, 选C), 然后抛B或者C决定正反面, 正面记1, 反面记0; 然后估算3个硬币的正反面概率值。

下面对着三枚硬币建模模型:
$\begin{align*} P(y|\theta) &= \sum_z P(y,z|\theta) = \sum_z P(z|\theta)P(y|z,\theta) \\ &= \pi p^y(1-p)^{1-y} + (1-\pi)q^y(1-q)^{1-y} \ \ (1) \end{align*}$
上式, 随机变量y是观测变量, 一次试验最终结果是1, 则y=1; 否则, y=0; 随机变量z是隐变量, 表示中间为观测到的掷硬币A的结果; $\theta=(\pi, p, q)$ 是模型参数, 这模型是以上数据的生成模型.

注意: 对隐变量的理解是理解EM算法的第一要义, 这里, 随机变量y的数据可以观测, 但是随机变量z的数据不可观测.

我们可以简单的来核对一下这个概率模型写得对不对。我们画出一次抛掷硬币的整个过程，并计算出相应的概率。然后带入到上面的公式中就可以知道模型构建是否正确了。

case	A(z)	B	C	prob
1	1	1	-	$\pi * p$
2	1	0	-	$\pi * (1-p)$
3	0	-	1	$(1-\pi)*q$
4	0	-	0	$(1-\pi)*(1-q)$

分析:

试验结果为1
根据上表, 有 $P(y=1) = P(case1)+P(case3) = \pi * p + (1-\pi)*q$
同时, y=1带入上式(1), 有:
$P(y=1|\theta) =\pi p^1(1-p)^{1-1} + (1-\pi)q^1(1-q)^{1-1} = \pi p + (1-\pi)q$
试验结果为0
根据上表, 有 $P(y=0) = P(case2)+P(case4) = \pi * (1-p) + (1-\pi)*(1-q)$
同时, y=1带入上式(1), 有:
$P(y=0|\theta) =\pi p^0(1-p)^{1-0} + (1-\pi)q^0(1-q)^{1-0} = \pi * (1-p) + (1-\pi)*(1-q)$
可见, 公式(1)符合实际实验结果.

用极大似然估计求参数 $\theta$ :
观测数据 $Y=(Y_1,\cdots,Y_n)^T$ , 为观测数据 $Z=(Z_1,\cdots,Z_n)^T$ , 则观测数据的似然函数为:
$P(Y|\theta) = \sum_Z P(Z|\theta)P(Y|Z,\theta)$
即,
$P(Y|\theta) = \prod_{j=1}^n[ \pi p^{y_j}(1-p)^{1-y_j} + (1-\pi)q^{y_j}(1-q)^{1-y_j}]$
考虑求模型参数 $\theta=(\pi, p, q)$ 的极大似然估计:
$\hat \theta = \arg \underset{\theta}{\max} \log P(Y|\theta)$
该问题没有解析解, 只能通过迭代的方法求解, EM算法便是可求解这一问题的一种迭代算法.

一般地, 用Y表示观测变量的数据, Z表示隐变量的数据, Y和Z连在一起称为完全数据, 观测数据Y又称不完全数据.

不完全数据Y的概率分布是 $P(Y|\theta)$ , 对数似然函数 $L(\theta) = \log P(Y|\theta)$
完全数据Y和Z的联合概率分布 $P(Y,Z|\theta)$ , 对数似然函数是 $\log P(Y,Z|\theta)$

EM算法通过迭代求 $L(\theta) = \log P(Y|\theta)$ 的极大似然估计, 每次迭代先求E(期望), 后求M(极大化).

Q函数:

完全数据的对数似然 $\log P(Y,Z|\theta)$ 关于给定观测数据Y和当前参数 $\theta^{(i)}$ 下对未观测数据Z的条件概率分布 $P(Z|Y,\theta^{(i)}$ 的期望称为Q函数:
$Q(\theta, \theta^{(i)} = E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]$

EM算法:
输入: 观测变量数据, 隐变量数据Z, 二者联合分布 $P(Y,Z|\theta)$ , 条件分布 $P(Z|Y,\theta)$
输出: 模型参数 $\theta$

(1) 选择参数的初值 $\theta^{(0)}$ , 开始迭代
注意: EM算法对初始值敏感, 不同的初值可能得到不同的参数估计值
(2) E步: 第i+1次迭代的E步, 计算:
$\begin{align*} Q(\theta, \theta^{(i)}) &= E_Z[\log P(Y,Z|\theta) | Y, \theta^{(i)}] \\ &=\sum_Z\log P(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \end{align*}$
这里 , $Q^{(i)}$ 是第i次迭代参数 $\theta$ 的估计值, $P(Z|Y, \theta^{(i)})$ 是在观测数据Y和当前参数估计 $\theta^{(i)}$ 下隐变量数据Z的条件概率分布
(3)M步: 求使 $Q(\theta, \theta^{(i)})$ 极大化的 $\theta$ , 确定第i+1次迭代的参数估计值 $\theta^{(i+1)}$ , 完成一次迭代 $\theta^{(i)} \rightarrow \theta^{(i+1)}$ :
$\theta^{(i+1)} = \arg \underset{\theta}{\max} Q(\theta, \theta^{(i)})$
每次迭代使似然函数增大或达到局部极值.
(4) 重复(2)(3)步, 直到收敛.
迭代终止条件, 一般是对较小的 $\epsilon_1,\epsilon_2$ , 若满足:
$\|\theta^{(i+1)}-\theta^{(i)} \| < \epsilon_1 \; \; \text{or} \; \; \| Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)}) \| < \epsilon_2$
则停止迭代.