算法以及其推廣_第1頁(yè)
算法以及其推廣_第2頁(yè)
算法以及其推廣_第3頁(yè)
算法以及其推廣_第4頁(yè)
算法以及其推廣_第5頁(yè)
已閱讀5頁(yè),還剩21頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、關(guān)于算法及其推廣第一張,PPT共二十六頁(yè),創(chuàng)作于2022年6月EM算法是一種迭代算法,1977年由Dempster 等人總結(jié)提出,用于含有隱變量的概率模型參數(shù)的極大似然估計(jì),或極大后驗(yàn)概率估計(jì)。EM算法的每次迭代由兩步組成:E步,求期望;M步,求極大。所以這一算法稱為期望極大算法(Expectation Maximization),簡(jiǎn)稱EM算法。第二張,PPT共二十六頁(yè),創(chuàng)作于2022年6月極大似然估計(jì)極大似然估計(jì)是概率論在統(tǒng)計(jì)學(xué)中的應(yīng)用,它是參數(shù)估計(jì)的方法之一。說的是已知某個(gè)隨機(jī)樣本滿足某種概率分布,但是其中具體的參數(shù)不清楚,參數(shù)估計(jì)就是通過若干次實(shí)驗(yàn),觀察其結(jié)果,利用結(jié)果推出參數(shù)的大概值。

2、第三張,PPT共二十六頁(yè),創(chuàng)作于2022年6月 極大似然估計(jì)似然函數(shù):已知樣本集X,X是通過概率密度p(x|)抽取。樣本集X中各個(gè)樣本的聯(lián)合概率:為了便于分析,由于L()是連乘的,還可以定義對(duì)數(shù)似然函數(shù),將其變成連加的:第四張,PPT共二十六頁(yè),創(chuàng)作于2022年6月 極大似然估計(jì)求極值可以轉(zhuǎn)換為以下方程:的極大似然估計(jì)量表示為:第五張,PPT共二十六頁(yè),創(chuàng)作于2022年6月9.1 EM算法的引入9.1.1EM算法9.1.2EM算法的導(dǎo)出9.1.3EM算法在非監(jiān)督學(xué)習(xí)中的應(yīng)用9.2 EM算法的收斂性第六張,PPT共二十六頁(yè),創(chuàng)作于2022年6月9.1.1 EM算法例9.1(三硬幣模型)假設(shè)有3枚

3、硬幣,分別記作A, B, C. 這些硬幣正面出現(xiàn)的概率分別是, p, q. 進(jìn)行如下擲硬幣試驗(yàn):先擲硬幣A,根據(jù)其結(jié)果選出硬幣B或硬幣C,正面選硬幣B,反面選硬幣C;然后擲選出的硬幣,擲硬幣的結(jié)果,出現(xiàn)正面記作1,出現(xiàn)反面記作0;獨(dú)立地重復(fù)n次試驗(yàn)(這里,n=10),觀測(cè)結(jié)果如下:1,1,0,1,0,0,1,0,1,1假設(shè)只能觀測(cè)到擲硬幣的結(jié)果,不能觀測(cè)擲硬幣的過程。問如何估計(jì)三硬幣正面出現(xiàn)的概率,即三硬幣模型的參數(shù)。第七張,PPT共二十六頁(yè),創(chuàng)作于2022年6月解 三硬幣模型可以寫作y: 觀測(cè)變量,表示一次試驗(yàn)觀測(cè)的結(jié)果是1或0z: 隱變量,表示未觀測(cè)到的擲硬幣A的結(jié)果:=(,p,q)是模型

4、參數(shù)第八張,PPT共二十六頁(yè),創(chuàng)作于2022年6月將觀測(cè)數(shù)據(jù)表示為Y=(Y1,Y2,Yn)T,未觀測(cè)數(shù)據(jù)表示為Z=(Z1,Z2,Zn)T,則觀測(cè)數(shù)據(jù)的似然函數(shù)為即考慮求模型參數(shù)=(,p,q)的極大似然估計(jì),即 第九張,PPT共二十六頁(yè),創(chuàng)作于2022年6月EM算法首先選取參數(shù)的初值,記作 ,然后通過下面的步驟迭代計(jì)算參數(shù)的估計(jì)值,直至收斂為止。第i次迭代參數(shù)的估計(jì)值為 。EM算法的第i+1次迭代如下E步:計(jì)算在模型參數(shù) 下觀測(cè)數(shù)據(jù)yj 來自擲硬幣B的概率那么觀測(cè)數(shù)據(jù)yj 來自硬幣C的概率為1-(i+1)第十張,PPT共二十六頁(yè),創(chuàng)作于2022年6月M步:先寫出期望然后分別求導(dǎo),計(jì)算模型參數(shù)的新

5、估計(jì)值第十一張,PPT共二十六頁(yè),創(chuàng)作于2022年6月假設(shè)模型參數(shù)的初值取為由E步公式對(duì)yj=1與yj=0均有j(1)=0.5利用M步迭代公式,得到繼續(xù)計(jì)算j(2)=0.5,j=1,2,10繼續(xù)迭代,得于是得到模型參數(shù)的極大似然估計(jì):EM算法與初值的選擇有關(guān),選擇不同的初值可能得到不同的參數(shù)估計(jì)值。如果取初值那么得到的模型參數(shù)的極大似然估計(jì)是第十二張,PPT共二十六頁(yè),創(chuàng)作于2022年6月算法9.1(EM算法)輸入:觀測(cè)變量數(shù)據(jù)Y,隱變量數(shù)據(jù)Z,聯(lián)合概率分布P(Y,Z|),條件概率分布P(Z,Y|);輸出:模型參數(shù).(1)選擇參數(shù)的初值 ,開始迭代,參數(shù)的初值可以任意選擇,但需注意EM算法對(duì)初

6、值是敏感的;(2)E步:記 為第i次迭代參數(shù)的估計(jì)值,在第i+1次迭代得E步,計(jì)算這里, 是在給定觀測(cè)數(shù)據(jù)Y和當(dāng)前的參數(shù)估計(jì) 下隱變量數(shù)據(jù)Z的條件概率分布.注意, 的第一個(gè)變?cè)硎疽獦O大化的參數(shù),第2個(gè)變?cè)硎緟?shù)的當(dāng)前估計(jì)值.每次迭代實(shí)際在求Q函數(shù)及其極大;第十三張,PPT共二十六頁(yè),創(chuàng)作于2022年6月(3)M步:求使 極大化的,確定i+1次迭代得參數(shù)的估計(jì)值(4)重復(fù)第(2)步和第(3)步,直到收斂,這里給出停止迭代得條件,一般是對(duì)較小的正數(shù) ,若滿足則停止迭代.第十四張,PPT共二十六頁(yè),創(chuàng)作于2022年6月定義9.1(Q函數(shù))完全數(shù)據(jù)(觀測(cè)變量數(shù)據(jù)Y和隱變量數(shù)據(jù)Z)的對(duì)數(shù)似然函數(shù) 關(guān)

7、于在給定觀測(cè)數(shù)據(jù)Y和當(dāng)前參數(shù) 下對(duì)未觀測(cè)數(shù)據(jù)Z的條件概率分布 的期望稱為Q函數(shù),即第十五張,PPT共二十六頁(yè),創(chuàng)作于2022年6月9.1.2 EM算法的導(dǎo)出琴生( Jensen )不等式如果f是凸函數(shù),X是隨機(jī)變量,那么Ef(X)f(EX)特別地,如果f是嚴(yán)格凸函數(shù),Ef(X)f(EX)那么當(dāng)且僅當(dāng)p(x=EX)=1,也就是說X是常量。這里我們將f(EX)簡(jiǎn)寫為f(EX)Jensen不等式應(yīng)用于凹函數(shù)時(shí),不等號(hào)方向反向,也就是 Ef(X)f(EX)第十六張,PPT共二十六頁(yè),創(chuàng)作于2022年6月下面通過近似求解觀測(cè)數(shù)據(jù)的對(duì)數(shù)似然函數(shù)的極大化問題來導(dǎo)出EM算法,由此可以清楚地看出EM算法的作用。

8、假設(shè)在第i次迭代后的估計(jì)值是 .我們希望新估計(jì)值能使L()增加,即L()L( ),并逐步達(dá)到極大值.為此,考慮兩者的差:第十七張,PPT共二十六頁(yè),創(chuàng)作于2022年6月利用Jensen不等式得到其下界:令則 第十八張,PPT共二十六頁(yè),創(chuàng)作于2022年6月任何可以使 增大的,也可以使L()增大.為了使L()有盡可能大的增長(zhǎng),選擇 使 達(dá)到極大,即現(xiàn)在求 的表達(dá)式.省去對(duì)的極大化而言是常數(shù)的項(xiàng),有上式等價(jià)于EM算法的一次迭代,即求Q函數(shù)及其極大化.EM算法是通過不斷求解下界的極大化逼近求解對(duì)數(shù)似然函數(shù)極大化的算法.第十九張,PPT共二十六頁(yè),創(chuàng)作于2022年6月第二十張,PPT共二十六頁(yè),創(chuàng)作于

9、2022年6月9.1.3 EM算法在非監(jiān)督學(xué)習(xí)中的應(yīng)用有時(shí)訓(xùn)練數(shù)據(jù)只有輸入沒有對(duì)應(yīng)的輸出(x1,),(x2,),(xn,),從這樣的數(shù)據(jù)學(xué)習(xí)模型稱為非監(jiān)督學(xué)習(xí)問題EM算法可以用于生產(chǎn)模型的非監(jiān)督學(xué)習(xí)生成模型由聯(lián)合概率分布P(X,Y)表示,可以認(rèn)為非監(jiān)督學(xué)習(xí)訓(xùn)練數(shù)據(jù)是聯(lián)合概率分布產(chǎn)生的數(shù)據(jù).X為觀測(cè)數(shù)據(jù),Y為未觀測(cè)數(shù)據(jù).第二十一張,PPT共二十六頁(yè),創(chuàng)作于2022年6月9.2 EM算法的收斂性定理9.1 設(shè)P(Y|)為觀測(cè)數(shù)據(jù)的似然函數(shù), (i=1,2,)為EM算法得到的參數(shù)估計(jì)序列,則 (i=1,2,)為對(duì)應(yīng)的似然函數(shù)序列,則 是單調(diào)遞增的,即第二十二張,PPT共二十六頁(yè),創(chuàng)作于2022年6月證明由于取對(duì)數(shù)有由令于是對(duì)數(shù)似然函數(shù)可以寫成第二十三張,PPT共二十六頁(yè),創(chuàng)作于2022年6月只需證明右端為非負(fù)值即得出結(jié)果,由于使 達(dá)到極大,所以有其第二項(xiàng),由得出第二十四張,PPT共二十六頁(yè),創(chuàng)作于2022年6月定理9.2 設(shè)L()=logP(Y|)為觀測(cè)數(shù)據(jù)的對(duì)數(shù)似然函數(shù), (i=1,2,)為EM算法得到的參數(shù)估計(jì)序列, (i=1,2,)為對(duì)應(yīng)的對(duì)數(shù)似然函數(shù)序列.(1)如果 P(Y|)有上界,則收斂到某

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論