算法及其推廣

關(guān)于算法及其推廣第1頁，講稿共26頁，2023年5月2日，星期三EM算法是一種迭代算法，1977年由Dempster等人總結(jié)提出，用于含有隱變量的概率模型參數(shù)的極大似然估計(jì)，或極大后驗(yàn)概率估計(jì)。EM算法的每次迭代由兩步組成：E步，求期望；M步，求極大。所以這一算法稱為期望極大算法（ExpectationMaximization）,簡稱EM算法。第2頁，講稿共26頁，2023年5月2日，星期三極大似然估計(jì)極大似然估計(jì)是概率論在統(tǒng)計(jì)學(xué)中的應(yīng)用，它是參數(shù)估計(jì)的方法之一。說的是已知某個(gè)隨機(jī)樣本滿足某種概率分布，但是其中具體的參數(shù)不清楚，參數(shù)估計(jì)就是通過若干次實(shí)驗(yàn)，觀察其結(jié)果，利用結(jié)果推出參數(shù)的大概值。第3頁，講稿共26頁，2023年5月2日，星期三極大似然估計(jì)似然函數(shù)：已知樣本集X,X是通過概率密度p(x|θ)抽取。樣本集X中各個(gè)樣本的聯(lián)合概率：為了便于分析，由于L(θ)是連乘的，還可以定義對(duì)數(shù)似然函數(shù)，將其變成連加的：第4頁，講稿共26頁，2023年5月2日，星期三極大似然估計(jì)求極值可以轉(zhuǎn)換為以下方程：θ的極大似然估計(jì)量表示為：第5頁，講稿共26頁，2023年5月2日，星期三9.1EM算法的引入9.1.1 EM算法9.1.2 EM算法的導(dǎo)出9.1.3 EM算法在非監(jiān)督學(xué)習(xí)中的應(yīng)用9.2EM算法的收斂性第6頁，講稿共26頁，2023年5月2日，星期三9.1.1EM算法例9.1（三硬幣模型）假設(shè)有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ù)。第7頁，講稿共26頁，2023年5月2日，星期三解三硬幣模型可以寫作y:觀測(cè)變量，表示一次試驗(yàn)觀測(cè)的結(jié)果是1或0z:隱變量，表示未觀測(cè)到的擲硬幣A的結(jié)果θ：θ=(π,p,q)是模型參數(shù)第8頁，講稿共26頁，2023年5月2日，星期三將觀測(cè)數(shù)據(jù)表示為Y=(Y1,Y2,…,Yn)T,未觀測(cè)數(shù)據(jù)表示為Z=(Z1,Z2,…,Zn)T,則觀測(cè)數(shù)據(jù)的似然函數(shù)為

即考慮求模型參數(shù)θ=(π,p,q)的極大似然估計(jì)，即

第9頁，講稿共26頁，2023年5月2日，星期三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)第10頁，講稿共26頁，2023年5月2日，星期三M步：先寫出期望然后分別求導(dǎo)，計(jì)算模型參數(shù)的新估計(jì)值第11頁，講稿共26頁，2023年5月2日，星期三假設(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ì)是第12頁，講稿共26頁，2023年5月2日，星期三算法9.1（EM算法）輸入：觀測(cè)變量數(shù)據(jù)Y，隱變量數(shù)據(jù)Z，聯(lián)合概率分布P(Y,Z|θ)，條件概率分布P(Z,Y|θ)；輸出：模型參數(shù)θ.（1）選擇參數(shù)的初值，開始迭代，參數(shù)的初值可以任意選擇，但需注意EM算法對(duì)初值是敏感的；（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ù)及其極大；第13頁，講稿共26頁，2023年5月2日，星期三（3）M步：求使極大化的θ，確定i+1次迭代得參數(shù)的估計(jì)值（4）重復(fù)第（2）步和第（3）步，直到收斂，這里給出停止迭代得條件，一般是對(duì)較小的正數(shù)，若滿足

則停止迭代.第14頁，講稿共26頁，2023年5月2日，星期三定義9.1（Q函數(shù)）完全數(shù)據(jù)（觀測(cè)變量數(shù)據(jù)Y和隱變量數(shù)據(jù)Z）的對(duì)數(shù)似然函數(shù)關(guān)于在給定觀測(cè)數(shù)據(jù)Y和當(dāng)前參數(shù)下對(duì)未觀測(cè)數(shù)據(jù)Z的條件概率分布的期望稱為Q函數(shù)，即第15頁，講稿共26頁，2023年5月2日，星期三9.1.2EM算法的導(dǎo)出琴生（Jensen）不等式如果f是凸函數(shù)，X是隨機(jī)變量，那么

E[f(X)]≥f(EX)特別地，如果f是嚴(yán)格凸函數(shù),E[f(X)]≥f(EX)那么當(dāng)且僅當(dāng)p(x=E[X])=1，也就是說X是常量。這里我們將f(E[X])簡寫為f(EX)Jensen不等式應(yīng)用于凹函數(shù)時(shí)，不等號(hào)方向反向，也就是E[f(X)]≤f(EX)第16頁，講稿共26頁，2023年5月2日，星期三下面通過近似求解觀測(cè)數(shù)據(jù)的對(duì)數(shù)似然函數(shù)的極大化問題來導(dǎo)出EM算法，由此可以清楚地看出EM算法的作用。假設(shè)在第i次迭代后θ的估計(jì)值是.我們希望新估計(jì)值θ能使L(θ)增加，即L(θ)>L(),并逐步達(dá)到極大值.為此，考慮兩者的差：第17頁，講稿共26頁，2023年5月2日，星期三利用Jensen不等式得到其下界：令則

第18頁，講稿共26頁，2023年5月2日，星期三任何可以使增大的θ，也可以使L(θ)增大.為了使L(θ)有盡可能大的增長，選擇

使達(dá)到極大，即現(xiàn)在求的表達(dá)式.省去對(duì)θ的極大化而言是常數(shù)的項(xiàng)，有上式等價(jià)于EM算法的一次迭代，即求Q函數(shù)及其極大化.EM算法是通過不斷求解下界的極大化逼近求解對(duì)數(shù)似然函數(shù)極大化的算法.第19頁，講稿共26頁，2023年5月2日，星期三第20頁，講稿共26頁，2023年5月2日，星期三9.1.3EM算法在非監(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ù).第21頁，講稿共26頁，2023年5月2日，星期三9.2EM算法的收斂性定理9.1設(shè)P(Y|θ)為觀測(cè)數(shù)據(jù)的似然函數(shù)，(i=1,2,…)為EM算法得到的參數(shù)估計(jì)序列，則(i=1,2,…)為對(duì)應(yīng)的似然函數(shù)序列，則是單調(diào)遞增的，即第22頁，講稿共26頁，2023年5月2日，星期三證明由于取對(duì)數(shù)有由令于是對(duì)數(shù)似然函數(shù)可以寫成第23頁，講稿共26頁，2023年5月2日，星期三只需證明右端為非負(fù)值即得出結(jié)果，由于使達(dá)到極大，所以有

其第二項(xiàng)，由

得出第24頁，講稿共26頁，2023年5月2日，星期三定理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|θ)有上界，則收斂到某一值L*；（2