EM算法--應(yīng)用到三個(gè)模型： 高斯混合模型 ，混合樸素貝葉斯模型，因子分析模型

判別模型求的是條件概率p(y|x)，

生成模型求的是聯(lián)合概率p(x,y)   .即 = p(x|y) ? p(y) 
常見的判別模型有線性回歸、對(duì)數(shù)回歸、線性判別分析、支持向量機(jī)、boosting、條件 隨機(jī)場(chǎng)、神經(jīng)網(wǎng)絡(luò)等。
常見的生產(chǎn)模型有隱馬爾科夫模型、樸素貝葉斯模型、高斯混合模型、LDA、Restricted Boltzmann Machine等。

所以這里說的高斯混合模型，樸素貝葉斯模型都是求p(x,y)聯(lián)合概率的。(下面推導(dǎo)會(huì)見原因)

套路小結(jié)： 凡是生產(chǎn)模型，目的都是求出聯(lián)合概率表達(dá)式，然后對(duì)聯(lián)合概率表達(dá)式里的各個(gè)參數(shù)再進(jìn)行估計(jì)，求出其表達(dá)式。

下面的EM算法，GMM等三個(gè)模型都是做這同一件事：設(shè)法求出聯(lián)合概率，然后對(duì)出現(xiàn)的參數(shù)進(jìn)行估計(jì)。

 一、EM算法：

作用是進(jìn)行參數(shù)估計(jì)。

應(yīng)用：（因?yàn)槭菬o監(jiān)督，所以一般應(yīng)用在聚類上，也用在HMM參數(shù)估計(jì)上）所以凡是有EM算法的，一定是無監(jiān)督學(xué)習(xí).因?yàn)镋M是對(duì)參數(shù)聚集

給定訓(xùn)練樣本是 樣例獨(dú)立，

我們想要知道每個(gè)樣例隱含的類別z，使是p(x,z)最大，（即 如果將樣本x(i)看作觀察值， 潛在類別z看作是隱藏變量， 則x可能是類別z， 那么聚類問題也就是參數(shù)估計(jì)問題，）

故p(x,z)最大似然估計(jì)是：

所以可見用到EM算法的模型（高斯混合模型，樸素貝葉斯模型）都是求p(x,y)聯(lián)合概率，為生成模型。

對(duì)上面公式，直接求θ一般比較困難，因?yàn)橛须[藏變量z存在，但是一般確定了z后，求解就容易了。

EM是一種解決存在隱含變量?jī)?yōu)化問題的有效方法。竟然不能直接最大化?(θ)，我們可建立?的下界（E步），再優(yōu)化下界（M步），見下圖第三步，取的就是下界

  （總式）

解釋上式：

對(duì)于每一個(gè)樣例 i，讓Qi表示該樣例隱含變量 z 的某種分布，Qi滿足的條件是 （如果 z 是連續(xù)性的，那么Qi是概率密度函數(shù)（因子分析模型就是如此），需要將求和符號(hào)換成積分符號(hào)即：因子分析模型是如此，這個(gè)會(huì)用在EM算法的M步求。

比如要將班上學(xué)生聚類，假設(shè)隱藏變量z是身高，那么就是連續(xù)的高斯分布。 如果按照隱藏變量是男女，那么就是伯努利分布（即兩點(diǎn)分布：）了。

上總式第1到第2步是分子分母同乘一個(gè)數(shù)，

第2到3步是：用了jasen不等式： （凸函數(shù)圖形上表示反為凹函數(shù)，記住。）

如圖：  。因?yàn)榈?步log是凹函數(shù) ：，所以f(E(x)) >= E[f(x)].這樣就完成了第3步（詳情見對(duì)應(yīng)講義。）

至此推導(dǎo)完上面3步公式，下面所有模型都是對(duì)上面第3步公式進(jìn)行參數(shù)估計(jì)的！?。?/p>

下面 對(duì)第三步的Q(z)進(jìn)行推導(dǎo)：

（見講義）

所以Q(Z)最終表示： ，其中z只受參數(shù)θ影響。

所以EM算法：

（承上啟下：在m步中，最終是對(duì)參數(shù)θ進(jìn)行估計(jì)，而這一步具體到高斯混合模型，則θ有三個(gè)參數(shù)：mu,phi,sigma代替，即高斯混合模型要推導(dǎo)三個(gè)參數(shù)，下面會(huì)講）

至此，這就是EM算法所有推導(dǎo)，EM算法推導(dǎo)也只能推導(dǎo)這些步，具體再將這些公式推導(dǎo)下去，就要結(jié)合模型了。

總結(jié)：

如果將樣本看作觀察值， 潛在類別看作是隱藏變量，   那么聚類問題也就是參數(shù)估計(jì)問題，只不過聚類問題中參數(shù)分為隱含類別變量和其他參數(shù)。

對(duì)應(yīng)到EM上，E步估計(jì)隱含變量，M步估計(jì)其他參數(shù)，交替將極值推向最大。

例子：在Mitchell的Machine Learning書中也舉了一個(gè)EM應(yīng)用的例子，將班上學(xué)生的身高都放在一起，要求聚成兩個(gè)類。這些身高可以看作是男生身高的高斯分布和女生 身高的高斯分布組成。因此變成了如何估計(jì)每個(gè)樣例是男生還是女生，然后在確定男女生情 況下，如何估計(jì)均值和方差，里面也給出了公式。

二、混合高斯模型：

將EM算法融到高斯混合模型，將上面EM算法的E步、M步的公式再具體推導(dǎo)下去。

整個(gè)模型簡(jiǎn)單描述為：

對(duì)于每個(gè)樣例 ，我們先從k個(gè)類別中按多項(xiàng)式分布抽取一個(gè)，

然后根據(jù)所對(duì)應(yīng)的 k 個(gè)多值高斯分布中的一個(gè)，生成樣例，整個(gè)過程稱作混合高斯模型。

（即對(duì)樣例x， 最終目的是生成樣例x。（？？）即對(duì)樣例x，從k個(gè)類別抽取一個(gè)z,從根據(jù)z生成x。）

特別地，混合高斯模型的

（1）隱含類別標(biāo)簽 ，被認(rèn)為滿足多項(xiàng)式分布，即  (這里只受?參數(shù)（即phi）影響)

（2）樣例被認(rèn)為滿足 高斯分布，即   (所以μ和Σ分別為樣例x的均值和協(xié)方差)

  　　　　　　　　　　 補(bǔ)充：服從的多項(xiàng)式分布概率公式為：，即類似C(n,x)*p6^x*(1-p6)^(n-x) 類型

　　所以 上面（1）（2）可知混合高斯模型中， 這里的仍是隱含隨機(jī)變量。模型細(xì)化多了三個(gè)變量?，μ和Σ。(即是phi,mu,sigma). 

其中?j就是樣本類別中  = j的比率。μj是類別為 j 的樣本特征均值，Σj是類別為 j 的樣例的特征的協(xié)方差矩陣(Σj是一個(gè)矩陣！！)。

所以由上面（1）（2）合并得，最大似然估計(jì)p(x, z)，對(duì)數(shù)化后如下：

  （對(duì)比一、EM算法里的總式： ，只是參數(shù)θ由原化成三個(gè)?，μ和Σ）

注意第二步有兩個(gè)迭加號(hào)。第二個(gè)迭加號(hào)是z(i)=1 直到k個(gè)類別。z只有k個(gè)類別。

參考一、中EM算法推導(dǎo)：

所以混合高斯模型：

從EM算法步驟的   變成： （其中M步三個(gè)參數(shù)的右邊公式在下面會(huì)進(jìn)行推導(dǎo)。這里直接先給出參數(shù)結(jié)果。）

1. E步：   每個(gè)樣例i的隱含類別z(i)為j的概率  可以通過條件概率計(jì)算得到。即

　　　　  （E）

　　　　　　　　　　　　　　　　　　　　（這里貝葉斯公式，分子是z=j一種類別情況，分母是z={1~k}k中類別的累加）　

　　　　1）對(duì)上式的分子第一項(xiàng)：（由上面加黃色背景段文字可知）服從高斯分布：，

　　　　　　故 =    。（其中Σ即是）

　　　　2）對(duì)(E)式分子第二項(xiàng)（又上面可知） 服從 多項(xiàng)式分布：

           所以分子直接代入即可，所以 可以求得。

2.M步：

　　　　先給出最終結(jié)果為: ,推導(dǎo)如下：

　　　　　　先看EM算法的M步：

                   （M）

 　　　　　下面對(duì)三個(gè)參數(shù)phi,mu,sigma(?，μ和Σ)分別進(jìn)行求導(dǎo):

　　　　　（i）對(duì)μi 求導(dǎo)得(固定i，Σi):

　　　　　　　       <--  它是由　　　（據(jù)Ng說求的過程不重要？）等于0時(shí)所得　

　　　　　（ii）對(duì)i求導(dǎo)(固定μi，Σi）：

 　　              　　   推導(dǎo)過程用了SVM中的拉格朗日乘子方法：

　　　　　　　　　　因?yàn)?i是 隱性隨機(jī)變量z的多項(xiàng)式分布概率值，又有約束條件   

　　　　　　　　　　又由上面（M）步公式：

　　　　　　　　　　（why?????）

                               所以聯(lián)合上兩式，直接構(gòu)成拉格朗日乘子：

　　　　　　　　　　　，   

　　　　　（iii）Σ的推導(dǎo)：

　　　　　　　　　　也類似，不過稍微復(fù)雜一些，畢竟是矩陣。結(jié)果在之前的混合高斯模型中已經(jīng)給出。

3.迭代：對(duì)上面E,M步進(jìn)行迭代，最后一定會(huì)收斂（證明見講義）

　　　　　　如圖，最終收斂成2個(gè)類，這里的樣例收斂于橢圓，原因是高斯分布的二維幾何圖形是一個(gè)橢圓，（具體幾何圖形見下面因子分析，有詳解）

拓展：

混合高斯模型GMM與K-means比較：

相同點(diǎn)：都是可用于聚類的算法；都需要指定K值。

不同點(diǎn)：對(duì)GMM來說，引入了概率；GMM可以給出一個(gè)樣本屬于某類的概率是多少。所以高斯混合模型既可以做聚類，也可做概率密度估計(jì)

 三、混合樸素貝葉斯模型

   混合高斯的例子：文本聚類: 要對(duì)一系列的文本聚類成若干主題。（用svm寫文本分類是最好的）

　news.google.com就是文本聚類一個(gè)應(yīng)用

　　怎樣在文本新聞問題用到EM算法呢?

　　----->混合樸素貝葉斯模型?；旌蠘闼刎惾~斯模型有2個(gè)：多值伯努利事件模型（文本聚類就是用此）；多項(xiàng)式事件模型。

    模型描述為：

　　給定m個(gè)樣本的訓(xùn)練集合是 ， 每個(gè)文本屬于(0,1)^n。即每個(gè)文本是n維 0或1的向量。

　　故= { wordj 是否出現(xiàn)在文本i 里} 

　　我們要對(duì)(值是0或1) 進(jìn)行建模，是隱含隨機(jī)變量，這里取兩個(gè)值：2個(gè)聚類。

    所以對(duì)混合貝葉斯模型，假設(shè)  服從參數(shù)有伯努利分布（兩點(diǎn)分布），即： 圖中x換成即可）。

     故每個(gè)文本按某概率屬于聚類1或者聚類2

   同高斯混合模型，混合貝葉斯模型的聯(lián)合概率是：

　　又     由貝葉斯公式可知：

     p(|) = p(| )     （i）

    p( = 1 | = 0)  =          (ii)

        把上面的z全部換成y,就得到常見的樸素貝葉斯公式：

 一般會(huì)前面兩個(gè)等式右邊的x=1，或省去=1，即寫成i|y=1 = p(xi | y =1)      i|y=0  = p(xi | y =0) ,默認(rèn)x取了1  

　　其中p(y=1)表示類別1（例如類別1表示垃圾郵件）的在所有文本的概率。這里xi表示一個(gè)單詞，取值只有0或者1，表示出現(xiàn)在文本里或者沒有出現(xiàn)。

EM算法步驟：

1.E步：

　　　 這里三個(gè)參數(shù)phi,mu,sigma,改成，，與?j|z

               將上面（i）（ii）式帶入即可求得

2.M步：

　　　　　　　　對(duì)比貝葉斯原公式：

 　　　　  =     

　　　　　　　　     這里Wi表示文本來自于類1，分子Σ表示：類1且包含詞j的文檔個(gè)數(shù)，分布表示類1的文檔總數(shù)。所以全式表示：類1包含詞j的比率。

 　　     　　　　　　EM算法不能做出絕對(duì)的假設(shè)0或者1，所以只能用Wi表示，最終Wi的值會(huì)靠近0或1，在數(shù)值上與0或1無分別。

　　　　  =   （分子的橫斜是多余的，忽略）

　　　　　　　　　　　　　　全式表示：類0包含詞j的比率

　　　        j|z         =  

3.迭代上面12步驟，收斂，求出參數(shù)估計(jì)，帶回聯(lián)合概率，將聯(lián)合概率排序，由聯(lián)合概率最高值 ，可得知哪個(gè)文本是輸入哪個(gè)類了。