自然语言处理中稀疏矩阵逼近的概率矩阵分解算法

⃝≤K⃝可在www.sciencedirect.com上在线ScienceDirectICT Express 4（2018）87www.elsevier.com/locate/icte自然语言处理中稀疏矩阵逼近的概率矩阵分解算法Gianmaria Tarantino，Stefania Monica，Federico BergentiDipartimento di Scienze Matematiche，Fisiche e Informatiche Universitá degli Studi di Parma，43124 Parma，Italy接收日期：2018年2月12日;接受日期：2018年在线提供2018年摘要本文提出了一个著名的概率矩阵分解算法，这是常用的数据分析和科学计算，并已被认为是最近服务于自然语言处理的变化。所提出的变型意在利用以下事实：在自然语言处理任务中处理的矩阵通常是稀疏矩形矩阵，其中一个维度比另一个维度大得多，并且这可以用于在可接受的计算时间内确保足够的准确度在真实文本语料库上的初步实验表明，该算法与原算法相比取得了相应的改进。c2018韩国通信与信息科学研究所（KICS）。Elsevier B.V.的出版服务。这是一个开放获取CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：潜在语义分析;自然语言处理;奇异值分解1. 介绍将单词和文档表示为密集向量是几个NLP（自然语言处理）任务的基本步骤，包括信息检索，词义消歧和文本相似性。文献提出了两种类型的方法来计算单词和文档的表示[1]：全局矩阵分解方法和局部上下文窗口方法。然而，如[2]中所讨论的，这种类型的方法之间的区别变得模糊，因为具有负采样的众所周知的方法skip gram[3]隐式地分解了单词上下文矩阵。在全局矩阵分解方法中，构建文档和单词的密集表示的经典方法是LSA（潜在语义分析）[4]。简单地说，LSA通过首先提取术语的规范化词汇表来处理给定的文本文档语料库。然后，它建立一个TDM（术语-文档矩阵）[5]，其位置（i， j）中的元素是*通讯作者。电子邮件地址：gianmaria. unipr.it（G. 塔伦蒂诺），斯蒂芬妮.莫妮卡@ unipr.it（S。Monica），federico. unipr.it（F.Bergenti）。同行评审由韩国通信和信息科学研究所（KICS）负责https://doi.org/10.1016/j.icte.2018.04.005术语i在文档j中出现的次数。最后，LSA通过SVD（奇异值分解）[6]分解产生的TDM，以减少需要处理的矩阵的大小，而不会丢失相关信息。考虑到真实世界语料库的TDM可能有数千行，截断SVD[6]通常用于进一步减小矩阵的大小。给定TDMW，其具有秩k rank（ W）的截断SVD使用三个矩阵Uk、Rankk和Vk构建，使得W=UkkVT，（ 1）其中，仅考虑W的最大k个奇异值以形成对角矩阵Wk，以及对应的左奇异向量和右奇异向量以形成酉矩阵Uk和Vk。对于给定k，W在Wk方面的表示用于获得作为密集k维向量的单词和文档的表示k的选择影响TDMW的近似在对应的k方面的准确性。奇异值分解应用于现实世界的问题，这需要处理巨大的语料库与良好的近似，通常需要禁止计算时间，即使当2405-9595/c2018韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。×=←←·×=×A.N×：=AATqA，A的奇异向量相同，88克。塔伦蒂诺等人/ICT Express 4（2018）87使用大型计算基础设施。文献提出了许多算法来解决这个问题，其中概率方法是目前首选的，因为它们可以利用现代计算基础设施的功能。本文提出了一种在合理的计算时间内以足够的精度处理实际TDM的概率算法MQRR（直接SVD的混合QR随机子空间迭代）。这样的算法利用TDM通常是稀疏矩形的事实来减少所需的计算时间，而精度损失较小或没有损失的算法1所提出的算法MQRR的伪代码，用于执行输入矩阵A的近似SVD。1：函数MQRR（A， l）第二章： 输入A：m n实矩阵第三章： 输入l：整数4：输出（U，V， V）：U， V酉，V对角5：n∈Nn×l6：Y0←A7：Q0R0=QRe（Y0）8：对于j←1到q做所提出的算法是众所周知的RSIDSVD的变体（随机子空间迭代与直接SVD）[7]，和一个九：第十章：Yj←ATQj−1QjRj=QR（Yj）与原始算法的性能比较在第3节中示出。详细地说，第3节中讨论的初步实验结果表明，MQRR比RSIDSVD在更低的计算时间内实现了本文的组织结构如下。第2节提出了MQRR算法，重点是计算稀疏矩形矩阵的低秩分解第3节显示了所提出的算法的性能的初步评估。最后，第4节总结了本文，并概述了这条研究线的未来发展计划。2. 该算法概率算法通常用于大型矩阵的低秩矩阵近似在[7]中给出了构造近似矩阵分解的最新概率算法的详细概述简单地说，给定m×n11：YjAQj12：Qj RjQRe（Yj）13：结束14：Q←Qj15：B←QT A16：U VT=SVDe（B）第17章：你是谁18：返回（U，V， V）十九日： end function其中[a.. b]表示a和b之间的整数集合，包括范围边界，并且σj（）表示矩阵的第j个奇异值，按降序计数。请注意，[8]文件中，在许多情况下，q=1或q=2就足够了。最后，请注意，应用于矩阵A的随机抽样会出现舍入误差矩阵A，需要低秩近似，概率低秩近似算法的基本思想是执行以下两个步骤[7]：1. 计算其范围近似于A的范围的标准正交矩阵Q;以及2. 从B=QT A开始计算A的近似SVD分解。详细地说，第一步是通过使用QR分解[6]对矩阵A进行因式分解来执行的，其中A是具有高斯分布的合适的n-l随机矩阵，并且l是根据可接受的近似精度和计算时间来选择的。第二步是通过首先将B因子化为U VT，然后将A的请求近似SVD计算为U VT，其中UQU对于奇异值衰减缓慢的矩阵，可以改进概率低秩近似的概述方案，如在上述RSIDSVD中所假设的这种技术的思想是将随机抽样应用于命题1中定义的矩阵A，对于一个小整数q，因为下面的命题成立[7]：建议1. 给定一个m×n实矩阵A，定义以下条件成立：当使用浮点运算执行时，因此有必要在应用A和AT之后对样本矩阵的列进行正交归一化。该算法的重点是提高RSIDSVD处理稀疏矩形矩阵时的精度。该算法的伪代码如算法1所示，它遵循简要概述的RSIDSVD的一般方案。该算法的描述假定以下约定。首先，用n×l表示nl个随机矩阵的空间，这些随机矩阵具有标准高斯分布.然后，SVDe（X）用于表示矩阵X在秩（X）处的截断SVD，从现在起将其称为经济大小SVD。最后，QRe（Y）用于表示m> n的m n矩阵Y的经济规模QR分解，这是Y的QR分解，仅使用Q的前n列和R的前n行。注意，所提出的算法仅在第10行使用完全QR分解，而在第7行和第12行使用经济尺寸QR分解。第10行的全QR分解的重要性是由[6]的以下结果以及常见TDM的奇异值的值激发的，如下一节中所例示的。2号提案给定一般的m×n矩阵W，对于任意k≤rank（W），条件成立：[1. . rank（A）]σj（A）=σj（A）2q+1（2）minW′∈Mk<$W−W′<$=σk+1（W）（3）×+公司简介××=表1G. Tarantino等人/ ICT Express 4（2018）87-9089表2当参数l变化时，在两个TDM上执行WARNRR和MQRR的计算时间（以秒为单位）最后两行分别对应于计算精确SVD和经济规模SVD所花费的时间l克兰菲尔德CISIRRMQRRRRMQRR109.1秒3.1秒11.3秒3.5秒259.6秒3.1秒12.1秒3.5秒5010.3秒3.1秒13.6秒3.7秒10011.7秒3.5秒16.1秒4.0秒2009.7秒3.3秒11.5秒4.0秒3009.7秒3.3秒12.2秒3.9秒SV DSVD4.0秒2.5 S4.8秒2.6秒哪里是谱范数，k是秩为k的矩阵的集合，并且该条件由W ′来实现，W′经由等式（1）中表示的经济规模SVD来获得。（一）.在算法1中应用至少一个完全QR分解确保了第15行处的矩阵B是n ×n矩阵，并且因此第16行处的经济大小SVD分解可以导致输入矩阵的近似，其误差不受矩阵W的l1奇异值的限制。注意，完全QR分解也可以应用在第7行，而不是第10行，但是，在假设m> n的情况下，它将导致慢得多的计算。原因是q是一个小整数，如前所述，Y0是一个m×l矩阵，Yj是一个n×l矩阵。3. 实验结果该算法在两个TDM上进行了测试，1从标准信息检索测试集合2即CRANFIELD（TDM 4563 1398）和CISI（TDM5544）中1460 ） 。 该 算 法 的 性 能 进 行 了 比 较 的 两 个 变 化 的RSIDSVD方法。第一种方法是RSIDSVD方法，它的QR分解都是满的。第二种方法称为EQRR方法，即RSIDSVD方法，其中所有的QR分解都是经济规模的.所有实验都是多次调用函数，然后取测量值的中位数。使用MATLAB函数timeit执行表1中显示的结果。使用MATLAB R2017 b在具有Intel（R）Core（TM）i7- 3615 QM的膝上型计算机2.3 GHz处理器和8 GB RAM。用于进行实验并获得表1和表2所示结果的MATLAB代码可在ailab.unipr.it/software/mqrr.zip下载。表1和表2报告了当输入矩阵是从CRANFIELD和CISI数据集获得的TDM时，针对不同的l表1的每一行以秒为单位示出了用于执行MRR和MQRR算法所花费的时间，而表2在其行中示出了具有所计算的因子分解的输入矩阵的近似的实验1 http://scgroup20.ceid.upatras.gr:8000/tmg网站。2 http：//web. eecs. UTK。edu/reearch/lsi/corpa. HTML.当参数l变化时，使用通过在两个TDM上执行EQRR和MQRR获得的因子化的输入矩阵的近似的谱范数误差最后一行对应于通过用精确SVD近似输入矩阵而获得的谱范数误差l克兰菲尔德CISIEQRR MQRR10 68.4 ≤1.0e−11 44.6 ≤1.0e−1125 51.0 ≤1.0e−11 33.8 ≤1.0e−1150 40.8 ≤1.0e−11 28.1 ≤1.0e−11100 32.3 ≤1.0e−11 22.0 ≤1.0e−11200 23.2 ≤1.0e−11 16.9 ≤1.0e−11300 18.6 ≤1.0e−11 14.0 ≤1.0e−11SV D≤1.0e−11 ≤1.0e−11表1中的结果表明，对于参数l的所有测试值，MQRR在计算上比MQRR有效得多，保持了与精确SVD相同的谱范数精度，如表2所示。此外，表1显示执行MQRR的计算时间少于精确SVD，并与经济规模SVD相当，两者都使用MATLAB提供的本地命令最后，表2表明，即使l的值很小，例如l10，为MQRR的执行提供可接受的准确性。为了获得略微的执行速度提升，可以优选小的l从执行EQRR获得更好的计算效率，但是表2中报告的大的谱范数误差，即使对于参数l的大值，也阻止在处理大的矩形稀疏矩阵时使用这样的算法。如第3节所述，此行为取决于两个TDM的奇异值的值事实上，首先注意，所有考虑的TDM都有其第301个10阶奇异值。但是，对于CISI TDM的情况，直到第1453个的所有奇异值至少有1阶此外，CRANFIELD TDM的所有奇异值因此，即使具有更大的l值，用EQRR获得的近似也不能与MQRR的近似相比，因为Eq. （3）保持。4. 结论本文提出了一种算法，以提高从现实世界的文本语料库的词和文档的密集表示的建设的性能。的TDMs真实世界的语料库通常很大，需要复杂的算法在可接受的时间内处理它们所提出的算法，这是一个众所周知的算法的变化，使用的事实，即TDM通常是矩形稀疏矩阵，以减少计算时间，也达到更好的精度比原来的算法。此外，该算法中所有矩阵乘积都是内在并行的，易于适应，现代计算基础设施的并行计算特性。最后，如[8]中所述，经济规模QR分解的随机分块版本可用于修改所提出的算法，以便在不损失准确性的情况下在执行时间方面具有更多好处。90G。塔伦蒂诺等人/ICT Express 4（2018）87利益冲突作者声明，本文中不存在利益冲突引用[1] 彭 宁 顿 河 Socher ， C.D. Manning ， GloVe ： Global vectors forwordrepresentation ， in ： Empirical Methods in Natural LanguageProcessing，EMNLP，2014，pp. 1532-1543年。[2] O. Levy，Y. Goldberg，in：Z. Ghahramani，M.威灵角北达科他州科尔特斯劳伦斯，K.Q. Weinberger（Eds.），作为隐式矩阵分解的神经词 嵌 入 ， 在 ： 神 经 信 息 处 理 系 统 的 进 展 ， 第 27 卷 ， CurranAssociates，Inc.，2014，pp. 2177-2185。[3] T.米科洛夫岛Sutskever，K. Chen，G. Corrado，J. Dean，单词和短语的分布式表示及其组合性，在：会议记录第 26 届 神 经 信 息 处 理 系 统 国 际 会 议 - 第 2 卷 ， NIPS'13 ， CurranAssociates Inc.， USA，2013，pp. 3111-3119[4] S. Deerwester，S.T. Dumais，G.W. Furnas，T.K.兰道尔河李文，潜在语义分析的应用，北京科技大学出版社。41（6）（1990）391-407。[5] G.W. O.，M.W. Berry，S.T.陈文辉，应用线性代数于智慧型资讯撷取，国立中山大学资讯工程研究所硕士论文，2000。[6] G.H. 戈卢布足球俱乐部 范洛安，矩阵计算，《约翰霍普金斯数学科学丛书》，第3卷，约翰霍普金斯大学出版社，1989年。[7] N. Halko ， P.G.Martinsson ， J.A.Tropp ， Finding structure withrandom ： Probabilityalgorithms for constructing approximate matrixdecompositions，SIAM Rev.53（2）（2011）217-288。[8] S. 沃 罗 宁 ， P.- G. Martinsson ， A randomized blocked algorithm forefficientlycomputing rank-revealing factorizations of matrix ， SIAM J.Sci. Comput. 38（5）（2016）S485-S507。