趙桂儒，李衛(wèi)東，劉典婷，吳 敏，崔滿豐

（1.中國(guó)地震臺(tái)網(wǎng)中心，北京 100045；2.邁阿密大學(xué)，美國(guó) 佛羅里達(dá)州 33146）

高斯混合模型（Gaussian Mixture Model，GMM）作為一種通用的概率模型，能有效地模擬多維矢量的任意連續(xù)概率分布，在此基礎(chǔ)上發(fā)展起來的高斯混合模型通用背景模型（GMM-UBM）在語音識(shí)別[1]、圖像識(shí)別和檢索[2-4]等領(lǐng)域都取得了良好的效果。

GMM-UBM需要大量的訓(xùn)練樣本數(shù)據(jù)通過GMM模擬所有樣本數(shù)據(jù)的空間分布狀態(tài)作為通用背景模型，因此GMM參數(shù)的估算顯得尤為重要。期望最大化（Expectation Maximization，EM）算法是傳統(tǒng)的估計(jì)GMM參數(shù)的方法，樣本數(shù)據(jù)規(guī)模增大時(shí)，EM算法存在迭代次數(shù)多、運(yùn)行時(shí)間過長(zhǎng)等問題，這影響了GMM參數(shù)估算的速度。在不影響參數(shù)估算準(zhǔn)確程度的基礎(chǔ)上加快EM算法的運(yùn)行速度將具有非常重要的現(xiàn)實(shí)意義。

本文針對(duì)EM算法運(yùn)行時(shí)間過長(zhǎng)的問題，提出了一種改進(jìn)的EM算法，文章結(jié)合KTH人體行為數(shù)據(jù)庫(kù)，對(duì)改進(jìn)的EM算法從運(yùn)行速度和行為識(shí)別準(zhǔn)確率兩方面進(jìn)行了驗(yàn)證，結(jié)果顯示改進(jìn)后的EM算法能夠顯著提高GMM參數(shù)求解的速度，而對(duì)行為識(shí)別準(zhǔn)確率的影響非常小。

1 GMM-UBM及其參數(shù)求解

1.1 GMM-UBM

GMM-UBM用來描述所有樣本數(shù)據(jù)的分布狀態(tài)，其概率密度函數(shù)描述為

式中：x是D維特征向量；K代表高斯成分的數(shù)量；θ={ωk,μk,Σk}Kk=1是一組參數(shù)，包括每個(gè)高斯成分的權(quán)值ωk、均值向量μk和協(xié)方差矩陣Σk。

1.2 GMM參數(shù)求解

GMM的參數(shù)估計(jì)一般采用EM算法[5]，GMM的對(duì)數(shù)似然函數(shù)（log-likelihood function）為

式中：T為樣本總數(shù)，適合當(dāng)前樣本集的GMM參數(shù)將會(huì)使式（2）最大化。EM算法可分為E步和M步：

1）E步

根據(jù)當(dāng)前GMM的參數(shù)計(jì)算每行樣本數(shù)據(jù)屬于第k類分布的后驗(yàn)概率為

式中：γ(i,k)代表第i行樣本數(shù)據(jù)屬于第k類分布的后驗(yàn)概率。

2）M步

利用E步得出的概率值，重新估計(jì)每類分布的參數(shù)值

式中：N為重復(fù)1）和2）兩步直到式（2）收斂于一個(gè)充分小的值為止。

1.3 EM算法存在的問題及改進(jìn)

在實(shí)際應(yīng)用中，當(dāng)樣本數(shù)據(jù)規(guī)模較大、GMM的高斯成分?jǐn)?shù)K比較高時(shí)，EM算法往往需要運(yùn)行很長(zhǎng)時(shí)間并經(jīng)過多次迭代才能收斂，這成為EM算法估算GMM參數(shù)的一個(gè)瓶頸。通過1.2節(jié)中對(duì)E步和M步的分析可以發(fā)現(xiàn)，M步中重新估計(jì)每類高斯分布的參數(shù)值(ωk,μk,Σk)時(shí)，需要利用每行樣本數(shù)據(jù)xi及其屬于第k類高斯分布的后驗(yàn)概率值γ(i,k)來進(jìn)行計(jì)算。后驗(yàn)概率值γ(i,k)越大意味著xi對(duì)高斯分布參數(shù)估計(jì)的影響越大，反之亦然。舍棄那些后低驗(yàn)概率值對(duì)應(yīng)的數(shù)據(jù)，加快M步的運(yùn)算速度，從而節(jié)省估算GMM參數(shù)的時(shí)間是本文改進(jìn)EM算法的指導(dǎo)思想。

一行樣本數(shù)據(jù)xi屬于所有高斯分布的后驗(yàn)概率γ(i,k)的總和為1，因此理論上γ(i,k)的取值只有兩種情況：大于等于平均概率值1/K或者小于該值，如果γ(i,k)遠(yuǎn)小于（例如0.1%倍）平均概率值則意味著xi對(duì)估計(jì)第k類高斯分布參數(shù)值的影響更小，同時(shí)也意味著必有其他樣本數(shù)據(jù)xi在估計(jì)第k類高斯分布參數(shù)值時(shí)起到的作用更大。

鑒于此，本文提出了一種加快EM算法迭代速度的方法，基本思想為：在EM算法的M步中，只挑選部分特征數(shù)據(jù)來重新估計(jì)每類分布的參數(shù)值。挑選的原則為設(shè)置一個(gè)閾值CTH/K，當(dāng)在E步中計(jì)算出的后驗(yàn)概率γ(i,k)大于等于該閾值時(shí)，即選擇樣本數(shù)據(jù)xi，否則直接舍棄。

修改后的M步如下：

為了保證GMM參數(shù)求解的準(zhǔn)確程度，CTH應(yīng)當(dāng)越小越好，為了提高EM算法的運(yùn)行速度，CTH應(yīng)當(dāng)越大越好，這是一個(gè)矛盾，但總體上CTH的取值應(yīng)當(dāng)在0～1之間取舍。本文第3部分對(duì)CTH的設(shè)置進(jìn)行了實(shí)際驗(yàn)證和分析。

2 實(shí)驗(yàn)平臺(tái)的設(shè)計(jì)

通過對(duì)E步和M步的分析可知，當(dāng)樣本數(shù)據(jù)規(guī)模增大（行數(shù)增多、維數(shù)變大）、GMM的高斯成分?jǐn)?shù)K增多時(shí)EM算法的運(yùn)行時(shí)間將呈現(xiàn)非線性增長(zhǎng)，在小規(guī)模的數(shù)據(jù)集上驗(yàn)證改進(jìn)的EM算法將沒有實(shí)際意義，但在大規(guī)模數(shù)據(jù)上驗(yàn)證EM算法時(shí)又不能直觀地比較GMM參數(shù)估算值的差異，因此本文對(duì)改進(jìn)后EM算法的驗(yàn)證分成兩部分：第一部分在較大規(guī)模數(shù)據(jù)集上比較改進(jìn)前后EM算法的運(yùn)行速度，第二部分在實(shí)際應(yīng)用中比較改進(jìn)前后的EM算法對(duì)結(jié)果的影響。

2.1 數(shù)據(jù)準(zhǔn)備及運(yùn)行環(huán)境

為了讓算法的比較具有實(shí)際意義，文章選擇KTH人體行為數(shù)據(jù)庫(kù)作為實(shí)驗(yàn)對(duì)象，KTH數(shù)據(jù)庫(kù)由瑞典皇家理工學(xué)院的Schldt[6]等在人體行為識(shí)別的研究中提出，該數(shù)據(jù)庫(kù)包括6個(gè)常見的行為類別：拳擊（boxing）、擊掌（hand clapping）、揮手（hand waving）、慢跑（jogging）、行走（walking）和跑步（running）。每個(gè)行為由25個(gè)不同的人在不同的場(chǎng)景中完成。4個(gè)場(chǎng)景包括室外、室外尺度變化、室外穿著變化和室內(nèi)。該數(shù)據(jù)庫(kù)一共包含599段視頻序列，每段視頻以25 f/s（幀/秒）的速度持續(xù)10～15 s。

對(duì)KTH視頻數(shù)據(jù)提取STIP[7]（Space-Time Interest Point）和SIFT[8]（Scale-Invariant Feature Transform）特征，應(yīng)用PCA降維方法將STIP特征從162維降為32維，SIFT特征從128維降為32維，高斯混合模型中的高斯成分?jǐn)?shù)量設(shè)為256[3]。

算法實(shí)驗(yàn)環(huán)境為美國(guó)邁阿密大學(xué)的超算平臺(tái)（IBM Platform LSF），GMM程序采用Bouman C A教授公開的3.6.6版本[9]，文中將該程序中的GMM參數(shù)初始化修改為通過Kmeans聚類獲取。

2.2 實(shí)驗(yàn)設(shè)計(jì)流程

從單個(gè)視頻提取的特征（STIP或SIFT）往往不足以精確地估算GMM的參數(shù)[10]，因此從所有的訓(xùn)練視頻樣本中提取特征，估算GMM參數(shù)，從而得出一個(gè)UBM。為了更好地描述特定視頻特征數(shù)據(jù)的分布狀態(tài)，用最大后驗(yàn)概率（MAP）[11]方法來調(diào)整UBM參數(shù)（通常只調(diào)整均值向量μ）。以UBM中的第k個(gè)高斯成分為例，針對(duì)特定視頻的特征數(shù)據(jù)，首先計(jì)算γ(t,k)，然后計(jì)算如下參數(shù)

式中：xt代表某個(gè)視頻的第t行特征值；r是一個(gè)調(diào)節(jié)參數(shù)，通常設(shè)置值在8～20之間[12]；Ek(x)代表所有樣本數(shù)據(jù)針對(duì)第k類高斯分布的加權(quán)平均；為調(diào)整后的第k類高斯分布的均值向量。

將調(diào)整后的所有高斯成分的均值歸一化后，連接起來就形成了GMM超向量，歸一化公式為

算法驗(yàn)證的第一部分比較改進(jìn)前后的EM算法估算GMM-UBM參數(shù)的運(yùn)算速度。第二部分將在GMM-UBM的基礎(chǔ)上構(gòu)建GMM超向量，結(jié)合SVM進(jìn)行多值分類，對(duì)KTH進(jìn)行留一交叉驗(yàn)證法（LOOCV）驗(yàn)證。實(shí)驗(yàn)設(shè)計(jì)的流程圖如圖1所示。

3 算法驗(yàn)證

3.1 GMM參數(shù)估算速度的比較

圖1 實(shí)驗(yàn)設(shè)計(jì)流程圖

選擇STIP特征數(shù)據(jù)對(duì)KTH進(jìn)行留一交叉驗(yàn)證，每次用24人的視頻數(shù)據(jù)訓(xùn)練GMM-UBM，共需25輪，經(jīng)過降維、采樣等處理后，每輪STIP特征數(shù)據(jù)平均133 Mbyte左右。為了兼顧運(yùn)行速度和參數(shù)估算準(zhǔn)確程度，CTH取值選擇了5個(gè)參數(shù)值（0，0.001，0.01，0.1，0.5）進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖2所示。參數(shù)CTH值為0代表原EM算法。從實(shí)驗(yàn)的幾組閾值可以看出當(dāng)CTH設(shè)為0.001時(shí)相比原EM算法運(yùn)行速度提高了很多（92.3%），而當(dāng)CTH增加時(shí)運(yùn)行速度的提高變得相對(duì)緩慢。通過查看EM算法迭代過程輸出的中間值γ(i,k)可以發(fā)現(xiàn)幾乎每行樣本對(duì)應(yīng)的256個(gè)概率值大部分γ(i,k)都小于0.001/256，只有少數(shù)幾個(gè)比較大。隨著閾值的增大，運(yùn)行速度的提高并不明顯，這說明CTH取0.001時(shí)已經(jīng)舍棄了絕大多數(shù)樣本數(shù)據(jù)，只有少數(shù)樣本數(shù)據(jù)對(duì)應(yīng)的γ(i,k)需要更大的閾值進(jìn)行舍棄。

圖2 不同閾值參數(shù)運(yùn)行時(shí)間比較

綜上分析可以得出用GMM擬合樣本數(shù)據(jù)分布時(shí)，大部分樣本數(shù)據(jù)具有明顯的傾向性，即屬于某個(gè)或某幾個(gè)高斯成分的概率大，屬于其他高斯成分的概率則很低，舍棄影響特別低的樣本數(shù)據(jù)有助于加快EM算法的運(yùn)行速度。這進(jìn)一步驗(yàn)證了本文提出改進(jìn)EM算法的指導(dǎo)思想。

3.2 在KTH上的應(yīng)用比較

在STIP特征數(shù)據(jù)訓(xùn)練出GMM-UBM的基礎(chǔ)上構(gòu)建GMM超向量，結(jié)合LIBSVM[13]進(jìn)行多值分類，SVM采用徑向基核函數(shù)（RBF）。采用不同閾值得出的識(shí)別準(zhǔn)確率如表1所示。

表1 不同閾值應(yīng)用比較

由表1可以看出不同的閾值在實(shí)際應(yīng)用中對(duì)識(shí)別準(zhǔn)確率的影響不大，這說明改進(jìn)后的EM算法幾乎沒有影響原EM算法求解GMM參數(shù)的準(zhǔn)確度。

本文采用改進(jìn)后的EM算法，將CTH設(shè)為0.001，分別基于STIP特征和SIFT特征進(jìn)行行為識(shí)別，基于STIP特征的識(shí)別準(zhǔn)確率為88.98%，基于SIFT特征的識(shí)別準(zhǔn)確率為82.48%，合并兩種特征得出的相似度（SVM score）后得出的識(shí)別準(zhǔn)確率為91.33%，其對(duì)應(yīng)的混淆矩陣如圖3所示。

圖3 KTH數(shù)據(jù)庫(kù)混淆矩陣，平均準(zhǔn)確率91.33%

4 結(jié)語

通過分析EM算法運(yùn)行時(shí)間過長(zhǎng)的原因，本文提出了一種改進(jìn)的EM算法，改進(jìn)后的EM算法通過設(shè)置一個(gè)閾值來挑選部分特征數(shù)據(jù)重新估計(jì)每類分布的參數(shù)值，實(shí)驗(yàn)證明當(dāng)數(shù)據(jù)規(guī)模較大、高斯成分?jǐn)?shù)很高時(shí)，通過設(shè)置適當(dāng)?shù)膮?shù)，改進(jìn)后的EM算法相比原有的EM算法在估算GMM參數(shù)時(shí)能夠顯著地提高運(yùn)行速度，而在KTH人體行為庫(kù)的實(shí)際應(yīng)用中，行為識(shí)別準(zhǔn)確率只受到了很小的影響。

本文是通過降維和采樣的方法來縮小數(shù)據(jù)規(guī)模進(jìn)行實(shí)驗(yàn)，改進(jìn)的EM算法還可以嘗試結(jié)合Hadoop應(yīng)用到大數(shù)據(jù)處理上，來加快大數(shù)據(jù)求解GMM參數(shù)的時(shí)間。

：

[1]CAMPBELL W M，STURIM D E，REYNOLDS D A.Support vector machines using GMM supervectors for speaker verification[J].IEEE Signal Processing Letters，2006，13（5）：308-311.

[2]INOUE N，SHINODA K.A fast MAP adaptation technique for GMM-supervector-based video semantic indexing systems[C]//Proc.19th ACM International Conference on Multimedia.[S.l.]：ACM Press，2011：1357-1360.

[3]LIU D，SHYU M L，ZHAO G.Spatial-temporal motion information integration for action detection and recognition in non-static background[C]//Proc.2013 IEEE 14th International Conference on Information Reuse and Integration(IRI).[S.l.]：IEEE Press，2013：626-633.

[4]陳曉，張尤賽，鄒維辰.一種基于GMM的圖像語義標(biāo)注方法[J].電視技術(shù)，2013，36（23）：35-38.

[5]鐘金琴，辜麗川，檀結(jié)慶，等.基于分裂EM算法的GMM參數(shù)估計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（34）：28-32.

[6]SCHULDT C，LAPTEV I，CAPUTO B.Recognizing human actions:a local SVM approach[C]//Proc.7th International Conference on Pattern Recognition.[S.l.]：IEEE Press，2004：32-36.

[7]LAPTEV I.On space-time interest points[J].International Journal of Computer Vision，2005，64（2/3）：107-123.

[8]LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[9]BOUMAN C A，SHAPIRO M，COOK G W，et al.Cluster:an unsupervised algorithm for modeling Gaussian mixtures[EB/OL].[2014-01-10].http://dynamo.ecn.purdue.edu/～bouman/software/cluster.

[10]INOUE N，SAITO T，SHINODA K，et al.High-level feature extraction using sift GMMs and audio models[C]//Proc.2010 20th International Conference on Pattern Recognition(ICPR).[S.l.]：IEEE Press，2010：3220-3223.

[11]REYNOLDS D.Gaussian mixture models[J].Encyclopedia of Biometrics，2009（10）：659-663.

[12]CHARBUILLET C，TARDIEU D，PEETERS G.GMM-supervector for content based music similarity[C]//Proc.International Conference on Digital Audio Effects.Paris，F(xiàn)rance：IEEE Press，2011：425-428.

[13]CHANG C C，LIN C J.LIBSVM:a library for support vector machines[J].ACM Trans.Intelligent Systems and Technology(TIST)，2011，2（3）：27.