58 views

只要有一些訓練數據,再定義一個最大化函數,採用EM演算法,利用計算機經過若干次迭代,就可以得到所要的模型。這實在是太美妙了,這也許是我們的造物主刻意安排的。所以我把它稱作為上帝的演算法。——吳軍

01 極大似然原理

要立即EM演算法,我們先來了解一個經典的原理——極大似然原理(也叫最大似然原理)。

看完這個示例,想必你對極大似然已經有了初步的認識,沒錯,滿足某個條件,使得事件發生的可能性最大。上面這個例子,就是,滿足小球從乙箱中取出,使得球是黑球的概率最大。

我們再來看一個經典的示例:

問題:假設我們需要調查我們學校的男生和女生的身高分佈。

步驟1:在校園裡隨便地活捉了100個男生和100個女生,共200人。

步驟2:你開始喊:「男的左邊,女的右邊,其他的站中間!」。

步驟3:統計分別得到100個男生的身高和100個女生的身高。

求解:假設他們的身高是服從高斯分佈的。但是這個分佈的均值u和方差∂2我們不知道,這兩個參數就是我們要估計的。記作θ=[u, ∂]T。

用剛才的語境來解釋,就是,滿足這個分部的均值u和方差∂2,使得我們的觀測數據(100個男生身高和100個女生的身高)出現的可能性最大。

總結一下,最大似然估計的目的就是:利用已知的樣本結果,反推最有可能(最大概率)導致這樣結果的參數值。極大似然估計提供了一種給定觀察數據來評估模型參數的方法,即:「模型已定,參數未知」。通過若干次試驗,觀察其結果,利用試驗結果得到某個參數值能夠使樣本出現的概率為最大,則稱為極大似然估計。

02 EM演算法(期望最大值演算法)

回到例子本身,如果沒有「男的左邊,女的右邊,其他的站中間!」這個步驟,現在這200個人已經混到一起了。這個時候,對於每一個樣本或者你抽取到的人,就有兩個東西需要估計的了:

  1. 這個人是男生還是女生?
  2. 男生和女生對應的身高的高斯分佈的參數是多少?

那這個問題EM演算法是怎麼解決的呢?我們先來看答案。

步驟1:我們先隨便猜一下男生(身高)的正態分佈的參數:如均值和方差是多少。例如男生的均值是1米7,方差是0.1米(當然了,剛開始肯定沒那麼准)。女生的正態分佈參數同理。

步驟2:計算出每個人更可能屬於第一個還是第二個正態分佈中的。例如,這個人的身高是1米8,那很明顯,他最大可能屬於男生的那個分佈)。這個是屬於Expectation一步。

步驟3:有了每個人的歸屬,我們已經大概地按上面的方法將這200個人分為男生和女生兩部分了。

現在看出來了嗎?我們已經分別得到了100個男生的身高和100個女生的身高。是不是回到了最大似然估計問題?

步驟4:根據最大似然估計,通過這些被大概分為男生的n個人來重新估計第一個分佈的參數,女生的那個分佈同樣方法重新估計,也就是重新求解這個分佈的均值u和方差∂2。這個是Maximization

假定計算結果當前男生的均值是1米74,方差是0.08。

看出來了嗎?這和我們最初隨便猜的那個參數不一致呀!

步驟5:重新猜。假定我們第二次猜測時取個中間值,例如男生的均值是1米72,方差是0.09。繼續步驟1——步驟2——步驟3——步驟4……如此往複,直到收斂,參數基本不再發生變化為止。

我們再用一個簡單的例子來總結這EM演算法的精髓:

小時候,老媽給一大袋糖果給你,叫你和你姐姐等分,然後你懶得去點糖果的個數,所以你也就不知道每個人到底該分多少個。咱們一般怎麼做呢?先把一袋糖果目測的分為兩袋,然後把兩袋糖果拿在左右手,看哪個重,如果右手重,那很明顯右手這代糖果多了,然後你再在右手這袋糖果中抓一把放到左手這袋,然後再感受下哪個重,然後再從重的那袋抓一小把放進輕的那一袋,繼續下去,直到你感覺兩袋糖果差不多相等了為止。

EM演算法就是這樣,假設我們想估計知道A和B兩個參數,在開始狀態下二者都是未知的,但如果知道了A的信息就可以得到B的信息,反過來知道了B也就得到了A。可以考慮首先賦予A某種初值,以此得到B的估計值,然後從B的當前值出發,重新估計A的取值,這個過程一直持續到收斂為止。

現在,我們來總結一下:

EM(Expectation Maximization)演算法包括了兩個過程和一個目標函數:

E-step: 根據現有的聚類結果,對所以數據(點)重新進行劃分。如果把最終得到的分類結果看作是一個數學的模型,那麼這些聚類的中心(值),以及每一個點和聚類的隸屬關係,可以看成是這個模型的參數。

M-step: 根據重新劃分的結果,得到新的聚類。

目標函數:上面的點到聚類的距離d和聚類之間的距離D,整個過程就是要最大化目標函數。

03 EM演算法在分類中的應用

了解了EM演算法,我們來看一個EM演算法在文本分類中的真實應用。

假設有N篇文本,對應N個向量V1,V2 …Vn, (文本如何轉變為向量,之前的文章已經寫過,詳見《AI產品經理必修——揭開演算法的面紗(餘弦定理)》)希望把他們分到K類中,而這K類的中心是C1,C2 …Ck。K可以是一個固定的數,比如我們認為文本的主題只有100類;也可以是一個不定的數,比如我們並不知道文本的主題有多少類,最終有多少類就分成多少類。分類步驟如下:

步驟1.隨機挑選K個點,作為起始的中心。(E-step)

步驟2:計算所有點到這些聚類中心的距離,將這些點歸到最近的一類中。(M-step)

步驟3:重新計算每一類的中心。新的聚類中心和原先的相比會有一個位移。(E-step)

步驟4:重複上述過程,直到每次新的中心和舊的中心支局的偏移非常非常小,即過程收斂。(M-step)

步驟5:迭代(重複E-step和M-step)

現在,我們已經實現了只利用一組觀測數據自動對文本進行分類。這個方法不需要任何人工干預和先驗的經驗,是一些純粹的數學計算,最後就完全得到了自動的分類,這簡直有點令人難以置信!更奇妙的是,對文本分成多少類也是由觀測數據自動得出的。

至此,我們已經了解了一種典型的非監督學習演算法。堪稱精妙!

 

Go Top