iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 26
0

EM的全名是Expectation Maximum algorithm,常常在找出機率模型中的分佈狀況,例如一些混合模型,或是在分群上也很常用,甚至可以用在回歸問題上。那人如其名,EM演算法就是分為E跟M兩個步驟,一直重複這兩個步驟直到收斂:

  • E step: 估計期望值。
  • M step: 估計參數,使likelihood最大。

就是說我們要最大化的是,資料對於某些變數的 likelihood ,我們以theta表示變數,z表示潛在變數,這種有潛在變數的方式我們叫做潛在模型。

p 是資料真正的機率分佈,q 是我目前推論最可能的機率分佈,z 這邊沒出現,不過在計算的時候會出現。那我們從這個角度來看的話,EM演算法就會是

  • E step: 給定舊theta,求得 q
  • M step: 給定 q ,求得 新theta

如此迭代直到收斂,這個方式是可以證明likelihood一定會越來越高直到收斂的。不過直接看這個可能會比較沒辦法理解,所以我們先從最簡單的Kmeans開始介紹,他沒有機率的概念,所以自然也看不到潛在變數,不過他是EM演算法最簡單的應用,EM又是潛在模型最起步的概念,所以一定要先介紹他!

Kmeans的分群我們要先假設有 K 個群,這個 K 是我們已知的,也就是使用時需要輸入。我們會有一組平均值的向量,也就是每一個群自己的平均。以及,每一個資料對於每一個類別都有一個r,就是以r nk來表示,這個值在kmeans不是一就是零,意思就是這個資料現在是屬於哪個群的。

所以我們可以得到

所以EM的流程會是

  • E step : 固定 mu 最小化 J ,可以得到新的r_nk
  • M step : 固定 r_nk 最小化 J,可以得到新的 mu

重複這兩個步驟,直到mu收斂。

在 E step,其實這邊很簡單的, r_nk 的值是 1 如果他 k 這個平均值比其他平均值近的話,否則就是零,也就是這個式子

而 M step,也很簡單的,就是算出新得到的分群狀況的平均而已,也就是

很直觀的也是可以發現,如果資料量很大,這也是會很難算,所以這邊其實也可以用循序學習的方式做,而且也很簡單,就是

就是這麼簡單,實做也是非常短,所以還是就等到最後講完一起做給大家看吧。這個是EM演算法最簡單的應用例子,他甚至沒有機率成份在裡面,不過這就可惜了EM演算法背後的理論了,所以明天跟大家介紹混合高斯模型,他也是透過EM演算法的想法應用的,而且可以更讓我們對EM演算法有概念。


上一篇
SVM - 動手做做看 soft margin svm篇
下一篇
EM - Gaussian Mixture Model
系列文
機器學習你也可以 - 文組帶你手把手實做機器學習聖經30

尚未有邦友留言

立即登入留言