2007年1月1日下午03:10:00 发表者:Google研究员,吴军
我在大学学习线性代数时,实在想不出它除了告诉我们如何解线性方程外,还能有什么别的用途。关于矩阵的许多概念,比 如特征值等等,更是脱离日常生活。后来在数值分析中又学了很多矩阵的近似算法,还是看不到可以应用的地方。当时选这些课,完全是为了混学分的学位。我想, 很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究,我才发现数学家们提出那些矩阵的概念和算法,是有实际应用的意义的。
在自然语言处理中,最常见的两类的分类问题分别是,将文本按主题归类(比如将所有介绍亚运会的新闻归到体育类)和将 词汇表中的字词按意思归类(比如将各种体育运动的名称个归成一类)。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类 解决这两个问题的,让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。
分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词,或者说实词的向量,然后求这两个向量的夹角。当这 两个向量夹角为零时,新闻就相关;当它们垂直或者说正交时,新闻则无关。当然,夹角的余弦等同于向量的内积。从理论上讲,这种算法非常好。但是计算时间特 别长。通常,我们要处理的文章的数量都很大,至少在百万篇以上,二次回标有非常长,比如说有五十万个词(包括人名地名产品名称等等)。如果想通过对一百万 篇文章两篇两篇地成对比较,来找出所有共同主题的文章,就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章,完成这一百万篇文章相关性比较 就需要十五年时间。注意,要真正完成文章的分类还要反复重复上述计算。
在文本分类中,另一种办法是利用矩阵运算中的奇异值分解 (SingularValueDecomposition,简称SVD)。现在让我们来看看奇异值分解是怎么回事。首先,我们可以用一个大矩阵A来 描述这一百万篇文章和五十万词的关联性。这个矩阵中,每一行对应一篇文章,每一列对应一个词。
在上面的图中,M=1,000,000,N=500,000。第i行,第j列的元素,是字典中第j个词在第i篇文章中出现的加权词频(比如,TF/IDF)。读者可能已经注意到了,这个矩阵非常大,有一百万乘以五十万,即五千亿个元素。
奇异值分解就是把上面这样一个大矩阵,分解成三个小矩阵相乘,如下图所示。比如把上面的例子中的矩阵分解成一个一百 万乘以一百的矩阵X,一个一百乘以一百的矩阵B,和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿,仅仅是原来的三千分之一。相 应的存储量和计算量都会小三个数量级以上。
三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词,其中的每个非零元素表示这类词中每个 词的重要性(或者说相关性),数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章,其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵 则表示类词和文章雷之间的相关性。因此,我们只要对关联矩阵A进行一次奇异值分解,w我们就可以同时完成了近义词分类和文章的分类。(同时得到每类文章 和每类词的相关性)。
现在剩下的唯一问题,就是如何用计算机进行奇异值分解。这时,线性代数中的许多概念,比如矩阵的特征值等等,以及数 值分析的各种算法就统统用上了。在很长时间内,奇异值分解都无法并行处理。(虽然Google早就有了MapReduce等并行计算的工具,但是由 于奇异值分解很难拆成不相关子运算,即使在Google内部以前也无法利用并行计算的优势来分解矩阵。)最近,Google中国的张智威博士和几个 中国的工程师及实习生已经实现了奇异值分解的并行算法,我认为这是Google中国对世界的一个贡献。
分享到:
相关推荐
数学建模-MATLAB中的矩阵运算.zip
【陕西理工大学】数学软件实训【2023】——数学实验报告(7)(矩阵运算与多项式计算),实验课程-MATLAB语言基础,实验项目-矩阵运算、多项式与插值。一、实验目的 1. 掌握数矩阵的各种运算。 2. 掌握数据插值和...
二年级下册数学第五单元--混合运算.doc
本数学矩阵运算库采用C语言编写,可以实现基本的数学矩阵运算,如加减,相乘,求行列式的值,求矩阵的逆等,使用方便。
Mathcad-数学运算-数理统计与数据处理完美版资料.ppt
人教版四年级数学下(下册)--运算定律.doc
在矩阵运算教学中融入数学建模和Matlab软件的探索与实践.pdf
c#语言 数学矩阵运算的类 包括矩阵相乘 矩阵求逆 矩阵转置 矩阵加减
数学建模-基于k-means的中文文本聚类算法的研究与实现.zip
模糊数学——模糊矩阵运算PPT学习教案.pptx
很清楚的电子书,图像处理方面的一定要看看,数学知识
c#矩阵运算,包括一些数学是运算和所有的矩阵运算求秩等
强化练习-数学运算1+钱敏+(讲义+笔记).pdf
数学建模及Matlab软件在矩阵运算教学中的应用
数学建模及Matlab软件在矩阵运算教学中的应用.pdf
产品版本号:矩阵运算工具3.0 试用版 矩阵运算工具,是帷幄软件的核心产品,又称帷幄矩阵运算工具。 矩阵运算工具1.0和2.0为内部测试版本,矩阵运算工具3.0 现在推出试用版。 官方网站:...
A11-俄罗斯数学教材选译-矩阵论(下)-甘特马赫尔著_柯召译(Dir).rar A11-俄罗斯数学教材选译-矩阵论(下)-甘特马赫尔著_柯召译(Dir).rar
离散数学中闭包运算实验,在。net,使用了Warshall算法
第1章 向量代数与矩阵第2章 范数理论及其应用第3章 矩阵分析及其应用第4章 高斯消去法第5章 特征值的估计及宮.....
1、介绍了各种矩阵分解的原理及应用场景 2、算法仿真 3、实例