EM算法

1.与极大似然估计的关系：
极大似然估计：已知结果和概率分布估计概率分布的参数 θ$\theta$
EM算法：已知结果估计概率分布的参数 θ$\theta$，EM算法是含有隐变量的概率模型参数的极大似然估计法。

  一般的用Y表示观测随机变量的数据，Z表示隐随机变量的数据。Y和Z连在一起称为完全数据，观测数据Y称为不完全数据。
  假设给定观测数据Y,其概率分布是P(Y | θ$\theta$), 其中 θ$\theta$ 为要估计的模型参数，那么Y的似然函数为L(θ$\theta$) = log P(Y | θ$\theta$)，假设Y和Z的联合概率分布是P(Y,Z | θ$\theta$)，那么完全数据的对数似然函数是log P(Y,Z | θ$\theta$)。

例子：http://blog.****.net/u011300443/article/details/46763743

2. EM算法思想：

（1）选择参数的初始值 θ(0)${\theta }^{(0)}$，重复以下步骤
（2）E步：记θ(i)${\theta }^{(i)}$为第i次迭代参数θ$\theta$的估计值，计算第i+1次的隐形变量的期望：

这是完全数据对数似然函数log P(Y,Z | θ$\theta$)关于在给定个观测数据Y和当前参数θ(i)${\theta }^{(i)}$下对未观测数据Z的条件概率分布P(Y,Z | θ(i)${\theta }^{(i)}$)的期望。

（3）M步：求使似然函数最大化的参数 θ(i+1)${\theta }^{(i+1)}$，

（4）重复（2）（3）直到收敛。
EM算大与初始值的选择有关，选择不同的初始值可能会有不同的参数估计值。

3. EM算法的推导：
  对于一个含有隐形变量的概率模型，我们的目标是极大化不完全数据Y对于参数θ$\theta$的对数似然函数，即极大化：

我们想找到合适的 θ$\theta$ 和z使得L(θ$\theta$) 最大，但是以往的分别对θ$\theta$ 和z求偏导并使其为0的方法并不适用，因为目标函数里有关于z的概率密度和，是关于z的和的对数。
  EM算法是通过迭代逐步近似极大化L(θ$\theta$)，我们希望第i+1次的估计值比第i次的估计值使得L(θ$\theta$)增加，并逐步达到极大值。考虑两者之差：

其中利用Jensen不等式（log(∑ni=1xin)≥∑ni=1log(xi)n$log(\sum _{i=1}^n\frac{x_i}{n})\ge \sum _{i=1}^n\frac{log(x_i)}{n}$）进行了转换.
令
即为L(θ$\theta$)的一个下界。任何使得 B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$增大的θ$\theta$，也使得L(θ$\theta$)增大，所以问题等价为选择θ(i+1))${\theta }^{(i+1)})$使得B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$极大。

上式等价于EM算法的一次迭代。EM算法是不断求解下界的极大化来逼近求解对数似然函数的极大化。

4. EM算法直观解释：

图中上方实线为L(θ$\theta$)，下方细实线为B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$，在 θ(i)${\theta }^{(i)}$ 处两个函数相等，EM算法计算的下一个点θ(i+1)${\theta }^{(i+1)}$ 使得B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$极大化，函数B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$的增加，保证对数似然函数L(θ$\theta$)在每次迭代中也是增加的，但是EM算法不能保证全局最优值。

学习参考：
http://blog.****.net/zouxy09/article/details/8537620