看來了一下EM算法的推導，感覺信号檢測與估值的課需要複習了。。。
斯坦福大學機器學習——EM算法求解高斯混合模型（系列）
下面主要介紹EM的整個推導過程。
1. Jensen不等式
回顧優化理論中的一些概念。設f是定義域為實數的函數，如果對于所有的實數x，
，那麼稱f是嚴格凸函數。
Jensen不等式表述如下：
如果f是凸函數，X是随機變量，那麼
，也就是說X是常量。
這裡我們将
。
如果用圖表示會很清晰：
成立。
當f是（嚴格）凹函數當且僅當-f是（嚴格）凸函數。
Jensen不等式應用于凹函數時，不等号方向反向，也就是
2. EM算法
給定的訓練樣本是
一般比較困難，因為有隐藏變量z存在，但是一般确定了z後，求解就容易了。
EM是一種解決存在隐含變量優化問題的有效方法。竟然不能直接最大化
的下界（E步），然後優化下界（M步）。這句話比較抽象，看下面的。
對于每一個樣例i，讓
是機率密度函數，需要将求和符号換做積分符号）。比如要将班上學生聚類，假設隐藏變量z是身高，那麼就是連續的高斯分布。如果按照隐藏變量是男女，那麼就是伯努利分布了。
可以由前面闡述的内容得到下面的公式：
| 設Y是随機變量X的函數 （g是連續函數），那麼 （1） X是離散型随機變量，它的分布律為 |
對應于上述問題，Y是
，X是
，
是
，g是
到
的映射。這樣解釋了式子（2）中的期望，再根據凹函數時的Jensen不等式：
可以得到（3）。
這個過程可以看作是對
求了下界。對于
的選擇，有多種可能，那種更好的？假設
已經給定，那麼
的值就決定于
和
了。我們可以通過調整這兩個機率使下界不斷上升，以逼近
的真實值，那麼什麼時候算是調整好了呢？當不等式變成等式時，說明我們調整後的機率能夠等價于
了。按照這個思路，我們要找到等式成立的條件。根據Jensen不等式，要想讓等式成立，需要讓随機變量變成常數值，這裡得到：
c為常數，不依賴于
。對此式子做進一步推導，我們知道
，那麼也就有
，（多個等式分子分母相加不變，這個認為每個樣例的兩個機率比值都是c），那麼有下式：
至此，我們推出了在固定其他參數
後，
的計算公式就是後驗機率，解決了
如何選擇的問題。這一步就是E步，建立
的下界。接下來的M步，就是在給定
後，調整
，去極大化
的下界（在固定
後，下界還可以調整的更大）。那麼一般的EM算法的步驟如下：
| 循環重複直到收斂 { （E步）對于每一個i，計算 |
那麼究竟怎麼確定EM收斂？假定
是EM第t次和t+1次疊代後的結果。如果我們證明了
，也就是說極大似然估計單調增加，那麼最終我們會到達最大似然估計的最大值。下面來證明，標明
後，我們得到E步
這一步保證了在給定
時，Jensen不等式中的等式成立，也就是
然後進行M步，固定
，并将
視作變量，對上面的
求導後，得到
，這樣經過一些推導會有以下式子成立：
解釋第（4）步，得到
時，隻是最大化
，也就是
的下界，而沒有使等式成立，等式成立隻有是在固定
，并按E步得到
時才能成立。
況且根據我們前面得到的下式，對于所有的
都成立
第（5）步利用了M步的定義，M步就是将
調整到
，使得下界最大化。是以（5）成立，（6）是之前的等式結果。
這樣就證明了
會單調增加。一種收斂方法是
不再變化，還有一種就是變化幅度很小。
再次解釋一下（4）、（5）、（6）。首先（4）對所有的參數都滿足，而其等式成立條件隻是在固定
，并調整好Q時成立，而第（4）步隻是固定Q，調整
，不能保證等式一定成立。（4）到（5）就是M步的定義，（5）到（6）是前面E步所保證等式成立條件。也就是說E步會将下界拉到與
一個特定值（這裡
）一樣的高度，而此時發現下界仍然可以上升，是以經過M步後，下界又被拉升，但達不到與
另外一個特定值一樣的高度，之後E步又将下界拉到與這個特定值一樣的高度，重複下去，直到最大值。
如果我們定義
從前面的推導中我們知道
，EM可以看作是J的坐标上升法，E步固定
，優化
，M步固定
優化
從最大似然到EM算法淺解
EM算法有很多的應用，最廣泛的就是GMM混合高斯模型、聚類、HMM等等。具體可以參考JerryLead的cnblog中的Machine Learning專欄：
（EM算法）The EM Algorithm
混合高斯模型（Mixtures of Gaussians）和EM算法
K-means聚類算法
C/C++基本文法學習
STL
C++ primer