EM算法的數(shù)學(xué)原理

摘要

        EM算法主要分為兩個步驟：E-step和M-step，主要應(yīng)用在概率模型中。機器學(xué)習(xí)中，概率模型在進(jìn)行參數(shù)估計時，我們主要應(yīng)用的是最大似然估計，所以在對EM算法進(jìn)行討論時，是離不開最大似然估計的。EM算法主要是用來解決那些樣本中存在隱變量的情況。E-step固定模型參數(shù)通過數(shù)學(xué)模型求解隱變量，M-step根據(jù)E-step求得的隱變量在通過最大似然估計最大化似然函數(shù)從而求出模型的參數(shù)，這樣相互的迭代，從而得到模型的局部最優(yōu)解。EM算法主要應(yīng)用在聚類算法中，因為一般情況下聚類問題都存在一個隱變量。

什么是隱變量

        樣本中存在隱變量即我們在對數(shù)據(jù)進(jìn)行采樣中，可以認(rèn)為隱變量是那些我們不能通過數(shù)據(jù)采樣所能確定的屬性。如果不存在隱變量，那對于一些聚類模型，我們的參數(shù)求解就簡單很多，比如k-means，k-means只是利用了EM算法的思想。我們有一批數(shù)據(jù)，想利用k-means算法來進(jìn)行聚類分析，對于k-means算法，我們要確定的是k和k個質(zhì)心，假如我們在對這批數(shù)據(jù)采樣時已經(jīng)知道他們分為4類，而且采樣前就已經(jīng)把數(shù)據(jù)給分好類了，已經(jīng)知道了，還用聚類算法干嘛，我們這是暫時的假設(shè)用他來舉例說明什么是隱變量，那么我們在用k-means算法時就變得很簡單了，直接求出這k個質(zhì)心，而不用我們所熟知的k-means算法的計算步驟。之所以我們使用我們所熟知的k-means算法的步驟，那是因為我們不知道每個樣本應(yīng)該歸屬于哪個類以及他們存在多少個聚類中心比較合適。那么這個隱變量就是每一個樣本應(yīng)該歸屬于哪個類。在舉一個例子，高斯混合模型，這個是典型用到了EM算法的思想，如果對這個模型不太清楚，可以網(wǎng)上查資料。同樣，我們也有這樣一批數(shù)據(jù)，在采樣中，我們就已經(jīng)知道k和每個樣本應(yīng)該屬于哪個類，那么我們所要做的工作就是把每一類數(shù)據(jù)拿出來，直接通過均值和方差就可以求出每一個高斯函數(shù)的模型了，而不需要再進(jìn)行EM算法通過最大似然估計來計算我們的高斯混合模型參數(shù)了。而現(xiàn)實的應(yīng)用中是我們不知道這樣的一批數(shù)據(jù)應(yīng)該分為幾個類以及每一個樣本應(yīng)該屬于哪一個類，那么這就是隱變量。這樣的問題和先有雞還是先有蛋的問題差不多，當(dāng)我們知道數(shù)學(xué)模型的參數(shù)后，我們就知道了樣本應(yīng)該屬于哪個類，同時當(dāng)我們知道隱變量后，我們也就知道樣本屬于哪個類，從而得到數(shù)學(xué)模型的參數(shù)，但是不幸的是在開始的時候我們只有樣本，隱變量和模型參數(shù)都不知道。

凸函數(shù)和凹函數(shù)以及其性質(zhì)

為什么要講這個，因為EM算法得以實施的基礎(chǔ)就是函數(shù)的凹凸性以及凹凸函數(shù)的一些性質(zhì)。所以這里還是說一下吧。

在高等數(shù)學(xué)和數(shù)學(xué)分析(數(shù)學(xué)專業(yè)的書)對于凹凸函數(shù)的定義可能有些不一樣。這個沒有關(guān)系只是叫法不同，但是他們這些圖形和圖形的性質(zhì)是一樣的。

凸函數(shù)定義：函數(shù)的二階導(dǎo)函數(shù)在一定的區(qū)間內(nèi)大于等于零，性質(zhì)如下

如下圖：

凹函數(shù)的定義：函數(shù)的二階導(dǎo)函數(shù)在一定的區(qū)間內(nèi)小于等于零，性質(zhì)如下：

如下圖所示：

最大似然估計步驟

因為在概率模型中，進(jìn)行參數(shù)估計一般都采用最大似然估計

1、確定概率模型求出似然函數(shù)

2、對似然函數(shù)取log，把連乘變?yōu)榍蠛?/span>

3、對變換后的似然函數(shù)求導(dǎo)，并另導(dǎo)數(shù)等于0，然后整理得到似然方程組

4、求解似然方程組，得到模型參數(shù)

EM算法

假設(shè)我們有一批數(shù)據(jù)樣本{x(1),…,x(n)},，樣本容量為n，概率模型為p(x,z)來對我們的數(shù)據(jù)進(jìn)行擬合。根據(jù)概率模型的參數(shù)估計算法，我們可以得到似然函數(shù)：

上式中（1）我們是通過最大似然估計的步驟獲取的，從（1）到（2）引入了樣本屬于某一個類的概率函數(shù)，從而對某一個樣本求得該樣本屬于某個類的全概率公式，即引入了隱變量z。

當(dāng)我們采用傳統(tǒng)的概率模型求解參數(shù)的方法即最大似然估計，對上述式子進(jìn)行求導(dǎo)數(shù)，從而得到似然方程：

我們會發(fā)現(xiàn)上述似然方程中存在對數(shù)，并且對數(shù)里面是個求和公式，這種求解是很難得到參數(shù)的解析解的。遇到胡同了，我們就要想一下拐一下彎，既然這個公式無法求解的難點在于對數(shù)里面有求和公式，那么我們能不能采用什么辦法把對數(shù)后面的求和號給拿到外面。再看看對數(shù)函數(shù)的性質(zhì)是什么樣子的？對數(shù)函數(shù)是一個凹函數(shù)那么他肯定滿足凹函數(shù)的基本性質(zhì)：

把上式進(jìn)行變換：

我們的目標(biāo)函數(shù)和凹函數(shù)的性質(zhì)還差那么一點點的差距，那么我們就認(rèn)為對于每一個實例i，用Qi表示對應(yīng)于隱含變量即其屬于哪個類的概率分布，我們這是對于一個樣本而言的，那么樣本有n個，就會存在n個這樣的Qi的函數(shù)分布，一定要把這一點弄明白。這個Qi表示的樣本i對應(yīng)于k個類，其屬于這k個類的概率分布。那么Qi應(yīng)該滿足的條件是：

那么我們就可以把我們的似然函數(shù)進(jìn)行改寫了：

這樣一看就和我們的凹函數(shù)性質(zhì)一致了吧。于是我們可以把上述函數(shù)通過凹函數(shù)的性質(zhì)進(jìn)行變換：

既然原函數(shù)無法得到最優(yōu)解，我們可以通過調(diào)整原函數(shù)的下界函數(shù)，對原函數(shù)的下界函數(shù)求最大值，從而使原函數(shù)逐步逼近最優(yōu)解或者得到一個局部最優(yōu)解。即我們不停的求解上式中（4）的最大值，從而是我們原函數(shù)逼近最優(yōu)解。

看到這可能會有一個問題，通過最大似然估計得到的原似然方程無法得到解析解，為什么變成（4）就可以得到了呢？我們在已知隱變量的前提下對模型參數(shù)進(jìn)行求偏導(dǎo)得到的似然方程中，發(fā)現(xiàn)log已經(jīng)不復(fù)存，已經(jīng)變成了我們熟悉的線性方程組或者非線性方程組(這個跟數(shù)學(xué)模型有關(guān))，一般情況下這個就可以利用線性代數(shù)的理論進(jìn)行求解了啊。

因此EM算法的基本思想就是通過引入隱變量，先得到樣本屬于某一個類的概率，然后再使用最大似然估計最大化似然函數(shù)來求解參數(shù)，得到參數(shù)以后，數(shù)學(xué)模型就已經(jīng)確定，那么我就可以得到樣本屬于哪個類了，從而得到隱變量的值，因此就用迭代的進(jìn)行求解最終得到問題的解。當(dāng)我們引入隱變量后，整個似然函數(shù)就會存在兩類參數(shù)類型：隱變量和數(shù)學(xué)模型的參數(shù)。那么EM算法采用的步驟如下：

E-step: 通過固定數(shù)學(xué)模型的參數(shù)，利用現(xiàn)有樣本對隱變量進(jìn)行參數(shù)估計，即求出隱變量的期望也就是我們期望樣本屬于哪一個類

M-step: 通過E-step求得的隱變量，對數(shù)學(xué)模型參數(shù)求導(dǎo)，最大化似然函數(shù)。

隱變量的求解

對于EM算法，我們是不斷的逼近最優(yōu)值，那么E-step計算的是什么呢？因為在凹函數(shù)的性質(zhì)中上述不等式取等號的前提條件是xi為常數(shù)

則：

對上式進(jìn)行求和：

通過上述兩個式子我們進(jìn)行變換得到：

在上式中從（1）到（2）為什么會是這樣，我們按照舉個例子，用二元一次函數(shù)的積分問題來看待這個問題的推導(dǎo)，因為積分的實質(zhì)也是一種求和對函數(shù)下部的面積進(jìn)行無線的拆分然后再求和。如下式的二元函數(shù)：

然后我們對上面的二元一次函數(shù)對y進(jìn)行求積分：

從而消除了變量y，同樣的道理，從（1）到（2）的過程中，我們分母對樣本i的所有的可能隱變量取值求和，從而把隱變量z給消除，從而得到公式（2）從（2）到（3）是通過條件概率的公式得到的。因此我們可以發(fā)現(xiàn)隱變量其實就是在固定數(shù)學(xué)模型參數(shù)和已知數(shù)據(jù)樣本的情況下的后驗概率。

以上只是理論部分，下面我們簡單說一下EM算法的實際應(yīng)用。

在實際應(yīng)用中我們不會按照上面公式來推導(dǎo)我們的算法。我們只知道兩個點就可以了：隱變量的求解和已知隱變量的前提下最大化似然函數(shù)從而來求解數(shù)學(xué)模型的參數(shù)。

隱變量的求解：我們已經(jīng)知道其是樣本和數(shù)學(xué)模型參數(shù)的后驗概率，那么我就可以根據(jù)實際的情況來推導(dǎo)計算這個后驗概率從而得到我們的隱變量和參數(shù)的關(guān)系表達(dá)式從而用于迭代求解即為E-step

最大化似然函數(shù)：這個是我們最大似然估計算法的步驟了即M-step。

---能力有限，存在不對的地方，望請指教。