机器学习笔记(十)EM算法及实践(以混合高斯模型(GMM)为例来次完整的EM)

今天要来讨论的是EM算法。第一眼看到EM我就想到了我大枫哥,EM Master,千里马,RUA!!!不知道看这个博客的人有没有懂这个梗的。好的,言归正传,今天要讲的EM算法,全称是Expectation maximization,期望最大化。怎么个意思呢,就是给你一堆观测样本,让你给出这个模型的参数估计。我靠,这套路我们前面讨论各种回归的时候不是已经用烂了吗?求期望,求对数期望,求导为0,得到参数估计值,这套路我懂啊,MLE!但问题在于,如果这个问题存在中间的隐变量呢?会不会把我们的套路给带崩呢,我们通过两个例子来认识一下这两种情况。

====================================================================

不存在中间变量的EM。

假设有一天人类消除了性别的差别,所有的人都是同一个性别。这个时候,我给了你一群人的身高让你给我做一个估计人身高的模型。

怎么办呢?感觉上身高应该是服从高斯分布吧,所以假设人的身高分布服从高斯分布N(Mu,Sigma^2),现在我又有了N个人的身高的数据,我就可以照着上面的套路进行了。先求对数似然函数

接着对两个参数求偏导为0

这样就得到了我们的参数估计

喜闻乐见的结果,又好求又符合我们的直觉,那我们再来看看另一种情况。

====================================================================

存在中间变量的EM。

正如你所知,身高和人种的关系挺大的,而人类又有那么多种族,所以,再给你一堆人的数据,要做一个估计人身高的模型,那我们应该怎么做呢?

首先,现在分为不同种族若干类了,这些类别的概率肯定有个分布,其次,各种族当中身高是服从不同的分布的,那么这样身高的估计就变成了

Alpha代表了该样本属于某一人种的比例,其实就是隐藏的中间变量。Muk和sigmak^2为各类高斯分布的参数。按照我们上面的套路就是求对数似然概率再求导得到参数的估计,那么先来看看似然函数

这下尴尬的情况出现了,对数里面带加号,这下求导就变得复杂异常了,而且没法求解,事实上,这种式子确实没有解析解。不过憋灰心啊,假设我们随便猜一个alpha的分布为Q,那么对数似然函数可以写成

由于Q是alpha的一个分布,所以似然函数可以看成是一个log(E(x)),log是个凹函数啊,割线始终在函数图像下方,Jensen不等式反向应用一下,有log(E(x))>=E(log(x)),所以上面的对数似然有

冷静分析一下现在的情况,我们现在得到了一个对数似然函数的下界函数,我们采用曲线救国的战略,我们求解它的局部最大值,那么更新后的参数带入这个下界函数一定比之前的参数值大,而它本身又是对数似然函数的下界函数,所以参数更新后,我们的对数似然函数一定是变大了!所以,就利用这种方法进行迭代,最后就能得到比较好的参数估计。还有点晕吗,没事,我从百度扒个图给你来个形象的解释

红色那条线就是我们的对数似然函数,蓝色那条是我们在当前参数下找到的对数似然的下界函数,可以看到,我们找到它的局部极值那么参数更新成thetanew,此时对数似然函数的值也得到了上升,这样重复进行下去,是不是就可以收敛到对数似然函数的一个局部极值了嘛。对的,局部极值,并不能保证是全局最优,但它就是个估计嘛,你还要她怎样?!

到了这里,我们好像跳着先把第二步参数更新的工作做完了,那么还有一个事情是我们要注意的,Q呢,Q是啥,没Q你算啥极值,更新啥参数。我们已经知道Q是alpha的一个分布,然后我们肯定是希望这个下界函数尽量贴近原来的对数似然函数,这样我们才能更快地更新参数,那下界函数啥时最大呢,等号成立呗,等号成立说明你求期望的对象是个常数呀,所以log和Q谁在前后都无所谓,那么就有了

直观地可以理解成第i个样本来自第k个类别的可能性。好了,现在Q也确定了,我们根据上面所说的方法更新参数,再更新Q,再更新参数,迭代进行下去就可以了。

如果你能坚持看到这里,少侠我只能说你大功已成。因为其实我们已经把EM算法整个推导完了,也许你还是有点云里雾里,那我们再来仔细梳理一下这个流程

1 拿到所有的观测样本,根据先验或者喜好先给一个参数估计。

2 根据这个参数估计和样本计算类别分布Q,得到最贴近对数似然函数的下界函数。

3 对下界函数求极值,更新参数分布。

4 迭代计算,直至收敛。

说起来啊,EM算法据说是机器学习进阶的一个算法,但至少目前来看,它的思路还是很容易理解的嘛,整个过程中唯一一个可能初学者觉得有点绕的地方就是应用Jensen不等式的那一步,那我再啰嗦两句。所谓Jensen不等式,你可以这么理解,对于一个凸函数f而言,它的割线始终在函数图像上方你承认吧,我在上面任取两点x1,x2,参数theta介于0到1之间,那么theta*x1+(1-theta)*x2就是介于x1和x2之间的一点吧,在这点上过x1x2割线的值大于函数值吧,是不是就有了theta*f(x1)+(1-theta)*f(x2)>f(theta*x1+(1-theta)*x2),根据这个结论再推广开来,就有E(f(x))>f(E(x)),在对数似然函数中,由于log是个凹函数,所以把它反过来用,老铁没毛病吧?!这一点想通了我觉得整个EM算法的流程还是蛮好懂的。

下面呢,我们还回到这个身高模型的预测,假设给了m个样本,有k个种族,每个种族的身高都是服从高斯分布的,那么这就变成了EM算法中最具代表性的一个例子,高斯混合模型GMM。

====================================================================高斯混合模型(GMM)

刚才已经讲了EM算法的套路了,假设我们现在处于某一步迭代中,那么我们该干嘛呢?

E-step 求最佳的类别分布

可以将其理解为第i个样本属于第J类的概率。

M-step 更新参数

求得了Q之后,我们就得到了最贴近原对数似然函数的下界函数,那我们对它求极值就可以得到更新后的参数,先看一下这个下界函数

Log函数里面全是乘积项这是我们最喜欢的形式,这样求导的时候但凡不相关的我们直接扔掉就行,待求参数mu,sigma^2,psi,依次求导为0就成。

对于psi的求解可能复杂一些,首先我们把下界函数中与psi不相关的项全部去掉,然后psi作为各类别的比例有一个天然的约束条件就是所有的psi之和为1,所以目标函数变成

这种带约束的优化前面在SVM的时候不知道用了多少回,拉格朗日乘子法

接下来对psi求导

两边同时再对j从1到k连加,psi那一项就没了,右式就变成样本数目m,这样就求得了beta,回代我们就可以求得psi参数的更新

至此,所有的参数更新工作就已完成,下面重复进行迭代就行了。

我们先把GMM的算法梳理一下

1 给参数取初始值,开始迭代。

2 求每个样本对每个类别的概率,科学的叫法叫求响应度

3 更新模型参数

4 重复23两步直至收敛。

我们再来看看这些参数的意义,其实未尝不符合我们的直觉认识。W(i,j)可以看做第i个样本属于第j类的概率,那么所有样本中属于第j类的个数就是w(i,j)之和,每个样本xi对应第j类的值就是W(i,j) xi,这样算的平均数就是第j类对应的mu,继续按照这个思路算的方差就是第j类的sigma^2,第j类的概率就是第j类的个数除以总样本数。所以,GMM模型虽然推导起来有点吓人,但仔细想想它最后的结果也是符合我们的直觉认识的,每个样本都是一部分属于某一类,所有样本中的某一类的部分构成了这一类的分布,perfect!!!

====================================================================

这样的话,理论部分我们就讲完了,接下来又是调包侠的时刻了,上次写完后我想到鸢尾花数据无监督算法也能做啊,不给标签我们强行给它分类看看效果如何。所以这里我们K-Means和GMM算法分别对鸢尾花进行处理,看看它们的聚类效果如何。

代码如下

import numpy as np
from sklearn import datasets
from sklearn.cluster import KMeans
from sklearn.mixture import GaussianMixture
#读取数据
iris=datasets.load_iris()
x=iris.data[:,:2]
y=iris.target
mu = np.array([np.mean(x[y == i], axis=0) for i in range(3)])
print ‘实际均值 = \n‘, mu
#K-Means
kmeans=KMeans(n_clusters=3,init=‘k-means++‘,random_state=0)
y_hat1=kmeans.fit_predict(x)
mu1=np.array([np.mean(x[y_hat1 == i], axis=0) for i in range(3)])
print ‘K-Means均值 = \n‘, mu1
print ‘分类正确率为‘,np.mean(y_hat1==y)
gmm=GaussianMixture(n_components=3,covariance_type=‘full‘, random_state=0)
gmm.fit(x)
print ‘GMM均值 = \n‘, gmm.means_
y_hat2=gmm.predict(x)
print ‘分类正确率为‘,np.mean(y_hat2==y)

输出结果为

实际均值 =

[[5.006  3.418]

[5.936  2.77 ]

[6.588  2.974]]

K-Means均值 =

[[5.77358491  2.69245283]

[ 5.006      3.418     ]

[ 6.81276596 3.07446809]]

分类正确率为 0.233333333333

GMM均值 =

[[5.01494511  3.44040237]

[ 6.69225795 3.03018616]

[ 5.90652226 2.74740414]]

分类正确率为 0.533333333333怒摔键盘啊,什么破正确率呀!!!憋急啊,我看事情并不简单。机智的我们观察一下均值矩阵。K-Means给出的第一行似乎和实际的第二行很接近,第二行和实际的第一行很接近。同样,GMM给出的均值矩阵也有同样的问题,第二行和第三行似乎对调了。这不是算法的锅啊,它只管给你聚类,哪里还能保证标签和你一样啊,三个类别六种标签方式人家算法也只能随机一种好吗,所以现在我们把预测的结果的标签改一下看看实际的正确率如何。

import numpy as np
from sklearn import datasets
from sklearn.cluster import KMeans
from sklearn.mixture import GaussianMixture
#读取数据
iris=datasets.load_iris()
x=iris.data[:,:2]
y=iris.target
mu = np.array([np.mean(x[y == i], axis=0) for i in range(3)])
print ‘实际均值 = \n‘, mu
#K-Means
kmeans=KMeans(n_clusters=3,init=‘k-means++‘,random_state=0)
y_hat1=kmeans.fit_predict(x)
y_hat1[y_hat1==0]=3
y_hat1[y_hat1==1]=0
y_hat1[y_hat1==3]=1
mu1=np.array([np.mean(x[y_hat1 == i], axis=0) for i in range(3)])
print ‘K-Means均值 = \n‘, mu1
print ‘分类正确率为‘,np.mean(y_hat1==y)
gmm=GaussianMixture(n_components=3,covariance_type=‘full‘, random_state=0)
gmm.fit(x)
print ‘GMM均值 = \n‘, gmm.means_
y_hat2=gmm.predict(x)
y_hat2[y_hat2==1]=3
y_hat2[y_hat2==2]=1
y_hat2[y_hat2==3]=2
print ‘分类正确率为‘,np.mean(y_hat2==y)

输出结果为

实际均值 =

[[5.006  3.418]

[ 5.936 2.77 ]

[ 6.588 2.974]]

K-Means均值 =

[[5.006       3.418     ]

[ 5.77358491 2.69245283]

[ 6.81276596 3.07446809]]

分类正确率为 0.82

GMM均值 =

[[5.01494511  3.44040237]

[ 6.69225795 3.03018616]

[ 5.90652226 2.74740414]]

分类正确率为 0.786666666667

啊,这样的结果还是比较让人满意的,甚至比前面的一些监督学习的结果还要好一些……另外,标签不一致的问题我这里采用的是最蠢的手动调整,大家当然可以根据你算出的均值矩阵每行与原始均值矩阵哪行的距离最小,确定它在原始数据中的标签自动调整,这当然是OK的,我这里偷一点懒。

好了,愉快的工作日又要结束了,哈哈哈,周末你好!!!

时间: 03-22

机器学习笔记(十)EM算法及实践(以混合高斯模型(GMM)为例来次完整的EM)的相关文章

Andrew Ng机器学习笔记+Weka相关算法实现(四)SVM和原始对偶问题

这篇博客主要解说了Ng的课第六.七个视频,涉及到的内容包含,函数间隔和几何间隔.最优间隔分类器 ( Optimal Margin Classifier).原始/对偶问题 ( Primal/Dual Problem). SVM 的对偶问题几个部分. 函数间隔和几何间隔 函数间隔( functional margin) 与几何间隔( geometric margin)是理解SVM的基础和前提. 如果y∈{-1,1},而不再是0,1,我们能够将分类器函数表演示样例如以下: 这里的b參数事实上就是原来的

【机器学习】EM算法详细推导和讲解

[机器学习]EM算法详细推导和讲解 今天不太想学习,炒个冷饭,讲讲机器学习十大算法里有名的EM算法,文章里面有些个人理解,如有错漏,还请读者不吝赐教. 众所周知,极大似然估计是一种应用很广泛的参数估计方法.例如我手头有一些东北人的身高的数据,又知道身高的概率模型是高斯分布,那么利用极大化似然函数的方法可以估计出高斯分布的两个参数,均值和方差.这个方法基本上所有概率课本上都会讲,我这就不多说了,不清楚的请百度. 然而现在我面临的是这种情况,我手上的数据是四川人和东北人的身高合集,然而对于其中具体的

EM算法学习笔记2:深入理解

文章<EM算法学习笔记1:简介>中介绍了EM算法的主要思路和流程,我们知道EM算法通过迭代的方法,最后得到最大似然问题的一个局部最优解.本文介绍标准EM算法背后的原理. 我们有样本集X,隐变量Z,模型参数θ,注意他们3个都是向量,要求解的log似然函数是lnp(X|θ),而这个log似然函数难以求解,我们假设隐变量Z已知,发现lnp(X,Z|θ) 的最大似然容易求解. 有一天,人们发现引入任意一个关于隐变量的分布q(Z),对于这个log似然函数,存在这样一个分解: lnp(X|θ)=L(q,θ

简单易学的机器学习算法——EM算法

一.机器学习中的參数预计问题 在前面的博文中,如"简单易学的机器学习算法--Logistic回归"中,採用了极大似然函数对其模型中的參数进行预计,简单来讲即对于一系列样本,Logistic回归问题属于监督型学习问题,样本中含有训练的特征 X_i" title="X_i" >以及标签.在Logistic回归的參数求解中.通过构造样本属于类别和类别的概率: 这样便能得到Logistic回归的属于不同类别的概率函数: 此时,使用极大似然预计便可以预计出模型

EM算法原理以及高斯混合模型实践

EM算法有很多的应用: 最广泛的就是GMM混合高斯模型.聚类.HMM等等. The EM Algorithm 高斯混合模型(Mixtures of Gaussians)和EM算法 EM算法 求最大似然函数估计值的一般步骤: (1)写出似然函数: (2)对似然函数取对数,并整理: (3)求导数,令导数为0,得到似然方程: (4)解似然方程,得到的参数即为所求. 期望最大化算法(EM算法): 优点: 1. 简单稳定: 2. 通过E步骤和M步骤使得期望最大化,是自收敛的分类算法,既不需要事先设定类别也

从最大似然到EM算法浅解

原文在这里 机器学习十大算法之一:EM算法.能评得上十大之一,让人听起来觉得挺NB的.什么是NB啊,我们一般说某个人很NB,是因为他能解决一些别人解决不了的问题.神为什么是神,因为神能做很多人做不了的事.那么EM算法能解决什么问题呢?或者说EM算法是因为什么而来到这个世界上,还吸引了那么多世人的目光. 我希望自己能通俗地把它理解或者说明白,但是,EM这个问题感觉真的不太好用通俗的语言去说明白,因为它很简单,又很复杂.简单在于它的思想,简单在于其仅包含了两个步骤就能完成强大的功能,复杂在于它的数学

EM算法求高斯混合模型参数估计——Python实现

EM算法一般表述: 当有部分数据缺失或者无法观察到时,EM算法提供了一个高效的迭代程序用来计算这些数据的最大似然估计.在每一步迭代分为两个步骤:期望(Expectation)步骤和最大化(Maximization)步骤,因此称为EM算法. 假设全部数据Z是由可观测到的样本X={X1, X2,--, Xn}和不可观测到的样本Z={Z1, Z2,--, Zn}组成的,则Y = X∪Z.EM算法通过搜寻使全部数据的似然函数Log(L(Z; h))的期望值最大来寻找极大似然估计,注意此处的h不是一个变量

EM算法1-原理

EM算法用于含有隐含变量的概率模型参数的极大似然估计.什么是隐含变量的概率模型呢?举个例子,假设有3枚硬币,分别记为A,B,C,它们正面出现的概率分别为r,p,q.每次实验先掷硬币A,如果出现的是正面就投B,如果出现的反面就投C,出现正面记为1,出现反面记为0.独立10次实验,观测结果如下:1101001011.如果只有这个结果,而不知道过程,问如何估计r,q,p?也就是说,我们能看到每次的观测结果,可是这个结果是B产生的还是C产生的我们不知道,也就是A的结果我们不知道,这个就是所谓的隐含变量.

实战EM算法与图像分割

EM 算法是求参数极大似然估计的一种方法,它可以从非完整数据集中对参数进行估计,是一种非常简单实用的学习算法.这种方法可以广泛地应用于处理缺损数据.截尾数据以及带有噪声等所谓的不完全数据,可以具体来说,我们可以利用EM算法来填充样本中的缺失数据.发现隐藏变量的值.估计HMM中的参数.估计有限混合分布中的参数以及可以进行无监督聚类等等. 贴相关几个好文章:从最大似然到EM算法浅解 混合高斯模型(Mixtures of Gaussians)和EM算法 斯坦福大学机器学习--EM算法求解高斯混合模型

EM算法及其推广的要点

1.EM算法是含有隐变量的变量的概率模型极大似然估计或极大后验概率估计的迭代算法,含有隐变量的概率模型的数据表示为$P(Y,Z|\theta)$.这里,$Y$是观测变量的数据,$Z$是隐变量的数据,$\theta$是模型参数.EM算法通过迭代求解观测数据的对数似然函数$L(\theta)=logP(Y|\theta)$的极大化,实现极大似然估计.每次迭代包括两步:E步,求期望,即求$logP(Y|\theta)$关于$P(Y|\theta^{(i)})$的期望: $Q(\theta,\theta