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演算法有概念。