算法及其推廣

關于算法及其推廣第一頁，共二十六頁，2022年，8月28日EM算法是一種迭代算法，1977年由Dempster等人總結提出，用于含有隱變量的概率模型參數的極大似然估計，或極大后驗概率估計。EM算法的每次迭代由兩步組成：E步，求期望；M步，求極大。所以這一算法稱為期望極大算法（ExpectationMaximization）,簡稱EM算法。第二頁，共二十六頁，2022年，8月28日極大似然估計極大似然估計是概率論在統計學中的應用，它是參數估計的方法之一。說的是已知某個隨機樣本滿足某種概率分布，但是其中具體的參數不清楚，參數估計就是通過若干次實驗，觀察其結果，利用結果推出參數的大概值。第三頁，共二十六頁，2022年，8月28日極大似然估計似然函數：已知樣本集X,X是通過概率密度p(x|θ)抽取。樣本集X中各個樣本的聯合概率：為了便于分析，由于L(θ)是連乘的，還可以定義對數似然函數，將其變成連加的：第四頁，共二十六頁，2022年，8月28日極大似然估計求極值可以轉換為以下方程：θ的極大似然估計量表示為：第五頁，共二十六頁，2022年，8月28日9.1EM算法的引入9.1.1 EM算法9.1.2 EM算法的導出9.1.3 EM算法在非監(jiān)督學習中的應用9.2EM算法的收斂性第六頁，共二十六頁，2022年，8月28日9.1.1EM算法例9.1（三硬幣模型）假設有3枚硬幣，分別記作A,B,C.這些硬幣正面出現的概率分別是π,p,q.進行如下擲硬幣試驗：先擲硬幣A，根據其結果選出硬幣B或硬幣C，正面選硬幣B，反面選硬幣C；然后擲選出的硬幣，擲硬幣的結果，出現正面記作1，出現反面記作0；獨立地重復n次試驗（這里，n=10），觀測結果如下：1,1,0,1,0,0,1,0,1,1假設只能觀測到擲硬幣的結果，不能觀測擲硬幣的過程。問如何估計三硬幣正面出現的概率，即三硬幣模型的參數。第七頁，共二十六頁，2022年，8月28日解三硬幣模型可以寫作y:觀測變量，表示一次試驗觀測的結果是1或0z:隱變量，表示未觀測到的擲硬幣A的結果θ：θ=(π,p,q)是模型參數第八頁，共二十六頁，2022年，8月28日將觀測數據表示為Y=(Y1,Y2,…,Yn)T,未觀測數據表示為Z=(Z1,Z2,…,Zn)T,則觀測數據的似然函數為

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

第九頁，共二十六頁，2022年，8月28日EM算法首先選取參數的初值，記作

，然后通過下面的步驟迭代計算參數的估計值，直至收斂為止。第i次迭代參數的估計值為。EM算法的第i+1次迭代如下E步：計算在模型參數下觀測數據yj來自擲硬幣B的概率

那么觀測數據yj

來自硬幣C的概率為1-μ(i+1)第十頁，共二十六頁，2022年，8月28日M步：先寫出期望然后分別求導，計算模型參數的新估計值第十一頁，共二十六頁，2022年，8月28日假設模型參數的初值取為由E步公式對yj=1與yj=0均有μj(1)=0.5利用M步迭代公式，得到繼續(xù)計算μj(2)=0.5，j=1,2,…,10繼續(xù)迭代，得于是得到模型參數θ的極大似然估計：

EM算法與初值的選擇有關，選擇不同的初值可能得到不同的參數估計值。如果取初值

那么得到的模型參數的極大似然估計是第十二頁，共二十六頁，2022年，8月28日算法9.1（EM算法）輸入：觀測變量數據Y，隱變量數據Z，聯合概率分布P(Y,Z|θ)，條件概率分布P(Z,Y|θ)；輸出：模型參數θ.（1）選擇參數的初值，開始迭代，參數的初值可以任意選擇，但需注意EM算法對初值是敏感的；（2）E步：記為第i次迭代參數θ的估計值，在第i+1次迭代得E步，計算這里，是在給定觀測數據Y和當前的參數估計下隱變量數據Z的條件概率分布.注意，的第一個變元表示要極大化的參數，第2個變元表示參數的當前估計值.每次迭代實際在求Q函數及其極大；第十三頁，共二十六頁，2022年，8月28日（3）M步：求使極大化的θ，確定i+1次迭代得參數的估計值（4）重復第（2）步和第（3）步，直到收斂，這里給出停止迭代得條件，一般是對較小的正數，若滿足

則停止迭代.第十四頁，共二十六頁，2022年，8月28日定義9.1（Q函數）完全數據（觀測變量數據Y和隱變量數據Z）的對數似然函數關于在給定觀測數據Y和當前參數下對未觀測數據Z的條件概率分布的期望稱為Q函數，即第十五頁，共二十六頁，2022年，8月28日9.1.2EM算法的導出琴生（Jensen）不等式如果f是凸函數，X是隨機變量，那么

E[f(X)]≥f(EX)特別地，如果f是嚴格凸函數,E[f(X)]≥f(EX)那么當且僅當p(x=E[X])=1，也就是說X是常量。這里我們將f(E[X])簡寫為f(EX)Jensen不等式應用于凹函數時，不等號方向反向，也就是E[f(X)]≤f(EX)第十六頁，共二十六頁，2022年，8月28日下面通過近似求解觀測數據的對數似然函數的極大化問題來導出EM算法，由此可以清楚地看出EM算法的作用。假設在第i次迭代后θ的估計值是.我們希望新估計值θ能使L(θ)增加，即L(θ)>L(),并逐步達到極大值.為此，考慮兩者的差：第十七頁，共二十六頁，2022年，8月28日利用Jensen不等式得到其下界：令則

第十八頁，共二十六頁，2022年，8月28日任何可以使增大的θ，也可以使L(θ)增大.為了使L(θ)有盡可能大的增長，選擇

使達到極大，即現在求的表達式.省去對θ的極大化而言是常數的項，有上式等價于EM算法的一次迭代，即求Q函數及其極大化.EM算法是通過不斷求解下界的極大化逼近求解對數似然函數極大化的算法.第十九頁，共二十六頁，2022年，8月28日第二十頁，共二十六頁，2022年，8月28日9.1.3EM算法在非監(jiān)督學習中的應用有時訓練數據只有輸入沒有對應的輸出{(x1,·),(x2,·),…,(xn,·)}，從這樣的數據學習模型稱為非監(jiān)督學習問題EM算法可以用于生產模型的非監(jiān)督學習生成模型由聯合概率分布P(X,Y)表示，可以認為非監(jiān)督學習訓練數據是聯合概率分布產生的數據.X為觀測數據，Y為未觀測數據.第二十一頁，共二十六頁，2022年，8月28日9.2EM算法的收斂性定理9.1設P(Y|θ)為觀測數據的似然函數，(i=1,2,…)為EM算法得到的參數估計序列，則(i=1,2,…)為對應的似然函數序列，則是單調遞增的，即第二十二頁，共二十六頁，2022年，8月28日證明由于取對數有由令于是對數似然函數可以寫成第二十三頁，共二十六頁，2022年，8月28日只需證明右端為非負值即得出結果，由于使達到極大，所以有

其第二項，由

得出第二十四頁，共二十六頁，2022年，8月28日定理9.2設L(θ)=logP(Y|θ)為觀測數據的對數似然函數，(i=1,2,…)為EM算法得到的參數估計序列，(i=1,2,…)為對應的對數似然函數序列.（1）如果P(Y|θ)有上界，則收斂到某一值L*；（2）