混合高斯模型(Mixtures-of-Gaussians)和EM算法

混合高斯模型(Mixtures-of-Gaussians)和EM算法混合高斯模型（MixturesofGaussians）和EM算法

這篇討論使用期望最大化算法（Expectation-Maximization）來(lái)進(jìn)行密度估計(jì)（densityestimation）。

與k-means一樣，給定的訓(xùn)練樣本是，我們將隱含類別標(biāo)簽用表示。與k-means的硬指定不同，我們首先認(rèn)為是滿足一定的概率分布的，這里我們認(rèn)為滿足多項(xiàng)式分布，，其中，有k個(gè)值{1,…,k}可以選取。而且我們認(rèn)為在給定后，滿足多值高斯分布，即。由此可以得到聯(lián)合分布。

整個(gè)模型簡(jiǎn)單描述為對(duì)于每個(gè)樣例，我們先從k個(gè)類別中按多項(xiàng)式分布抽取一個(gè)，然后根據(jù)所對(duì)應(yīng)的k個(gè)多值高斯分布中的一個(gè)生成樣例，。整個(gè)過(guò)程稱作混合高斯模型。注意的是這里的仍然是隱含隨機(jī)變量。模型中還有三個(gè)變量和。最大似然估計(jì)為。對(duì)數(shù)化后如下：

這個(gè)式子的最大值是不能通過(guò)前面使用的求導(dǎo)數(shù)為0的方法解決的，因?yàn)榍蟮慕Y(jié)果不是closeform。但是假設(shè)我們知道了每個(gè)樣例的，那么上式可以簡(jiǎn)化為：

這時(shí)候我們?cè)賮?lái)對(duì)和進(jìn)行求導(dǎo)得到：

就是樣本類別中的比率。是類別為j的樣本特征均值，是類別為j的樣例的特征的協(xié)方差矩陣。實(shí)際上，當(dāng)知道后，最大似然估計(jì)就近似于高斯判別分析模型（Gaussiandiscriminantanalysismodel）了。所不同的是GDA中類別y是伯努利分布，而這里的z是多項(xiàng)式分布，還有這里的每個(gè)樣例都有不同的協(xié)方差矩陣，而GDA中認(rèn)為只有一個(gè)。

之前我們是假設(shè)給定了，實(shí)際上是不知道的。那么怎么辦呢？考慮之前提到的EM的思想，第一步是猜測(cè)隱含類別變量z，第二步是更新其他參數(shù)，以獲得最大的最大似然估計(jì)。用到這里就是：循環(huán)下面步驟，直到收斂：{

（E步）對(duì)于每一個(gè)i和j，計(jì)算

（M步），更新參數(shù)：

}

對(duì)應(yīng)于上述問(wèn)題，Y是，X是，是，g是到的映射。這樣解釋了式子（2）中的期望，再根據(jù)凹函數(shù)時(shí)的Jensen不等式：

可以得到（3）。

這個(gè)過(guò)程可以看作是對(duì)求了下界。對(duì)于的選擇，有多種可能，那種更好的？假設(shè)已經(jīng)給定，那么的值就決定于和了。我們可以通過(guò)調(diào)整這兩個(gè)概率使下界不斷上升，以逼近的真實(shí)值，那么什么時(shí)候算是調(diào)整好了呢？當(dāng)不等式變成等式時(shí)，說(shuō)明我們調(diào)整后的概率能夠等價(jià)于了。按照這個(gè)思路，我們要找到等式成立的條件。根據(jù)Jensen不等式，要想讓等式成立，需要讓隨機(jī)變量變成常數(shù)值，這里得到：

c為常數(shù)，不依賴于。對(duì)此式子做進(jìn)一步推導(dǎo)，我們知道，那么也就有，（多個(gè)等式分子分母相加不變，這個(gè)認(rèn)為每個(gè)樣例的兩個(gè)概率比值都是c），那么有下式：

至此，我們推出了在固定其他參數(shù)后，的計(jì)算公式就是后驗(yàn)概率，解決了如何選擇的問(wèn)題。這一步就是E步，建立的下界。接下來(lái)的M步，就是在給定后，調(diào)整，去極大化的下界（在固定后，下界還可以調(diào)整的更大）。那么一般的EM算法的步驟如下：循環(huán)重復(fù)直到收斂{

（E步）對(duì)于每一個(gè)i，計(jì)算

（M步）計(jì)算

那么究竟怎么確保EM收斂？假定和是EM第t次和t+1次迭代后的結(jié)果。如果我們證明了，也就是說(shuō)極大似然估計(jì)單調(diào)增加，那么最終我們會(huì)到達(dá)最大似然估計(jì)的最大值。下面來(lái)證明，選定后，我們得到E步

這一步保證了在給定時(shí)，Jensen不等式中的等式成立，也就是

然后進(jìn)行M步，固定，并將視作變量，對(duì)上面的求導(dǎo)后，得到，這樣經(jīng)過(guò)一些推導(dǎo)會(huì)有以下式子成立：

解釋第（4）步，得到時(shí)，只是最大化，也就是的下界，而沒有使等式成立，等式成立只有是在固定，并按E步得到時(shí)才能成立。

況且根據(jù)我們前面得到的下式，對(duì)于所有的和都成立

第（5）步利用了M步的定義，M步就是將調(diào)整到，使得下界最大化。因此（5）成立，（6）是之前的等式結(jié)果。

這樣就證明了會(huì)單調(diào)增加。一種收斂方法是不再變化，還有一種就是變化幅度很小。

再次解釋一下（4）、（5）、（6）。首先（4）對(duì)所有的參數(shù)都滿足，而其等式成立條件只是在固定，并調(diào)整好Q時(shí)成立，而第（4）步只是固定Q，調(diào)整，不能保證等式一定成立。（4）到（5）就是M步的定義，（5）到（6）是前面E步所保證等式成立條件。也就是說(shuō)E步會(huì)將下界拉到與一個(gè)特定值（這里）一樣的高度，而此時(shí)發(fā)現(xiàn)下界仍然可以上升，因此經(jīng)過(guò)M步后，下界又被拉升，但達(dá)不到與另外一個(gè)特定值一樣的高度，之后E步又將下界拉到與這個(gè)特定值一樣的高度，重復(fù)下去，直到最大值。

如果我們定義

從前面的推導(dǎo)中我們知道，EM可以看作是J的坐標(biāo)上升法，E步固定，優(yōu)化，M步固定優(yōu)化。3.重新審視混合高斯模型

我們已經(jīng)知道了EM的精髓和推導(dǎo)過(guò)程，再次審視一下混合高斯模型。之前提到的混合高斯模型的參數(shù)和計(jì)算公式都是根據(jù)很多假定得出的，有些沒有說(shuō)明來(lái)由。為了簡(jiǎn)單，這里在M步只給出和的推導(dǎo)方法。E步很簡(jiǎn)單，按照一般EM公式得到：

簡(jiǎn)單解釋就是每個(gè)樣例i的隱含類別為j的概率可以通過(guò)后驗(yàn)概率計(jì)算得到。

在M步中，我們需要在固定后最大化最大似然估計(jì)，也就是

這是將的k種情況展開后的樣子，未知參數(shù)和。

固定和，對(duì)求導(dǎo)得

等于0時(shí)，得到

這就是我們之前模型中的的更新公式。

然后推導(dǎo)的更新公式?？粗暗玫降?/p>

在和確定后，分子上面的一串都是常數(shù)了，實(shí)際上需要優(yōu)化的公式是：

需要知道的是，還需要滿足一定的約束條件就是。

這個(gè)優(yōu)化問(wèn)題我們很熟悉了，直接構(gòu)造拉格朗日乘子。

還有一點(diǎn)就是，但這一點(diǎn)會(huì)在得到的公式里自動(dòng)滿足。

求導(dǎo)得，

等于0，得到

也就是說(shuō)再次使用，得到

這樣就神奇地得到了。

那么就順勢(shì)得到M步中的更新公式：

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

如果將樣本看作觀察值，潛在類別看作是隱藏變量，那么聚類問(wèn)題也就是參數(shù)估計(jì)問(wèn)題，只不過(guò)聚類問(wèn)題中參數(shù)分為隱含類別變量和其他參數(shù)，這猶如在x-y坐標(biāo)系中找一個(gè)曲線的極值，然而曲線函數(shù)不能直接求導(dǎo)，因此什么梯度下降方法就不適用了。但固定一個(gè)變量后，另外一個(gè)可以通過(guò)求導(dǎo)得到，因此可以使用坐標(biāo)上升法，一次固定一個(gè)變量，對(duì)另外的求極值，最后逐步逼近極值。對(duì)應(yīng)到EM上，E步估計(jì)隱含變量，M步估計(jì)其他參數(shù)，交替將極值推向最大。EM中還有“硬”指定和“軟”指定的概念，“軟”指定看似更為合理，但計(jì)算量要大，“硬”指定在某些場(chǎng)合如K-means中更為實(shí)用（要是保持一個(gè)樣本點(diǎn)到其他所有中心的概率，就會(huì)很麻煩）。

另外，EM的收斂性證明方法確實(shí)很牛，能夠利用log的凹函數(shù)性質(zhì)，還能夠想到利用創(chuàng)造下界，拉平函數(shù)下界，優(yōu)化下界的方法來(lái)逐步逼近極大值。而且每一步迭代都能保證是單調(diào)的。最重要的是證明的數(shù)學(xué)公式非常精妙，硬是分子分母都乘以z的概率變成期望來(lái)套上Jensen不等式，前人都是怎么想到