只要有一些訓(xùn)練數(shù)據(jù)庆揩，再定義一個(gè)最大化函數(shù)膳叨，采用EM算法洽洁，利用計(jì)算機(jī)經(jīng)過若干次迭代，就可以得到所要的模型菲嘴。這實(shí)在是太美妙了饿自，這也許是我們的造物主刻意安排的。所以我把它稱作為上帝的算法龄坪≌汛疲——吳軍

1.極大似然原理

要立即EM算法，我們先來了解一個(gè)經(jīng)典的原理——極大似然原理（也叫最大似然原理）健田。

看完這個(gè)示例烛卧，想必你對(duì)極大似然已經(jīng)有了初步的認(rèn)識(shí)，沒錯(cuò)妓局，滿足某個(gè)條件总放，使得事件發(fā)生的可能性最大呈宇。上面這個(gè)例子，就是局雄，滿足小球從乙箱中取出甥啄，使得球是黑球的概率最大。

我們?cè)賮砜匆粋€(gè)經(jīng)典的示例：

問題：假設(shè)我們需要調(diào)查我們學(xué)校的男生和女生的身高分布哎榴。

步驟1：在校園里隨便地活捉了100個(gè)男生和100個(gè)女生型豁，共200人僵蛛。

步驟2：你開始喊：“男的左邊尚蝌，女的右邊，其他的站中間充尉！”飘言。

步驟3：統(tǒng)計(jì)分別得到100個(gè)男生的身高和100個(gè)女生的身高。

求解：假設(shè)他們的身高是服從高斯分布的驼侠。但是這個(gè)分布的均值u和方差?2我們不知道姿鸿，這兩個(gè)參數(shù)就是我們要估計(jì)的。記作θ=[u, ?]T倒源。

用剛才的語(yǔ)境來解釋苛预，就是，滿足這個(gè)分部的均值u和方差?2笋熬，使得我們的觀測(cè)數(shù)據(jù)（100個(gè)男生身高和100個(gè)女生的身高）出現(xiàn)的可能性最大热某。

總結(jié)一下，最大似然估計(jì)的目的就是：利用已知的樣本結(jié)果胳螟，反推最有可能（最大概率）導(dǎo)致這樣結(jié)果的參數(shù)值昔馋。極大似然估計(jì)提供了一種給定觀察數(shù)據(jù)來評(píng)估模型參數(shù)的方法，即：“模型已定糖耸，參數(shù)未知”秘遏。通過若干次試驗(yàn)，觀察其結(jié)果嘉竟，利用試驗(yàn)結(jié)果得到某個(gè)參數(shù)值能夠使樣本出現(xiàn)的概率為最大邦危，則稱為極大似然估計(jì)。

2.EM算法（期望最大值算法）

回到例子本身舍扰，如果沒有“男的左邊铡俐，女的右邊，其他的站中間妥粟！”這個(gè)步驟审丘，現(xiàn)在這200個(gè)人已經(jīng)混到一起了。這個(gè)時(shí)候勾给，對(duì)于每一個(gè)樣本或者你抽取到的人滩报，就有兩個(gè)東西需要估計(jì)的了：

一锅知、這個(gè)人是男生還是女生？

二脓钾、男生和女生對(duì)應(yīng)的身高的高斯分布的參數(shù)是多少售睹？

那這個(gè)問題EM算法是怎么解決的呢？我們先來看答案可训。

步驟1：我們先隨便猜一下男生（身高）的正態(tài)分布的參數(shù)：如均值和方差是多少昌妹。例如男生的均值是1米7，方差是0.1米（當(dāng)然了握截，剛開始肯定沒那么準(zhǔn)）飞崖。女生的正態(tài)分布參數(shù)同理。

步驟2：計(jì)算出每個(gè)人更可能屬于第一個(gè)還是第二個(gè)正態(tài)分布中的谨胞。例如固歪，這個(gè)人的身高是1米8，那很明顯胯努，他最大可能屬于男生的那個(gè)分布）牢裳。這個(gè)是屬于Expectation一步。

步驟3：有了每個(gè)人的歸屬叶沛，我們已經(jīng)大概地按上面的方法將這200個(gè)人分為男生和女生兩部分了蒲讯。

現(xiàn)在看出來了嗎？我們已經(jīng)分別得到了100個(gè)男生的身高和100個(gè)女生的身高灰署。是不是回到了最大似然估計(jì)問題判帮？

步驟4：根據(jù)最大似然估計(jì)，通過這些被大概分為男生的n個(gè)人來重新估計(jì)第一個(gè)分布的參數(shù)氓侧，女生的那個(gè)分布同樣方法重新估計(jì)脊另，也就是重新求解這個(gè)分布的均值u和方差?2。這個(gè)是Maximization约巷。

假定計(jì)算結(jié)果當(dāng)前男生的均值是1米74偎痛，方差是0.08。

看出來了嗎独郎？這和我們最初隨便猜的那個(gè)參數(shù)不一致呀踩麦！

步驟5：重新猜。假定我們第二次猜測(cè)時(shí)取個(gè)中間值氓癌，例如男生的均值是1米72谓谦，方差是0.09。繼續(xù)步驟1——步驟2——步驟3——步驟4……如此往復(fù)贪婉，直到收斂反粥，參數(shù)基本不再發(fā)生變化為止。

我們?cè)儆靡粋€(gè)簡(jiǎn)單的例子來總結(jié)這EM算法的精髓：

小時(shí)候，老媽給一大袋糖果給你才顿，叫你和你姐姐等分莫湘，然后你懶得去點(diǎn)糖果的個(gè)數(shù)，所以你也就不知道每個(gè)人到底該分多少個(gè)郑气。咱們一般怎么做呢幅垮？先把一袋糖果目測(cè)的分為兩袋，然后把兩袋糖果拿在左右手尾组，看哪個(gè)重忙芒，如果右手重，那很明顯右手這代糖果多了讳侨，然后你再在右手這袋糖果中抓一把放到左手這袋呵萨，然后再感受下哪個(gè)重，然后再?gòu)闹氐哪谴ヒ恍“逊胚M(jìn)輕的那一袋爷耀，繼續(xù)下去甘桑，直到你感覺兩袋糖果差不多相等了為止拍皮。

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

現(xiàn)在组砚，我們來總結(jié)一下：

EM（Expectation Maximization）算法包括了兩個(gè)過程和一個(gè)目標(biāo)函數(shù)：

E-step: 根據(jù)現(xiàn)有的聚類結(jié)果吻商，對(duì)所以數(shù)據(jù)（點(diǎn)）重新進(jìn)行劃分。如果把最終得到的分類結(jié)果看作是一個(gè)數(shù)學(xué)的模型糟红，那么這些聚類的中心（值）艾帐，以及每一個(gè)點(diǎn)和聚類的隸屬關(guān)系，可以看成是這個(gè)模型的參數(shù)盆偿。

M-step: 根據(jù)重新劃分的結(jié)果柒爸，得到新的聚類。

目標(biāo)函數(shù)：上面的點(diǎn)到聚類的距離d和聚類之間的距離D事扭，整個(gè)過程就是要最大化目標(biāo)函數(shù)捎稚。

3.EM算法在分類中的應(yīng)用

了解了EM算法，我們來看一個(gè)EM算法在文本分類中的真實(shí)應(yīng)用。

假設(shè)有N篇文本今野，對(duì)應(yīng)N個(gè)向量V1,V2 …Vn, （文本如何轉(zhuǎn)變?yōu)橄蛄课保暗奈恼乱呀?jīng)寫過，詳見AI產(chǎn)品經(jīng)理必修——揭開算法的面紗（余弦定理））希望把他們分到K類中腥泥，而這K類的中心是C1,C2 …Ck匾南。K可以是一個(gè)固定的數(shù)，比如我們認(rèn)為文本的主題只有100類蛔外；也可以是一個(gè)不定的數(shù)蛆楞，比如我們并不知道文本的主題有多少類，最終有多少類就分成多少類夹厌。分類步驟如下：

步驟1.隨機(jī)挑選K個(gè)點(diǎn)豹爹，作為起始的中心。（E-step）

步驟2：計(jì)算所有點(diǎn)到這些聚類中心的距離矛纹，將這些點(diǎn)歸到最近的一類中臂聋。（M-step）

步驟3：重新計(jì)算每一類的中心。新的聚類中心和原先的相比會(huì)有一個(gè)位移或南。（E-step）

步驟4：重復(fù)上述過程孩等，直到每次新的中心和舊的中心支局的偏移非常非常小，即過程收斂采够。（M-step）

步驟5：迭代（重復(fù)E-step和M-step）

現(xiàn)在肄方，我們已經(jīng)實(shí)現(xiàn)了只利用一組觀測(cè)數(shù)據(jù)自動(dòng)對(duì)文本進(jìn)行分類。這個(gè)方法不需要任何人工干預(yù)和先驗(yàn)的經(jīng)驗(yàn)蹬癌，是一些純粹的數(shù)學(xué)計(jì)算权她，最后就完全得到了自動(dòng)的分類，這簡(jiǎn)直有點(diǎn)令人難以置信逝薪！更奇妙的是隅要，對(duì)文本分成多少類也是由觀測(cè)數(shù)據(jù)自動(dòng)得出的。

至此董济，我們已經(jīng)了解了一種典型的非監(jiān)督學(xué)習(xí)算法步清。堪稱精妙感局！