EM算法

EM算法EM算法--应用到三个模型：高斯混合模型，混合朴素贝叶斯模型，因子分析模型判别模型求的是条件概率p(y|x)，生成模型求的是联合概率p(x,y).即=p(x|y)?p(y)常见的判别模型有线性回归、对数回归、线性判别分析、支持向量机、boosting、条件随机场、神经网络等。常见的生产模型有隐马尔科夫模型、朴素贝叶斯模型、高斯混合模型、LDA、RestrictedBoltzmannMachine等。所以这里说的高斯混合模型，朴素贝叶斯模型都是求p(x,y)联合概率的。(下面推导会见原因)套路小结：凡是生产模型，目的都是求出联合概率表达式，然后对联合概率表达式里的各个参数再进行估计，求出其表达式。下面的EM算法，GMM等三个模型都是做这同一件事：设法求出联合概率，然后对出现的参数进行估计。一、EM算法：作用是进行参数估计。应用：（因为是无监督，所以一般应用在聚类上，也用在HMM参数估计上）所以凡是有EM算法的，一定是无监督学习.因为EM是对参数聚集给定训练样本是高斯混合模型，混合朴素贝叶斯模型，因子分析模型样例独立，我们想要知道每个样例隐含的类别z，使是p(x,z)最大，（即如果将样本x(i)看作观察值，潜在类别z看作是隐藏变量，则x可能是类别z，那么聚类问题也就是参数估计问题，）故p(x,z)最大似然估计是：高斯混合模型，混合朴素贝叶斯模型，因子分析模型所以可见用到EM算法的模型（高斯混合模型，朴素贝叶斯模型）都是求p(x,y)联合概率，为生成模型。对上面公式，直接求θ一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化?(θ)，我们可建立?的下界（E步），再优化下界（M步），见下图第三步，取的就是下界高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19180744-0ed1369378104b548dbee01337f6ba69.jpgaction-type=show-slide（总式）解释上式：对于每一个样例i，让Qi表示该样例隐含变量z的某种分布，Qi满足的条件是（如果z是连续性的，那么Qi是概率密度函数（因子分析模型就是如此），需要将求和符号换成积分符号即：高斯混合模型，混合朴素贝叶斯模型，因子分析模型因子分析模型是如此，这个会用在EM算法的M步求。比如要将班上学生聚类，假设隐藏变量z是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布（即两点分布：高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19213448-daeed49b6205467eb5b39a0d6936f583.jpgaction-type=show-slide）了。上总式第1到第2步是分子分母同乘一个数，第2到3步是：用了jasen不等式：高斯混合模型，混合朴素贝叶斯模型，因子分析模型（凸函数图形上表示反为凹函数，记住。）如图：高斯混合模型，混合朴素贝叶斯模型，因子分析模型。因为第2步log是凹函数：高斯混合模型，混合朴素贝叶斯模型，因子分析模型，所以f(E(x))>=E[f(x)].这样就完成了第3步（详情见对应讲义。）至此推导完上面3步公式，下面所有模型都是对上面第3步公式进行参数估计的！！！下面对第三步的Q(z)进行推导：高斯混合模型，混合朴素贝叶斯模型，因子分析模型（见讲义）所以Q(Z)最终表示：高斯混合模型，混合朴素贝叶斯模型，因子分析模型，其中z只受参数θ影响。所以EM算法：高斯混合模型，混合朴素贝叶斯模型，因子分析模型（承上启下：在m步中，最终是对参数θ进行估计，而这一步具体到高斯混合模型，则θ有三个参数：mu,phi,sigma代替，即高斯混合模型要推导三个参数，下面会讲）至此，这就是EM算法所有推导，EM算法推导也只能推导这些步，具体再将这些公式推导下去，就要结合模型了。总结：如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题，只不过聚类问题中参数分为隐含类别变量和其他参数。对应到EM上，E步估计隐含变量，M步估计其他参数，交替将极值推向最大。例子：在Mitchell的MachineLearning书中也举了一个EM应用的例子，将班上学生的身高都放在一起，要求聚成两个类。这些身高可以看作是男生身高的高斯分布和女生身高的高斯分布组成。因此变成了如何估计每个样例是男生还是女生，然后在确定男女生情况下，如何估计均值和方差，里面也给出了公式。二、混合高斯模型：将EM算法融到高斯混合模型，将上面EM算法的E步、M步的公式再具体推导下去。整个模型简单描述为：对于每个样例高斯混合模型，混合朴素贝叶斯模型，因子分析模型，我们先从k个类别中按多项式分布抽取一个高斯混合模型，混合朴素贝叶斯模型，因子分析模型，然后根据高斯混合模型，混合朴素贝叶斯模型，因子分析模型所对应的k个多值高斯分布中的一个，生成样例高斯混合模型，混合朴素贝叶斯模型，因子分析模型，整个过程称作混合高斯模型。（即对样例x，最终目的是生成样例x。（？？）即对样例x，从k个类别抽取一个z,从根据z生成x。）特别地，混合高斯模型的（1）隐含类别标签高斯混合模型，混合朴素贝叶斯模型，因子分析模型，被认为满足多项式分布，即高斯混合模型，混合朴素贝叶斯模型，因子分析模型(这里高斯混合模型，混合朴素贝叶斯模型，因子分析模型只受?参数（即phi）影响)（2）样例高斯混合模型，混合朴素贝叶斯模型，因子分析模型被认为满足高斯分布，即高斯混合模型，混合朴素贝叶斯模型，因子分析模型高斯混合模型，混合朴素贝叶斯模型，因子分析模型(所以μ和Σ分别为样例x的均值和协方差)补充：高斯混合模型，混合朴素贝叶斯模型，因子分析模型服从的多项式分布概率公式为：高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19203710-402647dc579f4e68baa7db5716993b17.jpgaction-type=show-slide，即类似C(n,x)*p6^x*(1-p6)^(n-x)类型所以上面（1）（2）可知混合高斯模型中，这里的高斯混合模型，混合朴素贝叶斯模型，因子分析模型仍是隐含随机变量。模型细化多了三个变量?，μ和Σ。(即是phi,mu,sigma).其中?j就是样本类别中高斯混合模型，混合朴素贝叶斯模型，因子分析模型=j的比率。μj是类别为j的样本特征均值，Σj是类别为j的样例的特征的协方差矩阵(Σj是一个矩阵！！)。所以由上面（1）（2）合并得，最大似然估计p(x,z)，对数化后如下：高斯混合模型，混合朴素贝叶斯模型，因子分析模型高斯混合模型，混合朴素贝叶斯模型，因子分析模型（对比一、EM算法里的总式：高斯混合模型，混合朴素贝叶斯模型，因子分析模型，只是参数θ由原化成三个?，μ和Σ）注意第二步有两个迭加号。第二个迭加号是z(i)=1直到k个类别。z只有k个类别。参考一、中EM算法推导：高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19180744-0ed1369378104b548dbee01337f6ba69.jpgaction-type=show-slide所以混合高斯模型：从EM算法步骤的高斯混合模型，混合朴素贝叶斯模型，因子分析模型变成：高斯混合模型，混合朴素贝叶斯模型，因子分析模型（其中M步三个参数的右边公式在下面会进行推导。这里直接先给出参数结果。）1.E步：每个样例i的隐含类别z(i)为j的概率可以通过条件概率计算得到。即高斯混合模型，混合朴素贝叶斯模型，因子分析模型高斯混合模型，混合朴素贝叶斯模型，因子分析模型（E）（这里贝叶斯公式，分子是z=j一种类别情况，分母是z={1~k}k中类别的累加）1）对上式的分子第一项：高斯混合模型，混合朴素贝叶斯模型，因子分析模型（由上面加黄色背景段文字可知）服从高斯分布：高斯混合模型，混合朴素贝叶斯模型，因子分析模型高斯混合模型，混合朴素贝叶斯模型，因子分析模型，故高斯混合模型，混合朴素贝叶斯模型，因子分析模型=高斯混合模型，混合朴素贝叶斯模型，因子分析模型。（其中Σ即是高斯混合模型，混合朴素贝叶斯模型，因子分析模型）2）对(E)式分子第二项高斯混合模型，混合朴素贝叶斯模型，因子分析模型（又上面可知）服从多项式分布：高斯混合模型，混合朴素贝叶斯模型，因子分析模型所以分子直接代入即可，所以高斯混合模型，混合朴素贝叶斯模型，因子分析模型可以求得。2.M步：先给出最终结果为:高斯混合模型，混合朴素贝叶斯模型，因子分析模型,推导如下：先看EM算法的M步：高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19182954-8ac531223dd84249b96e3068f75f76af.jpgaction-type=show-slide高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19212818-897c51d8baaa426da5f8eed96e7404f8.jpgaction-type=show-slide（M）下面对三个参数phi,mu,sigma(?，μ和Σ)分别进行求导:（i）对μi求导得(固定i，Σi):高斯混合模型，混合朴素贝叶斯模型，因子分析模型<--它是由高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19214342-701de6e9d3ae4919afb9ef6b7ea0e2dc.jpgaction-type=show-slide（据Ng说求的过程不重要？）等于0时所得（ii）对i求导(固定μi，Σi）：高斯混合模型，混合朴素贝叶斯模型，因子分析模型推导过程用了SVM中的拉格朗日乘子方法：因为?i是隐性随机变量z的多项式分布概率值，又有约束条件高斯混合模型，混合朴素贝叶斯模型，因子分析模型又由上面（M）步公式：高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19215249-d9a21ead11ed438ebc9e4a33f37f04db.jpgaction-type=show-slide（why?????）所以联合上两式，直接构成拉格朗日乘子：高斯混合模型，混合朴素贝叶斯模型，因子分析模型action-data=http%3A%2F%2Fimages.cnitblog.com%2Fblog%2F515474%2F201305%2F19215659-0adc330526af497cb9af214ab1faccc0.jpgaction-type=show-slide高斯混合模型，混合朴素贝叶斯模型，因子分析模型，高斯混合模型，混合朴素贝叶斯模型，因子分析模型