基于CUDA的GMM模型快速训练方法及应用

基于CUDA的GMM模型快速训练方法及应用吴奎，宋彦，戴礼荣（中国科学技术大学电子工程与信息科学系，安徽合肥，230027）摘要由于能够很好地近似描述任何分布，GMM在模式在识别领域得到了广泛的应用。GMM模型参数通常使用迭代的EM算法训练获得，当训练数据量非常庞大及模型混合数很大时，需要花费很长的训练时间。NVIDIA公司推出的CUDA技术通过在GPU并发执行多个线程能够实现大规模并行快速计算。由此，本文提出一种基于CUDA，适用于特大数据量的GMM模型快速训练方法，包括用于模型初始化的K-means算法的快速实现方法，以及用于模型参数估计的EM算法的快速实现方法。文中还将这种训练方法应用到语种GMM模型训练中。实验结果表明，与IntelDualCorePentiumⅣ3.0GHzCPU的一个单核相比，在NVIDIAGTS250GPU上语种GMM模型训练速度提高了26倍左右。关键词：GMM模型；语种识别；图形处理单元；统一计算设备架构CUDAbasedFastGMMModelTrainingMethodanditsApplicationWuKui，SongYan，DaiLiRong(DepartmentofElectronicEngineeringandInformationScience，UniversityofScienceandTechnologyofChina，Hefei，230027，China)Abstract:Duetoitsgoodpropertytoprovideanapproximationtoanydistribution,GMMhasbeenwidelyappliedinthefieldofpatternrecognition.Usually,theiterativeEMalgorithmisappliedtoestimateGMMparameters.Thecomputationalcomplexityatmodeltrainingprocedurewillbecomeveryhighwhenlargeamountsoftrainingdataandlargemixturenumberareengaged.TheCUDAtechnologyprovidedbyNVIDIACorporationcanperformfastparallelcomputationbyrunningthousandsofthreadssimultaneouslyonGPU.Inthispaper,afastGMMmodeltrainingimplementationusingCUDAispresented,whichisespeciallyapplicabletolargeamountsoftrainingdata.Thefasttrainingimplementationcontainstwoparts,theK-meansalgorithmformodelinitializationandtheEMalgorithmforparameterestimation.Furthermore,thisfasttrainingmethodhasbeenappliedinlanguageGMMstraining.TheexperimentalresultsshowthatlanguagemodeltrainingusingGPUisabout26timesfasteronNVIDIAGTS250whencomparedtotraditionalimplementationononeofthesinglecoreofIntelDualCorePentiumⅣ3.0GHzCPU.Keywords:GMMmodel;Languageidentification;GPU;CUDA1引言由于能够很好地近似描述任何分布，高斯混合模型（GaussianMixtureModel，GMM）在模式识别领域得到了广泛的应用。GMM模型参数通常使用迭代的EM(Expectation-Maximization)算法[1]训练获得。EM算法是一个迭代算法,需要对模型初始化，一般采用K-means算法实现EM算法的初始化。当训练数据量非常庞大及模型混合数很大时，模型训练需要花费很长的时间。例如，在GMM-UBM（GaussianMixtureModel-UniverseBackgroundModel）模型的语种识别系统[2]中，语种训练样本数非常庞大（如：NISTLRE2007包含14个大语种，对应的SDC[2]训练矢量特征总数为68281155），模型混合高斯数多（一般为2048）计算量巨大。如果用一个CPU的单核训练模型，那么训练时间就不得不成为一个需要考虑的因素,而并行化处理是加快训练一个有效途径。可编程GPU(GraphicProcessingUnit，图形处理器单元)的出现，开辟了快速并行处理的新途径。目前，GPU计算能力和发展速度都超过了传统CPU。GPU具有大量并行处理的流处理器（StreamProcessers,SP），适合计算密集型的应用。在NVIDIA公司推出的统一计算设备架构（ComputeUnifiedDeviceArchitecture，CUDA）编程环境中，使用简单且易实现的扩展C语言就能编写GPU并行程序，大大提高了GPU的可编程性。近期，N.Kumar等[3]用CUDA实现了GMM模型训练的EM算法，然而这种实现方法需要计算并存放多个阶数与高斯混合数、特征维数和训练样本数成正比的矩阵。由于显存容量有限，高斯混合数、特征维数和训练样本数的大小受到限制，不能满足训练样本数庞大的情形。K-means算法在GPU上已有多种实现方法[4-5]，尽管如[5]中所报道的方法对类别数和维数没有限制，但同样受到训练样本数的限制。本文采取分批处理策略，提出了一种改进的基于CUDA的GMM模型快速训练方法，包括用于模型初始化的K-means算法和模型参数估计的EM算法的快速实现方法。这种GMM模型快速训练方法不受训练样本数的限制，且高斯混合数取值范围可以很大（2到4096），能够满足大部分实际要求，如语种GMM模型训练。在实现过程中，简化了[3]中繁琐的协方差矩阵更新过程。实验结果表明，在训练语种GMM模型时，使用这种方法，模型训练速度是传统CPU单核的26倍左右。本文的组织如下：第二节简要介绍CUDA；第三节描述分批策略下用于训练GMM模型的EM算法和K-means算法在GPU上的实现方法；最后以语种GMM训练为例，给出了这种基于CUDA的GMM模型训练方法的性能。2CUDA概述NVIDIA公司的CUDA是一种新型的硬件和软件相结合的架构。CUDA将GPU视为并行计算设备，在计算时自动完成资源的分配和管理，而无需映射到复杂的图形API中，并且使用简单的扩展C即可编写GPU并行程序，极大地提高了GPU的可用性和编程性。线程（thread）是CUDA中的最小的执行单位，并以线程块（threadblocks）的形式组织起来，执行相同的指令，但处理不同的数据。执行相同程序的线程块组成一个网格（grid）。所有线程执行的相同的程序称为一个kernel，一个kernel对应一个grid。线程可以访问多种形式的存储空间。每个线程都有自己的快速读写的本地寄存器（localregister）和本地存储单元（localmemory）。同一个线程块中的线程可以访问属于该线程块的16KB共享内存（sharedmemory）。线程访问共享内存没有产生bankconflict[7]时，可达到与寄存器同样的速度。线程还可以访问容量较大的globalmemory，因为没有缓存，读取globalmemory的延时很大。CUDA提供的（accesscoalescing）机制[7]可以加快对globalmemory的访问。register和sharedmemory是GPU上的有限资源，需要合理的使用以让尽可能多的blocks和threads同时工作。CUDA可以直接集成在VS2005或者其他的编译器中。GPU称为设备（device），CPU称为宿主（host）。host主要负责启动kernel和传输数据，设备负责计算。Device上的kernel的执行和host是异步的，这样GPU在工作时，CPU还可以做其他任务，当然GPU和CPU是可以同步的。[7]详细介绍了CUDA。3分批处理策略下的GMM模型训练在GPU上的实现在EM和K-means算法中，训练样本在计算过程中是相互独立，适合GPU的并行计算。由于EM算法较为复杂，而K-means算法相对简单，所以我们着重介绍EM算法的快速实现方法，然后再简要地介绍K-means算法的快速实现方法。3.1EM算法的矩阵表示首先用矩阵的形式描述EM算法，以更好的介绍EM算法在GPU上的实现过程。混合数为M的GMM模型的密度函数表示为1||iMiiiipxpx其中1212,,,,,,,MM是参数集合，,iiiμ，i，i，i分别是第i个高斯分量的权重、均值向量和协方差矩阵，且11Mii，第i个高斯的密度函数为：1121221|2TiiiiDipxexμxμ将所有训练样本集X表示成矩阵形式1,,TNXxx，样本数为N，维数为D，其中12,,,,1,2,,TiiiiDxxxiNx。上述形式的GMM模型的EM算法迭代公式[6]如下11|,NnewgliiplNx（1）11|,|,NgiinewilNgiiplplxxμx（2）11|,|,NTgiiiiinewilNgiiplxxplxuux（3）其中11,,,,,gggggMM是已知的当前模型参数估计值，1|p|,|gglilgiMggkikkplpxxx，称为高斯分量l对训练样本ix的占有率。实际应用中，协方差矩阵通常取对角阵，所以式（3）又可写为11|,|,NgTTiiinewnewnewilllNgiipldiagplxxxμμx（4）将M个高斯分量的参数表示成矩阵形式：权重矩阵12,,MW；均值矩阵1,TTTDMEANuu；协方差矩阵1,,TTTD，22212,,iiiiD是第i个高斯分量的对角协方差矩阵中对角线上的元素构成的向量。估计模型的参数，也就是去估计上面三个矩阵。定义三个统计累积量矩阵：权重累积量矩阵1,2,,,,,accaccaccMaccW，均值累积量矩阵1,,,,TTTaccaccDaccMEANuu，方差累积量矩阵1,,,,TTTaccaccDacc及NM阶占有率矩阵O，其中,1|,Nglaccnnaplx，,1,,1,,|,NglacclacclDaccnnnplxx222,1,,1,,|,NglacclacclDaccnnnplxx2221,TnnnDxxx，,|,gnnlplOx1,,nN1,,lM写成矩阵形式：1,1,,1accWO（5）TaccMEANOX（6）2TaccΣOX（7）其中2221,,,TNXxx根据式（1、2、4）可以得到参数矩阵更新公式：,laccnewlN（8）,laccnewlnewlNuu（9）2,laccnewnewllnewlNu（10）其中2221,,newnewnewlllDuuu，1,,lM。这里在更新协方差矩阵时，充分考虑了协方差是对角阵这一条件。这样，EM算法的过程可以表示式（5-6）的矩阵运算及式（8-10）的除