人工智能經(jīng)典電子書(shū)4.貝葉斯分類(lèi)器-EM算法

EM(ExpectationMaximization)貝葉斯分類(lèi)器學(xué)習(xí)大綱8月25日：1.初識(shí)貝葉斯分類(lèi)器2.最大似然估計(jì)和貝葉斯參數(shù)估計(jì)9月1日：3.貝葉斯網(wǎng)絡(luò)與樸素貝葉斯分類(lèi)器實(shí)戰(zhàn)9月8日：4.EM算法實(shí)戰(zhàn)outlineEM算法簡(jiǎn)介EM算法引例EM算法步驟EM算法的原理EM算法的應(yīng)用EMintroductionEM算法是一種迭代算法，1977年由Dempster等人總結(jié)提出，用于含有隱變量的概率模型參數(shù)的極大似然估計(jì)，或極大后驗(yàn)概率估計(jì)。EM算法的每次迭代由兩步組成：E步，求期望（Expectation）；M步，求極大（Maximization）。所以這一算法稱(chēng)為期望極大算法極大似然估計(jì)

極大似然估計(jì)是一種常用的參數(shù)估計(jì)方法，它是以觀測(cè)值出現(xiàn)的概率最大作為準(zhǔn)則。關(guān)于極大似然估計(jì)，我們有以下直觀的想法：現(xiàn)在已經(jīng)取到樣本值了，這表明取到這一樣本的概率L(θ)比較大。我們自然不會(huì)考慮那些不能使樣本出現(xiàn)的θ作為估計(jì)值，再者，如果已知當(dāng)θ=θ(0)是使L(θ)取很大值，而Θ中的其他θ的值使L(θ)取值很小，我們自然認(rèn)為取θ(0)作為未知參數(shù)θ的估計(jì)值較為合理。

極大似然估計(jì)(MLE)獨(dú)立同分布(IID)的數(shù)據(jù)其概率密度函數(shù)為似然函數(shù)定義為對(duì)數(shù)似然函數(shù)定義為的極大似然估計(jì)為極大似然估計(jì)存在著問(wèn)題是：1.對(duì)于許多具體問(wèn)題不能構(gòu)造似然函數(shù)解析表達(dá)式2.似然函數(shù)的表達(dá)式過(guò)于復(fù)雜而導(dǎo)致求解方程組非常困難

正是在這種情況下，人們提出了EM算法。EM算法主要用于非完全數(shù)據(jù)參數(shù)估計(jì)，它是通過(guò)假設(shè)隱變量的存在，極大化地簡(jiǎn)化了似然函數(shù)方程，從而解決了方程求解問(wèn)題。極大似然估計(jì)與EM算法的關(guān)系計(jì)算極大似然估計(jì)(maximumlikelihood

estimate,

MLE)，需要求似然函數(shù)的極值.解析法:如求正態(tài)分布均值和方差的MLE值計(jì)算：如高斯混合模型EM算法完整數(shù)據(jù)觀測(cè)數(shù)據(jù)：觀測(cè)到的隨機(jī)變量的IID樣本缺失數(shù)據(jù)：未觀測(cè)到的隨機(jī)變量的值完整數(shù)據(jù)：包含觀測(cè)到的隨機(jī)變量和未觀測(cè)到的隨機(jī)變量的數(shù)據(jù)，EMintroduction（三硬幣模型）

假設(shè)有3枚硬幣，分別記作A,B,C。這些硬幣正面出現(xiàn)的概率概率分別是a,b,c。進(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è)到擲硬幣的過(guò)程。問(wèn)如何估計(jì)三硬幣正面出現(xiàn)的概率，即三硬幣模型的參數(shù)。三硬幣模型可以寫(xiě)作這里，隨機(jī)變量y是觀測(cè)變量，表示一次試驗(yàn)觀測(cè)的結(jié)果是1或0；隨機(jī)變量z是隱變量，表示未觀測(cè)到的擲硬幣A的結(jié)果，θ=(a,b,c)是模型參數(shù)。注意，隨機(jī)變量y的數(shù)據(jù)可以觀測(cè)，隨機(jī)變量z的數(shù)據(jù)不可觀測(cè)。

將觀測(cè)數(shù)據(jù)表示為未觀測(cè)數(shù)據(jù)表示為

則觀測(cè)數(shù)據(jù)的似然函數(shù)為

即

考慮求模型參數(shù)θ=(a,b,c)的極大似然估計(jì)，即這個(gè)問(wèn)題沒(méi)有解析解，只能通過(guò)迭代的方法求解。EM算法就是可以用于求解這個(gè)問(wèn)題的一種迭代算法，下面給出針對(duì)以上問(wèn)題的EM算法。EM算法首先選取參數(shù)的初值，記作然后通過(guò)下面的步驟迭代計(jì)算參數(shù)的估計(jì)值，直至收斂為止。第i次迭代參數(shù)的估計(jì)值為EM算法的第i+1次迭代如下。

E步：計(jì)算在模型參數(shù)下觀測(cè)數(shù)據(jù)來(lái)自擲硬幣B的概率(1)計(jì)算似然函數(shù)的期望

（2）

M步：求似然函數(shù)的極大值

計(jì)算模型參數(shù)的新估計(jì)值：（3）（4）

（5）進(jìn)行數(shù)字計(jì)算。假設(shè)模型參數(shù)的初始值取為由式（1），對(duì)y=0與y=1均有利用迭代公式(3)-(5)，得到由式（1）,

j=1,2,...,10繼續(xù)迭代，得于是參數(shù)模型的極大似然估計(jì)EMsteps選擇模型參數(shù)的初值，開(kāi)始迭代；E步：記為第i次迭代參數(shù)θ的估計(jì)值，在第i+1次迭代的E步，定義Q函數(shù)并計(jì)算這里，Q函數(shù)定義為完全數(shù)據(jù)的對(duì)數(shù)似然函數(shù)在給定觀測(cè)數(shù)據(jù)Y和當(dāng)前的參數(shù)下對(duì)未觀測(cè)數(shù)據(jù)Z的條件概率分布的期望；通過(guò)求期望，去掉了完整似然函數(shù)中的變量Z。即EM的E步。M步：求使極大化的θ，確定第i+1次迭代的參數(shù)的估計(jì)值重復(fù)E、M兩步，直到收斂。每次參數(shù)更新會(huì)增加非完整似然值反復(fù)迭代后，會(huì)收斂到似然的局部最大值EM算法的原理EM算法是一種解決存在隱含變量?jī)?yōu)化問(wèn)題的有效方法。它的具體思想是：既然不能直接最大化參數(shù)似然函數(shù)L，我們可以不斷地建立參數(shù)似然函數(shù)L的下界（E步），然后優(yōu)化下界（M步）。利用琴生不等式得到似然函數(shù)的下界：（6）（7）（8）對(duì)于每一個(gè)樣例i，讓Qi表示該樣例隱含變量z的某種分布，Qi滿足的條件是：這個(gè)過(guò)程可以看作是對(duì)L（θ）求了下界。對(duì)于的選擇有很多種，哪種更好呢？假設(shè)θ已經(jīng)給定，那么L（θ）的值就決定于和。我們可以通過(guò)調(diào)整這兩個(gè)概率使下界不斷上升，以逼近L（θ）的真實(shí)值，那么什么時(shí)候算是調(diào)整好了呢？當(dāng)不等式變成等式時(shí)，說(shuō)明我們調(diào)整后的概率能夠等價(jià)于L（θ）了。根據(jù)琴生不等式，等式成立的條件是隨機(jī)變量取值為常數(shù)值，故可得到：c為常數(shù)，不依賴(lài)于。我們知道，那么就有（多個(gè)等式分子分母相加不變，這個(gè)認(rèn)為每個(gè)樣例的兩個(gè)概率比值都是c），那么有：將代入（8）式，可以發(fā)現(xiàn)L（θ）的下界函數(shù)就是我們前面定義的函數(shù)。這一步是E步，建立了L（θ）的下界。接下來(lái)是M步，就是在給定后，調(diào)整θ，去極大化L（θ）的下界，那么怎么確保EM收斂呢？又如何確保每次迭代都能使極大似然估計(jì)單調(diào)增加呢？下述兩個(gè)定理表明了利用EM算法所得到的估計(jì)序列具有良好的收斂性，且其收斂到p(θ丨Y)的最大值。定理1：設(shè)P（Y丨θ）為觀測(cè)數(shù)據(jù)的似然函數(shù)，（i=1,2...）為EM算法得到的參數(shù)估計(jì)序列，（i=1,2...）為對(duì)應(yīng)的似然函數(shù)序列，則是單調(diào)遞增的，即

保證了EM算法的每次迭代都使似然函數(shù)增大或達(dá)到局部極值定理2：設(shè)為觀測(cè)數(shù)據(jù)的對(duì)數(shù)似然函數(shù)（i=1,2...）為EM算法得到的參數(shù)估計(jì)序列，（i=1,2...）為對(duì)應(yīng)的對(duì)數(shù)似然序列。（1）如果P（Y丨θ）有上界，則收斂到某一值（2）在函數(shù)與滿足一定條件下，由EM算法得到的參數(shù)估計(jì)序列的收斂值是的穩(wěn)定點(diǎn)。保證了EM算法所得到的估計(jì)序列具有良好的收斂性，且其收斂到p(θ丨Y)的最大值。EM算法的另一種理解坐標(biāo)上升法

圖中的直線式迭代優(yōu)化的路徑，可以看到每一步都會(huì)向最優(yōu)值前進(jìn)一步，而且前進(jìn)路線是平行于坐標(biāo)軸的，因?yàn)槊恳徊街粌?yōu)化一個(gè)變量。這猶如在x-y坐標(biāo)系中找一個(gè)曲線的極值，然而曲線函數(shù)不能直接求導(dǎo)，因此什么梯度下降方法就不適用了。但固定一個(gè)變量后，另外一個(gè)可以通過(guò)求導(dǎo)得到，因此可以使用坐標(biāo)上升法，一次固定一個(gè)變量，對(duì)另外的求極值，最后逐步逼近極值。對(duì)應(yīng)到EM上，E步：固定θ，優(yōu)化Q；M步：固定Q，優(yōu)化θ；交替將極值推向最大。EM算法的幾點(diǎn)說(shuō)明step1：參數(shù)的初值可以任意選擇，但需要注意EM算法對(duì)初值是敏感的。step2：E步求Q函數(shù)。Q函數(shù)式中Z是未觀測(cè)數(shù)據(jù)，Y是觀測(cè)數(shù)據(jù)。注意，的第一個(gè)變?cè)硎疽獦O大化的參數(shù)，第二個(gè)變?cè)硎緟?shù)的當(dāng)前估計(jì)值。每次迭代實(shí)際在求Q函數(shù)及其