EM算法 - 最大期望算法


EM算法——最大期望算法 ——吴泽邦 吴林谦 万仔仁 余淼 陈志明 秦志勇 16:54:09 1 食堂的大师傅炒了一份菜,要等分成两份给两个人吃 ——显然没有必要拿来天平一点一点的精确的去称分量, 最简单的办法是先随意的把菜分到两个碗中,然后观察是 否一样多,把比较多的那一份取出一点放到另一个碗中, 这个过程一直迭代地执行下去,直到大家看不出两个碗所 容纳的菜有什么分量上的不同为止 EM算法就是这样,假设我们估计知道A和B两个参数,在 开始状态下二者都是未知的,并且知道了A的信息就可以 得到B的信息,反过来知道了B也就得到了A。可以考虑首 先赋予A某种初值,以此得到B的估计值,然后从B的当前 值出发,重新估计A的取值,这个过程一直持续到收敛为 止。 16:54:10 2 EM算法  最大期望算法(Expectation-maximization algorithm,又译期望最大化算法)在统计中被 用于寻找,依赖于不可观察的隐性变量的概率 模型中,参数的最大似然估计。  在统计计算中,最大期望算法是在概率模型中 寻找参数最大似然估计或者最大后验估计的算 法,其中概率模型依赖于无法观测的隐藏变量。 最大期望经常用在机器学习和计算机视觉的数 据聚类领域。 16:54:11 3 期望值(EXPECTED VALUE)  在概率和统计学中,一个随机变量的期望 值是变量的输出值乘以其机率的总和,换 句话说,期望值是该变量输出值的平均数  如果X是在概率空间(Ω, P)中的一个随机 变量,那么它的期望值E[X]的定义是 E[X] = ∫ΩX dP  离散:EX = 푝푖푥푖푖  连续:EX = 푥푓 푥 푑푥∞ −∞ 16:54:11 4 最大似然估计 某位同学与一位猎人一起外出打猎,一只野兔 从前方窜过.只听一声枪响,野兔应声到下, 如果要你推测,这一发命中的子弹是谁打的? ——你就会想,只发一枪便打中,由于猎人命 中的概率一般大于这位同学命中的概率,看来 这一枪是猎人射中的 16:54:11 5 最大似然估计  假设我们需要调查我们学校的男生和女生的身高分布。 你在校园里随便地活捉了100个男生和100个女生。男 左女右,首先统计抽样得到的100个男生的身高。假设 他们的身高是服从高斯分布的。但是这个分布的均值u 和方差∂2我们不知道,这两个参数就是我们要估计的。 记作θ=[u, ∂]T。  数学语言: 在学校那么多男生(身高)中,我们独立地按照概率密度 p(x|θ)抽取100了个(身高),组成样本集X,我们想通过样 本集X来估计出未知参数θ。概率密度p(x|θ)我们知道了是高 斯分布N(u,∂)的形式,其中的未知参数是θ=[u, ∂]T。 抽到这100个人的概率: 16:54:11 6 似然函数:L(휽) = L(x1,x2,…xn|휽) = 풑(풙풊|휽)풏 풊=ퟏ 最大似然估计  上例中,在学校那么男生中,我一抽就抽到这 100个男生(表示身高),而不是其他人,那 是不是表示在整个学校中,这100个人(的身 高)出现的概率最大啊。那么这个概率怎么表 示?哦,就是上面那个似然函数L(θ)。所以, 我们就只需要找到一个参数θ,其对应的似然 函数L(θ)最大,也就是说抽到这100个男生 (的身高)概率最大。这个叫做θ的最大似然 估计量 16:54:11 7 最大似然估计  设总体X是离散型随机变量,其概率函数为 푝(푥; 휃) ,其中휃 是未知参数.设X1,X2,…Xn为取自总体X的样本,X1,X2,…Xn 的 联合概率函数为:  若已知样本取值为x1,x2,…xn ,则事件 {X1 = x1 , X2 = x2,…Xn = xn }发生的概率为 풑(풙풊|휽)풏 풊=ퟏ  显然上面的概率随휃改变而改变,从直观上来讲,既然样本 值x1,x2,…xn出现,即表示其出现的概率相对较大,而使得 풑(풙풊; 휽)풏 풊=ퟏ 取较大的值,不妨看做휃的函数  16:54:11 8 似然函数:L(휽) = L(x1,x2,…xn|휽) = 풑(풙풊|휽)풏 풊=ퟏ 풑(풙풊|휽)풏 풊=ퟏ 휃为常量, X1,X2,…Xn为变量 最大似然估计  如何求L(휃)最大值?  考虑到有累乘,不妨取对数,这里是因为lnL函数的单 调性和L函数的单调性一致,因此L(휃)的最大值转换为 lnL(휃)的最大值 퐇 휽 = 풍풏푳 휽 = 풍풏 풑 풙풊 휽 = 풍풏풑(풙풊|휽) 풏 풊=ퟏ 풏 풊=ퟏ  求最值,可转换为求解下面的方程 풅풍풏푳(휽) 풅휽 = ퟎ 16:54:11 9 似然方 程 EXAMPLE  设某工序生产的产品的不合格率为 p,抽 n个 产品作检验,发现有T个不合格,试求p的极大 似然估计. 分析:设X是抽查一个产品时的不合格个数,则X 服从参数的二点分布b(1,p).抽查n个产品,得样本 X1,X2,…X3,其观察值为x1,x2,...,x3,加入样本有T个 不合格,表示x1,x2,...,x3中有T个取值为1,n-T个取 值为0.按照离散分布场合方法,求p的极大似然估计 16:54:11 10 解: 1. 写出似然函数 퐿 푝 = 푝푥푖푛 푖=1 (1 − 푃)1−푥푖 2. 对퐿 푝 取对数,得对数似然函数 : 3. 写出似然方程 4. 解似然方程得: 5. 验证在 时, ,这表明 可使似 然函数达到最大 16:54:11 11    n i i n i ii ppxpnpxpxpl 11 )]1ln([ln)1ln()]1ln()1(ln[)( 0)1( 1 1)1 11(1 )( 11    n i i n i i xppp n ppxp n dp pdl xxnp n i i   1 1ˆ xp ˆ 0)( 2 2 dp pld xp ˆ 小结 极大似然估计,只是一种概率论在统计学的应 用,它是参数估计的方法之一。说的是已知某 个随机样本满足某种概率分布,但是其中具体 的参数不清楚,参数估计就是通过若干次试验, 观察其结果,利用结果推出参数的大概值。最 大似然估计是建立在这样的思想上:已知某个 参数能使这个样本出现的概率最大,我们当然 不会再去选择其他小概率的样本,所以干脆就 把这个参数作为估计的真实值。 16:54:11 12 最大期望算法  继续回到身高的例子,我抽到这200个人中, 某些男生和某些女生一见钟情,已经好上了, 怎么着都不愿意分开,这时候,你从这200个 人里面随便给我指一个人,我都无法确定这个 人是男生还是女生。  也就是说你不知道抽取的那200个人里面的每 一个人到底是从男生的那个身高分布里面抽取 的,还是女生的那个身高分布抽取的。用数学 的语言就是,抽取得到的每个样本都不知道是 从哪个分布抽取的。 16:54:18 13 最大期望算法  这个时候,对于每一个样本或者你抽取到的人, 就有两个东西需要猜测或者估计的了,一是这个 人是男的还是女的?二是男生和女生对应的身高 的高斯分布的参数是多少?  只有当我们知道了哪些人属于同一个高斯分布的 时候,我们才能够对这个分布的参数作出靠谱的 预测;反过来,只有当我们对这两个分布的参数 作出了准确的估计的时候,才能知道到底哪些人 属于第一个分布,那些人属于第二个分布 16:54:18 14 先有鸡还是先有蛋 16:54:18 15 为了解决这个你依赖我,我依赖你的循环依赖 问题,总得有一方要先打破僵局,说,不管了, 我先随便整一个值出来,看你怎么变,然后我 再根据你的变化调整我的变化,然后如此迭代 着不断互相推导,最终就会收敛到一个解 16:54:18 16 亲,还记得ppt开始分菜的厨师么? EM:EXPECTTATION MAXIMIZATION  依然用身高的例子  Expectation:我们是先随便猜一下男生(身高)的正态 分布的参数:如均值和方差是多少。例如男生的均值是 1米7,方差是0.1米,然后计算出每个人更可能属于第 一个还是第二个正态分布中的(例如,这个人的身高是 1米8,那很明显,他最大可能属于男生的那个分布)  Maximization:有了每个人的归属,或者说我们已经大 概地按上面的方法将这200个人分为男生和女生两部分, 我们就可以根据之前说的最大似然那样,通过这些被大 概分为男生的n个人来重新估计第一个分布的参数,女 生的那个分布同样方法重新估计  这时候,两个分布的概率改变了,那么我们就再需要调 整E步……如此往复,直到参数基本不再发生变化为止 16:54:18 17 QUESTIONS  你老迭代迭代的,你咋知道新的参数的估计就 比原来的好啊?  为什么这种方法行得通呢?  有没有失效的时候呢?  什么时候失效呢?  用到这个方法需要注意什么问题呢? 16:54:22 18 EM算法推导  假设我们有一个样本集{x(1),…,x(m)},包含m个 独立的样本。但每个样本i对应的类别z(i)是未 知的(相当于聚类),也即隐含变量。故我们 需要估计概率模型p(x,z)的参数θ,但是由于里 面包含隐含变量z,所以很难用最大似然求解, 但如果z知道了,那我们就很容易求解了。 16:54:22 19 EM算法推导  这里把每个人(样本)的完整描述看做是三元 组yi={xi,zi1,zi2},  xi是第i个样本的观测值  zi1和zi2表示利用男女哪个高斯分布,隐含变量 zij在xi由第j个高斯分布产生时值为1,否则 为0 。 例如一个样本的观测值为1.8,来自男生高 斯分布,则样本表示为{1.8, 1, 0}。 即若zi1和zi2的值已知,也就是说每个人我 已经标记为男生或者女生了 16:54:22 20  对于参数估计,我们本质上还是想获得一个使似 然函数最大化的那个参数θ,现在与最大似然不同 的只是似然函数式中多了一个未知的变量z  也就是说我们的目标是找到适合的θ和z让L(θ)最大 16:54:22 21  (1)式最大化,也就是最大化似然函数,但 是可以看到里面有“和的对数”,求导后形式会 非常复杂,所以很难求解得到未知参数z和θ。  (2)式只是分子分母同乘以一个相等的函数, 还是有“和的对数”啊,还是求解不了  (3)式变成了“对数的和”,那这样求导就容 易了。我们注意点,还发现等号变成了不等号 为什么能这么变? Jensen不等式 16:54:22 22  Jensen不等式 f凸函数: E[f(X)] >= f(E[X]) f凹函数: E[f(X)] <= f(E[X])  f(x) = log x, 二次导数为-1/x2<0, 为凹函数 (注意:国内外凹凸函数定义不同,本处采用 国际定义) 16:54:22 23 EM算法流程  E步骤:根据参数初始值或上一次迭代的模型 参数记휃(푛),来求一个分布q(z),使得L(q,휃)最大 化  M步骤:固定q(z),求一个휃,记为휃(푛+1),使得 L(q,휃)最大 16:54:22 24 PROBLEMS  局部最优  收敛速度 怎么解决? 16:54:22 25 THANK YOU 16:54:22 26
还剩25页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

nmfp

贡献于2015-02-11

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf