加载中…
个人资料
yfx416
yfx416
  • 博客等级:
  • 博客积分:0
  • 博客访问:103,897
  • 关注人气:75
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

EM算法

(2011-10-03 00:22:33)
标签:

em算法

分类: 数据挖掘

所谓EM算法,指的是就是Expect-Maximum算法,是一种非常有用的算法。假设这么一个问题,我们有一堆样本集合X,我们已知该样本总体的分布类型(比如是高斯分布),但是我们不知道这个分布的参数具体是多少,我们希望有方法能够根据这些观测到的样本集合来估计出这个分布的参数。怎么办呢?于是就有了极大似然估计,该方法思路很简单,设计出一个样本同时出现的概率公式,这个公式也叫似然函数,这个似然函数表示的是样本同时出现的前提下,参数分布的概率,该公式肯定包含了这些参数作为公式的因子。我们的目标是使得该样本出现的概率最大,那么剩下的问题就是一个数学问题了,选择合适的参数值使得这个公式的值最大,比如求导等等。极大似然估计的的思路很直接,选择一个目标函数,使该目标函数最大。本质上最大似然估计是根据贝叶斯公式,计算出一个公式,该公式表示的是在样本出现的前提下,参数的分布概率。通过选取合适的参数值,使得这个分布概率最大。

如果我们在对上述问题再加一点难度,除了分布参数我们不知道,另外还有一些隐藏的变量我们也不知道,或者说观测到得数据不完整,在这种情况下,包含了隐藏变量的目标函数往往没有解析解,因此无法估算出这些参数变量。那我们又该怎么估计出这些参数和这些缺失的隐藏变量呢?解决的方法就是EM算法。关于EM算法,52npl上有一篇博客做了比较深刻的说明,请参阅。这里对其说明进行一些评注,便于大家理解。

EM算法的目标是找出有隐性变量的概率模型的最大可能性解,它分为2个步骤,E-step和M-step,E-step根据最初假设的模型参数值或者上一步的模型参数计算出隐性变量的后验概率,其实就是隐性变量的期望,M-step根据这个E-step的后验概率重新计算出模型参数,然后再重复这两个步骤,直至目标函数收敛。

观测到的变量组成的向量我们表示成X,所有隐性变量组成的向量为Z,模型的参数表示成

所谓EM算法,指的是就是Expect-Maximum算法,是一种非常有用的算法。假设这么一个问题,我们有一堆样本集合X,我们已知该样本总体的分布类型(比如是高斯分布),但是我们不知道这个分布的参数具体是多少,我们希望有方法能够根据这些观测到的样本集合来估计出这个分布的参数。怎么办呢?于是就有了极大似然估计,该方法思路很简单,计算出这些样本出现的分布概率公式,该公式肯定包含了这些参数作为公式的因子。我们的目标是使得该样本出现的概率最大,那么剩下的问题就是一个数学问题了,选择合适的参数值使得这个公式的值最大,比如求导等等。极大似然估计的的思路很直接,选择一个目标函数,使该目标函数最大。

如果我们在对上述问题再加一点难度,除了分布参数我们不知道,另外还有一些隐藏的变量我们也不知道,或者说观测到得数据不完整,在这种情况下,包含了隐藏变量的目标函数往往没有解析解,因此无法估算出这些参数变量。那我们又该怎么估计出这些参数和这些缺失的隐藏变量呢?解决的方法就是EM算法。关于EM算法,52npl上有一篇博客做了比较深刻的说明,请参阅。这里对其说明进行一些评注,便于大家理解。

EM算法的目标是找出有隐性变量的概率模型的最大可能性解,它分为2个步骤,E-step和M-step,E-step根据最初假设的模型参数值或者上一步的模型参数计算出隐性变量的后验概率,其实就是隐性变量的期望,M-step根据这个E-step的后验概率重新计算出模型参数,然后再重复这两个步骤,直至目标函数收敛。

观测到的变量组成的向量我们表示成X,所有隐性变量组成的向量为Z,模型的参数表示成62559509F70C641E47B83A0CA3BB0D96241CA6E6[12](一个或多个参数)。在分类问题中,Z就表示的是可能的潜在分类,X就是需要分类的数据,我们得目标是找出模型的参数62559509F70C641E47B83A0CA3BB0D96241CA6E6[22]和隐性变量来使得X出现的概率最大,也就是3EB4140F32C1D03C587897317219D266F10FD698最大(其实3EB4140F32C1D03C587897317219D266F10FD698本来可以写成F6086E9E7F630424F4D06FBD5C587B32CDB788E3,但是62559509F70C641E47B83A0CA3BB0D96241CA6E6[24]不是随机变量而是一个参数,所以将 | 改成;)

由于很多模型的概率都带有指数,所以在3EB4140F32C1D03C587897317219D266F10FD698上加一个对数ln,这个对数并不影响其极值,3EB4140F32C1D03C587897317219D266F10FD698的最大值也就是ln3EB4140F32C1D03C587897317219D266F10FD698的最大值。

假设FCEFF1ED40CBE2101F9801F9C5DF8D7143D87FE9D2909BE8DD15E5FE1C70612739AD393BA27E7D2A上的一个概率分布,那么就有AFD48FBC965144B9D00A93F381A11EDA4C901B74

69B4F694CAFC984ACAACFD7C9C3BB5D7BF0A3A42

公式(1)

最后一步是基于琴生不等式,所谓琴生不等式

1C345925F54D0F549C8A6814579CF65ED081DDC2

需要注意的是,中国大陆数学界某些机构关于函数凹凸性定义和国外的定义是相反的。Convex Function在某些国内的数学书中指凹函数。Concave Function指凸函数。但在中国大陆涉及经济学的很多书中,凹凸性的提法和国外的提法是一致的,也就是和数学教材是反的。举个例子,同济大学高等数学教材对函数的凹凸性定义与本文相反,本条目的凹凸性是指其上方图是凹集或凸集,而同济大学高等数学教材则是指其下方图是凹集或凸集,两者定义正好相反。

在本文中,ln是一个凹函数。

根据公式(1),我们看到了204603EF27F0430FB24FC93765EEA88ECE3BC0C0的下界是多少。EM算法分为2步:

第一步:E-step

其目的是计算出204603EF27F0430FB24FC93765EEA88ECE3BC0C0的下界,以及在此下界时,FCEFF1ED40CBE2101F9801F9C5DF8D7143D87FE9的值。

根据琴声不等式,我们得知204603EF27F0430FB24FC93765EEA88ECE3BC0C0在到达下界时的条件为

9D035E3D8B8F393C769B6709FB4B8D3A84C54F15公式(2)

c为常数。我们已知AFD48FBC965144B9D00A93F381A11EDA4C901B74,那么此临界条件下由公式(2)就有BDE14C4476B27D05A8AC5D100033BF39986659D4

公式2变化一下如下

F9336727218C96636C7B4EBAF3519F9E430D6D43公式3

第二步:M-step

在E-step中,我们得到了204603EF27F0430FB24FC93765EEA88ECE3BC0C0的下界以及此下界时FCEFF1ED40CBE2101F9801F9C5DF8D7143D87FE9[23]的值,那么在M-step中我们的目标就变成了通过变换参数62559509F70C641E47B83A0CA3BB0D96241CA6E6[26]来最大化这个下界。下界提高了,那么204603EF27F0430FB24FC93765EEA88ECE3BC0C0值也会提高。

M-step本质上就是求ln3EB4140F32C1D03C587897317219D266F10FD698[21]的极值点,求极值点的方法就不用再啰嗦了吧,求偏导,通过C1C26C09FBF24DBB94A584FBBBBAEE47451CE077求参数

EM算法概要如下

882AE7F2A4369AC4DCB929802717906B045C81FF

EM算法通过不断提高目标函数204603EF27F0430FB24FC93765EEA88ECE3BC0C0的下界的方法来寻找目标函数的最大值,因为通过M-step使得204603EF27F0430FB24FC93765EEA88ECE3BC0C0的下界不断提高,只要204603EF27F0430FB24FC93765EEA88ECE3BC0C0存在最大值,那么EM算法一定会收敛。

做了这么多分析,举两个例子,可能会更容易理解。先看第一个例子,来自文献[3]:

混合高斯模型

数据X是一个实例集合,它由k个不同的正态分布混合而成的分布生成,这里涉及k个不同的正态分布的混合,而且我们还不知道哪个变量实例由哪个分布生成的。因此这是一个涉及隐藏变量的典型例子。可以把每个实例完整描述成5692C28B643E34267C413D37DCE563B9F53E1BFA,其中xi是第i个实例的观测值,7113759BBB65D5FA1A9F743C7EFE805DB2DFEABE表示k个正态分布中的哪一个用于生成xi,确切得讲,当xi由第j个正态分布产生时,zij为1,否则为0。由此Z向量只有一个分量为1,其它分量为0。这里xi是实例描述中已经观察到的变量,7113759BBB65D5FA1A9F743C7EFE805DB2DFEABE是隐藏变量。k个正态分布的均值07CE80CE9FBE3F881481EECF69D0F3E49B8B1C2A就是我们需要估计的模型参数。

算法伊始,我们首先假设一个模型参数初始值62559509F70C641E47B83A0CA3BB0D96241CA6E6[28],接下来就是计算我们的目标函数204603EF27F0430FB24FC93765EEA88ECE3BC0C0,该目标函数的公式推导如下:

ED35D9B7CCBEB93056E9BA4D695F375DA719734A

公式2

接下来就是E-step.我们的目标是选择一个概率分布FCEFF1ED40CBE2101F9801F9C5DF8D7143D87FE9[25]使得204603EF27F0430FB24FC93765EEA88ECE3BC0C0达到下界,我们就有

063738D747030D040188217F279A04064B890D0F

那此时我们目标函数204603EF27F0430FB24FC93765EEA88ECE3BC0C0[40]的值根据公式2就是

D9EF040BDEB729BB406E1BAB274DFE162175073E公式3

接下来就是M-step,在FCEFF1ED40CBE2101F9801F9C5DF8D7143D87FE9[27]确定的情况下,选择合适参数07CE80CE9FBE3F881481EECF69D0F3E49B8B1C2A使得204603EF27F0430FB24FC93765EEA88ECE3BC0C0[42]最大化,根据公式2,这就是一个数学问题,对公式3求偏导,你会发现参数C0C43A958BA9034162F4FFF2C67C11463CE9CAF4的极值点为

1A91537EA300CA6B52E45488A6B21BF42C4342CA

然后算法就利用估算出的参数C0C43A958BA9034162F4FFF2C67C11463CE9CAF4再重复计算E-step,M-step直至收敛。

因子分析

所谓因子分析,就是指从变量群中提取公共因子的方法,该因子是用来描述隐藏在观测变量中的一些更基本的,但又无法直接测量到的隐性变量。EM算法也可以用来解决这样的问题,从而能够估算出隐藏的公共因子及该模型的参数。文献4的博客给出了一个很好的说明,讲得比较清楚。这里主要是引用这篇文章的内容,加入一些自己的评论,使其更便于理解。

举个因子分析的例子,有m个n维特征向量的样本集,每个样本实例表示为AB4C970CDCF5EDCB6A11B6F87486D0BCD7A24594,样本实例的生成模型为

EA7B5EF5E3B5C9467144DC1A7180B5F3802949D2

其中CCCB70B44A40ECA9EF4C3A36E6B21AFE9FB873E8是样本点,其维度为n,其表示为

1501B4F00A91EA2AFC4FC6CE0D5DE8157566F09D

2691CDDA80705113485B1E2CBB739B39F3866789代表因子,该因子存在于一个k维向量空间,该k维空间就代表因子的维度空间,也就是说每一个实例变量CCCB70B44A40ECA9EF4C3A36E6B21AFE9FB873E8实际上是由这k维的因子所决定的,我们目标就是估算出实例变量的k维因子。其公式表示如下

AEC53474CBF55455B387C0D04E6957E0B32B053E

因子遵循多元正态分布,2E31450121D1017C6C380F0135B769BF09847856E2E9971043CA08F7AB2C051D5B8437634C21C662表示单位矩阵,对角线元素为1,其他元素为0.

1FD3D0ADD2E1B0ABB1525201E74D3340C549E66F是一个变换矩阵,有时也被称为装载矩阵,其目的是将因子映射到样本的n维空间。

9E1748F06A74D5DEDBCD9F3F7F32AB1B10913FBE是一个n维向量,其含义是样本的中心点。

CFD28433B1439B48B3D89223C47C868806DAA9E6是一个n维向量,表示的是真实样本和模型的误差,同2691CDDA80705113485B1E2CBB739B39F3866789一样,它也遵循多元高斯分布,DE7249AA807DC5DB96D1EC6022474BE3366B1732 其中D22EEC966831CD8703B669ED700175EEBB757230是一个n x n对角矩阵

下面来分析EM算法的使用,首先明确我们的目标,我们的目标是根据样本实例集估算出参数值CFD28433B1439B48B3D89223C47C868806DAA9E69E1748F06A74D5DEDBCD9F3F7F32AB1B10913FBE952052EE263AC94BDBF05C3C789FB7C84C81F600。有了这三个参数我们就能根据模型以及样本实例计算出每个样本对应的因子向量(也就是隐藏变量)2691CDDA80705113485B1E2CBB739B39F3866789,一个矩阵方程组变化而已。

回想EM算法,那么对应因子分析,其E-step如下:

我们将观测到得实例变量X和隐藏变量Z组成一个联合的变量Y,该联合变量Y也符合多元高斯分布。为什么Y也符合多元高斯分布呢?很简单,首先Z是一个多元高斯分布,而X是多元高斯分布变量Z的一个线性变化,所以X也是一个多元高斯分布(参见文献[5],多元正态分布的线性变化仍然是),那么X,Z组合成的变量Y也符合高斯分布。其公式代表如下:

47FE2E706AAE2216AD8FEB3AA8312F0FD4A2653A

参见文献[5],你会发现多元正态分布的另外一个特性,多元正态分布的条件分布仍然是多元正态分布

该特性表述如下:

635E0AC29D78D15115C51E982D617A473D5BC2E6

对应我们的例子,就有

5BAD4865C4E498C8B046B42BA02C780DD695540E

5C560B651FBA9938E837C5563CFD42BB55EFFEF8

这个过程中利用了z和CFD28433B1439B48B3D89223C47C868806DAA9E6独立假设(911BADA6999A8B20E53CCF586E58E39A553B0DD2)

F8C64878725706F76F70C9CC58C3684B0075D2BD公式如下

9F5EE9E2A97CF957C952E2CF96C45C7F925F1905

那么就可以得到Y的分布:

8F1EA3AA3FB8ECA72183BB787701CB8D2B18792E

套用上述的特性-性质6,就有

DE35656360726E376AC66965BF849C39CDFC1201

这就是我们的目标。E-step就到此为止。再看M-step,M-step的目标函数如下

8A512C036E2FE14680A271D5B36119668573EF9F

分别对3个参数求该目标函数的偏导,得到3个偏导公式,让其都为0,组成一个方程组。该方程组的解就是我们待沽参数。

具体的公式推导参见文献[4],文献[4]给出了比较详细的推导,如果对多元高斯分布了解的比较深入的话,该推导应该不难读懂。

个人觉得文献[3]中关于EM的讲述有一些瑕疵,讲得不是很清楚,但是文中的例子倒是可以作为参考。文献[4],[5]对此讲述的比较清楚,是个非常不错的参考,值得一读。

参考文献:

[1]理解EM算法 52nlp

[2]http://zh.wikipedia.org/wiki/凸函数

[3]数据挖掘原理与算法-毛国君

[4] http://www.cnblogs.com/jerrylead/archive/2011/05/11/2043317.html

[5]多维高斯分布讲解 http://www.docin.com/p-121202383.html

[6] EM算法http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html

[7] The Top Ten Algorithms in Data Mining

[7] http://zh.wikipedia.org/zh-cn/似然函数

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有