文摘

潜在语义分析(LSA)是一种方法,让我们能够从一组对象自动索引和检索信息通过减少term-by-document矩阵使用奇异值分解(圣)技术。然而,LSA高计算成本分析大量的信息。这项工作的目标是改善执行时间(i)的语义空间建设、降维,LSA的信息检索阶段基于异构系统和(2)评估的准确性和回忆信息检索阶段。提出了一种异构潜在语义分析(hLSA)系统,已开发使用通用计算图形处理单元(gpgpu)架构,可以更快地解决大数值的问题通过成千上万的并发线程在多个CUDA gpu和cpu体系结构的核心,它可以通过多处理环境中更快地解决大型文本的问题。我们执行hLSA系统公共医学中心(PMC)的文档数据库。实验的结果表明,加速度hLSA系统达成的一百五十百万的大型矩阵值大约是八倍LSA标准版本的准确性达88%和100%的回忆。

1。介绍

潜在语义分析(LSA)是一种方法,让我们能够从一组对象自动索引和检索信息通过减少term-by-document矩阵使用日志等术语权重方案熵或术语Frequency-Inverse文档频率(TF-IDF)和使用奇异值分解(圣)技术。LSA改进信息检索技术的一个主要问题,即处理一词多义的词,通过假设有一些潜在的潜在语义结构的数据部分被词选择的随机性(1]。LSA使用统计技术来估计这个潜在的结构和摆脱模糊”噪声。”也,LSA已被视为一个新的收购相似性和知识表示的一般理论,有助于在模拟的学习词汇和其他心理语言学现象(2]。

潜在语义分析,从开始到现在,一直在几个研究课题实现的,例如,在应用中预测读者的兴趣新闻文章的选择,根据他们的兴趣报道其他文章(3];自我诊断的疾病通过医学影像的描述4];在应用程序中检测网络欺凌在青少年和年轻的成年人5];在视觉领域的计算机通过改进技术跟踪移动的人6];在应用程序中不太受欢迎的分类网站(7]。

LSA的计算复杂度 ,在哪里是文档的数量之间的较小值的条款和数量k是奇异值的数量(8]。LSA需要大量的时间指数和计算语义空间,当它应用于大规模数据集(9- - - - - -11]。

介绍基于GPU的并行LSA的实现取得了加速五到七次大16岁和2倍整除矩阵与另一个大小。使用GPU的tridiagonalization矩阵,并计算矩阵的特征值和特征向量的例程仍在CPU上实现。结果呈现,准确性和速度需要进一步研究,以产生一个有效的完全可实现LSA算法(12]。

了一种叫做指数插值提出了一种快速计算term-by-document矩阵对于大型文档集合;相关的对称特征向量问题然后解决分布计算在任意数量的计算单位不增加乘法的总数。实验花了42.5小时计算cpu(16日300000条款13]。

我们提出一个完全基于潜在语义分析异构系统(hLSA),利用GPU和CPU架构的资源加速执行时间。减少,我们的目标是计算和检索信息的速度比标准LSA版本和评价信息检索的精度和召回过程hLSA系统。hLSA已评估的性能,结果表明,加速度可以实现高达8倍,88%的精度和召回的100%。早期版本的hLSA系统提出了海报的GPU技术会议(14]。

剩下的纸是组织如下。部分2介绍了LSA的相关背景。节3,我们目前异构潜在语义分析系统。部分4给出了实验设计的描述。部分5介绍了实验的结果。最后,部分6总结了工作。

2。背景

LSA term-by-document需要一个矩阵(米)和语义空间中构造一个条款和文件是放在另一个密切相关。通常,构建语义空间尽可能多的维度独特的方面。此外,而不是处理统计数据时,矩阵的条目米是加权的表示一个词的出现令牌在一个文档中。因此,LSA使用正规化矩阵可大而稀疏。对于这个研究,使用两种类型的权重方案。

(我)首先是一个对数局部和全局熵加权,称为对数熵方案。也就是说,如果表示的次数(频率),一个字出现在文档和在数据集文件的总数,然后呢 在哪里文档包含的分数吗届任期;例如, 这个术语权重方案已经非常成功的LSA许多研究[15),但其他功能是可能的。

(2)第二个术语频率和逆文档频率加权,称为TF-IDF计划,分配的词在文档 ,当是数据集和文件的总数吗是由文档频率矩阵;例如, 这个术语权重方案已经非常成功的LSA许多研究[8]。

反映的主要关联模式矩阵一个而忽略不重要的影响越小,矩阵的reduced-rank近似一个计算使用截断奇异值分解(16]。注意,原始的加权矩阵的奇异值分解可以写成 在哪里words-by-documents矩阵;是一个 正交矩阵的值代表的左奇异向量 ; 是一个 正交矩阵的值代表的右奇异向量 ;和是一个 对角矩阵的奇异值包含在降序排列。请注意,是单词的总数之间的较小值吗和文档的总数d。

获取截断奇异值分解用 ,有必要限制计算矩阵第一< min(条款、文件)维度,揭示了 选择合适的尺寸是一个开放的研究问题。建议的最佳值k从50到500维度,根据数据集的大小。如[17),如果维度的数量太小,重要的语义内容仍未捕获的,如果尺寸太大,随机噪声在用词会改造。注意,截断奇异值分解将条款和文件都表示为向量维空间。

最后,对信息检索的目的,使用维语义空间。因此,用户查询并入条款维空间语义空间来确定空间中的一个点。这可以通过查询解析为一个向量用的非零值对应的术语权重独特有效的用户查询。然后,查询用折叠过程可以表示成 然后,这向量可以与任何或所有文件/条件的向量维语义空间。比较向量点积或余弦点之间使用。例如, 在哪里是一个向量表示的吗维空间。LSA提出检索信息在两个方面:通过建立相似的最小值,例如,所有的相似性大于0.90,通过获得的顶级值相似,例如,前10名,前5名。

3所示。异构潜在语义分析系统

hLSA系统有几个技术难题:如何构建语义空间使用cpu架构加快文本处理;如何降低维数term-by-document矩阵的使用架构GPU加速矩阵处理;和如何检索信息从语义空间使用GPU机制加快矩阵计算和文本。图1介绍了提出hLSA系统建设,减少,使用异构体系结构和检索相关文件。

值得注意的是,hLSA系统的特点之一是使用GPU的体系结构,它能够执行SIMD(单指令多数据)操作,如矩阵和向量乘法,非常有效地高并行性。此外,我们利用多cpu体系结构,能够执行SIMD操作,如地图和减少功能。一方面,hLSA系统利用GPU的体系结构来解决矩阵运算,特别是在阶段降维和信息检索。另一方面,hLSA系统利用CPU和多CPU架构来解决文本处理,语义空间的舞台。因此,使用这些机制hLSA系统能够实现加速性能。

3.1。语义空间的舞台

构建语义空间的输入是一个知识库;这是代表数据集的原始文本,通常存储在个人计算机的磁盘驱动器中。因此,hLSA系统首先需要找到文本文档。这个执行没有主要的计算成本,因此由CPU执行的顺序。结果,生成一个文档列表加载到内存的CPU。

从获得的文档列表,hLSA系统开始阅读每个文档文本并启动预处理,例如,消除在开头和结尾的空格,也消除特殊字符,如“? ! ();。^·和忽略常见词称为stopwords,如“的”;“对”;和“你”。因此,文本预处理的hLSA系统生成一个列表,存储在主CPU内存。这个过程在CPU上执行运行时的顺序。

然后,hLSA系统开始生成项频率计算矩阵的文档表示一个,行代表的条款和列表示文件。为了做到这一点,hLSA系统分析预处理的文档的列表。

因此,hLSA系统需要每个列表的文本预处理和分割内容时,会出现一个空白。例如,文本“这是一个例子”在每个空格分割。因此,一个单词列表:[“这”;“是”;“一个”;“榜样”)是生成的。

接下来,hLSA系统迭代的新单词列表,每次一词出现在文档hLSA系统增加了一个相应的单元矩阵的价值一个。这种方法具有很高的计算成本。

因此,我们使用多cpu体系结构实现并行多处理模型。每个CPU核心负责处理的预处理文本列表的一个元素,如图2。由于语义空间的阶段,hLSA系统生成并行和顺序程序矩阵一个,每个单元格值对应的频率,一个词出现在文档的知识库。

3.2。降维的阶段

hLSA系统使用CUDA编程模型来处理降维的矩阵一个。因此,hLSA系统使用两个维度( , CUDA架构);的x维度与矩阵的行相关联y维矩阵的列。每一块CUDA架构执行32个并发线程和块的总数取决于执行处理矩阵的总大小。

hLSA体系需要规范化矩阵一个。因此,两个术语权重方案用于规范化矩阵答:日志熵和术语Frequency-Inverse文档频率的方案。为了计算术语权重方案,hLSA系统负载矩阵一个到全球GPU内存中,然后执行CUDA内核函数和由此产生的矩阵保存到GPU全局内存A_norm。

hLSA系统采用奇异值分解算法,分解矩阵A_norm为三个矩阵。矩阵T是一个左奇异向量的正交矩阵。矩阵年代是一个对角矩阵,包含奇异值大小下令。矩阵D^T是一个右奇异向量的正交矩阵。因此,hLSA系统需要的GPU全局内存中保留空间合成矩阵T,年代,和D^T。然后,它执行compute_svdCUDA的功能。最后执行hLSA系统释放GPU内存空间的矩阵A_norm。

最后,hLSA系统对合成矩阵计算函数的截断成第一k维度。因此,它执行的truncate_svdCUDA的功能。因此,hLSA系统生成三个矩阵,表示为Sy,泰,Dy。最后执行矩阵复制到主内存的CPU和GPU全局内存被释放。的降维阶段hLSA系统如图3。

3.3。信息检索阶段

hLSA系统使用用户查询来检索相关信息的语义空间。因此,hLSA系统创建了一个一维向量,表示为问,大小等于总数方面获得的语义空间。然后,分析了查询;也就是说,如果一个单词查询对应于一个词的语义空间,hLSA系统增加一个相应的单元值的向量 。这个执行没有主要的计算成本,因此由CPU执行的顺序。

然后hLSA系统折叠向量问使用查询到语义空间折叠方程(6)。因此,hLSA系统执行query_foldingCUDA使用矩阵函数Sy,泰,Dy在GPU全局内存加载。因此,hLSA系统生成一个向量 ,其值对应的术语权重独特的单词查询。然后,hLSA系统比较向量与所有文档向量在语义空间为了找到他们的相似之处。

计算相似度,hLSA系统使用余弦相似度方程(7)。因此,它执行cosine_similarity使用CUDA函数向量的文档向量矩阵Dy。最终,hLSA系统显示最相关的文档基于向量之间的相似度值和每个文档向量。呈现结果,hLSA系统建立相似度阈值,例如,所有的相似性大于0.90,和/或hLSA系统获得的顶级值相似,例如,前20名,前10名,前五名。的信息检索阶段hLSA系统如图4。

4所示。实验

本节的目的是评估的性能提出hLSA系统。实验详细的设计知识库的定义,定义数据集的大小,Stopword文档的定义,的定义维度,定义的用例评价方法。

(1)定义的知识库。hLSA的实验系统使用文档的开放获取公共医学中心(PMC)的子集的知识基础实验。PMC是一个在线数字的免费全文生物医学文献数据库。广泛应用在文本检索会议(TREC)(文本检索会议(TREC),联合国家标准与技术研究院(NIST)和美国国防部,可以发现http://trec.nist.gov)。每篇文章的文本在开放获取子集被表示为一个NXML文件,使用一个XML格式的核磁测井杂志存档和交换标记集(《存档和交换标记集定义元素和属性描述期刊文章的内容和元数据,包括研究和nonresearch文章、信件,社论,书和产品评论)。

文件命名和通过一个独特的识别号码(PMCID)定义的< article-id >元素。另外,每个NXML文件XML元素等<标题>,< doi >,<摘要>,<图>,< publisher-name >,。实验的目的,我们只使用文档的摘要。从每个NXML和提取这些信息复制到一个新的文本文件(. txt)。每个文本文件存储在一个工作目录与文件名称等于PMCID标识符。

(2)定义的数据集的大小。hLSA的实验系统使用PMC的总共五千个文档数据库。为了观察执行总时间的变化hLSA系统的大规模数据集,我们五千文档分割成十二个子集大小不同的大小从五百年到五千年不等的文档。在表1,我们现在每个子集的一个总结。第一列表示文件的总数。第二列表示单词的总数在数据集预处理的原始文本。第三列展示了独特的单词总数的数据集。第四列表示的矩阵元素的总数term-by-document和最后一列代表term-by-document矩阵的大小以兆字节为单位。

(3)Stopword文档的定义。hLSA的实验系统使用的文档文件stopwords排除某些单个词比如决定因素,也就是说,“,”“,”“,”和“另一个”;并列连词,“对”,“但是,”“或”和“所以”;介词,“在”、“下”和“对”;代词的形式,也就是“我”,“我”,“我”和“你”;动词形式,即“我”、“是”“是”和“做”;在其他单词。总共使用了一千九百八十二个单词。

(4)的定义 维。hLSA使用几个值的实验找到适当的值与hLSA系统更准确。总的来说,二十的值使用从25到五百维度25的增量。

(5)定义的用例。hLSA的实验系统进行了三个用例:(a)双相情感障碍,(b)红斑狼疮疾病,(c)托吡酯减肥。

(一)双相情感障碍。双相情感障碍可能在患者在他们中年肥胖疾病,那些挣扎于自己的体重,吃的时候感觉沮丧,过度焦虑,烦躁,易怒,当有自杀的念头和/或失眠。

(b)红斑狼疮疾病。红斑狼疮疾病可以在脱发患者皮疹在鼻子和检查,精致nonpalpable紫癜牛犊,和肿胀和疼痛的手腕和脚踝和正常红血球的贫血,血小板减少,阳性蛋白和红细胞投。

(c)托吡酯减肥。一些研究报告表明,抗惊厥的托吡酯导致各种减肥病人组。病人失去了7.75公斤的平均在6个月和12个月患者失去了平均9.61公斤。

(6)评价方法。我们定义的子集的大小,数量的k维度,为我们的实验和用例。因此,评估我们的hLSA系统,我们使用两种方法:(a)我们已经构建了LSA系统使用CPU sequential-only架构,为了达成的具体评估加速度hLSA系统。因此,我们的执行时间相比hLSA和LSA (CPU sequential-only)系统。(b)我们已经评估的准确性和回忆信息检索阶段。

(一)时间执行。我们执行了hLSA系统和LSA系统共有四百八十次完成所有的实验不同的子集,k维度、权重方案和用例。因此,为了比较hLSA系统的执行时间和LSA系统,我们收集了每个程序的执行时间参与每个阶段的两个系统。因此,我们提出了在部分4这些执行的平均值。

(b)相似度的准确性。我们执行了hLSA系统和LSA系统共有四百八十次完成所有的实验不同的子集,k维度、权重方案和用例。因此,为了评估hLSA系统的信息检索过程,我们提出了排名前十的文件,我们已经生成的相似值相比hLSA系统在每个实验中五千个文档的子集。

5。结果

在本节中,我们提出与hLSA系统实验的结果。首先,我们展示了执行时间语义空间的舞台。其次,我们目前的执行时间降维阶段。第三,我们显示信息检索阶段的执行时间。第四,我们完整的hLSA系统的执行时间。最后,结果评估相似精度和召回信息检索阶段。

hLSA系统上执行一个Linux OpenSUSE 13.2(3.16.6-2内核)系统与英特尔酷睿i7处理器2.50 GHz的16 GB DDR3L主内存和4核每个核心8线程和NVIDIA GeForce GTX 970米。GPU已经10 SMs 128 CUDA核对于每个SM,总共有1280 CUDA内核。GPU的总量全球3064 mb的内存和2.5 GHz的时钟速度。同时,每个多处理器的最大线程数是2048,和每个块的最大线程数是1028。线程阻塞的GPU最大尺寸大小是“1024、1024和64年”( , , )维度。

(1)运行时结果:语义空间舞台。程序执行的语义空间阶段阅读stopwords文件,发现文件在硬盘驱动器,从硬盘驱动器读取文档,文档解析成主CPU内存,并构建矩阵计算频率的文档。hLSA系统使用CPU体系结构解析文档的好处在主CPU内存。表2当前程序的执行时间执行的CPU sequential-only。在表3,我们比较的执行时间文档解析器程序使用CPU sequential-only和多CPU体系结构有四个,八个,16个处理器。此外,在图5,我们目前的整体执行时间使用CPU和CPU架构。执行时间是获得的平均值四百八十执行,提出了以毫秒为单位。

高的程序执行时间的LSA系统读文件和文档解析器。另一方面,最高的程序执行时间在hLSA系统读文件。这是由于这一事实读文件程序访问磁盘驱动器为了阅读文本文档,访问磁盘驱动器和时间取决于硬件。因此,有一个瓶颈是有限的磁盘I / O系统的硬件,这超出了我们的工作范围。

此外,我们发现了一个实质性的改善文档解析器hLSA系统程序使用cpu体系结构。加速度的2.50倍是五百个文档和最大加速度的2.90倍和五千个文档使用四个处理器。使用8个处理器时,加速度的3.00倍是五百个文档和最大加速度与五千个文档的3.85倍。最后,对16个处理器,加速3.30倍是五百个文档和最大加速度与五千个文档的3.96倍。因此,找到一个更好的整体性能与16个处理器和更大的加速度当文档语料库增加。

(2)运行时结果:降维阶段。加权方案日志熵和术语Frequency-Inverse文档频率LSA系统中具有较高的计算成本,如表所示4。hLSA系统达到30次的加速度较小的数据集(五百年至二千五百年)和加速八百五十倍的更大的数据集使用TF-IDF计划(三千年至五千年)。同时,使用日志熵方案hLSA系统已达到六十二倍的加速度较小的数据集和加速度的一千零五十二倍大的数据集。

日志熵的计算复杂度是0 (d),TD-IDF方案O(dw),单词的总数和吗语料库是文档的总数。如结果所示,TF-IDF方案hLSA系统减少了执行时间超过160秒不到0.20秒,hLSA系统和日志熵方案减少了执行时间超过321秒不到0.20秒。

与此同时,精确计算的计算复杂度O ,这是昂贵的大型矩阵。hLSA系统,我们实现GPU-SVD函数,它给了我们三倍的加速比LSA系统。在图6,我们现在比较之间的计算执行时间hLSA系统和LSA系统。

在最小的数据集,我们测量一个执行时间1.60秒的LSA系统,在大数据集,我们测量一个执行时间为122.10秒。另一方面,在hLSA系统,我们测量一个执行时间最小数据集和一个0.50秒的最大执行时间53.40秒的数据集。因此,我们在大多数情况下加速度的两到三倍。

因此,英伟达视觉分析器的计算过程进行了分析。我们发现圣言会产生大约77%的时间处理和发射约六千七百三十的内核实例计算在CUDA架构。此外,分析器显示内存访问的优化问题,计算计算过程。共享内存,圣言会使用39.193 GB / s的低带宽273163加载/存储事务,对于设备内存,圣言会利用一个低带宽1193617年42.814 GB / s的读/写事务。

同时,截断奇异值分解过程的计算成本只需要不到一秒LSA系统使用最大的数据集。然而,hLSA系统,我们加快了九倍的小数据集和四倍大的数据集。在表5,我们现在执行的结果与二千年的数据集文件。在这个执行,我们的结果呈现加速度的四倍。

我们已经提出了程序的结果:日志熵,TF-IDF,圣言,截断奇异值分解。如结果所示,降维阶段最计算成本在我们的实验。因此,我们现在在图7降维的完整执行阶段的结果 和TF-IDF加权方案。我们获得的加速度较小的数据集从六到十倍,和更大的数据集加速度从5到8倍。

(3)运行时结果:信息检索阶段。我们已经实现了hLSA系统不仅对索引文件,而且对信息检索。因此,我们现在的结果执行时间在信息检索过程如下:查询解析器,查询折叠和余弦相似性。

我们获得的过程时间查询解析器程序,已实现两个系统的CPU sequential-only hLSA和LSA。我们现在,在桌子上6,查询的结果解析程序使用三个用例在每个数据集。

最高的过程计算成本的信息检索阶段是查询解析器程序。最大的数据集与双相情感障碍的用例34秒左右,与用例狼疮病花了27秒左右,和用例的托吡酯减肥用了超过120秒。这是由于独特的单词数量的查询。第一个用例平均31独特的话说,第二个用例平均22独特的话说,最后用例平均136个不同的字。

另外,我们现在查询的结果乘以折叠过程和余弦相似性过程。我们现在使用托吡酯的用例的减肥效果最好。这些程序没有高计算成本;在大多数情况下,执行时间小于一秒hLSA和LSA系统中所有的数据集。表7展示了几个查询折叠和余弦相似性程序的结果。

(4)运行时结果:hLSA和LSA。我们在表8hLSA系统的总执行时间和LSA系统五千个文档,尺寸等于三百,三个用例,和两个权重方案。另外,使用双相情感障碍的情况下,我们目前的结果与四个处理器;对于用例狼疮疾病,我们结果与8个处理器;托吡酯减肥的用例,我们目前的结果与16个处理器。我们到达整体加速5到8倍。

(5)信息检索结果。评估的准确性,我们比较hLSA系统检索到的文档的基于文本的查询与每个用例和相关文件定义的专家。最相关的文档的专家定义用例的双相情感障碍是标识符的文章1087494,1434505,2031887;为用例狼疮疾病最相关的文档标识符的文章1065341,1459118,1526641;和托吡酯减肥最相关的用例文档标识符的文章是1087494。我们提出相似的结果为每个知识库的相关文档覆盖所有的文档有两个权重方案和20的值 ,双相情感障碍的用例图8红斑狼疮疾病的用例图9和托吡酯减肥的用例图10。

如结果所示,实验中发现的最好的相似之处与双相情感障碍的hLSA系统用例的值 和准确性= 0.88,对于用例狼疮疾病发现的值 和准确性= 0.56,使用托吡酯的减肥的值 和准确性= 0.98。总之,相似性值归一化的范围从一百五十年到三百年。

此外,我们现在排名前十的结果与双相情感障碍的用例文档表9;与用例狼疮疾病,我们在表显示查询结果10,使用托吡酯的减肥的情况下,我们提出在表的结果11。如结果所示,在几个实验的相关文件的标识符定义的专家检索在前十。

6。结论

介绍了异构系统基于潜在语义分析的方法。该系统允许索引的文本文档知识库的速度比标准的LSA版本。此外,hLSA系统允许基于查询检索相关文件。结果我们发现是可行的和有前途的。

hLSA系统分为三个主要阶段:语义空间降维,和信息检索。加速度语义所示四倍空间的阶段,加速度的八倍所示一个降维阶段,在信息检索阶段,我们没有发现加速度。然而,hLSA系统主要是有限的和GPU和CPU的全局内存。因此,在未来的工作中,我们建议增加一个multi-GPU功能增加处理矩阵的大小。

我们已经成功的主要动机提高潜在语义分析方法的执行时间通过使用异构架构gpu和cpu等。如图所示在实验测试中,我们取得了整体加速度约8倍标准LSA系统五千个文档。

我们使用十二检索文档的子集不同大小从五百年到五千年的开放获取的文档子集PubMed Central通过使用两个权重方案:日志熵和术语Frequency-Inverse文档频率和20个不同的值从25到250来证明hLSA系统的适当的值更准确。因此,hLSA取得了88%的准确性与双相情感障碍的用例,准确率56%的用例狼疮疾病,98%的准确性和托吡酯减肥的用例。此外,我们可以推断在我们实验日志相似熵方案具有更高的价值在三分之二的用例TF-IDF方案。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作是支持的大学为Salesiana (UPS)通过云计算的研究小组,智能城市和高性能计算(GIHP4C)和科学研究委员会(CONACyT)研究项目。262756年。