记得曾经写过一篇关于EM算法的博客，在新浪博客上，不知道是因为是没有仔细学习还是别的什么原因，突然发现自己又不太理解这个算法了，所以在这里又详细进行了一番思考和记录。

准备知识

1.贝叶斯公式：

相信学过统计的同学们对这个公式都不会陌生，贝叶斯公式是表示在确定事件A发生的条件下事件B发生的概率，因而我们将此概率称为最大后验概率，公式表示为：
$$P(A|B)=\frac{P(B|A)P(A)}{P(B)}\propto L(A|B)P(A)\quad(1)$$
其中$P(A)$为事件A出现的先验概率，$P(A|B)$为在B发生的条件下A发生的概率。

2.高斯分布：

高斯分布相对来说比较简单也比较熟悉，高斯分布主要有两个参数，1.确定高斯分布位置的参数$\mu$，2.确定高斯分布离散度的参数$\delta$， 这两个参数确定了之后高斯分布也就确定了，高斯分布的标准形式为：
$$p(x)=\frac{1}{\sqrt{2\pi}\delta}e^{-\frac{(x-\mu)^2}{2\delta^2}}\,(\delta >0)\quad(2)$$
高斯分布的主要特征为：

  1. 集中性，正态分布的高峰位于正中央，即均数所在的位置；
  2. 对称性：正态曲线以均数为中心，左右对称，曲线两端永远不与横轴相交。
  3. 均匀变动性：正态曲线由均数所在处开始，分别向左右两侧逐渐均匀下降。
  4. 正态分布有两个参数，$\mu$ 和标准差 $\delta$，可记作$N(\mu,\delta)$:期望决定正态曲线的中心位置，标准差 $\delta$决定正态曲线的 $\delta$越小，曲线越陡峭；$\delta$越大，曲线越扁平。

3.相对熵:

相对熵又称KL散度，相对熵是两个概率分布非对称性的度量。设 $p(x)$ 和 $q(x)$ 为随机变量$X$的两个不同的分布密度，则他们的相对熵定义为：
$$D(p|q)=\Sigma_xp(x)log\frac{p(x)}{q(x)}\quad(3)$$
相对熵的性质有：1.相对熵是不对称的；2.相对熵不满足三角距离公式。

EM算法介绍

EM算法是一种经典的最大似然算法，主要用于解决样本数目不足或似然函数中含有参数的方法，从有限的样本数据中准确求取模型的参数是EM算法的主要目的。
现在给定训练样本$x_1,…x_m$,样本间相互独立，现在假设样本都来自同一个高斯分布，则我们要找到高斯分布的参数使得取出这些样本的概率最大，则可以表示为：
$$L(\theta)=\prod p(x_i,\theta)\quad(4)$$
对于上式求解极大值，由于对于累乘的求解比较困难，取对数化为累加,然后对于 $\theta$ 求偏导等于0，求解出最优参数 $\theta$ ，上面描述的问题是一个简单的高斯分布的参数求取问题，而实际上我们面临的问题要复杂得多，我们假设从一个高斯混合模型中取得了样本 $x^1,…x^m$ 样本相互独立但是我们不知道取出的样本属于哪个高斯分布，那么现在我们的问题是根据这些样本估计各个高斯分布的参数。
首先如果我们知道哪些样本属于同一高斯分布，则我们就可以通过这些样本求取各个高斯分布的参数，另外，如果我们知道各个高斯分布的参数，那么我们就可以通过高斯分布的参数确定各个样本的归属。也就是说高斯分布的参数和各个样本的归属类别其实是相互影响的。对于这样的情况就比较适用EM方法进行求解了。（什么你跟我说这个跟K均值算法很相似，好吧确实有点相似，我们等一下会分析他们之间的联系和区别的）
对于上面那个混合高斯模型的问题，实际上在各个变量中隐藏了一个参数就是各个变量的归属，我们假设这个参数为$z$，则公式（4）的最大似然估计可以被描述为:
$$L(\theta)=\Sigma_i^m logp(x;\theta)\\ =\Sigma_i^mlog\Sigma_zp(x,z;\theta)(5)$$

相信在看过了上面的解释后大家对这个变量$z$的出现就不以为然了。现在我们所要做的就是对公式(5)进行求解，但是由于有着隐藏变量$z$的存在，求解比较困难，所以我们想呀，如果$z$确定了，那就跟最大似然是一样的了，好了这里我们留一个悬念，下面直接进入EM环节，在EM算法中分为两个步骤：E步骤，建立函数$l$的下界，M步骤，对 $l$ 函数的下界进行优化，这两个步骤看起来比较抽象，下面我们将进入具体的公式环节，
对于每一个给定的样本$x_i$我们假设$Q_i$为隐藏变量$z$的分布，$Q_i$满足：$\Sigma_zQ_i(z)=1\,,Q_i(z)\ge 0$。这个$Q_i$跟$z$的表示相关。
则对于公式（5）我们对公式进行变形得：
$$\Sigma_i log p(x^i;\theta)=\Sigma_i log\Sigma_zQ_i(z^i)\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}\quad(6)$$
好了我们可以看到，公式（5）和公式（6）比较起来只是乘了一个$Q$，可是依旧没有什么帮助，但是最重要的部分为公式（6）的等式可以转换为
$$\ge\Sigma_i\Sigma_zQ_i(z^i)log\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}\quad(7)$$
由（6）到（7）的变换为Jensen不等式，这个不等式可以参考：http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html
好了根据以上推导我们可疑总结一下EM算法流程了：
E步骤：根据参数 $\theta$ 的初始值或上一次迭代结果记为： $\theta^n$ ，通过迭代结果 $\theta^n$ 来求解一个分布 $q(z)$ 使得 $l(q,\theta)$ 最大化；
$$Q_i(x^i):=p(z^i|x^i;\theta)$$
M步骤：固定$q(z)$，求一个 $\theta$ ，记为 $\theta^{n+1}$ ，使得 $l(q,\theta)$ 最大
$$\theta:=argmax\theta\Sigma_i\Sigma_zQ_i(z^i)log\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}$$

EM算法与K-Means算法的区别:

其实EM算法和k均值算法很类似，都是分配然后调整的过程，只是在k均值算法过程中采用的调整策略是距离策略，而EM算法采用的调整策略是概率策略，当然，对于正太分布的对象来说他们之间的区别在这里，而对于EM算法来说它是一种广义的调整算法，类别可以为各种分布形式而不仅仅局限于高斯分布。