EM Algorithm

最近补一些Basic的知识，先从最常见的EM算法开始讲吧，EM算法被广泛的应用于各种各样的算法之中,对于那些概率模型之中存在着难以观测的隐变量的情况下，我们都可以使用它寻找参数的最大似然估计。

EM算法主要有两步所构成，分别是

1. 第一步计算期望(E):对于隐变量的现有的估计的值，计算器最大似然估计值
2. 第二步最大化(M):最大化在E步上得到的最大似然值计算参数的值，在M之中寻找的估计用于下一个E步的计算之中，然后不断的交替的运行。

说起来有点抽象，我们用一个实际的例子进行讲解，也就是最著名的Flipping Coins的问题

假设我们有两个硬币分别是$A$以及$B$，现在丢硬币的时候对于选择$A$还是$B$的是不清楚的，可以看成冥冥之中有一个隐变量控制我们选择那一块硬币，现在我们想要知道的是在每一次投掷硬币的时候是选择了哪一个硬币。这个看起来是非常的麻烦，因为我们并不知道那个隐变量到底是如何控制我们选择硬币的。

不过我们能够知道的就是在某一个时刻一定是会选择A或者是B作为当前投掷的硬币，那么不妨计算一个如果是A硬币的概率，再计算一个如果是B硬币的概率，再比较一下，哪一个的概率高就是哪个硬币。随机初始一个概率$P(A)$以及$P(B)$,然后再判断在某一次投硬币的时候会是哪个硬币

上面就是投币的情况，对于初始的概率，我们可以计算出不同的时间所可能投掷的硬币的情况，在上面的情况就是

那么有3次投掷是A而总共A向上的情况出现了5次，占总投掷15次的三分之一，那么久可以得到A投掷向上的概率，同理可以计算出B的概率。通过上面的这样的过程就可以得到一个硬币的向上的概率的值。我们可以将其抽象化看成是一个如下的模型

其中$z$一般被记作是隐藏状态，而$y$被记作是观测状态。对于这个模型有两种状态，分别是Complete和Incomplete。在Complete Case之中，也就是隐藏和观测状态都可以被观测到，但是在InComplete 的情况下，隐藏状态是一个未知的量。

对于Complete Case的话，由于$y$以及$z$都是可以知道的量，所以模型的成立的概率就等于

$$p(y,z|\theta)$$

取一个对数就可以得到

而对于Incomplete Case的情况，我们仅仅能够获得的信息是关于$y$的信息，而$z$的情况是未知的，但是我们又希望可以在模型之中考虑$z$以帮助我们进行决策，所以可以写成

那么对于这样的模型解决方法选择EM算法会是一个非常好的选择。

上面的算法流程有些抽象，但是不要紧，我们一步一步的进行讲解，首先还是得到我们的数据，然后有一个初始的参数值记作是$\theta_0$，那么在第一次迭代的时候，我们假定这个$theta_0$是真实的值，那么现在有了$\theta_0$以及$y$，我们就可以反推出当时的$z$的值是多少，或者说可以看看不同的$z$的情况有多大的可能造成这样$\theta_0$以及$y$。那么一旦$z$也给定了的话，就变成了是Complete Case了所以整个模型的概率就可以写成是一个关于$\theta$的函数

$$\sum_{Z }p(Z|Y,\theta_0) \log P(Y,Z|\theta)$$

如果将上面的这个式子记作是$Q(\theta,\theta_0)$的话，由于这时候只有$\theta$是未知的，所以可以对于其进行优化，寻找到一个使得上面的式子最大的$\theta$，并将这个$\theta$记作是$\theta_{1}$

$$\theta_{1} = \arg \max Q(\theta , \theta_0)$$

然后这时候在下一步也是将$\theta_1$认为是已知的，从而达到不断的迭代的过程。

Converge？

我们应用一个算法，关注的一点当然是看他可以不可以收敛到某个具体的值上，那么我们现在来看看EM算法是不是的确可以收敛到某一个特定的值上面。

根据条件概率公式，我们可以将模型的概率写成是

$$p(y|\theta) = \frac{p(y,z|\theta)}{p(z|y,\theta)}$$

取对数的话

$$\log p(y|\theta) = \log p(y,z|\theta) + \log p(z|y,\theta)$$

对于左右同时取一个期望

由于左边与$z$无关，所以就等于乘了个1。那么两次迭代的结果相减

而对于$Q,H$来说呢

所以模型整体的期望是递增的，而由于模型又是有界的，即范围在[0,1]之内，所以EM算法一定是可以收敛的。

Computation

解决了收敛性的问题算是解决了后顾之忧了，现在我们看看在具体的计算的问题之中会不会出现什么幺蛾子呢？

将模型的概率展开

$$l(\theta) = \log p(y|\theta) = \log \sum_z p(y,z|\theta) = \log \sum_{z}p(y|z,\theta) p(z|\theta)$$

如果要对于上面的这个式子做优化的话，是一个非常恶心的过程，因为这里存在着一个这样的结构$\log \sum$，在优化的时候这个东西就是个魔鬼，所以我们需要把它变成一个稍微好处理一些的形式。

怎么变化呢？如果减去其前一次迭代时的概率的值可以得到

也就是说

如果使用

那么

而

也就是说我们完全是可以使用$B(\theta_i,\theta_i)$作为原来的目标函数的一个替代表示，而其相比于初始的状态，在计算上就更好优化以及应用了。

 

以上就是EM算法的理论的证明和应用，在之后的各种的涉及概率的模型之中我们都会大量的使用EM算法对于整个的模型的目标进行优化。比如说LDA和HMM之中，都会有使用到相关的内容。