統(tǒng)計學習方法9—EM算法

??EM算法是一種迭代算法炫隶，是一種用于計算包含隱變量概率模型的最大似然估計方法淋叶，或極大后驗概率。EM即expectation maximization伪阶，期望最大化算法煞檩。

1. 極大似然估計

??在概率模型中，若已知事件服從的分布或者其他概率模型的參數(shù)栅贴，那么我們可以通過計算得到某事件發(fā)生的概率斟湃。而在估計中，這些變成了方向過程：已知一組數(shù)據(jù)發(fā)生的結(jié)果檐薯，相當于獲得了經(jīng)驗概率凝赛，通過這組數(shù)據(jù)假設模型服從什么分布注暗，再通過經(jīng)驗概率求解模型參數(shù)。
??比如統(tǒng)計學校學生身高服從的概率分布墓猎，抽樣1000人得到他們的身高數(shù)據(jù)捆昏，再假設身高服從正態(tài)分布，于是只需要求解 $u,\sigma$ 即可毙沾。剩下的問題就是如何確定這兩個參數(shù)骗卜，極大似然估計的思想就是求解在這兩個參數(shù)下，得到的這組樣本發(fā)生的概率最大的情況便是這兩個參數(shù)最有可能的取值左胞。而抽取每個樣本都是獨立的膨俐，于是可用每個段身高的樣本數(shù)量/總樣本數(shù)量作為單個發(fā)生的概率p，讓每個p最大化就是讓其乘積最大化罩句，于是得到最大似然函數(shù)
$L(\theta) = \prod _xp(x | \theta)$ ??再求解其關(guān)于 $\theta$ 的極大化問題便能得到一個對 $\theta$ 的估計
$\widehat \theta = argmaxL(\theta)$

2.EM算法

??上面是模型變量都是可觀測的情況，這種情況可以直接根據(jù)觀測到的樣本數(shù)據(jù)敛摘，使用極大似然估計對模型參數(shù)進行估計门烂。但若模型中含有隱變量的時候，就不能簡單的使用極大似然估計進行計算兄淫。EM算法就是針對含有隱變量的概率模型參數(shù)的極大似然估計方法屯远。
例子：
??假設三枚硬幣，記為A捕虽、B慨丐、C，它們正面向上的概率分別為n泄私、p房揭、q。實驗如下：先拋A晌端，根據(jù)A的結(jié)果選擇B或者C再次拋捅暴，將這次正面向上的結(jié)果記為1，反面記為0咧纠，其中A正面向上則選擇B蓬痒，反面則選擇C。經(jīng)過n次實驗后得到n個觀測值漆羔，根據(jù)這n個觀測值估計n梧奢、p、q的參數(shù)值演痒。實驗過程中只能觀測到最后結(jié)果亲轨，并不能觀察實驗過程，也就是A的結(jié)果是未知的鸟顺。該模型可以表示如下
$P(y|\theta) = \sum_zP(y,z|\theta) = \sum_zP(z|\theta)P(y|z,\theta)$ ??其中y表示隨機變量Y的觀測值瓶埋，表示該次結(jié)果是1或0。z代表隱變量，表示模型中未能觀測到的A的結(jié)果养筒， $\theta=（n,p,q)$ 是模型參數(shù)曾撤。其中Y是不完全數(shù)據(jù)，Y+Z是完全數(shù)據(jù)晕粪。
??若是沒有隱變量Z挤悉，那么可直接使用對數(shù)極大似然函數(shù)估計
$\widehat \theta=arg\underset \theta {max}L(\theta)=arg\underset \theta {max}\sum_y logP(y|\theta)$ ??加入隱變量后，對數(shù)極大似然函數(shù)變?yōu)?br> $L(\theta,z)=\sum_ylog\sum_zP(y,z|\theta)$ ??求解
$\widehat \theta,z=arg\underset {\theta,z} {max}L(\theta,z)$ ??按照極大似然估計中的方法巫湘，似乎應該對 $\theta,z$ 求導然后令其為0解方程組装悲，然后注意此時的 $L(\theta,z)$ 函數(shù)，log內(nèi)含有求和運算尚氛，若是直接求導計算十分困難诀诊，因此退而求其次，既然要極大化 $L(\theta,z)$ 阅嘶，就先找到一個它的下界属瓣，再想辦法提高這個下界，同樣能達到極大化L的效果讯柔。使用Jense不等式對似然函數(shù)進行放縮抡蛙。

Jense不等式（琴生不等式）

??凸函數(shù)：是定義在實數(shù)域上的函數(shù)，如果對于任意的實數(shù)魂迄，都有：
$f''\geqslant 0$
?? 則該函數(shù)是凸函數(shù)粗截。
??當函數(shù)是凸函數(shù)的時候，Jense不等式的含義是函數(shù)的期望大于等于期望的函數(shù)（凹函數(shù)相反）捣炬。圖下圖所示

jense不等式

??二維情況下可用凸函數(shù)定義來解釋熊昌，當一個函數(shù)是凸函數(shù)的時候，它滿足
??左邊其實相當于其變量x先求期望后帶入函數(shù)湿酸，右邊是先求函數(shù)值再計算函數(shù)值的期望浴捆，也就是
??再回到中來，目的是為了將對數(shù)函數(shù)中的和項去掉稿械，便可利用jense不等式的性質(zhì)选泻，將期望的函數(shù)變?yōu)楹瘮?shù)的期望。先進行放縮
??其中最后一步用到了Jense不等式美莫，因為對數(shù)函數(shù)是凹函數(shù)页眯，所以不等號反了過來，,此處??并且所添加的滿足??這是根據(jù)第三類Jense不等式的條件設定的厢呵，不同系數(shù)的加權(quán)求和期望只要滿足系數(shù)之和為1就能使用Jense不等式窝撵。
??所以得到結(jié)論，的加權(quán)平均就是的一個下界襟铭。這便是EM算法中E（期望）的來由碌奉。
??目前還是未知的短曾，需要根據(jù)一些條件來選擇一個合適的函數(shù)，再次強調(diào)最終目的是極大化似然函數(shù)赐劣，現(xiàn)在我們得到了似然函數(shù)的一個下界嫉拐，一個想法就是讓這個下界去更好的逼近似然函數(shù)的真實值，下界是根據(jù)不等式放縮后得到的魁兼，那么當不等式取等號的時候便是最接近原函數(shù)的時候婉徘。回憶Jense不等式咐汞，顯然當為常數(shù)的時候不等式成立盖呼。即
??既然要確定的是，不妨設為常數(shù)化撕，由上式得

??將c帶入x

??第二步用到邊緣概率几晤，第三步條件概率。至此植阴，我們得出了Q(z)的表達式蟹瘾，Q(z)是已知樣本觀測和模型參數(shù)下的隱變量的分布。那么已經(jīng)完成了E步墙贱，對對數(shù)似然函數(shù)下界的期望的表示
??接下來需要做的便是極大化這個似然函數(shù)，也就是M步贱傀。這一步中將視為常數(shù)惨撇，對進行極大化，去掉常數(shù)項后