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

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

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

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