新智元專欄
人工智慧很火，人工智慧大神很火。大神們的神器是什麼？有人說找到了，就是EM算法。 請看這篇：
但是最近網上引人關注的另一傳聞是，一位人工智慧論文獲獎者在獲獎感言中說深度學習方法是鍊金術，從而引起大神家族成員反駁。報導見：NIPS機器學習鍊金術之爭
看到上面兩篇，使我想到：EM算法是鍊金術嗎？
我近兩年碰巧在研究用以改進EM算法的新算法：http://survivor99.com/lcg/CM/Recent.html，對EM算法存在的問題比較清楚。我的初步結論是：EM算法雖然在理論上有問題，但是確實煉出金子了。反過來也可以說，雖然EM算法練出金子了，但是收斂很不可靠，流行的解釋EM算法的收斂理由更是似是而非。有人使之神秘化，使得它是有鍊金術之嫌。論據何在？下面我首先以混合模型為例，簡單介紹EM算法，並證明流行的EM算法收斂證明是錯的(沒說算法是錯的)。
假設n個高斯分布函數是：
P(X|θj)=Kexp[-(X-cj)2/(2dj2)]，j=1，2，…，n
其中K是係數，cj是中心，dj是標準差。假設一個數據分布P(X)是兩個高斯分布的混合
P(X)=P*(y1)P(X|θ*1)+P(y2)P(X|θ*2)
其中P*(y1)，P*(y2)是真的混合比例，θ*1和θ*2表示真的模型參數。我們只知道模型是高斯分布且n=2。現在我們猜測5個參數P(y1)，c1，c2，d1，d2。不是6個參數，是因為p(y2)=1-P(y1)。根據猜測得到的分布是
Q(X)=P(y1)P(X|θ1)+P(y2)P(X|θ2)
如果Q(X)非常接近P(X)，相對熵或 Kullback-leibler 距離
H(Q||P)=∑iP(xi)log[P(xi)/P(xi|θ)]
就接近0，比如小於0.001比特，那麼就算我們猜對了。參看下圖：
混合模型問題之所以重要，是因為它是限制分布類型而不是分布範圍的模糊聚類，是無監督學習的一個典型。
EM算法起源於這篇文章：Dempster, A.P., Laird, N.M., Rubin,D. B.: Maximum Likelihood from Incomplete Datavia the EM Algorithm. Journal of the Royal Statistical Society, Series B39, 1–38(1977)。通過這個網站http://www.sciencedirect.com/搜索可見，光是標題有EM算法的英文文章就有6.8萬篇(有似然度的文章將近76萬篇)，可見研究和應用EM算法的人何其多。
Wiki百科上的EM算法介紹見這裡：
https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm
一篇中文介紹見這裡：
http://www.cnblogs.com/mindpuzzle/archive/2013/04/05/2998746.html
EM算法的基本思想是：
目的是改變預測模型參數求似然度logP(XN|θ)或logP(X|θ)達最大（N表示有N個樣本點，黑體X表示矢量），樣本和θ之間的似然度就是負的預測熵（或交叉熵，廣義熵的一種）：
Hθ』(X)=∑iP(xi)logP(xi|θ)
其中P(xi|θ)就是上面的曲線Q(X)上的一個點（X是變量，xi是常量），即P(xi|θ)=Q(xi)。我們用X的概率分布P(X)取代X序列。則EM算法的基本公式如下(下面y就是wiki百科中的z)：
其中θt表示M步優化前的θ。這裡的Q和上面的Q(X)中的Q含義不同，下面我們用Q(.)表示這裡的Q(θ|θt)。
從語義資訊理論(http://survivor99.com/lcg/books/GIT/)看，我們可以得到
[Q(θ|θt)-H]/N=Hθ』(X，Y)-Hθ』(Y|X)=-Hθ(X，Y)+Hθ(Y|X)
右邊是兩個負的廣義熵或負的交叉熵，和參數有關。為了討論方便，後面忽略左邊的N。
EM算法分兩步：
E-step：寫出預測的yj的條件概率
M-step：最大化Q(θ|θt)，也就是最大化負的聯合熵Hθ』(X，Y)，或最小化聯合交叉熵Hθ(X，Y)。
為什麼這樣能收斂呢？wiki百科這樣說：
Expectation-maximization works to improve Q(θ|θt) rather than directly improving log(X|θ). Here is shown that improvements to the former imply improvements to the latter.[13]
這就是說，只要Q(.)達最大，log(X|θ)就達到最大。
2）M-step可以增大Q(.)，E-step也不減少Q(.)，所以反覆迭代就能收斂。
這篇證明文章比較出名：Wu, C.F.J.: On the Convergence Properties of the EM Algorithm. Annals of Statistics11, 95–10(1983)。
這等於說，真模型在山頂上，爬山人每一步只上不下就能到達山頂。M步只上，E步不下，所以能到達山頂。
但是，使用EM算法時，往往在預測分布P(X|θ)和實際分布P(X)不重合就停下來了。流行的解釋是：那叫局部收斂（其實就是收錯了地方）；因為大山周圍有一些小山，出發點不對就上到小山頂上了。所以起始點很重要。於是有人專門研究如何通過測試找到較好的出發點，比如隨機選多點測試看哪個好。
EM有時雖然能收斂，但是常常收斂很慢。為了提高速度，於是又有很多人提出很多改進辦法。其中比較出名的一個就是上面《九層境界》中提到的VBEM算法(詳見Neal, R.，Hinton, G.: A view of the EM algorithm that justifies incremental, sparse, and other variants. in: Michael I. Jordan(ed.) Learning in Graphical Models，pp355–368. MITPress，Cambridge，MA(1999))，就是用
F(θ，q)=Q(θ|θt)+H(Y)
取代Q(θ|θt)(上面忽略了係數N)，不斷最大化F(θ，q)(q=P(Y))。在M步最大化F(.)，在E步也最大化F(.)。據說這樣收斂更快。但是VBEM的收斂證明是不是一樣有問題呢？我的結論是：算法好一些，但是收斂證明問題還是存在。
首先我們看EM算法(包括VBEM算法）的收斂證明錯在哪裡。
在Shannon資訊理論中有公式：
H(X，Y)=H(X)+H(Y|X)
由於引進似然函數，Shannon熵變成預測熵或交叉熵，但是基本關係還是成立
Hθ(X，Y)=Hθ(X)+Hθ(Y|X)=-logP(X|θ)+Hθ(Y|X)
寫成負熵的形式是：
H』θ(X，Y)=logP(X|θ)+H』θ(Y|X)
後面這一項Hθ(Y|X)和Y的熵有關，P(y1)=P(y2)=0.5的時候H(Y)最大，負熵就最小，H』θ(Y|X)也比較小。如果真的比例P*(Y)是接近等概率的，起步時P(y1)=0.1，P(y2)=0.9，Y的負熵較大，我們不斷最大化H』θ(X，Y)，就會阻止P(Y)向真比例P*(Y)靠近。這是EM算法收斂慢甚至不收斂的一個原因。這也是為什麼VBEM方法要用F(.)取代Q(.)。上式兩邊加上H(Y)以後就有
H』θ(X，Y)+H(Y)=logP(X|θ)+H』θ(Y|X)+H(Y)
H(Y)-Hθ(X，Y)=-Hθ(X)+H(Y)-Hθ(Y|X)
近似得到(後面解釋近似)：
-Hθ(X|Y)=-Hθ(X)+Iθ(X;Y)
也就是
F(θ，q)=-Hθ(X|Y)=-Hθ(X)+Iθ(X;Y)(3)
可見，F(θ，q)就是負的後驗熵。兩邊加上P(X)，左邊就是預測互信息或語義互信息(我早在1993年的《廣義資訊理論》一書中就提出)：
F(θ，q)+H(X)=H(X)-Hθ(X|Y)=I(X;)(4)
從上面兩個公式可以得到
H(Q||P)=H(X|θ)-H(X)=Iθ(X;Y)-I(X;)(5)
我們可以粗略理解，相對熵=Shannon互信息-預測互信息。後面我們將介紹這個公式的更加嚴格形式。
因為H(X)和模型無關，最大化F(.)就是最大化預測互信息，避免誤改P(Y)。這樣就好理解為什麼VBEM比EM好。
但是，F(θ，q)最大化和logP(X|θ)最大化是否總是一致的？結論是否定的。證明很簡單：
假設有一個真模型θ*和子模型比例P*(Y)，它們產生P(X)。同時相應的Shannon聯合熵是H*(X，Y)，X的後驗熵是H*(X|Y)，互信息是I*(X;Y)。那麼改變X和Y的概率分布，上面三個量都會變。
我們猜測的時候，如果聯合概率分布P(Y，X|θ)比P*(X，Y)更加集中，負熵log(X，Y|θ)=H』θ(X，Y)就會大於真模型的負熵-H*(X，Y)，繼續增大H』θ(X，Y)就會南轅北轍。
比如，下圖例子中，第一輪優化參數前就可能有H』θ(X，Y)>-H*(X，Y)。它對於EM算法收斂證明來說就是反例。圖中R=I(X;Y)，R*=I*(X;Y)。其中真實的Q*(.)和互信息I*(X;Y)比較小。
這個例子中迭代用的是信道匹配算法，和VBEM算法比，主要差別是，在E步把繼續增大F(.)改為調整P(Y)。其中紅線就是EM算法中Q(θ|θt)的變化軌跡，第一個E步之後，Q(.)就大於真模型的Q*(.)。如果起始參數是隨機的，那麼它可能導致Q(.)出現在紅線的任何位置，從而大於Q*(.)。
F(.)有類似情況，它和預測互信息(圖示是G)走勢完全一致，在每個E步是下降的。原來影響交叉熵有三個因素：
1)預測的分布和樣本的分布是否符合，如果更符合，負熵Q(.)和F(.)就更大；
2)X和Y的分布是否集中，如果更集中負熵就更大；
3)X和Y是否相關，如果更相關負熵就更大。
流行的收斂證明只考慮了第一條。
到此有人會問，如果終點不在山頂上，起點很可能高於終點，那麼為什麼EM算法在大多數情況下是收斂的？
回答是：EM算法收斂證明中第二條，Q(.)只增不減也錯了！原來在E步，Q(.)和F(.)是可能減小的！一般情況下都會使Q(.)向真模型的Q*=-H*(X，Y)靠攏，使F(.)向-H*(X|Y)靠攏。如果調整P(Y)，收斂就更加可靠，EM算法就變為CM算法。
下面提供CM算法的粗略數學證明。
先看為什麼需要調整P(Y)。在E步的公式(2)(計算Shannon信道的公式)中，P(yj|X)和P(X)及四個參數可能不匹配，導致
那樣，上面計算出的Shannon信道就是一個不稱職的Shannon信道。調整方法很簡單，就是不斷用左邊的P+1(yj)代替右邊的P(yj)，直到兩者相等。
下面介紹用信道匹配算法(CM算法)用到的公式：
上面第一行公式就是公式(5)的更加嚴格形式。其中用到子模型θj，P(X|θj) 就等於前面方法中的P(X|yj，θ)。RQ就近似於前面方法中Iθ(X;Y)。為什麼說近似呢，因為這裡用到Y的廣義熵或交叉熵H(Y+1)=-∑jP+1(yj)logP(yj) 和相對熵H(Y+1||Y)。聯合熵減去這個熵才是預測後驗熵。而在VBEM方法中，增加的H(Y)是Shannon熵。
有了上面公式(6)，我們就可以採用下面三步減小相對熵H(Q||P)——保證每一步都是減小的：
I：寫出Shannon信道表達式，等於EM算法中的E步;
II：調整P(Y)，使得P(Y+1)=P(Y);如果H(Q||P)<0.001，結束。
III:改變參數最大化語義互信息G。轉到I。
詳細討論見這裡：http://survivor99.com/lcg/CM.html
如果EM算法在M步先調整P(Y)，固定P(Y)再優化參數，EM算法就和CM算法相同。如果在VBEM算法中添加的H(Y)改為交叉熵，E步調整P(Y)而不是最大化F(.)，VBEM算法就和CM算法相同。
從語義互信息公式看
迭代就是輪流改變log左邊(I和II)和右邊(III)。改變右邊是語義信道匹配Shannon信道，改變左邊是Shannon信道匹配語義信道。所以該算法叫信道匹配(Channels』Matching)算法或CM算法(保留EM中的M)。我們也可以說CM算法是EM算法的改進版本。但是基本思想是不同的。CM算法也沒用到Jensen不等式。
為什麼CM算法會使Q(X)會收斂到P(X)呢？相對熵會不會表現為很多山窪，有高有低，我們不巧，落到一個較高的山窪裡呢？
這要從Shannon的信息率失真理論談起。Shannon在1948年發表經典文章《通信的數學理論之》，11年之後，他提出信息率失真函數R(D)——就是給定平均損失上限D求互信息I(X;Y)最小值R(D)。我在1993年的《廣義資訊理論》中把它改造為R(G)函數。G是廣義互信息或語義互信息(也就是平均log標準似然度)的下限。R(G)是給定G時的Shannon互信息I(X;Y)的最小值。可以證明，所有R(G)函數都是碗狀的。R(D)函數像是半個碗，也是凹的。證明G是碗狀的很簡單，因為R(D)函數處處是凹的(已有結論)，R(G)函數是它的自然擴展，也是處處是凹的。
進一步結論：R(G)-G也是處處是凹的。所以山窪只有一個。求相對熵最小，就是求R(G)-G最小，就是找R=G的點，也就是上圖中45度斜線和碗狀曲線相切的點。
像E步那樣，用公式(2)求Shannon信道，並調整P(Y)，就能得到R(G)。原來求信息率失真函數也用到迭代算法，也用到和公式(2)類似的公式。EM和VBEM算法之所以慢，除了因為沒有調整P(Y)，還和指導思想有關。因為認為增大負熵就能達到目的，所以設置初始參數時就想把負熵弄得小一點，比如把兩個標準差d1和d2設得大一點，防止漏掉真模型。但是在計算試驗中我發現，有時候選擇較小的偏差，收斂反而更快。從文獻數字和我的計算實驗看，CM算法迭代5次收斂比較常見，而EM算法(包括改進的)達到收斂的迭代次數大多超過10次。
誠然，CM算法也不是完美無缺的。在少數極端情況下(比如兩個分布重疊較多，兩個分量比例相差較大時)，初始值選擇不當收斂也很慢。結合已有的EM算法研究中關於初始參數的研究成果，應該還能改進。
我上面只是證明了流行的EM算法收斂證明是錯的，是否還有其他對的證明？我不能肯定。北大的馬盡文教授是EM算法專家，做過很多推廣和應用。他說有，我很期待。我以為如果有，可能和我的證明異途同歸。我和VBEM的第一作者Neal教授通過信，他說要是E步減小Q(.)或F(.)，那就太震動了。看來他一直相信流行的負熵只增不減證明。
現在回到「鍊金術」話題。
實際上，把深度學習和鍊金術聯繫起來的AliRahimi教授演講標題是：
《從「鍊金術」到「電力」的機器學習》，他並沒有否定深度學習，只是說要加強理論研究，也不排除先有實踐再有理論。
根據上面分析，可以說EM算法正在從「鍊金術」向「冶金術」過渡。如過它在理論上停滯不前，如果我們把它神話，它就真像是鍊金術了。反之，正視已有問題，尋找更簡潔更有說服力理論，才能使「鍊金術」成為可靠「冶金」工具。
作者簡介：
魯晨光，男，南京航空航天大學畢業(77級). 當過長沙市青年學術帶頭人，赴加拿訪問學者，北師大數學系訪問學者（汪培莊教授指導）…研究興趣是：語義資訊理論，統計學習，色覺的數學和哲學, 美學和進化論，投資組合。專著有：《廣義資訊理論》，《投資組合的熵理論和信息價值》，《色覺奧妙和哲學基本問題》，《美感奧妙和需求進化》。於《光學學報》,《機器人》，《通信學報》,《現代哲學》,《Int. J. of General System》等雜誌上發表論文多篇。最近主要工作是把語義資訊理論用到統計學習，用以解決最大似然估計，貝葉斯推理， 多標籤分類， 混合模型等問題。個人網站：http://survivor99.com/lcg/ 信箱：lcguang@foxmail.com。