EM算法研究与应用

研究在一个含有隐含变量中的一种算法

计算机技术与发展第19卷　第9期　　　　　　　　　19　No.9　　　　　　　　Vol.2009年9月Sep.　2009COMPUTERTECHNOLOGYANDDEVELOPMENT

EM算法研究与应用

王爱平,张功营,刘　方

(安徽大学计算智能与信号处理教育部重点实验室,安徽合肥230039)

摘　要:引入了可处理缺失数据的EM算法。EM算法是一种迭代算法,每一次迭代都能保证似然函数值增加,并且收敛到一个局部极大值。对EM算法的基本原理和实施步骤进行了分析。算法的命名,是因为算法的每一迭代包括两步:第一步求期望(ExpectationStep),称为E步;第二步求极大值(MaximizationStep),称为M步。EM算法主要用来计算基于不完全数据的极大似然估计。在此基础上,把EM算法融合到状态空间模型的参数估计问题。给出了基于Kalman平滑和算法的线性状态空间模型参数估计方法。关键词:EM算法;状态空间模型;Kalman

中图分类号:TP301.6　　　　　　文献标识码:A　　　　　　　文章编号:1673-629X(2009)09-0108-03

ResearchandApplicationofEMAlgorithm

WANGAi2ping,ZHANGGong2ying,IUFang

(MinistryofEducationKeyLab.ofIntelligent&,

AnhuiUniversity,Hefei,Abstract:Followingthedescriptionoftraditionalandthediscussionsontheirdisadvantages.EMalgorithmisaniterativealgorithm,toensurefunctioncanbeincreased,andtheconvergencetoalocalmaxima.PresentsanEMthattodealwithmissingdataproblems,wherethedetailsoftheEMalgorithmanditsre2alizationnamedbecauseeachiterativealgorithmincludestwosteps:thefirststepinseekingex2pectations(Step)astheEstep;thesecondstepformaxima(MaximizationStep),knownasstep-by-stepM.EMalgorithmtotheprincipalbasedonincompletedata,maximumlikelihoodestimation.ThisisthenfollowedbyapplyingtheproposedEMalgorithmtotheparameterestimationofstatespacemodels.ThepaperalsopresentstheKalmansmoothingbasedpa2rameterestimationmethodsforlinearstatespacemodels.Keywords:EMalgorithm;state-spacemodel;Kalman

1　EM算法及其应用

EM算法是一种迭代算法,每一次迭代都能保证

间模型的参数估计问题:

xt=Ftxt-1+ωt

yt=Htxt+υt

(1)(2)

似然函数值增加,并且收敛到一个局部极大值[1,2]。算法的命名,是因为算法的每一迭代包括两个步:第一步求期望(ExpectationStep),称为E步;第二步求极大值(MaximizationStep),称为M步。EM算法主要用来计算基于不完全数据的极大似然估计[3～5]。

其中,初始状态x0,随机误差项ωt和υt为独立高斯分布,三者之间是相互独立:x0～N(x0|0,P0|0),ωt～ωiidN(0,Q),υt～iidN(0,R),E[υt′t]=0,E[υtx′0]

=0,E[ωtx′0]=0。

假设模型噪声[11,12]、状态的初始条件都服从高斯

2　EM算法的状态空间模型参数估计

下面推导基于Kalman平滑和算法的状态空间模型参数估计方法[6～10]。给出一般形式的线性状态空

分布,即:

)=(2π)p(x0|θx0|0)′P0|0(x0-x0|0)}

)=(2π)p(yt|xt,θHtxt)′R

-1

--1

-

2

|P0|0|

-

2exp{

-

(x0-2

(3)

收稿日期:2008-12-26;修回日期:2009-03-24基金项目:国家自然科学基金项目(60472065)

作者简介:王爱平(1956-),女,安徽合肥人,教授,主要从事计算机教学与研究。

2

|R|

-

2exp{

-

(yt-2

(4)

(yt-Htxt)}

-

)=(2π)p(xt|xt-1,θ

2

|Q|

-

2exp{

-

(xt-2

研究在一个含有隐含变量中的一种算法

第9期　　　　　　　　　　　　　　　　王爱平等:EM算法研究与应用Ftxt-1)′Q

-1

109

(9)(10)

(xt-Ftxt-1)}(5)Htxt|T)′+HtPt|TH′t])

Q=

则完全数据的似然也服从高斯分布,完全数据的似然可以表示为:

T

T

(A-CB-1C′)

)=p(x0|θ)p(x0∶T,y1∶T|θ

T

t=1

∏p(x

t

|xt-1,

(6)

4　算法实施步骤

现在把应用EM算法进行状态空间模型[13]参数估计的实施步骤归纳如下:

1)对参数θ={R,Q,F,H,x0|0,P0|0}进行初始

θ)

t=1

∏p(y

t

)|xt,θ

因此,完全数据的对数似然等于:

)=lnp(x0∶T,y1∶T|θ

-1(x0-x0|0)′-ln|P0|0|-P0|0(x0-x0|0)

22-ln|Q|-22

--Tt=1T

化;

k-1

2)E步:根据θ,执行卡尔曼滤波及平滑,计算

∑(x

t

-Ftxt-1)′Q-Htxt)′R

-1

-1

(xt-Ftxt-1)

期望值:xt|T,Pt|T,Pt,t-1|T;

3)M步:计算参数θ={R,Q,F,H,x0|0,P0|0}新

2

ln|R|-2

2

t=1

∑(y

t

(yt-Htxt)

(7)

的值;

4)重复参数θ直至收敛[14]。

)ln(2π

其中,N是样本量,m是状态变量的维度,n是观测变量的维度。

5　实验仿真

,取

=Ft-+wtyttxt+vt

3　求解对数似然的期望的极大化

根据EM算法基本原理,获得以下式子:

E[lnp(x0∶T,y1∶T

-)]=-|θ|0)ln(2x0、噪声干扰wt和vt均被假设为高,即:

x0～N(x0|0,P0|0),wt～iidN(0,Qw),vt～iidN(0,Rv)

22

-1-tr(P0])|000|0)(0-x0|0)′2

-

ln|Q|-

ln|2

T

其中参数实际取值为:F=0.9,H=0.2,Qw=0.7,

Rv=0.2,状态初始设置为x0～N(0,10)。

(8)

t=1T

tr(Q∑

-1

E[(xt-Ftxt-1)(xt-Ftxt-1)′])

-2

t=1

∑

tr(R-1E[(yt-Htxt)(yt-Htxt)′])

依据Kalman滤波和平滑公式,然后联合EM算法

对模型参数θ={F,H,Rv,Qw}进行估计。EM算法迭代次数设置为400(当然迭代次数设置越大,能得到更好的估计结果)。

程序运行结果θ={0.9835,0.2049,0.2107,0.

683},仿真结果如图1～3所示。

记:

T

A=B=C=

t=1T

∑(x

T

t|Txt|T′+Pt|T)′

+Pt-1|T)

t=1

∑(x∑(x

t-1|Txt-1|T

t|Txt-1|T′+Pt,t-1|T)

t=1

这样,完全数据的对数似然期望可以表示为:

)]=-E[lnp(x0∶T,y1∶T|θln|P0|0|-2

2

2

ln|Q|-

2

ln|R|-T

x0|0)(x0|

)-ln(2π

-1tr(P0|0E[(x0|2

Tt=1

--1

T

-

x0|0)′+P0|T])-2

FtBF′t])-

tr(Q∑

-1

[A-2FtC′+Htxt|T)(yt-k-1

)收敛性图1　似然函数的期望的Q(θ,θ

2

T

t=1

tr(R∑

[(yt-

研究在一个含有隐含变量中的一种算法

　　　　　　　　　　　　　　　　　　　　　计算机技术与发展　　　　　　　　　　　　　　　　　　第19卷 110

　　用[D].广州:暨南大学,2007.

[2]　张　杰,阳宪惠.多变量统计过程控制[M].北

京:化工工业出版社,2000.

[3]　陈志国,刘文举.基于EM算法的极大似然参数

估计探讨[J].河南大学学报:自然科学版,2002,32(4):35-41.

[4]　孙大飞,DempsterAP,LairdNM,etal.Maxi2

mumlikelihoodfromIncompletedataviatheEMal2gorithm[J].JournaloftheRoyalStatisticalSociety,SeriesB,1997,39(1):1-38.

[5]　MengXL,RubinDB.RecentExtensiontothe

EMalgorithm[M].BayesianStatistics4.Oxford:OxfordUniversityPress,1992:307-320.

[6]　胡寿松,王执铨,胡维礼.最优控制理论与系统

[M].北京:科学出版社,2005.

[7]　郭　雷,程代展,冯德兴.控制理论导论[M].北

京:科学出版社,2005:1-107.

[8]　AndrieuC,DoucetA.Online-Maximiza2

tionTypeAlgorithmsEstimationin[C]inProc.IEEEConf.SignalProcessing.[s.l.]:[]:69-72.

9,朱征桃.最优估计及其应用[M].北京:

科学出版社,1994.

[10]ParzenE.Ontheestimationofaprobabilitydensity

functionandmode[J].AnnalsofMathematicalStatistics,1962,33:1065-1076.

[11]WangAP,WangH.Minimisingentropyandmeantracking

controlforaffinenonlinearandnon-Gaussiandynamicstochasticsystem[J].IEEProceedingsControlTheory&Ap2plication,2005,151(4):405-520.

[12]WangAP,WangH,TanJ.OptimalFilteringforMultivari2

ableStochasticSystemviaResidualProbabilityDensityFunc2tionShaping[C]∥ProceedingsofSICE2005AnnualConfer2ence.[s.l.]:[s.n.],2005:215-219.

[13]任　光,张均东.时间序列状态空间模型建模及应用[M].

,EM算法用于状态空间模型参数估计,其估计结果还是不错的,可以为时变不同的参数模型估计提供很好的帮助。

6　结束语

针对传统的极大似然参数估计方法在解决实际问题时所存在的不足,引入了EM算法。讨论了算法原理和实施步骤,并把EM算法推广到状态空间模型的参数估计问题,然后推导了基于Kalman平滑和EM算法的状态空间模型参数估计的过程,最后给出实验仿真。

参考文献:

[1]　陈学华.状态空间模型理论与算法及其在金融计量中的应

大连:大连海事大学出版社,2000:102-112.

[14]GuoL,WangH.Mininumentropyfilteringformultivariate

stochasticsystemswithnon-Gaussiannoises[J].IEEETransactionsonAutomaticControl,2006,51(4):670-695.[15]梁应敞,张贤达,李衍达,等.非高斯相关噪声中高斯信号

的时延估计[J].电子科学学刊,1997,19(5):607-612.

中国计算机学会会刊、中国科技核心期刊

《计算机技术与发展》欢迎订阅,邮发代号:52-127