混合高斯參數(shù)估計(jì)的兩種EM算法比較

劉旺鎖，王平波，顧雪峰

?

混合高斯參數(shù)估計(jì)的兩種EM算法比較

劉旺鎖1,2，王平波1，顧雪峰1

(1. 海軍工程大學(xué)，湖北武漢 430033; 2. 廣州大學(xué)，廣東廣州 510006)

混合高斯模型是一種典型的非高斯概率密度模型，獲得廣泛應(yīng)用。其參數(shù)的優(yōu)效估計(jì)可以通過最大似然方法獲得，但最大似然估計(jì)往往因其非線性而難以實(shí)現(xiàn)，故期望最大化(Expectation-Maximization, EM)迭代算法成為一種常用的替代方法。常規(guī)EM算法性能受迭代初值設(shè)置影響大，且不能對(duì)模型階數(shù)做出估計(jì)。一種名為貪婪EM的改進(jìn)算法可以克服這兩個(gè)缺點(diǎn)，獲得更為準(zhǔn)確的模型參數(shù)估計(jì)，但其運(yùn)算量一般會(huì)遠(yuǎn)大于前者。本文對(duì)這兩種EM算法進(jìn)行綜合研究，深入挖掘兩者之間的關(guān)系，并基于相同的數(shù)值仿真實(shí)例，直觀地演示比較兩者的性能差異。

混合高斯；最大似然估計(jì)；期望最大化；貪婪期望最大化

0 引言

混合高斯(Gaussian Mixture, GM)模型是一種比較優(yōu)秀的非高斯概率密度(Probability Density Function, PDF)模型，它具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、物理意義明顯直觀、擬合性能好等一系列優(yōu)點(diǎn)，為雷達(dá)、聲吶、通信、語(yǔ)音、圖像等信號(hào)處理領(lǐng)域所廣泛采用。使用GM模型對(duì)數(shù)據(jù)進(jìn)行非高斯PDF建模的關(guān)鍵是如何快速、準(zhǔn)確地得到GM模型參數(shù)估計(jì)。眾所周知，對(duì)于非隨機(jī)未知確定量，若其優(yōu)效估計(jì)存在，則必然是最大似然估計(jì)(Maximum Likelihood Estimation, MLE)[1]。所以，首選是尋求GM參數(shù)的MLE。

但是，對(duì)于多參量同時(shí)估計(jì)問題，MLE一般難以嚴(yán)格實(shí)現(xiàn)。此時(shí)，往往代之以一種名為期望最大化(Expectation-Maximization, EM)的迭代算法[2]。文獻(xiàn)[3]中提出了GM參數(shù)估計(jì)的EM迭代算法。這種EM算法存在參數(shù)初始化問題，如果初始化不恰當(dāng)，迭代可能會(huì)錯(cuò)誤地收斂于局部極值，不能得到正確的參數(shù)估計(jì)。不幸的是，對(duì)于GM參數(shù)估計(jì)，理想的EM迭代初始化方案尚未建立，這是EM算法應(yīng)用的主要局限性所在。EM算法的第二個(gè)局限性是，它不能對(duì)GM模型階數(shù)做出估計(jì)，只能在固定的GM階數(shù)下進(jìn)行。這就是說，使用EM算法，必須對(duì)GM模型階數(shù)做出預(yù)先假定，而對(duì)于某些極端非高斯數(shù)據(jù)，實(shí)際中很難事先確定其GM階數(shù)。

為了克服EM算法的這兩個(gè)缺陷，文獻(xiàn)[4]提出了一種名為貪婪EM(Greedy EM, GEM)迭代的改進(jìn)算法(為以示區(qū)別，下文把傳統(tǒng)EM算法簡(jiǎn)記為CEM)。理論上，GEM算法不依賴于初始值，且可自適應(yīng)估計(jì)GM階數(shù)。

文獻(xiàn)[5]、[6]分別把CEM算法和GEM算法引入到了水聲信號(hào)處理中。而且，文獻(xiàn)[5]中提出了一種多初值初始化方案，可以部分地避免錯(cuò)誤收斂問題。受當(dāng)時(shí)數(shù)值仿真方法的限制，文獻(xiàn)[6]直接使用一段海試數(shù)據(jù)簡(jiǎn)單演示了GEM算法的性能。本文將對(duì)CEM算法和GEM算法進(jìn)行綜合研究，深入發(fā)掘兩者之間的關(guān)系，并基于相同的數(shù)值仿真實(shí)例，直觀而詳細(xì)地比較兩者的性能差異。

1 混合高斯模型

一般地，GM模型的PDF可表述為如式(1)所示的加分布形式：

可以用圖1所示的“完全數(shù)據(jù)”的概念來(lái)解釋混合高斯數(shù)據(jù)的形成過程：

圖1 完全數(shù)據(jù)形成圖解

2 CEM算法

基于對(duì)圖1所示完全數(shù)據(jù)概念的理解，Aaron[3]導(dǎo)出了GM參數(shù)MLE的CEM算法，省略中間步驟，主要迭代公式如(5)所示。

CEM迭代算法流程如圖2所示。

可以看到，在假定模型階數(shù)和初始化模型參數(shù)后，即可使用式(5)更新參數(shù)估計(jì)，直到滿足令式(4)所示似然函數(shù)積分值取得最大。這就是CEM迭代算法的基本思想[3]。

在文獻(xiàn)[5]中提出的多初值CEM方案如圖3所示。依據(jù)圖示方案實(shí)施估計(jì)，可以大大降低迭代收斂于局部極值點(diǎn)的錯(cuò)誤概率。

3 GEM算法

GEM算法的理論依據(jù)是，一個(gè)混合分布的似然函數(shù)最大化過程可以通過一種所謂“貪婪”吸附的方式完成，即依據(jù)一定的規(guī)則，相繼向混合分布中增加新的高斯成員，直至最終完成數(shù)據(jù)的PDF擬合任務(wù)。

圖2 CEM估計(jì)算法流程圖

圖3 多初值的CEM算法

不難發(fā)現(xiàn)，不同于CEM算法在起始時(shí)即對(duì)GM所有可能源成份做出初始配置，GEM算法是從一階最佳GM擬合(即一個(gè)最佳高斯源)開始的，其初始化是根據(jù)數(shù)據(jù)通過計(jì)算完成的。接下來(lái)，即重復(fù)如下兩步，直到滿足循環(huán)停止條件(比如達(dá)到了預(yù)定模型階數(shù))：

(1) 插入一個(gè)新的源成份；

(2) 應(yīng)用EM迭代直到收斂。

有了初始化高斯參數(shù)和權(quán)系數(shù)，用式(8)對(duì)參量進(jìn)行更新(此即partial EM迭代算法，簡(jiǎn)記為pEM)，選擇使對(duì)數(shù)似然函數(shù)最大的一組參數(shù)作為新加入高斯分量的參數(shù)。

對(duì)給定的樣本序列，上述思路的GM模型參數(shù)GEM估計(jì)算法流程如圖4所示。

4 仿真實(shí)例

圖4 GEM算法流程圖

圖5 數(shù)值仿真實(shí)例的波形和PDF

圖6給出了根據(jù)這兩種方法得到的參數(shù)估計(jì)繪制出的PDF曲線(分別標(biāo)記為CEM、GEM)對(duì)比。為了便于比較，圖中同時(shí)給出了理論P(yáng)DF曲線和根據(jù)柱狀圖統(tǒng)計(jì)(這是一種常用的、適合于大樣本量的分布統(tǒng)計(jì)分析方法：平分樣本值域?yàn)槿舾蛇B續(xù)區(qū)間，統(tǒng)計(jì)取值落于這些區(qū)間內(nèi)的點(diǎn)數(shù)，以此可得到樣本值的大致分布)得到的PDF曲線。于是，每幅圖中共有4條PDF曲線。圖6(a)中顯示PDF原值，為了方便觀察各條曲線的區(qū)別，圖6(b)中給出了它們經(jīng)過最大值歸一化后的對(duì)比情形。

圖6 PDF曲線比較

由圖6可見，GEM算法得到的PDF曲線與理論P(yáng)DF曲線重合程度遠(yuǎn)高于CEM算法，這說明前者PDF擬合性能明顯優(yōu)于后者。在本例這種樣本量較為充足的條件下，GEM擬合與柱狀圖統(tǒng)計(jì)PDF擬合性能相當(dāng)。

5 結(jié)語(yǔ)

GM模型是對(duì)數(shù)據(jù)進(jìn)行非高斯PDF建模的有效模型之一。CEM算法是GM模型參數(shù)估計(jì)的常用方法，但CEM不能估計(jì)模型階數(shù)，估計(jì)精度受初始值設(shè)置影響嚴(yán)重。而GEM算法則可以克服這些缺點(diǎn)，但運(yùn)算量較大。

本文系統(tǒng)地梳理了CEM和GEM算法的關(guān)系及各自優(yōu)缺點(diǎn)，并基于同一仿真實(shí)例對(duì)其性能進(jìn)行了直觀比較演示。比較結(jié)果表明：GEM算法可以取得優(yōu)于CEM算法的PDF擬合性能，且能自動(dòng)估計(jì)GM模型階數(shù)。

由于通過不斷新增高斯分量的方式逼近最大似然估計(jì)，所以GEM算法不受初值設(shè)置影響(即使最初的初值設(shè)置不合理，它也可以通過后續(xù)新增高斯分量的方式予以彌補(bǔ))，可以取得較為穩(wěn)定的估計(jì)性能。但是每一次新增高斯分量，都會(huì)相應(yīng)增加運(yùn)算量，所以GEM算法運(yùn)算量往往遠(yuǎn)大于CEM算法。下一步將重點(diǎn)研究如何把GM階數(shù)限定在一個(gè)較小范圍內(nèi)應(yīng)用GEM算法對(duì)水聲混響數(shù)據(jù)進(jìn)行高效的PDF建模，并對(duì)CEM和GEM算法估計(jì)精度和速度等性能做出統(tǒng)計(jì)性比較，以最終判定究竟哪種方法更適用于水聲混響數(shù)據(jù)的統(tǒng)計(jì)建模。

[1] Steven M Kay. Fundamentals of statistical signal processing: Estimation theory[M]. New Jersey, USA: Prentice Hall, 1998: 326.

[2] Redner R A, Walker H F. Mixture densities, maximum likelihood, and the EM algorithm[J]. SIAM Review, 1984, 26(2): 195-202.

[3] Aaron A D. Using EM to estimate a probability density with a mixture of Gaussians[DB/OL]. http://citeseer.ist.psu.edu, 2000.

[4] Verbeek J J, Vlassis N, Krose B. Efficient Greedy Learning of Gaussian Mixture Models[R]. Netherlands: Reports of Computer Science Institute of Amsterdam Univ, 2001: 153.

[5] 王平波, 蔡志明, 劉旺鎖. 混合高斯概率密度模型參數(shù)的EM估計(jì) [J]. 聲學(xué)技術(shù), 2007, 26(3): 498-502.

WANG Pingbo, CAI Zhiming, LIU Wangsuo. EM Estimation of PDF Parameters for Gaussian Mixture Processes[J]. Technical Acoustics, 2007, 26(3): 498-502.

[6] 衛(wèi)紅凱, 王平波, 蔡志明. 混響數(shù)據(jù)的混合高斯建模研究[J]. 聲學(xué)技術(shù), 2007, 26(3): 514-518.

WEI Hongkai, WANG Pingbo, CAI Zhiming. Study of reverberation for gaussian mixture model[J]. Technical Acoustics, 2007, 26(3): 514-518.

[7] 劉旺鎖, 王平波, 顧雪峰, 等. 一種非白非高斯數(shù)據(jù)的數(shù)值仿真方法[J]. 聲學(xué)技術(shù), 2013, 32(3): 228-232.

LIU Wangsuo, WANG Pingbo, GU Xuefeng, et al. A simulation approach to colored non-Gaussian processes[J]. Technical Acoustics, 2013, 32(3): 228-232.

Comparison of two EM algorithms for Gaussian mixture parameter estimation

LIU Wang-suo1,2, WANG Ping-bo1, GU Xue-feng1

(1. Naval University of Engineering, Wuhan430033,Hubei,China;2. University of Guangzhou,Guangzhou510006,Guangdong, China)

Gaussian mixture is a typical and widely-used non-Gaussian probability density distribution model. The expectation-maximization algorithm is a usual iterative realization for the maximum likelihood estimation of its parameters. However, its performance depends highly on the initial values. And it can not estimate the order of Gaussian mixture. The greedy expectation-maximization algorithm can solve these problems by incrementally adding Gaussian components to the mixture. But its operation quantity is often much larger than the former. The relationship between these two algorithms is discussed, and their concrete realization methodsare given comparatively. With the same numerical instance, their performance differencesare illustratedand studied.

Gaussian mixture; Maximum Likelihood Estimation(MLE); Expectation-Maximization(EM); Greedy Expectation-Maximization(GEM)

TN911.7

A

1000-3630(2014)-06-0539-05

10.3969/j.issn1000-3630.2014.06.012

2014-04-29;

2014-08-07

國(guó)家自然科學(xué)基金資助項(xiàng)目(51109218)。

劉旺鎖(1965－), 男, 江蘇金壇人, 碩士生導(dǎo)師, 研究方向?yàn)槁暭{裝備保障與效能評(píng)估、水聲信號(hào)處理。

王平波, E-mail: blackberet@126.com