從最大似然到EM算法淺解

機(jī)器學(xué)習(xí)十大算法之一：EM算法。能評得上十大之一，讓人聽起來覺得挺NB的。什么是NB啊，我們一般說某個(gè)人很NB，是因?yàn)樗芙鉀Q一些別人解決不了的問題。神為什么是神，因?yàn)樯衲茏龊芏嗳俗霾涣说氖?。那么EM算法能解決什么問題呢？或者說EM算法是因?yàn)槭裁炊鴣淼竭@個(gè)世界上，還吸引了那么多世人的目光。

我希望自己能通俗地把它理解或者說明白，但是，EM這個(gè)問題感覺真的不太好用通俗的語言去說明白，因?yàn)樗芎唵?，又很?fù)雜。簡單在于它的思想，簡單在于其僅包含了兩個(gè)步驟就能完成強(qiáng)大的功能，復(fù)雜在于它的數(shù)學(xué)推理涉及到比較繁雜的概率公式等。如果只講簡單的，就丟失了EM算法的精髓，如果只講數(shù)學(xué)推理，又過于枯燥和生澀，但另一方面，想把兩者結(jié)合起來也不是件容易的事。所以，我也沒法期待我能把它講得怎樣。希望各位不吝指導(dǎo)。

一、最大似然

扯了太多，得入正題了。假設(shè)我們遇到的是下面這樣的問題：

假設(shè)我們需要調(diào)查我們學(xué)校的男生和女生的身高分布。你怎么做??？你說那么多人不可能一個(gè)一個(gè)去問吧，肯定是抽樣了。假設(shè)你在校園里隨便地活捉了100個(gè)男生和100個(gè)女生。他們共200個(gè)人（也就是200個(gè)身高的樣本數(shù)據(jù)，為了方便表示，下面，我說“人”的意思就是對應(yīng)的身高）都在教室里面了。那下一步怎么辦??？你開始喊：“男的左邊，女的右邊，其他的站中間！”。然后你就先統(tǒng)計(jì)抽樣得到的100個(gè)男生的身高。假設(shè)他們的身高是服從高斯分布的。但是這個(gè)分布的均值u和方差?2我們不知道，這兩個(gè)參數(shù)就是我們要估計(jì)的。記作θ=[u, ?]T。

用數(shù)學(xué)的語言來說就是：在學(xué)校那么多男生（身高）中，我們獨(dú)立地按照概率密度p(x|θ)抽取100了個(gè)（身高），組成樣本集X，我們想通過樣本集X來估計(jì)出未知參數(shù)θ。這里概率密度p(x|θ)我們知道了是高斯分布N(u,?)的形式，其中的未知參數(shù)是θ=[u, ?]T。抽到的樣本集是X={x1,x2,…,xN}，其中xi表示抽到的第i個(gè)人的身高，這里N就是100，表示抽到的樣本個(gè)數(shù)。

由于每個(gè)樣本都是獨(dú)立地從p(x|θ)中抽取的，換句話說這100個(gè)男生中的任何一個(gè)，都是我隨便捉的，從我的角度來看這些男生之間是沒有關(guān)系的。那么，我從學(xué)校那么多男生中為什么就恰好抽到了這100個(gè)人呢？抽到這100個(gè)人的概率是多少呢？因?yàn)檫@些男生（的身高）是服從同一個(gè)高斯分布p(x|θ)的。那么我抽到男生A（的身高）的概率是p(xA|θ)，抽到男生B的概率是p(xB|θ)，那因?yàn)樗麄兪仟?dú)立的，所以很明顯，我同時(shí)抽到男生A和男生B的概率是p(xA|θ)* p(xB|θ)，同理，我同時(shí)抽到這100個(gè)男生的概率就是他們各自概率的乘積了。用數(shù)學(xué)家的口吻說就是從分布是p(x|θ)的總體樣本中抽取到這100個(gè)樣本的概率，也就是樣本集X中各個(gè)樣本的聯(lián)合概率，用下式表示：

這個(gè)概率反映了，在概率密度函數(shù)的參數(shù)是θ時(shí)，得到X這組樣本的概率。因?yàn)檫@里X是已知的，也就是說我抽取到的這100個(gè)人的身高可以測出來，也就是已知的了。而θ是未知了，則上面這個(gè)公式只有θ是未知數(shù)，所以它是θ的函數(shù)。這個(gè)函數(shù)放映的是在不同的參數(shù)θ取值下，取得當(dāng)前這個(gè)樣本集的可能性，因此稱為參數(shù)θ相對于樣本集X的似然函數(shù)（likehood function）。記為L(θ)。

這里出現(xiàn)了一個(gè)概念，似然函數(shù)。還記得我們的目標(biāo)嗎？我們需要在已經(jīng)抽到這一組樣本X的條件下，估計(jì)參數(shù)θ的值。怎么估計(jì)呢？似然函數(shù)有啥用呢？那咱們先來了解下似然的概念。

直接舉個(gè)例子：

某位同學(xué)與一位獵人一起外出打獵，一只野兔從前方竄過。只聽一聲槍響，野兔應(yīng)聲到下，如果要你推測，這一發(fā)命中的子彈是誰打的？你就會(huì)想，只發(fā)一槍便打中，由于獵人命中的概率一般大于這位同學(xué)命中的概率，看來這一槍是獵人射中的。

這個(gè)例子所作的推斷就體現(xiàn)了極大似然法的基本思想。

再例如：下課了，一群男女同學(xué)分別去廁所了。然后，你閑著無聊，想知道課間是男生上廁所的人多還是女生上廁所的人比較多，然后你就跑去蹲在男廁和女廁的門口。蹲了五分鐘，突然一個(gè)美女走出來，你狂喜，跑過來告訴我，課間女生上廁所的人比較多，你要不相信你可以進(jìn)去數(shù)數(shù)。呵呵，我才沒那么蠢跑進(jìn)去數(shù)呢，到時(shí)還不得上頭條。我問你是怎么知道的。你說：“5分鐘了，出來的是女生，女生啊，那么女生出來的概率肯定是最大的了，或者說比男生要大，那么女廁所的人肯定比男廁所的人多”?？吹搅藳]，你已經(jīng)運(yùn)用最大似然估計(jì)了。你通過觀察到女生先出來，那么什么情況下，女生會(huì)先出來呢？肯定是女生出來的概率最大的時(shí)候了，那什么時(shí)候女生出來的概率最大啊，那肯定是女廁所比男廁所多人的時(shí)候了，這個(gè)就是你估計(jì)到的參數(shù)了。

從上面這兩個(gè)例子，你得到了什么結(jié)論？

回到男生身高那個(gè)例子。在學(xué)校那么男生中，我一抽就抽到這100個(gè)男生（表示身高），而不是其他人，那是不是表示在整個(gè)學(xué)校中，這100個(gè)人（的身高）出現(xiàn)的概率最大啊。那么這個(gè)概率怎么表示？哦，就是上面那個(gè)似然函數(shù)L(θ)。所以，我們就只需要找到一個(gè)參數(shù)θ，其對應(yīng)的似然函數(shù)L(θ)最大，也就是說抽到這100個(gè)男生（的身高）概率最大。這個(gè)叫做θ的最大似然估計(jì)量，記為：

有時(shí)，可以看到L(θ)是連乘的，所以為了便于分析，還可以定義對數(shù)似然函數(shù)，將其變成連加的：

好了，現(xiàn)在我們知道了，要求θ，只需要使θ的似然函數(shù)L(θ)極大化，然后極大值對應(yīng)的θ就是我們的估計(jì)。這里就回到了求最值的問題了。怎么求一個(gè)函數(shù)的最值？當(dāng)然是求導(dǎo)，然后讓導(dǎo)數(shù)為0，那么解這個(gè)方程得到的θ就是了（當(dāng)然，前提是函數(shù)L(θ)連續(xù)可微）。那如果θ是包含多個(gè)參數(shù)的向量那怎么處理??？當(dāng)然是求L(θ)對所有參數(shù)的偏導(dǎo)數(shù)，也就是梯度了，那么n個(gè)未知的參數(shù)，就有n個(gè)方程，方程組的解就是似然函數(shù)的極值點(diǎn)了，當(dāng)然就得到這n個(gè)參數(shù)了。

最大似然估計(jì)你可以把它看作是一個(gè)反推。多數(shù)情況下我們是根據(jù)已知條件來推算結(jié)果，而最大似然估計(jì)是已經(jīng)知道了結(jié)果，然后尋求使該結(jié)果出現(xiàn)的可能性最大的條件，以此作為估計(jì)值。比如，如果其他條件一定的話，抽煙者發(fā)生肺癌的危險(xiǎn)時(shí)不抽煙者的5倍，那么如果現(xiàn)在我已經(jīng)知道有個(gè)人是肺癌，我想問你這個(gè)人抽煙還是不抽煙。你怎么判斷？你可能對這個(gè)人一無所知，你所知道的只有一件事，那就是抽煙更容易發(fā)生肺癌，那么你會(huì)猜測這個(gè)人不抽煙嗎？我相信你更有可能會(huì)說，這個(gè)人抽煙。為什么？這就是“最大可能”，我只能說他“最有可能”是抽煙的，“他是抽煙的”這一估計(jì)值才是“最有可能”得到“肺癌”這樣的結(jié)果。這就是最大似然估計(jì)。

好了，極大似然估計(jì)就講到這，總結(jié)一下：

極大似然估計(jì)，只是一種概率論在統(tǒng)計(jì)學(xué)的應(yīng)用，它是參數(shù)估計(jì)的方法之一。說的是已知某個(gè)隨機(jī)樣本滿足某種概率分布，但是其中具體的參數(shù)不清楚，參數(shù)估計(jì)就是通過若干次試驗(yàn)，觀察其結(jié)果，利用結(jié)果推出參數(shù)的大概值。最大似然估計(jì)是建立在這樣的思想上：已知某個(gè)參數(shù)能使這個(gè)樣本出現(xiàn)的概率最大，我們當(dāng)然不會(huì)再去選擇其他小概率的樣本，所以干脆就把這個(gè)參數(shù)作為估計(jì)的真實(shí)值。

求最大似然函數(shù)估計(jì)值的一般步驟：

（1）寫出似然函數(shù)；

（2）對似然函數(shù)取對數(shù)，并整理；

（3）求導(dǎo)數(shù)，令導(dǎo)數(shù)為0，得到似然方程；

（4）解似然方程，得到的參數(shù)即為所求；

二、EM算法

好了，重新回到上面那個(gè)身高分布估計(jì)的問題?，F(xiàn)在，通過抽取得到的那100個(gè)男生的身高和已知的其身高服從高斯分布，我們通過最大化其似然函數(shù)，就可以得到了對應(yīng)高斯分布的參數(shù)θ=[u, ?]T了。那么，對于我們學(xué)校的女生的身高分布也可以用同樣的方法得到了。

再回到例子本身，如果沒有“男的左邊，女的右邊，其他的站中間！”這個(gè)步驟，或者說我抽到這200個(gè)人中，某些男生和某些女生一見鐘情，已經(jīng)好上了，糾纏起來了。咱們也不想那么殘忍，硬把他們拉扯開。那現(xiàn)在這200個(gè)人已經(jīng)混到一起了，這時(shí)候，你從這200個(gè)人（的身高）里面隨便給我指一個(gè)人（的身高），我都無法確定這個(gè)人（的身高）是男生（的身高）還是女生（的身高）。也就是說你不知道抽取的那200個(gè)人里面的每一個(gè)人到底是從男生的那個(gè)身高分布里面抽取的，還是女生的那個(gè)身高分布抽取的。用數(shù)學(xué)的語言就是，抽取得到的每個(gè)樣本都不知道是從哪個(gè)分布抽取的。

這個(gè)時(shí)候，對于每一個(gè)樣本或者你抽取到的人，就有兩個(gè)東西需要猜測或者估計(jì)的了，一是這個(gè)人是男的還是女的？二是男生和女生對應(yīng)的身高的高斯分布的參數(shù)是多少？

只有當(dāng)我們知道了哪些人屬于同一個(gè)高斯分布的時(shí)候，我們才能夠?qū)@個(gè)分布的參數(shù)作出靠譜的預(yù)測，例如剛開始的最大似然所說的，但現(xiàn)在兩種高斯分布的人混在一塊了，我們又不知道哪些人屬于第一個(gè)高斯分布，哪些屬于第二個(gè)，所以就沒法估計(jì)這兩個(gè)分布的參數(shù)。反過來，只有當(dāng)我們對這兩個(gè)分布的參數(shù)作出了準(zhǔn)確的估計(jì)的時(shí)候，才能知道到底哪些人屬于第一個(gè)分布，那些人屬于第二個(gè)分布。

這就成了一個(gè)先有雞還是先有蛋的問題了。雞說，沒有我，誰把你生出來的啊。蛋不服，說，沒有我，你從哪蹦出來啊。（呵呵，這是一個(gè)哲學(xué)問題。當(dāng)然了，后來科學(xué)家說先有蛋，因?yàn)殡u蛋是鳥蛋進(jìn)化的）。為了解決這個(gè)你依賴我，我依賴你的循環(huán)依賴問題，總得有一方要先打破僵局，說，不管了，我先隨便整一個(gè)值出來，看你怎么變，然后我再根據(jù)你的變化調(diào)整我的變化，然后如此迭代著不斷互相推導(dǎo)，最終就會(huì)收斂到一個(gè)解。這就是EM算法的基本思想了。

不知道大家能否理解其中的思想，我再來啰嗦一下。其實(shí)這個(gè)思想無處在不啊。

例如，小時(shí)候，老媽給一大袋糖果給你，叫你和你姐姐等分，然后你懶得去點(diǎn)糖果的個(gè)數(shù)，所以你也就不知道每個(gè)人到底該分多少個(gè)。咱們一般怎么做呢？先把一袋糖果目測的分為兩袋，然后把兩袋糖果拿在左右手，看哪個(gè)重，如果右手重，那很明顯右手這代糖果多了，然后你再在右手這袋糖果中抓一把放到左手這袋，然后再感受下哪個(gè)重，然后再從重的那袋抓一小把放進(jìn)輕的那一袋，繼續(xù)下去，直到你感覺兩袋糖果差不多相等了為止。呵呵，然后為了體現(xiàn)公平，你還讓你姐姐先選了。

EM算法就是這樣，假設(shè)我們想估計(jì)知道A和B兩個(gè)參數(shù)，在開始狀態(tài)下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反過來知道了B也就得到了A?？梢钥紤]首先賦予A某種初值，以此得到B的估計(jì)值，然后從B的當(dāng)前值出發(fā)，重新估計(jì)A的取值，這個(gè)過程一直持續(xù)到收斂為止。

EM的意思是“Expectation Maximization”，在我們上面這個(gè)問題里面，我們是先隨便猜一下男生（身高）的正態(tài)分布的參數(shù)：如均值和方差是多少。例如男生的均值是1米7，方差是0.1米（當(dāng)然了，剛開始肯定沒那么準(zhǔn)），然后計(jì)算出每個(gè)人更可能屬于第一個(gè)還是第二個(gè)正態(tài)分布中的（例如，這個(gè)人的身高是1米8，那很明顯，他最大可能屬于男生的那個(gè)分布），這個(gè)是屬于Expectation一步。有了每個(gè)人的歸屬，或者說我們已經(jīng)大概地按上面的方法將這200個(gè)人分為男生和女生兩部分，我們就可以根據(jù)之前說的最大似然那樣，通過這些被大概分為男生的n個(gè)人來重新估計(jì)第一個(gè)分布的參數(shù)，女生的那個(gè)分布同樣方法重新估計(jì)。這個(gè)是Maximization。然后，當(dāng)我們更新了這兩個(gè)分布的時(shí)候，每一個(gè)屬于這兩個(gè)分布的概率又變了，那么我們就再需要調(diào)整E步……如此往復(fù)，直到參數(shù)基本不再發(fā)生變化為止。

這里把每個(gè)人（樣本）的完整描述看做是三元組yi={xi,zi1,zi2}，其中，xi是第i個(gè)樣本的觀測值，也就是對應(yīng)的這個(gè)人的身高，是可以觀測到的值。zi1和zi2表示男生和女生這兩個(gè)高斯分布中哪個(gè)被用來產(chǎn)生值xi，就是說這兩個(gè)值標(biāo)記這個(gè)人到底是男生還是女生（的身高分布產(chǎn)生的）。這兩個(gè)值我們是不知道的，是隱含變量。確切的說，zij在xi由第j個(gè)高斯分布產(chǎn)生時(shí)值為1，否則為0。例如一個(gè)樣本的觀測值為1.8，然后他來自男生的那個(gè)高斯分布，那么我們可以將這個(gè)樣本表示為{1.8, 1, 0}。如果zi1和zi2的值已知，也就是說每個(gè)人我已經(jīng)標(biāo)記為男生或者女生了，那么我們就可以利用上面說的最大似然算法來估計(jì)他們各自高斯分布的參數(shù)。但是它們未知，因此我們只能用EM算法。

咱們現(xiàn)在不是因?yàn)槟莻€(gè)惡心的隱含變量（抽取得到的每個(gè)樣本都不知道是從哪個(gè)分布抽取的）使得本來簡單的可以求解的問題變復(fù)雜了，求解不了嗎。那怎么辦呢？人類解決問題的思路都是想能否把復(fù)雜的問題簡單化。好，那么現(xiàn)在把這個(gè)復(fù)雜的問題逆回來，我假設(shè)已經(jīng)知道這個(gè)隱含變量了，哎，那么求解那個(gè)分布的參數(shù)是不是很容易了，直接按上面說的最大似然估計(jì)就好了。那你就問我了，這個(gè)隱含變量是未知的，你怎么就來一個(gè)假設(shè)說已知呢？你這種假設(shè)是沒有根據(jù)的。呵呵，我知道，所以我們可以先給這個(gè)給分布弄一個(gè)初始值，然后求這個(gè)隱含變量的期望，當(dāng)成是這個(gè)隱含變量的已知值，那么現(xiàn)在就可以用最大似然求解那個(gè)分布的參數(shù)了吧，那假設(shè)這個(gè)參數(shù)比之前的那個(gè)隨機(jī)的參數(shù)要好，它更能表達(dá)真實(shí)的分布，那么我們再通過這個(gè)參數(shù)確定的分布去求這個(gè)隱含變量的期望，然后再最大化，得到另一個(gè)更優(yōu)的參數(shù)，……迭代，就能得到一個(gè)皆大歡喜的結(jié)果了。

這時(shí)候你就不服了，說你老迭代迭代的，你咋知道新的參數(shù)的估計(jì)就比原來的好?。繛槭裁催@種方法行得通呢？有沒有失效的時(shí)候呢？什么時(shí)候失效呢？用到這個(gè)方法需要注意什么問題呢？呵呵，一下子拋出那么多問題，搞得我適應(yīng)不過來了，不過這證明了你有很好的搞研究的潛質(zhì)啊。呵呵，其實(shí)這些問題就是數(shù)學(xué)家需要解決的問題。在數(shù)學(xué)上是可以穩(wěn)當(dāng)?shù)淖C明的或者得出結(jié)論的。那咱們用數(shù)學(xué)來把上面的問題重新描述下。（在這里可以知道，不管多么復(fù)雜或者簡單的物理世界的思想，都需要通過數(shù)學(xué)工具進(jìn)行建模抽象才得以使用并發(fā)揮其強(qiáng)大的作用，而且，這里面蘊(yùn)含的數(shù)學(xué)往往能帶給你更多想象不到的東西，這就是數(shù)學(xué)的精妙所在啊）

三、EM算法推導(dǎo)

假設(shè)我們有一個(gè)樣本集{x(1),…,x(m)}，包含m個(gè)獨(dú)立的樣本。但每個(gè)樣本i對應(yīng)的類別z(i)是未知的（相當(dāng)于聚類），也即隱含變量。故我們需要估計(jì)概率模型p(x,z)的參數(shù)θ，但是由于里面包含隱含變量z，所以很難用最大似然求解，但如果z知道了，那我們就很容易求解了。

對于參數(shù)估計(jì)，我們本質(zhì)上還是想獲得一個(gè)使似然函數(shù)最大化的那個(gè)參數(shù)θ，現(xiàn)在與最大似然不同的只是似然函數(shù)式中多了一個(gè)未知的變量z，見下式（1）。也就是說我們的目標(biāo)是找到適合的θ和z讓L(θ)最大。那我們也許會(huì)想，你就是多了一個(gè)未知的變量而已啊，我也可以分別對未知的θ和z分別求偏導(dǎo)，再令其等于0，求解出來不也一樣嗎？

本質(zhì)上我們是需要最大化（1）式（對（1）式，我們回憶下聯(lián)合概率密度下某個(gè)變量的邊緣概率密度函數(shù)的求解，注意這里z也是隨機(jī)變量。對每一個(gè)樣本i的所有可能類別z求等式右邊的聯(lián)合概率密度函數(shù)和，也就得到等式左邊為隨機(jī)變量x的邊緣概率密度），也就是似然函數(shù)，但是可以看到里面有“和的對數(shù)”，求導(dǎo)后形式會(huì)非常復(fù)雜（自己可以想象下log(f1(x)+ f2(x)+ f3(x)+…)復(fù)合函數(shù)的求導(dǎo)），所以很難求解得到未知參數(shù)z和θ。那OK，我們可否對（1）式做一些改變呢？我們看（2）式，（2）式只是分子分母同乘以一個(gè)相等的函數(shù)，還是有“和的對數(shù)”啊，還是求解不了，那為什么要這么做呢？咱們先不管，看（3）式，發(fā)現(xiàn)（3）式變成了“對數(shù)的和”，那這樣求導(dǎo)就容易了。我們注意點(diǎn)，還發(fā)現(xiàn)等號變成了不等號，為什么能這么變呢？這就是Jensen不等式的大顯神威的地方。

Jensen不等式：

設(shè)f是定義域?yàn)閷?shí)數(shù)的函數(shù)，如果對于所有的實(shí)數(shù)x。如果對于所有的實(shí)數(shù)x，f(x)的二次導(dǎo)數(shù)大于等于0，那么f是凸函數(shù)。當(dāng)x是向量時(shí)，如果其hessian矩陣H是半正定的，那么f是凸函數(shù)。如果只大于0，不等于0，那么稱f是嚴(yán)格凸函數(shù)。

Jensen不等式表述如下：

如果f是凸函數(shù)，X是隨機(jī)變量，那么：E[f(X)]>=f(E[X])

特別地，如果f是嚴(yán)格凸函數(shù)，當(dāng)且僅當(dāng)X是常量時(shí)，上式取等號。

如果用圖表示會(huì)很清晰：

圖中，實(shí)線f是凸函數(shù)，X是隨機(jī)變量，有0.5的概率是a，有0.5的概率是b。（就像擲硬幣一樣）。X的期望值就是a和b的中值了，圖中可以看到E[f(X)]>=f(E[X])成立。

當(dāng)f是（嚴(yán)格）凹函數(shù)當(dāng)且僅當(dāng)-f是（嚴(yán)格）凸函數(shù)。

Jensen不等式應(yīng)用于凹函數(shù)時(shí)，不等號方向反向。

回到公式（2），因?yàn)閒(x)=log x為凹函數(shù)（其二次導(dǎo)數(shù)為-1/x2<0）。

（2）式中的期望，（考慮到E(X)=∑x*p(x)，f(X)是X的函數(shù)，則E(f(X))=∑f(x)*p(x)），又，所以就可以得到公式（3）的不等式了（若不明白，請拿起筆，呵呵）：

OK，到這里，現(xiàn)在式（3）就容易地求導(dǎo)了，但是式（2）和式（3）是不等號啊，式（2）的最大值不是式（3）的最大值啊，而我們想得到式（2）的最大值，那怎么辦呢？

現(xiàn)在我們就需要一點(diǎn)想象力了，上面的式（2）和式（3）不等式可以寫成：似然函數(shù)L(θ)>=J(z,Q)，那么我們可以通過不斷的最大化這個(gè)下界J，來使得L(θ)不斷提高，最終達(dá)到它的最大值。

見上圖，我們固定θ，調(diào)整Q(z)使下界J(z,Q)上升至與L(θ)在此點(diǎn)θ處相等（綠色曲線到藍(lán)色曲線），然后固定Q(z)，調(diào)整θ使下界J(z,Q)達(dá)到最大值（θt到θt+1），然后再固定θ，調(diào)整Q(z)……直到收斂到似然函數(shù)L(θ)的最大值處的θ*。這里有兩個(gè)問題：什么時(shí)候下界J(z,Q)與L(θ)在此點(diǎn)θ處相等？為什么一定會(huì)收斂？

首先第一個(gè)問題，在Jensen不等式中說到，當(dāng)自變量X是常數(shù)的時(shí)候，等式成立。而在這里，即：

再推導(dǎo)下，由于（因?yàn)镼是隨機(jī)變量z(i)的概率密度函數(shù)），則可以得到：分子的和等于c（分子分母都對所有z(i)求和：多個(gè)等式分子分母相加不變，這個(gè)認(rèn)為每個(gè)樣例的兩個(gè)概率比值都是c），則：

至此，我們推出了在固定參數(shù)θ后，使下界拉升的Q(z)的計(jì)算公式就是后驗(yàn)概率，解決了Q(z)如何選擇的問題。這一步就是E步，建立L(θ)的下界。接下來的M步，就是在給定Q(z)后，調(diào)整θ，去極大化L(θ)的下界J（在固定Q(z)后，下界還可以調(diào)整的更大）。那么一般的EM算法的步驟如下：

EM算法（Expectation-maximization）：

期望最大算法是一種從不完全數(shù)據(jù)或有數(shù)據(jù)丟失的數(shù)據(jù)集（存在隱含變量）中求解概率模型參數(shù)的最大似然估計(jì)方法。

EM的算法流程：

初始化分布參數(shù)θ；

重復(fù)以下步驟直到收斂：

E步驟：根據(jù)參數(shù)初始值或上一次迭代的模型參數(shù)來計(jì)算出隱性變量的后驗(yàn)概率，其實(shí)就是隱性變量的期望。作為隱藏變量的現(xiàn)估計(jì)值：

M步驟：將似然函數(shù)最大化以獲得新的參數(shù)值：

這個(gè)不斷的迭代，就可以得到使似然函數(shù)L(θ)最大化的參數(shù)θ了。那就得回答剛才的第二個(gè)問題了，它會(huì)收斂嗎？

感性的說，因?yàn)橄陆绮粩嗵岣撸詷O大似然估計(jì)單調(diào)增加，那么最終我們會(huì)到達(dá)最大似然估計(jì)的最大值。理性分析的話，就會(huì)得到下面的東西：

四、EM算法另一種理解

坐標(biāo)上升法（Coordinate ascent）：

圖中的直線式迭代優(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è)可以通過求導(dǎo)得到，因此可以使用坐標(biāo)上升法，一次固定一個(gè)變量，對另外的求極值，最后逐步逼近極值。對應(yīng)到EM上，E步：固定θ，優(yōu)化Q；M步：固定Q，優(yōu)化θ；交替將極值推向最大。

五、EM的應(yīng)用

EM算法有很多的應(yīng)用，最廣泛的就是GMM混合高斯模型、聚類、HMM等等。具體可以參考JerryLead的cnblog中的Machine Learning專欄：

（EM算法）The EM Algorithm

混合高斯模型（Mixtures of Gaussians）和EM算法

K-means聚類算法

沒有雞和蛋的先后之爭，因?yàn)樗麄兌贾馈皼]有你就沒有我”。從此他們一起過上了幸福美好的生活。