首页 > 搜索 > em算法能解决什么问题,笔记(总结)

em算法能解决什么问题,笔记(总结)

互联网 2020-10-26 01:28:16
在线算命,八字测算命理

对Gaussian Mixture Model和Expectation Maximization算法一直以来了解不多,一来直接使用这两个方法的场景少,二来初看这两个算法确实有些一头雾水,不太理解为什么要这么做。上学期的课又涉及到了这部分,还是咬牙把这块给啃了下来,结合“周志华西瓜书”,在聚类场景下对这两部分做下总结。

高斯混合(Mixture of Gaussian)

nn维随机变量xx服从多元高斯分布,则概率密度函数为:

p(x)=1(2π)n2|Σ|12exp[−12(x−μ)TΣ−1(x−μ)]p(x)=1(2π)n2|Σ|12exp[−12(x−μ)TΣ−1(x−μ)]

其中μμ为均值向量,ΣΣ为协方差矩阵,给定这两个参数,则可以确定高斯分布,记为p(x|μ,Σ)p(x|μ,Σ)。当维度退化为一维、二维空间时,高斯分布图像如下: 这里写图片描述

在此基础上,我们可以定义高斯混合分布如下:

pM(x)=∑ki=1αi⋅p(x|μi,Σi)pM(x)=∑i=1kαi⋅p(x|μi,Σi)

该分布由kk个高斯分布混合而成,αiαi为混合系数,表示每个高斯分布的占比,∑iαi=1∑iαi=1。

为什么要使用高斯混合模型做聚类?考虑如下两个图: 这里写图片描述 这里写图片描述 对于上述点集可以清楚看到,用一个高斯分布来拟合(图一)和用两个单独的高斯分布(图二)来拟合的效果差距是很大的。如果我们想用一个模型来达到图二的效果,最好的办法是将两个高斯分布进行线性组合。可以想见,当点集十分复杂时,增大参与线性混合的高斯分布数量越多,拟合能力就越强大,即

高斯分布在混合分量足够多的情况能逼近任意分布(可比对神经网络模型,在神经元、层数够多时能拟合任何函数)

那为什么要使用高斯分布呢?因为高斯分布是现实生活中最常见的分布,而且数学性质良好(密度函数处处可导)。实际上,把混合成分换成其他分布也是可以的,比如伯努利分布,卡方分布等,这才是高斯混合分布的精髓思想,即:

高斯混合分布,重要的不是“高斯”,而是“混合”。思想本质是用多个简单分布的组合去拟合更复杂的分布。

GMM用于聚类

假设现在样本是由未知的高斯混合模型生成,我们现在要根据所有样本来确定GMM的参数(αi,μi,Σi,i=1,2,...,kαi,μi,Σi,i=1,2,...,k),从而确定每个样本是由哪个高斯分布产生。自然的,每个高斯分布对应聚类中的一类。定义高斯混合分布如下:

pM(x)=∑ki=1αi⋅p(x|μi,Σi)pM(x)=∑i=1kαi⋅p(x|μi,Σi)

给定样本集D={x1,x2,...,xm}D={x1,x2,...,xm},采用极大似然对参数进行估计,即最大化似然函数:

L=ln(∏mj=1pM(xj))=∑mj=1ln(∑ki=1αi⋅p(xj|μi,Σi))L=ln(∏j=1mpM(xj))=∑j=1mln(∑i=1kαi⋅p(xj|μi,Σi))

由于对数中含有求和式,难以直接求导。故常用EM算法进行求解。

EM算法

假设我们不考虑样本应来自于哪个高斯分布。此时我们使用极大似然法可以直接求解:

L=ln(∏mj=1p(xj)),x∼N(μ,Σ)L=ln(∏j=1mp(xj)),x∼N(μ,Σ)

而当我们需要考虑上述问题时,来自哪个高斯分布相当于“隐变量”。当我们确定了各个高斯分布的参数后,才能求解隐变量,不能直接对上式求导了。

我们采用EM算法进行求解。EM算法是一个迭代算法,概括起来其实就两步:

E step:固定参数,求解隐变量M step:固定隐变量,求参数

反复迭代直到收敛。下面具体应用到我们的问题中。

EM算法解GMME step

现有样本集D={x1,x2,...,xm}D={x1,x2,...,xm}。令随机变量zj∈{1,2,...,k}zj∈{1,2,...,k}表示样本xjxj属于的高斯分布,即为之前提到的隐变量。由于假设了样本是由GMM生成,先验概率下P(zj=i)=αi(i=1,2,...,k)P(zj=i)=αi(i=1,2,...,k),由贝叶斯,xjxj来自第ii个高斯分布的后验概率为:

pM(zj=i|xj)=P(zj=i)⋅pM(xj|zj=i)PM(xj)=P(zj=i)⋅pM(xj|zj=i)∑klP(zj=l)⋅pM(xj|zj=l)=αi⋅p(xj|μi,Σi)∑klαl⋅p(xj|μl,Σl),记为γjipM(zj=i|xj)=P(zj=i)⋅pM(xj|zj=i)PM(xj)=P(zj=i)⋅pM(xj|zj=i)∑lkP(zj=l)⋅pM(xj|zj=l)=αi⋅p(xj|μi,Σi)∑lkαl⋅p(xj|μl,Σl),记为γji

可以看到,利用模型参数求解出了隐变量。

M step

对于αiαi的选择要满足:

argmaxαiL=ln(∏j=1mpM(xj))=∑j=1mln(∑i=1kαi⋅p(xj|μi,Σi))s.t.∑i=1kαi=1arg⁡maxαiL=ln(∏j=1mpM(xj))=∑j=1mln(∑i=1kαi⋅p(xj|μi,Σi))s.t.∑i=1kαi=1

利用拉格朗日进行求解:

Lagrange=L+λ(∑ki=1αi−1)Lagrange=L+λ(∑i=1kαi−1)

令:

∂Lagrange∂αi=0∂Lagrange∂αi=0

将所得结果化简,有:

αi=1m∑mj=1γjiαi=1m∑j=1mγji

求解使似然函数最大的μ,Σμ,Σ,令:

∂L∂μi=0, ∂L∂Σi=0∂L∂μi=0, ∂L∂Σi=0

将所得结果化简,有:

μi=∑mj=1γjixj∑mj=1γji,   Σi=∑mj=1γji(xj−μi)(xj−μi)T∑mj=1γjiμi=∑j=1mγjixj∑j=1mγji,   Σi=∑j=1mγji(xj−μi)(xj−μi)T∑j=1mγji

隐变量取值固定,模型参数αi,μi,Σiαi,μi,Σi由隐变量确定。

确定聚类标签

迭代进行E step、M step直到收敛。对于每个样本,将其归类为最高后验概率对应的高斯分布,完成聚类,每个样本的聚类标签为:

λj=argmaxi∈{1,2,...,k}γjiλj=arg⁡maxi∈{1,2,...,k}⁡γji

一些问题EM算法一定收敛吗?结论是一定收敛,但由于LL函数不一定是严格凸函数,不能保证收敛到全局最优。E step和M step的结果是相互确定的,有点像“鸡生蛋、蛋生鸡”。算法初始时会对模型参数初始化,然后E-M-E…进行迭代,直至收敛。结合上一条,不同初始化可能收敛到不同的结果。GMM和K-means

当引入一些额外条件,GMM就退化成了K-means:

各高斯分布混合系数αiαi相同每个样本以概率1属于一个类协方差矩阵ΣΣ为单位阵

此时该GMM的参数只有μμ,用EM算法求解该特殊情况下的GMM如下(也可以说从EM的角度来看待K-means算法):

E step:

γji={1, if xj is nearest to μi0, otherwiseγji={1, if xj is nearest to μi0, otherwise

M step:

μi=1|Ci|∑x∈Cix,  Ciμi=1|Ci|∑x∈Cix,  Ci为属于第ii类高斯分布的样本集合

反复迭代执行E、M步骤,直至收敛。如此便得到了K-means算法。算法最初也会对参数进行随机初始化(选择kk个样本作为初始均值向量),不同的初始化方法会得到不同的聚类结果,这和GMM的EM算法是一样的。

本文首先介绍了什么是高斯混合,然后介绍了GMM来解决聚类问题的背景,利用EM算法求解GMM模型参数来解决聚类问题,最后介绍了EM观点下GMM和K-means的关联。列出参考链接如下:

高斯混合模型(GMM)的两种详解及简化 《机器学习实战》学习总结(十四)——EM算法 高斯混合模型(GMM)及其EM算法的理解 周志华西瓜书

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多