EM算法的改进及其在行为识别中的应用

赵桂儒，李卫东，刘典婷，吴 敏，崔满丰

（1.中国地震台网中心，北京 100045；2.迈阿密大学，美国 佛罗里达州 33146）

高斯混合模型（Gaussian Mixture Model，GMM）作为一种通用的概率模型，能有效地模拟多维矢量的任意连续概率分布，在此基础上发展起来的高斯混合模型通用背景模型（GMM-UBM）在语音识别[1]、图像识别和检索[2-4]等领域都取得了良好的效果。

GMM-UBM需要大量的训练样本数据通过GMM模拟所有样本数据的空间分布状态作为通用背景模型，因此GMM参数的估算显得尤为重要。期望最大化（Expectation Maximization，EM）算法是传统的估计GMM参数的方法，样本数据规模增大时，EM算法存在迭代次数多、运行时间过长等问题，这影响了GMM参数估算的速度。在不影响参数估算准确程度的基础上加快EM算法的运行速度将具有非常重要的现实意义。

本文针对EM算法运行时间过长的问题，提出了一种改进的EM算法，文章结合KTH人体行为数据库，对改进的EM算法从运行速度和行为识别准确率两方面进行了验证，结果显示改进后的EM算法能够显著提高GMM参数求解的速度，而对行为识别准确率的影响非常小。

1 GMM-UBM及其参数求解

1.1 GMM-UBM

GMM-UBM用来描述所有样本数据的分布状态，其概率密度函数描述为

式中：x是D维特征向量；K代表高斯成分的数量；θ={ωk,μk,Σk}Kk=1是一组参数，包括每个高斯成分的权值ωk、均值向量μk和协方差矩阵Σk。

1.2 GMM参数求解

GMM的参数估计一般采用EM算法[5]，GMM的对数似然函数（log-likelihood function）为

式中：T为样本总数，适合当前样本集的GMM参数将会使式（2）最大化。EM算法可分为E步和M步：

1）E步

根据当前GMM的参数计算每行样本数据属于第k类分布的后验概率为

式中：γ(i,k)代表第i行样本数据属于第k类分布的后验概率。

2）M步

利用E步得出的概率值，重新估计每类分布的参数值

式中：N为重复1）和2）两步直到式（2）收敛于一个充分小的值为止。

1.3 EM算法存在的问题及改进

在实际应用中，当样本数据规模较大、GMM的高斯成分数K比较高时，EM算法往往需要运行很长时间并经过多次迭代才能收敛，这成为EM算法估算GMM参数的一个瓶颈。通过1.2节中对E步和M步的分析可以发现，M步中重新估计每类高斯分布的参数值(ωk,μk,Σk)时，需要利用每行样本数据xi及其属于第k类高斯分布的后验概率值γ(i,k)来进行计算。后验概率值γ(i,k)越大意味着xi对高斯分布参数估计的影响越大，反之亦然。舍弃那些后低验概率值对应的数据，加快M步的运算速度，从而节省估算GMM参数的时间是本文改进EM算法的指导思想。

一行样本数据xi属于所有高斯分布的后验概率γ(i,k)的总和为1，因此理论上γ(i,k)的取值只有两种情况：大于等于平均概率值1/K或者小于该值，如果γ(i,k)远小于（例如0.1%倍）平均概率值则意味着xi对估计第k类高斯分布参数值的影响更小，同时也意味着必有其他样本数据xi在估计第k类高斯分布参数值时起到的作用更大。

鉴于此，本文提出了一种加快EM算法迭代速度的方法，基本思想为：在EM算法的M步中，只挑选部分特征数据来重新估计每类分布的参数值。挑选的原则为设置一个阈值CTH/K，当在E步中计算出的后验概率γ(i,k)大于等于该阈值时，即选择样本数据xi，否则直接舍弃。

修改后的M步如下：

为了保证GMM参数求解的准确程度，CTH应当越小越好，为了提高EM算法的运行速度，CTH应当越大越好，这是一个矛盾，但总体上CTH的取值应当在0～1之间取舍。本文第3部分对CTH的设置进行了实际验证和分析。

2 实验平台的设计

通过对E步和M步的分析可知，当样本数据规模增大（行数增多、维数变大）、GMM的高斯成分数K增多时EM算法的运行时间将呈现非线性增长，在小规模的数据集上验证改进的EM算法将没有实际意义，但在大规模数据上验证EM算法时又不能直观地比较GMM参数估算值的差异，因此本文对改进后EM算法的验证分成两部分：第一部分在较大规模数据集上比较改进前后EM算法的运行速度，第二部分在实际应用中比较改进前后的EM算法对结果的影响。

2.1 数据准备及运行环境

为了让算法的比较具有实际意义，文章选择KTH人体行为数据库作为实验对象，KTH数据库由瑞典皇家理工学院的Schldt[6]等在人体行为识别的研究中提出，该数据库包括6个常见的行为类别：拳击（boxing）、击掌（hand clapping）、挥手（hand waving）、慢跑（jogging）、行走（walking）和跑步（running）。每个行为由25个不同的人在不同的场景中完成。4个场景包括室外、室外尺度变化、室外穿着变化和室内。该数据库一共包含599段视频序列，每段视频以25 f/s（帧/秒）的速度持续10～15 s。

对KTH视频数据提取STIP[7]（Space-Time Interest Point）和SIFT[8]（Scale-Invariant Feature Transform）特征，应用PCA降维方法将STIP特征从162维降为32维，SIFT特征从128维降为32维，高斯混合模型中的高斯成分数量设为256[3]。

算法实验环境为美国迈阿密大学的超算平台（IBM Platform LSF），GMM程序采用Bouman C A教授公开的3.6.6版本[9]，文中将该程序中的GMM参数初始化修改为通过Kmeans聚类获取。

2.2 实验设计流程

从单个视频提取的特征（STIP或SIFT）往往不足以精确地估算GMM的参数[10]，因此从所有的训练视频样本中提取特征，估算GMM参数，从而得出一个UBM。为了更好地描述特定视频特征数据的分布状态，用最大后验概率（MAP）[11]方法来调整UBM参数（通常只调整均值向量μ）。以UBM中的第k个高斯成分为例，针对特定视频的特征数据，首先计算γ(t,k)，然后计算如下参数

式中：xt代表某个视频的第t行特征值；r是一个调节参数，通常设置值在8～20之间[12]；Ek(x)代表所有样本数据针对第k类高斯分布的加权平均；为调整后的第k类高斯分布的均值向量。

将调整后的所有高斯成分的均值归一化后，连接起来就形成了GMM超向量，归一化公式为

算法验证的第一部分比较改进前后的EM算法估算GMM-UBM参数的运算速度。第二部分将在GMM-UBM的基础上构建GMM超向量，结合SVM进行多值分类，对KTH进行留一交叉验证法（LOOCV）验证。实验设计的流程图如图1所示。

3 算法验证

3.1 GMM参数估算速度的比较

图1 实验设计流程图

选择STIP特征数据对KTH进行留一交叉验证，每次用24人的视频数据训练GMM-UBM，共需25轮，经过降维、采样等处理后，每轮STIP特征数据平均133 Mbyte左右。为了兼顾运行速度和参数估算准确程度，CTH取值选择了5个参数值（0，0.001，0.01，0.1，0.5）进行比较。实验结果如图2所示。参数CTH值为0代表原EM算法。从实验的几组阈值可以看出当CTH设为0.001时相比原EM算法运行速度提高了很多（92.3%），而当CTH增加时运行速度的提高变得相对缓慢。通过查看EM算法迭代过程输出的中间值γ(i,k)可以发现几乎每行样本对应的256个概率值大部分γ(i,k)都小于0.001/256，只有少数几个比较大。随着阈值的增大，运行速度的提高并不明显，这说明CTH取0.001时已经舍弃了绝大多数样本数据，只有少数样本数据对应的γ(i,k)需要更大的阈值进行舍弃。

图2 不同阈值参数运行时间比较

综上分析可以得出用GMM拟合样本数据分布时，大部分样本数据具有明显的倾向性，即属于某个或某几个高斯成分的概率大，属于其他高斯成分的概率则很低，舍弃影响特别低的样本数据有助于加快EM算法的运行速度。这进一步验证了本文提出改进EM算法的指导思想。

3.2 在KTH上的应用比较

在STIP特征数据训练出GMM-UBM的基础上构建GMM超向量，结合LIBSVM[13]进行多值分类，SVM采用径向基核函数（RBF）。采用不同阈值得出的识别准确率如表1所示。

表1 不同阈值应用比较

由表1可以看出不同的阈值在实际应用中对识别准确率的影响不大，这说明改进后的EM算法几乎没有影响原EM算法求解GMM参数的准确度。

本文采用改进后的EM算法，将CTH设为0.001，分别基于STIP特征和SIFT特征进行行为识别，基于STIP特征的识别准确率为88.98%，基于SIFT特征的识别准确率为82.48%，合并两种特征得出的相似度（SVM score）后得出的识别准确率为91.33%，其对应的混淆矩阵如图3所示。

图3 KTH数据库混淆矩阵，平均准确率91.33%

4 结语

通过分析EM算法运行时间过长的原因，本文提出了一种改进的EM算法，改进后的EM算法通过设置一个阈值来挑选部分特征数据重新估计每类分布的参数值，实验证明当数据规模较大、高斯成分数很高时，通过设置适当的参数，改进后的EM算法相比原有的EM算法在估算GMM参数时能够显著地提高运行速度，而在KTH人体行为库的实际应用中，行为识别准确率只受到了很小的影响。

本文是通过降维和采样的方法来缩小数据规模进行实验，改进的EM算法还可以尝试结合Hadoop应用到大数据处理上，来加快大数据求解GMM参数的时间。

：

[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的图像语义标注方法[J].电视技术，2013，36（23）：35-38.

[5]钟金琴，辜丽川，檀结庆，等.基于分裂EM算法的GMM参数估计[J].计算机工程与应用，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，France：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.