EM算法

  首先感谢高佩旭同学的PPT，很怀念以前一起学习数据挖掘十大算法的时光。

1.问题引入

一般情况：

  假设我们遇到这样一个问题：我们需要调查我们学校的男生和女生的身高分布。采取抽样调查的方法，在校园里随便选取100个男生和100个女生，共200个人（也就是200个身高的样本数据）。

  为了方便分类统计，我们可以将他们带进一个教室，然后让男生站到左边，女生站到右边。这样就可以先统计抽样得到的100个男生的身高。假设他们的身高是服从高斯分布的。但是这个分布的均值u和方差∂2我们不知道，这两个参数就是我们要估计的。记作θ=[u,∂]T。

  假设抽到男生的概率是p(XA|θ)，且每次抽取都是相互独立的，则抽到100个男生的概率为:

根据极大似然估计的思想，出现了的就应该是最有可能出现的，它出现的概率应该最大，所以转化为求解在何种θ的取值下，P(XA1,XA2,...,XA100;θ)能取到最大值。直接求导不方便，可以先去对数，然后再求导数：

然后便可以求解出参数{u,∂}，这样就可以得到相应的高斯分布，可以直接用于测试样本的性别了。

特殊情况：

  若这200人是混在一起的，无法分开。随机选取一人无法确定其是男生还是女生。 用数学的语言就是，抽取得到的每个样本都不知道是从哪个分布抽取的。

  这个时候参数不仅仅是高斯分布的{u,∂}，还多了一个这个样本是男生还是女生？直接用极大似然估计求解是不可能的，因为压根就不知道样本到底是男性还是女性，无法将所有男性连乘（哪些是男性都不知道，怎么连乘？）。这个时候就需要用到EM算法了。

  EM算法的基本思想是:假设我们想估计知道A和B两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

2.EM算法

  对于每个实例i,用Qi表示样本实例i的隐含变量z的某种分布，且Qi满足条件:(∑zQi(z)=1,Qi(z)>=0) ,如果Qi是连续性的，则Qi表示概率密度函数，需要将求和符号换成积分符号。例如上面的例子中隐变量就是样本的性别分布，该分布中有两种取值{男性，女性},Qi(z)表示样本i的隐变量第z种可能取值的概率。

  我们的目标就是求解使得P(x1,x2,...,xn;θ)最大的参数θ，也就是最大化∑ilogp(xi;θ)，又由于隐变量存在，所以需要引入隐变量，上式等价于:

第一步到第二步(公式2.1)很好理解，就是求各种取值下的z的概率之和，即p(xi;θ)=∑zip(xi;zi,θ)，根据概率归1性，这是很好理解的；第二步到第三步(公式2.2)相当于先乘了Qi(zi)再除以一个Qi(zi)，值是保持不变的。但是第三步到第四步(公式2.3)就不那么好理解了，需要先理解Jensen不等式。请参考后面的Jensen不等式说明。

  假设你已经看了下面的Jensen不等式介绍。我们可以将公式2.2和公式2.3中的对数函数看成某个凹函数，即f=log,将p(xi;zi,θ)Qi(zi)看成是X,将Qi(zi)看成是p(X).
  根据期望的定义E(X)=∑X∗p(X),在公式2.2中∑ziQi(zi)p(xi;zi,θ)Qi(zi)就是自变量p(xi;zi,θ)Qi(zi)的期望，然后再取log函数值，也就是期望的函数。
  同理在公式2.3中，根据E(f(X))=∑f(X)∗p(X)的定义，将公式2.3中的Qi(zi)看成是p(X)，将log(p(xi;zi,θ)Qi(zi))看成f(X)那么∑ziQi(zi)log(p(xi;zi,θ)Qi(zi))就是函数值的期望。
  根据Jensen不等式，期望值的函数要大于等于函数的期望值，所以上面的不等式是成立的。

  之所以转化为公式2.3有两个原因，一是因为公式2.3中的函数方便求导；二是这样可以得到目标函数L(x;θ)的一个下界，通过不断优化下界的最大值就可以让目标函数尽可能取到最大值，最终收敛。

  我们的目标函数L(x;θ)=∑ilogp(xi;θ)>=∑i∑ziQi(zi)log(p(xi;zi,θ)Qi(zi))=J(x;z,θ)，其中x是样本，是已知的，未知参数是{z,θ},所以我们要想办法不断的最大化J(z,θ)，使得L(θ)能够最大化。根据下图来进行讲解:

  EM算法的核心思想就是：假设我们想估计知道A和B两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

  如上图中，首先我们固定θ，调整Q(z)使下界J(z,Q)上升至与L(θ)在此点θ处相等（绿色曲线到蓝色曲线），然后固定Q(z)，调整θ使下界J(z,Q)达到最大值（θt到θt+1），然后再固定θ，调整Q(z)……直到收敛到似然函数L(θ)的最大值处的θ。

  因为L(x;θ)>=J(x;z,θ)，所以J的最大值就是L，所以每次θ固定时，调整z要取到的最大值就是L，也就是要调整z使得J=L。所以现在有两个问题:1.怎么样选择Q(z)(即每种z的取值概率)才能让J取到最大值，即J=L。2.该算法是否一定会收敛呢?

  对于第一个问题，根据Jensen不等式中，二者相等的条件，即变量X为常数时才相等，所以要让公式2.3中的p(xi;zi,θ)Qi(zi)为常数是，即p(xi;zi,θ)Qi(zi)=c时才能取到最大值。

  做一下变换,p(xi;zi,θ)=Qi(zi)∗c，两边对各种z的可能取值的概率求和，即:

又∑zQi(zi)=1,即z的可能取值之和的概率为1.则有:

又p(xi;zi,θ)=Qi(zi)∗c，根据公式2.5，用∑zp(xi;zi,θ)替换c的取值，则有:


至此，我们推出了在固定参数θ后，使得下界拉升到最大值的Q(z)的计算公式就是后验概率（条件概率）,这样就解决了如何确定Q(z)的值使得J最大，也就是前面的要解决的第一个问题。以前面的男女混在一起抽样为例，我们初始化了男的和女的高斯分布参数，这样就能够对每个样本进行分类，分为男的和女的。此时根据分类结果，计算男的后验概率和女的后验概率，作为让J取到最大值的Q(z),然后再固定这个Q(z)值，用极大似然估计来求解θ，然后循环往复的进行，直到收敛。这就是EM的两个基本步骤，E步骤和M步骤。

E步骤和M步骤:
E步骤:
  根据参数初始值的θ或上一次迭代的模型参数的θ来计算出隐性变量z的后验概率，其实就是隐性变量的期望。作为隐藏变量的现估计值:

M步骤:
  在获得当前的隐变量的估计值的情况下将似然函数最大化以获得新的参数值θ:

  对于第二个问题，为什么一定会收敛呢？ 假设现在进行第t轮和第(t+1)轮迭代，此时t轮结束时有：

其中Qti表示第t轮确定的隐变量取值，注意，下一轮开始时，这个Qti还是会用到

第(t+1)开始时有，固定Q(z)，优化θ，假设此时为θ(t+1)，则有:

在Q(z)相同的情况下,L(θ(t+1)) 是在L(θ(t))基础上优化θ取到的最大值，显然有:

这就证明了L(θ)会单调增加，肯定会达到最大值，然后收敛。要判断是否已经收敛有两种办法：一是L(θ)值不再变化；第二种是L(θ)变化幅度特别特别小了，这时需要定义一个阀值，如果小于这个阀值，那么就认为收敛了。

  至此就完成了证明过程，下面是Jensen不等式的介绍。

3.Jensen不等式

Jensen不等式：
  如果f是凹函数，X是随机变量，那么：

。（若为凸函数则相反）特别地，如果f是严格凸函数，当且仅当X是常量时，上式取等号。通俗一点就是如果函数是凹函数，那么期望值的函数要大于或等于函数值的期望。

  根据下图中的凹函数进行理解：

显然有f(x1+x22)>=f(x1)+f(x2)2，前面是x1和x2的期望值的函数，后面是函数f(x1)和f(x2)的期望。

  由于log函数(即对数函数)是凹函数,那么也满足上述性质，就可以用于EM算法推导过程。