第8章EM算法及其應用主要內(nèi)容EM算法的簡介EM算法的數(shù)學推導EM算法的流程EM算法的優(yōu)缺點EM算法的應用EM算法的簡介EM算法是一種迭代優(yōu)化算法。主要用于含有隱變量的模型的參數(shù)估計。含有隱變量的模型往往用于對不完全數(shù)據(jù)進行建模。EM算法是一種參數(shù)估計的思想，典型的EM算法有高斯混合模型、隱馬爾可夫模型和K-均值聚類等。EM算法的數(shù)學推導Jensen不等式設x是一個隨機變量，f

是作用于隨機變量x上的下凸函數(shù)，則有Jensen不等式在為常數(shù)時取等號。設是一個二維空間中的下凸函數(shù)，是和之間的任意一點，即直觀上可以看出Jensen不等式成立。EM算法的數(shù)學推導Jensen不等式推導圖EM算法的數(shù)學推導在含有隱變量的模型中，給定觀測數(shù)據(jù)x

，設其對應的隱變量為z，稱為完全數(shù)據(jù)。產(chǎn)生觀測數(shù)據(jù)的模型記為其中為參數(shù)，為完全數(shù)據(jù)的聯(lián)合概率分布。EM算法的數(shù)學推導假設經(jīng)過t輪迭代后，模型參數(shù)的估計值為。此時，根據(jù)參數(shù)可以得到當前時刻隱變量的分布EM算法的數(shù)學推導根據(jù)極大似然估計原理，模型的對數(shù)似然函數(shù)為EM算法的數(shù)學推導將看作隨機變量的函數(shù)，則有由Jensen不等式有EM算法的數(shù)學推導上式中為隨機變量關于隱變量分布的期望，是隱變量分布的熵。上式給出了對數(shù)似然函數(shù)的一個下界，EM算法的思想就是通過最大化這個下界使得最大。因為與無關，所以只考慮優(yōu)化即可，稱該式為Q函數(shù)EM算法的數(shù)學推導對于多個樣本，可以定義Q函數(shù)為每個樣本的Q函數(shù)之和，也即似然函數(shù)關于隱變量集的期望。這就是EM算法中E(Expectation)的由來。接下來，關于極大化Q函數(shù)得到，就是EM算法中M(Maximization)的過程。EM算法的流程輸入：聯(lián)合概率分布函數(shù)；觀察數(shù)據(jù)；隱變量；EM算法迭代次數(shù)M。輸出：模型EM算法的流程EM算法的優(yōu)點EM算法相比于其他算法的優(yōu)勢是其求解框架可以加入求解目標的額外約束，例如在高斯混合模型的例子中，EM算法在求解協(xié)方差時可以確保每次迭代的結果都是正定矩陣。EM算法的缺點EM算法的不足在于其會陷入局部最優(yōu)，在高維數(shù)據(jù)的問題中，局部最優(yōu)和全局最優(yōu)可能有很大差異。EM算法的應用之高斯混合模型高斯混合模型（GaussianMixtureModel,GMM）是EM算法的一個典型應用。下面以高斯混合聚類來闡述高斯混合模型。根據(jù)大數(shù)定律，人群中的身高分布應呈高斯分布。現(xiàn)給定一個隨機采樣而來的學生身高的樣本集合，設身高服從的高斯分布為，其中為待估計的參數(shù)。高斯分布的概率密度函數(shù)為EM算法的應用之高斯混合模型根據(jù)極大似然估計原理，身高分布的對數(shù)似然函數(shù)為令對數(shù)似然函數(shù)對和的導數(shù)為0，即可求得和的估計值和EM算法的應用之高斯混合模型現(xiàn)在，假設我們需要對全部的樣本進行聚類，分成男人和女人兩個類別。根據(jù)大數(shù)定律，男人和女人的身高分別服從高斯分布，設其參數(shù)分別為和。估計出這兩個分布的參數(shù)，即可估計出任意樣本屬于這兩個分布的概率。高斯混合模型就是基于這樣的思想完成聚類任務的。EM算法的應用之高斯混合模型高斯混合模型是若干個高斯模型的加權求和，其形式為其中為第i個子模型的權重，為混合模型的參數(shù)。高斯混合假設數(shù)據(jù)的產(chǎn)生過程分為兩步1) 以概率采樣選取一個高斯分布2) 在中進行m次采樣后獲得觀測數(shù)據(jù)集合EM算法的應用之高斯混合模型然而，我們最終看到的只有數(shù)據(jù)集，實際的采樣過程是無法觀測的，也即無法觀測到每個觀測是從那個子模型采樣的。記隨機變量第i次采樣過程中選擇的高斯分布編號。由于不可觀測，所以稱為隱變量。EM算法的應用之高斯混合模型以人群身高的聚類問題為例，可以認為采樣獲得學生身高數(shù)據(jù)集的過程為1) 以概率隨機選擇一個性別，設這個性別的身高服從高斯分布2) 在中進行采樣獲得一個身高數(shù)據(jù)估計兩種性別對應的高斯分布參數(shù)的過程是：對于每個樣本，計算性別分布，并假設性別為，直到將所有樣本都歸類完為止。稱為的后驗概率分布，表示來自第k個高斯分布的概率。EM算法的應用之高斯混合模型根據(jù)貝葉斯定理有記為t次迭代后的模型參數(shù)。當給定時，記，此時為常數(shù)。根據(jù)上式寫出Q函數(shù)，即EM算法的E步EM算法的應用之高斯混合模型極大化Q函數(shù)，即EM算法的M步。令Q函數(shù)對的導數(shù)為0可得最后考慮參數(shù)。在滿足且的條件下極大化Q函數(shù)，這是一個帶有約束條件的最優(yōu)化問題，可通過拉格朗日乘子法求解。構造拉格朗日函數(shù)EM算法的應用之高斯混合模型令拉格朗日函數(shù)對的導數(shù)為0可得于是EM算法的應用之高斯混合模型對于前述人群分類的例子，假設以毫米（mm）為單位的男女身高對應高斯分布分別為使用計算機模擬采樣得到10000個男性身高樣本和10000個女性身高樣本，共20000個樣本。采樣的頻數(shù)分布直方圖如圖所示EM算法的應用之高斯混合模型現(xiàn)對其利用高斯混合模型聚類，可以估計出男女的高斯分布分布為對應的模型權重分別為EM算法的應用之高斯混合模型從下圖中可以看到，通過高斯混合模型得到的高斯分布與采樣用的高斯分布非常接近。高斯聚類的分類準確率約為83.2%。本例中兩個高斯分布有較大面積的重疊，如果高斯混合模型的各個子模型均值之間距離更大、方差更小，則聚類準確率會更高。EM算法的應用之隱馬爾科夫模型EM算法的另一個典型應用就是隱馬爾可夫模型。隱馬爾可夫模型是經(jīng)典的序列建模算法，在語音識別、詞性標注、機器翻譯等領域有著廣泛的應用。估計隱馬爾可夫模型的參數(shù)就是帶有隱變量的極大似然估計問題，所以可以用EM算法進行參數(shù)估計。EM算法的應用之隱馬爾科夫模型假設觀測序列的樣本集合為。假設經(jīng)過l輪迭代得到的參數(shù)為，令隨機變量表示可能的狀態(tài)序列，則Q函數(shù)為因為參數(shù)已知，所以為常數(shù)。于是有隱變量的概率分布EM算法的應用之隱馬爾科夫模型因此Q函數(shù)可以寫作首先通過拉格朗日乘子法求。由于，所以拉格朗日函數(shù)為令拉格朗日函數(shù)對的導數(shù)為0EM算法的應用之隱馬爾科夫模型可得于是EM算法的應用之隱馬爾科夫模型下面通過拉格朗日乘子法求。由于，所以拉格朗日函數(shù)為令拉格朗日函數(shù)對的導數(shù)為0