《Pattern Recognition And Machine Learning》
Chapter 9 MIXTURE MODELS AND EM
引子
从寒假开始开始读Bishop这本书，读之前导师就告诉我这本书有难度，但认真去看会非常有收获。到现在为止看了大概有三个月了，这本书看过的部分也有三分之二了，突然感觉需要在读书过程中记录些东西。心得也好，自己的理解也好，哪怕是错的理解。一是因为因为读的过程中逐渐感觉书中讲的一些内容以现在的知识水平和见识还不能完全理解（连导师自己也说里面许多内容不懂= =），另外作者非常能扯，讲完一块内容总会顺带提及一些高级的内容，经常是一句话加一句引文的形式，真是无比蛋疼。导师还告诉我深究一些细枝末节暂时没什么用处，阅读时要把握每一章内容的主线内容，就像用一根线把本章贯穿起来，这样先有一个整体的把握是初学阶段比较好的方式。
这星期正要看完第九章，那就先从这章写起吧。以前的可能会陆续补上（估计要到暑假了。。。）。另外个人还想对机器学习中经常要用到的数学知识做一个梳理，因为感觉像矩阵求导、多维概率分布这些东西以前没有在课上学过，现在感觉半生不熟的，还是比较影响阅读的。
--------------------------------------------------------------------------------------------------------------分割线----------------------------------------------------------------------------------------------------------------
首先，这一章主要内容我认为是在EM算法的思想，作者主要用了Gaussian混合模型和Bernouli混合模型来对EM算法的引出和应用作了说明。当然，本章中的其他例子说明EM算法不只适用于混合模型，对于前面几章提到的Bayesian linear regression、RVM和著名的K-means算法其求解过程都可以用EM来加以解释和解决。下面先用Gaussian混合模型的例子来说明EM算法吧。
先看一看Gaussian混合模型的最基本形式：
其中x是数据点的向量表示，πk，μk，Σk都是参数。混合模型比仅适用一个Gaussian分布作为x的分布具有更强的表征能力，举个例子，如果已知数据的大体分布规律是双峰或者三峰的就能更好地拟合数据。这里引入了隐变量（latent variable）的概念，对于K个高斯分布的混合模型，用z1...zK分别代表K个隐变量，它们之中有且仅有一个为1，其余均为0，πk的意义如下：
zk = 1说明该数据点是由第k个Gaussian分布产生的，πk则是zk=1的概率。显然πk满足：
μk，Σk分别是第k个Gaussian分布的均值和协方差矩阵。
关于隐变量的含义，稍微说一下个人的看法（这个概念其实是在第八章概率图模型里最先正式介绍的）：对于客观世界中的物体，我们可以观察到一些对象（观测变量），而会有很多看不到的对象（隐变量）影响着它发生的概率。比如你看到一幅照片，而它其实是由被拍照的客观物体、拍照的方向与位置这些因素（隐变量）共同决定的。你把照片看成一个变量的话，那么它和上述的三个隐变量之间会满足某种概率关系。其实加入隐变量是为了通过增加变量数来提高模型的复杂程度，同时保证了模型中所有概率分布的简洁性。
好，那么由概率论的知识，下面几个式子是自然成立的：
（x,z）的联合分布就是上面两个式子的乘积。如果联合分布对z求和，就得到了关于x的边缘分布：
现在我们发现，这个式子就是x关于参数πk，μk，Σk的概率分布了，我们很自然地想到用最大似然发去估计这些参数，同样，将上式去对数得：
那么是不是对这个式子求偏导并让偏导等于0就好了？问题就在这里！因为ln是作用在一个求和符号上的，就变成了ln（a+b+c）这样的形式，不能直接把指数搬下来，于是这样偏导等于0的方程的解不是闭形解（closed-form solution），你无法直接得到最大似然下的参数。但是，我们还是要求偏导，看看有没有什么别的方法：
到这里我们发现一个很有趣的地方：
这一项不是zk在给定xn下的后验概率吗？好，那我们把它记做
其中
别忘了，
虽然(i)(ii)(iii)三个式子都不是闭形解，但我们发现，如果给μk、Σk和πk一些初始值，γ矩阵就可以被确定，那么Nk就可以确定，这样μk、Σk和πk都可以依次确定下来，然后再根据新的μk、Σk和πk计算出γ矩阵，从而进行下一轮的迭代。这其实是把未知变量分为两部分，每次先使其中一部分取得使目标函数最优化的值，在固定这部分变量最优化另一部分变量。这和svm中的SMO算法有类似之处。而上面所述的就是EM算法的核心步骤：
1、给定μk、Σk和πk的初始值
2、在当前μk、Σk和πk值的基础上用(0)式求出γ矩阵（即隐变量z的每个分量关于每个x的后验概率）（E-step）
3、利用2中求出的γ矩阵和(i)(ii)(iii)式求出μk、Σk和πk的最大似然解并覆盖原来的值.（M-step）
4、如果没有满足收敛条件，继续进行2
上面只是由一个例子介绍了EM算法的主要面貌，下面我们用更加理性的眼光来看一看EM算法：