4.1-EM算法

适用场景

  EM算法用于估计含有隐变量的概率模型参数的极大似然估计，或者极大后验概率估计。当概率模型既含有观测值，又含有隐变量或潜在变量时，就可以使用EM算法来求解概率模型的参数。当概率模型只含有观测值时，直接使用极大似然估计法，或者贝叶斯估计法估计模型参数就可以了。

举例说明

  这是一个抛硬币的例子，H表示正面向上，T表示反面向上，参数θ$\theta$表示正面朝上的概率。硬币有两个，A和B，硬币是有偏的。本次实验总共做了5组，每组随机选一个硬币，连续抛10次。如果知道每次抛的是哪个硬币，那么计算参数θ$\theta$就非常简单了，如上图所示。
  可以看出A硬币出现正面的概率为0.8，B硬币出现正面的概率为0.45.
  此时，如果我们只知道有2种硬币，但是不知道抽出来的是哪种硬币，还要求计算两种硬币出现正面的概率呢。用数学语言说就是，有一个隐含因素，且有一些列观测值，求其参数。此时就需要用EM算法了。具体过程如下图：

  其计算过程如下:
1. 给θA${\theta }_A$,θB${\theta }_B$一个初始值。
2. E-step，分别计算每组实验中，硬币A和硬币B为正面的概率。再计算其为正面的期望。
3. 利用3中计算得到期望值重新计算θA${\theta }_A$,θB${\theta }_B$。
4. 当迭代到一定的次数，或者算法收敛到一定精度，结束算法，否则继续2.

  稍微解释一下上图的计算过程，这里设初始值θA=0.6${\theta }_A=0.6$，θB=0.5${\theta }_B=0.5$。
  首先解释第二步中0.45如何来的。由于θA=0.6${\theta }_A=0.6$，所以第一个硬币为A硬币的概率为P(X1=A)=C510×0.65×0.45=0.45$P(X_1=A)=C_{10}^5\times {0.6}^5\times {0.4}^5=0.45$.表示第一个硬币为A的概率为0.45.同理第一个硬币为B的概率为0.55.
  然后解释图中第二步2.2H，2.2T是怎么来的呢。E(X1A=H)=5∗0.45=2.2$E(X_{1A}=H)=5\ast 0.45=2.2$,同理第一个硬币为A且出现反面的期望为E(X1A=T)=5∗0.45=2.2$E(X_{1A=T})=5\ast 0.45=2.2$.

EM算法的导出

观测数据:观测到的随机变量X的样本：X(x1,x2,......,xn)$X(x_1,x_2,......,x_n)$(这里假设总共有n个样本，总共m个特征)其中每个xi(xi1,xi2,......,xim)$x_i(x_{i1},x_{i2},......,x_{im})$
隐含变量:未观测到的随机变量Z的值: Z(z1,z2,......,zk)$Z(z_1,z_2,......,z_k)$
完整数据:包含观测到的随机变量X和隐含变量Z的数据:Y((x1,zj1),(x2,z2),......,(xn,zjn))$Y((x_1,z_{j1}),(x_2,z_2),......,(x_n,z_{jn}))$其中每个样本有一个隐含变量。

  边缘分布列的定义:∑+∞j=1P(X=xi,Y=yj)=P(X=xi)$\sum _{j=1}^{+\mathrm{\infty }}P(X=x_i,Y=y_j)=P(X=x_i)$

  似然函数为L(θ)=∑ni=1lnP(θ|xi)=∑ni=1ln∑kj=1P(θ,zj|xi)$L(\theta )=\sum _{i=1}^{n}lnP(\theta |x_i)=\sum _{i=1}^{n}ln\sum _{j=1}^{k}P(\theta ,z_j|x_i)$

  目标为极大化此似然函数。

  这里设Qi$Q_i$为z在每一个样本的分布函数，所以Qi$Q_i$满足的条件是：

∑kj=1Qi(zj)=1$\sum _{j=1}^k{Q}_i(z_j)=1$

Qi(zj)≥0$Q_i(z_j)\ge 0$ 其中j=1,2,....,k$j=1,2,....,k$ i为1到n间数字

L(θ)===∑ni=1lnP(θ|xi)∑ni=1ln∑kj=1P(θ,zj|xi)∑ni=1ln∑kj=1Qi(zj)P(θ,zj|xi)Qi(zj)$\begin{array}{lll}L(\theta )& =& \sum _{i=1}^{n}lnP(\theta |x_i)\\ & =& \sum _{i=1}^{n}ln\sum _{j=1}^{k}P(\theta ,z_j|x_i)\\ & =& \sum _{i=1}^{n}ln\sum _{j=1}^k{Q}_i(z_j)\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)}\end{array}$

  根据期望公式:E(f(x))=∑if(xi)p(xi)$E(f(x))=\sum _{i}f(x_i)p(x_i)$
  ∑kj=1Qi(zj)P(θ,zj|xi)Qi(zj)$\sum _{j=1}^k{Q}_i(z_j)\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)}$是P(θ,zj|xi)Qi(zj)$\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)}$的期望。

  根据Jensen不等式:

  f(x)=lnx$f(x)=lnx$是凹函数f(E(x))≥E(f(x))$f(E(x))\ge E(f(x))$

  所以：ln(E(x))≥E(lnx)$ln(E(x))\ge E(lnx)$

  所以:

L(θ)=∑ni=1lnE(P(θ,zj|xi)Qi(zj))≥∑ni=1E(lnP(θ,zj|xi)Qi(zj))$L(\theta )=\sum _{i=1}^{n}lnE(\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)})\ge \sum _{i=1}^{n}E(ln\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)})$

  根据数学期望相关定理:E(f(x))=∑if(xi)p(xi)$E(f(x))=\sum _{i}f(x_i)p(x_i)$

L(θ)≥∑ni=1E(lnP(θ,zj|xi)Qi(zj))=∑ni=1∑kj=1Qi(zj)lnP(θ,zj|xi)Qi(zj)$L(\theta )\ge \sum _{i=1}^{n}E(ln\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)})=\sum _{i=1}^n\sum _{j=1}^k{Q}_i(z_j)ln\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)}$

  这个过程可以看作是对L(θ)$L(\theta )$求下界，对于Qi$Q_i$的选择，有多种可能，哪种更好呢.假设θ$\theta$已经给定，那么L(θ)$L(\theta )$的值就决定于Qi(zj)$Q_i(z_j)$和p(zj|xi)$p(z_j|x_i)$了。我们可以通过调整这两个概率使下界不断上升，以逼近L(θ)$L(\theta )$的真实值，那么什么时候算调整好了呢。按照jesen不等式，当不等式变为等式时，所以此时我们得到:

P(θ,zj|xi)Qi(zj)=c$\frac{P(\theta ,z_j|x_i)}{Q_i(z_j)}=c$

  其中c为常数，不依赖于z(i)$z^{(i)}$对式子做进一步推导，我们知道∑kj=1Qi(zj)=1$\sum _{j=1}^k{Q}_i(z_j)=1$,所以∑kj=1P(θ,zj|xi)=c$\sum _{j=1}^{k}P(\theta ,z_j|x_i)=c$

Qi(zj)===P(θ,zj|xi)∑kj=1P(θ,zj|xi)P(θ,zj|xi)P(θ|xi)P(zj|xi,θ)$\begin{array}{lll}{Q}_i(z_j)& =& \frac{P(\theta ,z_j|x_i)}{\sum _{j=1}^{k}P(\theta ,z_j|x_i)}\\ & =& \frac{P(\theta ,z_j|x_i)}{P(\theta |x_i)}\\ & =& P(z_j|x_i,\theta )\end{array}$
  至此，我们推出了在固定了其它参数θ$\theta$后，解决Qi(zj)$Q_i(z_j)$如何选择的问题。这一步就是E步，建立L(θ)$L(\theta )$的下界。接下来就是M步，就是再给定Qi(zj)$Q_i(z_j)$后，调整θ$\theta$,去极大化L(θ)$L(\theta )$的下界。所以EM算法步骤为:

循环重复直到收敛
{
(E步)对于每一个i，计算
   Qi(zj):=P(zj|xi,θ)$Q_i(z_j):=P(z_j|x_i,\theta )$
(M步)计算
   θ:=argmaxθ∑ni=1∑kj=1Qi(zj)lnP(θ|zj,xi)Qi(zj)$\theta :=arg\underset{\theta }{max}\sum _{i=1}^n\sum _{j=1}^k{Q}_i(z_j)ln\frac{P(\theta |z_j,x_i)}{Q_i(z_j)}$
}

  那么究竟怎么确保EM收敛？假定θ(t)${\theta }^{(t)}$和θ(t+1)${\theta }^{(t+1)}$是EM算法的第t次和t+1次迭代后的结果，如果们我们证明了L(θ(t))≤L(θ(t+1))$L({\theta }^{(t)})\le L({\theta }^{(t+1)})$,也就是说极大似然估计单调增加，那么最终我们会得到最大似然估计的最大值。

L(θ(t+1))≥≥=∑ni=1∑kj=1Qi(zj)lnP(θ(t+1),zj|xi)Qi(zj)∑ni=1∑kj=1Qi(zj)lnP(θ(t),zj|xi)Qi(zj)L(θ(t))$\begin{array}{lll}L({\theta }^{(t+1)})& \ge & \sum _{i=1}^n\sum _{j=1}^k{Q}_i(z_j)ln\frac{P({\theta }^{(t+1)},z_j|x_i)}{Q_i(z_j)}\\ & \ge & \sum _{i=1}^n\sum _{j=1}^k{Q}_i(z_j)ln\frac{P({\theta }^{(t)},z_j|x_i)}{Q_i(z_j)}\\ & =& L({\theta }^{(t)})\end{array}$