混合高斯參數估計的兩種EM算法比較

劉旺鎖，王平波，顧雪峰

?

混合高斯參數估計的兩種EM算法比較

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

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

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

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

0 引言

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

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

為了克服EM算法的這兩個缺陷，文獻[4]提出了一種名為貪婪EM(Greedy EM, GEM)迭代的改進算法(為以示區別，下文把傳統EM算法簡記為CEM)。理論上，GEM算法不依賴于初始值，且可自適應估計GM階數。

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

1 混合高斯模型

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

可以用圖1所示的“完全數據”的概念來解釋混合高斯數據的形成過程：

圖1 完全數據形成圖解

2 CEM算法

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

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

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

在文獻[5]中提出的多初值CEM方案如圖3所示。依據圖示方案實施估計，可以大大降低迭代收斂于局部極值點的錯誤概率。

3 GEM算法

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

圖2 CEM估計算法流程圖

圖3 多初值的CEM算法

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

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

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

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

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

4 仿真實例

圖4 GEM算法流程圖

圖5 數值仿真實例的波形和PDF

圖6給出了根據這兩種方法得到的參數估計繪制出的PDF曲線(分別標記為CEM、GEM)對比。為了便于比較，圖中同時給出了理論PDF曲線和根據柱狀圖統計(這是一種常用的、適合于大樣本量的分布統計分析方法：平分樣本值域為若干連續區間，統計取值落于這些區間內的點數，以此可得到樣本值的大致分布)得到的PDF曲線。于是，每幅圖中共有4條PDF曲線。圖6(a)中顯示PDF原值，為了方便觀察各條曲線的區別，圖6(b)中給出了它們經過最大值歸一化后的對比情形。

圖6 PDF曲線比較

由圖6可見，GEM算法得到的PDF曲線與理論PDF曲線重合程度遠高于CEM算法，這說明前者PDF擬合性能明顯優于后者。在本例這種樣本量較為充足的條件下，GEM擬合與柱狀圖統計PDF擬合性能相當。

5 結語

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

本文系統地梳理了CEM和GEM算法的關系及各自優缺點，并基于同一仿真實例對其性能進行了直觀比較演示。比較結果表明：GEM算法可以取得優于CEM算法的PDF擬合性能，且能自動估計GM模型階數。

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

[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] 王平波, 蔡志明, 劉旺鎖. 混合高斯概率密度模型參數的EM估計 [J]. 聲學技術, 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] 衛紅凱, 王平波, 蔡志明. 混響數據的混合高斯建模研究[J]. 聲學技術, 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] 劉旺鎖, 王平波, 顧雪峰, 等. 一種非白非高斯數據的數值仿真方法[J]. 聲學技術, 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

國家自然科學基金資助項目(51109218)。

劉旺鎖(1965－), 男, 江蘇金壇人, 碩士生導師, 研究方向為聲納裝備保障與效能評估、水聲信號處理。

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