我在大学学习线性代数时,实在想不出它除了告诉我们如何解线性方程外,还能有什么别的用途。关于矩阵的许多概念,比如特征值等等,更是脱离日常生活。后来在数值分析中又学了很多矩阵的近似算法,还是看不到可以应用的地方。当时选这些课,完全是为了混学分的学位。我想,很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究,我才发现数学家们提出那些矩阵的概念和算法,是有实际应用的意义的。
在自然语言处理中,最常见的两类的分类问题分别是,将文本按主题归类(比如将所有介绍亚运会的新闻归到体育类)和将词汇表中的字词按意思归类(比如将各种体育运动的名称个归成一类)。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的,让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。
分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词,或者说实词的向量,然后求这两个向量的夹角。当这两个向量夹角为零时,新闻就相关;当它们垂直或者说正交时,新闻则无关。当然,夹角的余弦等同于向量的内积。从理论上讲,这种算法非常好。但是计算时间特别长。通常,我们要处理的文章的数量都很大,至少在百万篇以上,二次回标有非常长,比如说有五十万个词(包括人名地名产品名称等等)。如果想通过对一百万篇文章两篇两篇地成对比较,来找出所有共同主题的文章,就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章,完成这一百万篇文章相关性比较就需要十五年时间。注意,要真正完成文章的分类还要反复重复上述计算。
在文本分类中,另一种办法是利用矩阵运算中的奇异值分解(Singular Value Decomposition,简称 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 中国对世界的一个贡献。
http://googlechinablog.com/2007/01/blog-post.html
分享到:
相关推荐
我们深入探讨了深度学习的基本原理、神经网络的应用、自然语言处理、语言模型、文本分类、信息检索等领域。更有深度学习、机器学习、自然语言处理和计算机视觉的实战项目源码,助您从理论走向实践,如果您已有一定...
接着利用数学形态学运算和先验知识剔除伪文本区。最后利用改进的穿越线算法精确定位文本。实验表明,本算法不仅对横向文本具有较高的查全率和较低的虚警率,并且对竖向文本也有较好的定位效果。
MathScript通过一种面向数学的文本编程语言对LabVIEW进行扩展,用来进行数学运算与信号分析处理,扩展功能如下。 1.文本数学功能 MathScript内置超过600种函数,用于数学运算、信号分析处理,包括线性代数、...
MathScript通过一种面向数学的文本编程语言对LabVIEW进行扩展,用来进行数学运算与信号分析处理,扩展功能如下。 1.文本数学功能 MathScript内置超过600种函数,用于数学运算、信号分析处理,包括线性代数、...
矩阵运算/仿真平台 Linux 音频软件 - 开源视频播放器 - 开源视频播放器 - 跨平台音乐播放器,网易出品 实用小工具 - 扩展Zsh,爱上命令行 - 开源版本管理软件 编程软件 - 免费强大的IDE - 文本编辑器 - 免费代码编辑...
e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数SetupInventory(),用于从该文本文件中读取库存商品的数据, 实验报告要求: 1、 按要求记录下二叉搜索树的完整实验...
简短而全面的代码,用于使用zipf定律和pearson相关系数对文本数据进行数学处理 作者简介 姓名:Anirudh Kalla 附属机构:印度科普教育科学研究所 部门:物理 嘿,谢谢您访问这个空间,希望您在这里找到有用的东西。 ...
矩阵和数组都是由数值组成的数据集合,但在Matlab中,它们有着不同的属性和用法。 在Matlab中,矩阵是一个二维数组,其中所有的元素都是数值类型的。矩阵用于表示线性方程组、矢量空间、变换等等。在Matlab中,可以...
1.1 矩阵和数组运算 1.2 常用函数 1.3 控制结构语句 1.4 M 文件与函数 1.5 二维、三维作图 Matlab 提高: 2.1 文本、表单、图像数据读写, 2.2 线性和非线性插值和拟合:人口模型实例 2.3 微分方程数值解:...
mathSuite是一个功能非常强大的数学套件,主要处理复杂的代数和几何运算。 它由神话般的ExprEval C Parser提供支持。 该项目的主要目的是通过优化的直接文本界面实现面向数学的快速算法虚拟化。 它还为您提供了一个...
第4章 矩阵运算和函数 4.1 线性方程组 4.2 矩阵函数 4.3 特殊矩阵 4.4 稀疏矩阵 第5章 关系和逻辑运算 5.1 关系算子 5.2 逻辑算子 5.3 关系和逻辑函数 5.4 NaNs和空矩阵 第6章 文本 6.1 字符串 6.2 字符...
初学者需要了解NumPy库的基础知识,包括矩阵和数组的操作、矩阵的数学运算、矩阵的变形和索引等。 二、常用NumPy数据分析技巧 1.数据的读取和存储:NumPy库提供了读写各种格式的数据文件的方法,例如读取和写入文本...
解、插值和拟合计算、完成各种统计和优化问题,最新的版本甚至可以进行数字图象处理、小波分析等;同时它还有方便的画图功能和完善的图形可视化功能。 2、使用方便 MATLAB语言灵活,它将编译、连接和执行融为一体,...
动态规划:通过分解问题为子问题并存储子问题的解,减少重复计算,常用于优化递归解法。代码实现时需定义状态变量和状态转移方程。 图论:研究图的结构和性质的分支。代码可能涉及图的表示(邻接矩阵/邻接表)、遍历...
1.1 矩阵和数组运算 1.2 常用函数 1.3 控制结构语句 1.4 M 文件与函数 1.5 二维、三维作图 Matlab 提高: 2.1 文本、表单、图像数据读写, 2.2 线性和非线性插值和拟合:人口模型实例 2.3 微分方程数值解:...
1.1 矩阵和数组运算 1.2 常用函数 1.3 控制结构语句 1.4 M 文件与函数 1.5 二维、三维作图 Matlab 提高: 2.1 文本、表单、图像数据读写, 2.2 线性和非线性插值和拟合:人口模型实例 2.3 微分方程数值解:...
第4章 矩阵运算和函数 第5章 关系和逻辑运算 第6章 文本 6.3 循环串函数 第7章 决策: 控制流 第8章 M-文件函数 第9章 数据分析 第10章 多项式 第11章 曲线拟合与插值 第12章 三次条样 第13章 数值分析 第14章 富里...
088 马克思手稿中的数学题 089 配对新郎和新娘 090 约瑟夫问题 091 邮票组合 092 分糖果 093 波瓦松的分酒趣题 094 求π的近似值 095 奇数平方的有趣性质 096 角谷猜想 097 四方定理 098 卡布列克常数 099 ...