本节讲的主要是EM算法的推导，对于算法的应用解释的不多，所以这里不多赘述，只讲讲推理的主要思想。
E步就是想根据上一步的参数θ，找到最好的Qi，得到最好的下界，最好的下界。。
M步，就是想根据上一步得到的最好的下界（固定住Q），找到这个下界上最大的值，找到最好的θ。。
1、Jensen不等式
如果f是凸函数，X是随机变量，那么
当且仅当X是常量时，上式左右两边相等。
从图中可以看到，这是成立的。
当不等式，应用于凹函数时，不等号方向相反 ，也就是：
2、EM算法
--------------------------------------------------------------------------------------
故意写在前面，是为了下面思路连接起来清晰一些。
--------------------------------------------------------------------------------------
log(x)是凹函数，并且
是
的期望。其中，X是z(i) , Qi(z(i))是pk，上式是g(x)。
相当于求g(x)的期望。再根据不等式，可以得到（3）。
-----------------------------------------------------------------------
2.1 开始推导
已有数据x(i)，样例间独立，我们想要找到每个样例隐含的类别z，已知数据，又假设了分布，所以想到用极大似然 估计，如下：
但是，直接求θ并不好求，所以我们用EM方法，不断地建立极大似然函数的下界（E步），然后优化下界（M步）。其中用到了Jensen不等式以及“自变量的函数”期望公式。
此时相当于求出了下界的表达式。但是，想要找出最好的下界，那么最好就是2和3两式 相等。
再由
认为下面的[p(x,z)/Q(z)] 是随机变量X（这里不同于上式为了推出公式3的那个X了），函数log是f。于是可以知道f(E(X)) >= E[f(X)].即，
根据前面所说的，当且仅当X是常量时，
等式才能相等。把上面等式中的Q移到右边，再累计加k个不同类别的Q。
sigma Q = 1.于是可以得到：
再带入上式，可以求出Q：
可以看出，固定其他参数后，类别的概率密度计算公式就是后验概率
另外，至此，Q已经求出，就可以根据前面的（3）式，得到一个下界。然后接下来的M步，就可以根据上面得到的下界函数，极大化，求得参数θ。
一般的EM算法的步骤如下：
--------------------------------------------------------
其实，到现在为止，EM的思想什么的跟前面的高斯混合模型是一样的，前面写这么多，就是为了告诉你，为什么E步中，Q要是后验概率。
2.2 保证EM收敛。
我们只需要证明
就行了。
笔记上的推导式能够看明白的，这里，画个图，来加深理解。
如图，横坐标是θ，纵坐标是l(θ)的值：
最上面的曲线是p(x)的最大似然估计，整个算法就是在不停地逼近最大似然估计值，最终得到最大似然估计时的参数θ即为所求。
下面的曲线，就是在固定Qi以后，得到的下界函数，也是θ的函数。比如，最下面的曲线，就是在刚刚开始时，随机指定好类别以后（相当于固定了Q0）得到的第一个下界函数，θ0是在每个样例的Q0已知的情况下（有监督），通过极大似然得到的。
（一开始，就可以认为，极大似然函数l(θ)其实是Qi和θ两个参数的函数，而EM的过程，其实就是，固定一个，然后最大化l(θ)求得另一个参数，然后再固定求得的参数再去最大化另一个参数，类似于坐标上升法，不断地逼近最优值，学到最终的参数。）
现在开始EM算法，E步，根据上一步得到的θ0，用后验概率
求得每个类别的分布Qi，然后就是M步，固定Qi，最大化此时得到的下界函数。得到新的参数θ1。
对应到图上就是
- E步：
先根据刚刚开始得到的参数θ0，用后验概率（由前面证明可知此时会得到最好的下界）求得Q1。 - M步：
固定Q1，此时下界又公式（3）可以求得，即：图中的l0(θ)，最大化这个函数，得到新的估计的参数θ1。 - 不断循环上面两步，知道最终，下界函数的最大值逼近了或者等于原 极大似然函数的最大值，此时这个下界函数的估计的参数θi就是要求的值。
图中对应到EM算法中：
1、在E步中根据Q得到的下界，确实都是原极大似然函数的下界。
2、可以更加直观的理解公式4/5/6、图中的A点对应l1(θ1)，B点对应公式4中l0(θ1)，C点对应公式5/6中l0(θ0)。
3、另外，我们发现。图中的C点和A点是l0下界函数和l1下界函数的交点。这说明此时的l0函数是在固定了θ之后，能找到的最好的下界函数了此时的Q值就是Q0。
EM算法为什么有E，是因为利用了Jensen不等式，在每一步中，都得到了期望的下界。
关于重新审视混合高斯模型中的公式推导，可以看看讲义中的笔记，便于理解，这里不赘述了。
3、总结
有监督学习，只有一个变量，根据数据可以直接求出参数θ。
聚类问题，无监督学习，不知道类别标签，所以有两个变量，一个是参数θ，一个是类别标签z。
但是，可以参考前面所讲的坐标上升法，一次固定一个变量，最大化函数估计出另一个变量的，然后逐步逼近极值。
对应到EM算法中，就是E步估计隐含变量，M步估计其他参数，交替将极值推向最大。
EM中还有“硬”指定和“软”指定的概念，“软”指定看似更为合理，但计算量要大，“硬”指定在某些场合如K-means中更为实用（要是保持一个样本点到其他所有中心的概率，就会很麻烦）。
