機器學習中的EM演算法

07-09

機器學習中的EM演算法

摘要：最大期望演算法(EM)K均值演算法非常簡單(可參見之前發布的博文),詳細讀者都可以輕鬆地理解它。但下面將要介紹的EM演算法就要困難許多了,它與極大似然估計密切相關。1演算法原理不妨從一個例子開始我們的討論,假設現在有100個人的身高數據,而且這100條數據是隨機抽取的。一個常識性的看法是,男性身高滿足一定的分布(例如正態分布),女性身高也滿足一定的分布,但這兩個分布的參數不同。我們現在不僅不知道男女身高分布的參數,甚至不知道這100條數據哪些是來自男性,哪些是來自女性。這正符合聚類問
最大期望演算法(EM)
K均值演算法非常簡單(可參見之前發布的博文),詳細讀者都可以輕鬆地理解它。但下面將要介紹的EM演算法就要困難許多了,它與極大似然估計密切相關。
1 演算法原理

不妨從一個例子開始我們的討論,假設現在有100個人的身高數據,而且這100條數據是隨機抽取的。一個常識性的看法是,男性身高滿足一定的分布(例如正態分布),女性身高也滿足一定的分布,但這兩個分布的參數不同。我們現在不僅不知道男女身高分布的參數,甚至不知道這100條數據哪些是來自男性,哪些是來自女性。這正符合聚類問題的假設,除了數據本身以外,並不知道其他任何信息。而我們的目的正是推斷每個數據應該屬於哪個分類。所以對於每個樣本,都有兩個需要被估計的項,一個就是它到底是來自男性身高的分布,還是來自女性身高的分布。另外一個就是,男女身高分布的參數各是多少。
既然我們要估計知道A和B兩組參數,在開始狀態下二者都是未知的,但如果知道了A的信息就可以得到B的信息,反過來知道了B也就得到了A。所以可能想到的一種方法就是考慮首先賦予A某種初值,以此得到B的估計,然後從B的當前值出發,重新估計A的取值,這個過程一直持續到收斂為止。你是否隱約想到了什麼?是的,這恰恰是K均值演算法的本質,所以說K均值演算法中其實蘊含了EM演算法的本質。

EM演算法,又稱期望最大化(Expectation Maximization)演算法。在男女身高的問題裡面,可以先隨便猜一下男生身高的正態分布參數:比如可以假設男生身高的均值是1.7米,方差是0.1米。當然,這僅僅是我們的一個猜測,最開始肯定不會太準確。但基於這個猜測,便可計算出每個人更可能屬於男性分布還是屬於女性分布。例如有個人的身高是1.75米,顯然它更可能屬於男性身高這個分布。據此,我們為每條數據都劃定了一個歸屬。接下來就可以根據最大似然法,通過這些被大概認為是男性的若干條數據來重新估計男性身高正態分布的參數,女性的那個分布同樣方法重新估計。然後,當更新了這兩個分布的時候,每一個屬於這兩個分布的概率又發生了改變,那麼就再需要調整參數。如此迭代,直到參數基本不再發生變化為止。