基于GPU加速的并行WMD算法  

Parallel WMD Algorithm Based on GPU Acceleration

作　　者：胡蓉 阳王东 王昊天 罗辉章 李肯立 HU Rong;YANG Wang-dong;WANG Hao-tian;LUO Hui-zhang;LI Ken-li(College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China)

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《计算机科学》2021年第12期24-28,共5页Computer Science

基　　金：国家重点研发计划课题(2018YFB0204302);国家自然科学基金重点项目(92055213);国家自然科学基金项目(61872127,61751204)。

摘　　要：Word Mover’s Distance(WMD)是一种度量文本相似度的方法,它将两个文本之间的差异定义为文本的词嵌入向量之间的最小距离。WMD利用词汇表,将文本表示为归一化的词袋向量。文本的单词在语料中所占的比例很小,因此用词袋模型生成的文本向量很稀疏。多个文本可以组成一个高维的稀疏矩阵,这样的稀疏矩阵会生成大量不必要的运算。通过一次性对多个目标文本计算单个源文本的WMD,可以使计算过程高度并行化。针对文本向量的稀疏性,文中提出了一种基于GPU的并行Sinkhorn-WMD算法,采取压缩格式存储目标文本的方式来提高内存利用率,根据稀疏结构减少中间过程的计算。利用预训练词嵌入向量计算单词距离矩阵,对WMD算法进行改进,在两个公开的新闻数据集上进行优化算法的验证。实验结果表明,在NVIDIA TITAN RTX上并行算法与CPU串行相比最高可以达到67.43倍的加速。Word Mover’s Distance(WMD)is a method of measuring text similarity.It defines the difference between two texts as the minimum distance between the word embedding vectors of the text.WMD uses the vocabulary to represent the text as a normalized bag-of-words vector.Since the words of the text occupies a small proportion in the corpus,the document vector gene-rated by the bag-of-words model is very sparse.Multiple documents can form a high-dimensional sparse matrix,such a sparse matrix will generate a lot of unnecessary operations.By calculating the WMD of a single source document for multiple target documents at once,the calculation process can be highly parallelized.Aiming at the sparsity of text vectors,this paper proposes a GPU-based parallel Sinkhorn-WMD algorithm,which uses compressed format to store target text to improve memory utilization,and reduces intermediate calculations based on the sparse structure.The pre-trained word embedding vector is used to calculate the word distance matrix,the WMD algorithm is improved,and the optimization algorithm is verified on two public news data sets.The experimental results show that the parallel algorithm on NVIDIA TITAN RTX can achieve a speedup of up to 67.43×compared with the CPU serial algorithm.

关 键 词：文本相似度 WMD 并行计算 GPU 稀疏矩阵乘法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]