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

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

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