機器學(xué)習(xí)原理及應(yīng)用課件第8章

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

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

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