Skip to content

EM 算法

约 574 个字 预计阅读时间 2 分钟

定义

EM 算法是一种迭代算法，用于含有隐变量的概率模型求极大似然估计，或极大后验概率估计。EM算法的迭代每次由两步进行：E步，求期望(expectation)；M步，求极大(maximization)，所以这一算法被称作期望极大算法。

策略

三硬币模型

假设有 3 枚硬币，分别记作A、B、C,这些硬币出现正面的概率是\(\pi\)、\(p\)、\(q\)。进行如下抛硬币实验，先掷硬币A，根据其结果选择硬币B或C，正面选B，反面选C，然后掷选出的硬币，出现证明记作1，反面记作0，独立重复n次实验，得到一组观测结果。如果我们知道过程中到底掷了多少次B，多少次C，根据中心极限定理可以估算出\(\pi\)、\(p\)、\(q\)，但是我们现在不清楚中间过程，但还是要求出\(\pi\)、\(p\)、\(q\)，这就是目前面临的问题。

三枚硬币的整体概率可以写作$P(y|\theta)=\Sigma_zP(y,z|\theta)=\pi p^y(1-p)^{1-y}+(1-\pi)q^y(1-q)^{1-y} \(。其中y是观测变量，表示一次试验观测结果是0还是1，随机变量z是隐变量，表示未观测到的掷硬币A结果，\)\theta $是模型参数。

实际当中求这个式子的极大似然估计$\hat{\theta}=\arg\max_\theta\log P(Y|\theta) $，这个问题并没有解析解，只有通过迭代求解。

求解

迭代方案

EM 算法首先选取参数的初值，记作$\theta^{(0)}=(\pi^{(0)},p^{(0)},q^{(0)}) $，然后通过以下步骤迭代： $$ \pi^{(i+1)}=\frac{1}{n}\Sigma_{j=1}^n\mu_j^{(i+1)}\ p^{(i+1)}=\frac{\Sigma_{j=1}^n\mu_j^{(i+1)}y_j}{\Sigma_{j=1}^n\mu_j^{(i+1)}}\ q^{(i+1)}=\frac{\Sigma_{j=1}^n(1-\mu_j^{(i+1)})y_j}{\Sigma_{j=1}^n(1-\mu_j^{(i+1)})} $$其中 $$ \mu_j^{(i+1)}=\frac{\pi^{(i)}(p^{(i)})^{y_i}(1-p^{(i)})^{1-y_j}}{\pi^{(i)}(p^{(i)})^{y_i}(1-p^{(i)})^{1-y_j}+(1-\pi^{(i)})(q^{(i)})^{y_i}(1-q^{(i)})^{1-y_j}} $$

实际过程

  1. 选择起始参数，开始迭代
  2. E步：计算$Q(\theta,\theta^{(i)})=E_z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]=\Sigma_Z\log P(Y,Z|\theta)P(Z|Y,\theta^{(i)}) $
  3. M步：求使得$Q(\theta,\theta^{(i)}) \(极大化的\)\theta \(，作为第\)i+1 $次迭代参数的估计值