EM算法

EM算法原理与应用1.EM算法原理从最大似然到EM算法【例1】假设我们需要调查我们学校的男生和女生的身高分布。（抽样）假设你在校园里随便地活捉了100个男生和100个女生。他们共200个人（也就是200个身高的样本数据）都在教室里面了。那下一步怎么办啊？你开始喊：“男的左边，女的右边！”。然后你就先统计抽样得到的100个男生的身高。假设他们的身高是服从高斯分布的。但是这个分布的均值μ和方差σ2我们不知道，这两个参数就是我们要估计的。记作θ=[μ,σ2]T数学语言：在学校那么多男生（身高）中，我们独立地按照概率密度p(x|θ)抽取100个（身高），组成样本集X，我们想通过样本集X来估计出未知参数θ。这里概率密度p(x|θ)我们知道了是高斯分布N(μ,σ2)的形式，其中的未知参数是θ=[μ,σ2]T。抽到的样本集是X={x1,x2,…,xN}，其中xi表示抽到的第i个人的身高，这里N就是100，表示抽到的样本个数。由于每个样本都是独立地从p(x|θ)中抽取的，抽到男生A（的身高）的概率是p(xA|θ)，抽到男生B的概率是p(xB|θ)，那因为他们是独立的，所以很明显，我同时抽到男生A和男生B的概率是p(xA|θ)*p(xB|θ)，同理，我同时抽到这100个男生的概率就是他们各自概率的乘积了。数学语言：从分布是p(x|θ)的总体样本中抽取到这100个样本的概率，也就是样本集X中各个样本的联合概率，用下式表示：从最大似然到EM算法,);();,...,,()(121niinxpxxxLL这个概率反映了，在概率密度函数的参数是θ时，得到X这组样本的概率。因为这里X是已知的，也就是说我抽取到的这100个人的身高可以测出来，也就是已知的了。而θ是未知了，则上面这个公式只有θ是未知数，所以它是θ的函数。这个函数放映的是在不同的参数θ取值下，取得当前这个样本集的可能性，因此称为参数θ相对于样本集X的似然函数（likehoodfunction）。记为L(θ)。【例1】假设我们需要调查我们学校的男生和女生的身高分布。（抽样）假设你在校园里随便地活捉了100个男生和100个女生。他们共200个人（也就是200个身高的样本数据）都在教室里面了。那下一步怎么办啊？你开始喊：“男的左边，女的右边！”。然后你就先统计抽样得到的100个男生的身高。假设他们的身高是服从高斯分布的。但是这个分布的均值μ和方差σ2我们不知道，这两个参数就是我们要估计的。记作θ=[μ,σ2]T从最大似然到EM算法某些男生和女生一见钟情，无法硬把他们拉扯开。那现在这200个人已经混到一起了，随便指出一个人（的身高），无法确定这个人（的身高）是男生（的身高）还是女生（的身高）。也就是说不知道抽取的那200个人里面的每一个人到底是从男生的那个身高分布里面抽取的，还是女生的那个身高分布抽取的。用数学的语言就是，抽取得到的每个样本都不知道是从哪个分布抽取的。两个问题需要估计：一是这个人是男的还是女的？二是男生和女生对应的身高的高斯分布的参数是多少？先有鸡or先有蛋从最大似然到EM算法为了解决这个你依赖我，我依赖你的循环依赖问题，总得有一方要先打破僵局:先随便整一个A值出来，看另一方B如何变化，然后再根据B变化调整A变化，然后如此迭代着不断互相推导，最终就会收敛到一个解。这就是EM算法的基本思想。假设我们想估计知道A和B两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，持续迭代直到收敛为止。迭代的结果真的有效吗？121()(,,...,;)(;),nniiLLxxxpx似然函数：,);(ln)(lniixpL从最大似然到EM算法EM算法推导iziiizxpxp);,();(,);,()(1niziiEMizxpLiziiEMizxpL);,(ln)(lniziiiiizQzxpzQ)();,()(ln因不知样本性别，设为iziziiiiizQzxpzQ)();,(ln)(iziiEMizxpL);,(ln)(lniziiiiizQzxpzQ)();,()(lniziiiiizQzxpzQ)();,(ln)(从最大似然到EM算法EM算法推导Jensen不等式][)();,(xEzQzxpiii的期望)][ln()();,(lnxEzQzxpiii的期望]ln[)][ln(lnEXxEx凹函数][)]([EXfxfE凸函数aEXbf(a)E[f(X)]f(b)f(EX)][)]([EXfxfE凹函数aEXbf(EX)f(b)E[f(X)]f(a)iziiEMizxpL);,(ln)(lniziiiiizQzxpzQ)();,()(lniziiiiizQzxpzQ)();,(ln)(从最大似然到EM算法EM算法推导t1t2t从最大似然到EM算法EM算法推导)(izQ2、EM算法的应用在高斯混合模型中的应用在图像分割中的应用在医学研究中的应用在高斯混合模型中的应用高斯混合模型参数估计的EM算法（以高维数据为例）：step1、参数赋初始值，开始迭代step2、E步，计算混合项系数𝑍𝑖𝑗的期望E[𝑍𝑖𝑗]：step3、M步，计算新一轮迭代的参数模型：step4、重复第2、3步，直到收敛。1()()1()()1()()1/221()()1/221[]iTijjjiTikkkxxjijKxxkkeEZe()11[][]NiijijNijiEZxEZ()()11[]{()()}[]NiTiijjjijNijiEZxxEZ1[]NijijEZwN在高斯混合模型中的应用Python实例：程序随机从4个高斯模型中生成500个2维数据，真实参数：混合项w=[0.1，0.2，0.3，0.4]，均值u={[5，35]，[30，40]，[20，20]，[45，15]}，协方差矩阵∑={[30，0]，[0，30]}，然后以这些数据作为观测数据，根据EM算法来估计以上参数（未估计协方差矩阵）在高斯混合模型中的应用（左上）生成的观测数据，（右上）分类后的结果，（下）高斯混合模型的三维可视化图结果如下：混合项系数估计为[0.08790,0.18614,0.25716,0.46878]均值估计为{[3.748334.9302][29.912739.8799][19.975420.2637][45.207315.4781]}在高斯混合模型中的应用在图像分割（无监督聚类）中的应用实现方法：在聚类时，设置聚类数，则每一类数据认为是服从一个高斯分布，我们通过EM算法来估计各个类中的高斯参数。关于灰度图像，在聚类里面其实就是一个一维特征的样本，每个像素点视为一个样本点，值的大小视为其具有的特征，聚类后再把它转化为一个图像显示出来。在图像分割中的应用迭代次数=50在图像分割中的应用均值随迭代次数变化图方差随迭代次数变化图在图像分割中的应用随机产生聚类中心，开始EM算法，直至EM算法收敛右图分别是分类数为2,3,4的图像分割结果但算法的效果很大程度上依赖于初始聚类中心的选择EM算法是求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行估计，是一种非常简单实用的学习算法。这种方法可以广泛地应用于处理缺损数据、截尾数据以及带有噪声等所谓的不完全数据，可以具体来说，我们可以利用EM算法来填充样本中的缺失数据、发现隐藏变量的值、估计HMM中的参数、估计有限混合分布中的参数以及可以进行无监督聚类等等。在医学研究中的应用在医学研究中的应用例：有8名受试者用庆大霉素80mg后的血药浓度动态变化观察结果如表1所示,其中有2处数据存在缺失:第4例120min时观察缺失和第8例50min时观察缺失。假设每组数据均服从p维正态分布总体，但均值和方差均未知，则缺失的估计需要进行迭代计算。2(,)pNNunknownunknown在此处键入公式。在医学研究中的应用1)均值和方差的初始估计值和：根据未缺失的数据计算算术平均数作为均值的初始值,用算术均数代替缺失值后,可求方差的极大似然估计初始值。2)计算对于具有缺失值的每一个向量的条件数学期望,令表示缺失的分量,表示已知的分量,如果对和进行相应的分块变化,则的条件正态分布的均值为和的条件正态分布的均值分别为将具有缺失分量的结果与样本实际观察数据的计算结果结合起来,就可得到充分的估计值。ˆ2ˆˆ2ˆˆ(1)kY(2)kY2ˆ(1)kY(1)(1)(2)(1)1(2)(2)1222ˆˆˆˆˆˆˆ(,,)()kkkkYEYYY(1)(1)kkcYY(1)(2)kkcYY(1)(1)(1)(1)(2)1(1)(1)11122221ˆˆˆˆˆˆ(;,)kkkkckckkcYYEYYYYY(1)(2)(1)(2)(2)(1)(2)ˆˆ(;,)kkkkckckkcYYEYYYYYkY在医学研究中的应用3)计算均值和方差的最大似然估计校正值和：4)重复以上的2-3步,直至和收敛为止。经过EM迭代算法可得:迭代算法补入的两个数据:第4行第5个为2.5216,第8行第3个为4.5522。ˆ2ˆˆ2ˆ在医学研究中的应用5)MonteCarlo模拟,随机取,样本容量n=4,其中=[1234]去掉其中第2行第3列和第3行第2列的两个数(1)如果删去,不考虑这部分数据蕴含的信息,得到=[0.78941.22842.24663.6630]0.25000.30000.35000.40000.30000.36000.42000.4800ˆ0.35000.42000.49000.56000.40000.48000.56000.64004(,)xNˆ1ˆ10.14690.34440.49090.23500.03440.67860.15270.05510.49090.15271.71730.78540.23500.05510.78540.3760(2)如果用EM算法计算,得到=[0.78941.51582.92363.6630]通过计算比较可得:我们发现通过EM算法计算得到的结果比直接删除得到的结果更接近精确值。2ˆ在医学研究中的应用20.14690.10310.06970.23500.10310.08870.03180.16490.06970.03180.05120.11150.23500.16490.11150.37601ˆ()1.1493norm2ˆ()0.6311norm2ˆ()1.2333norm对EM算法应用的总结1.EM算法是一种迭代算法，主要用于计算后验分布的众数或极大似然估计，广泛地应用于缺损数据、截尾数据、成群数据、带有讨厌参数的数据等所谓不完全数据的统计推断问题。2.EM算法是一种非监督的学习算法，它的输入数据事先不需要进行标注。相反，该算法从给定的样本集中，能计算出高斯混和参数的最大似然估计。也能得到每个样本对应的标注值，类似于kmeans聚类（输入样本数据，输出样本数据的标注）。3.优点：EM算法简单且稳定，迭代能保证观察数据对数后验似然是单调不减的。缺点：对于大规模数据和多维高斯分布，其总的迭代过程，计算量大，迭代速度易受影响；EM算法的收敛速度，非常依赖初始值的设置，设置不当，计算时的代价是相当大的；EM算法中的M-Step依然是采用求导函数的方法,所以它找到的是极值点,即局部最优解,而不一定是全局最优解。谢谢