`
liuxinglanyue
  • 浏览: 565355 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

数学之美 系列十八 - 矩阵运算和文本处理中的分类问题

阅读更多

我在大学学习线性代数时,实在想不出它除了告诉我们如何解线性方程外,还能有什么别的用途。关于矩阵的许多概念,比如特征值等等,更是脱离日常生活。后来在数值分析中又学了很多矩阵的近似算法,还是看不到可以应用的地方。当时选这些课,完全是为了混学分的学位。我想,很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究,我才发现数学家们提出那些矩阵的概念和算法,是有实际应用的意义的。

在自然语言处理中,最常见的两类的分类问题分别是,将文本按主题归类(比如将所有介绍亚运会的新闻归到体育类)和将词汇表中的字词按意思归类(比如将各种体育运动的名称个归成一类)。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的,让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法

分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词,或者说实词的向量,然后求这两个向量的夹角。当这两个向量夹角为零时,新闻就相关;当它们垂直或者说正交时,新闻则无关。当然,夹角的余弦等同于向量的内积。从理论上讲,这种算法非常好。但是计算时间特别长。通常,我们要处理的文章的数量都很大,至少在百万篇以上,二次回标有非常长,比如说有五十万个词(包括人名地名产品名称等等)。如果想通过对一百万篇文章两篇两篇地成对比较,来找出所有共同主题的文章,就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章,完成这一百万篇文章相关性比较就需要十五年时间。注意,要真正完成文章的分类还要反复重复上述计算。

在文本分类中,另一种办法是利用矩阵运算中的奇异值分解(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 中国对世界的一个贡献。

分享到:
评论

相关推荐

    矩阵运算(MATLAB)

    矩阵运算是 MATLAB 中的一种基本运算,涉及矩阵的创建、矩阵运算、矩阵分解等知识点。下面将详细介绍矩阵运算的相关知识点。 矩阵定义 矩阵是一种数学对象,由行和列组成。矩阵可以用来表示线性方程组、变换、统计...

    谷歌黑板报-数学之美 数学在信息检索和自然语言处理中的主导作用和奇妙应用 共45页.pdf

    16. **矩阵运算**:在文本处理中,矩阵运算常用于表示词语关系,如奇异值分解(SVD)在推荐系统和主题建模中的应用。 17. **贝叶斯网络**:马尔可夫链的扩展,贝叶斯网络提供了处理变量间条件依赖的概率框架,常见于...

    数学之美系列完整版.doc

    【数学之美系列】是由Google研究员吴军撰写的一系列文章,主要探讨了数学在信息处理、自然语言处理(NLP)和搜索引擎技术中的应用。该系列文章涵盖了多个关键知识点,包括统计语言模型、中文分词、隐含马尔可夫模型...

    求逆矩阵运算

    在计算机科学和数学中,矩阵运算是至关重要的部分,特别是在线性代数和数值分析领域。本项目聚焦于使用C语言实现矩阵的加法、减法以及求逆矩阵的运算。接下来,我们将深入探讨这些概念及其在编程中的实现。 1. **...

    矩阵运算matlab-master (1).zip

    这个"矩阵运算matlab-master (1).zip"文件可能包含了一系列实际应用的例子,帮助用户深入理解和掌握MATLAB的矩阵运算技巧。通过学习和实践其中的代码,我们可以提升在MATLAB环境中处理矩阵问题的能力。

    自己编的矩阵类,很多矩阵运算,有点拙

    4. **矩阵运算**:除了基本的算术运算外,矩阵类可能还包括转置、逆矩阵、行列式、特征值、特征向量等高级运算。这些运算需要相应的线性代数知识来实现。 5. **效率优化**:在处理大矩阵时,效率是至关重要的。例如...

    基于ARM优化数学库arm_math实现的矩阵运算和机器人学工具库,可用于实现机械臂控制及后续功能开发.zip

    我们深入探讨了深度学习的基本原理、神经网络的应用、自然语言处理、语言模型、文本分类、信息检索等领域。更有深度学习、机器学习、自然语言处理和计算机视觉的实战项目源码,助您从理论走向实践,如果您已有一定...

    《高等应用数学问题的MATLAB求解-第二版》PPT+源程序

    MATLAB是一种广泛使用的交互式计算环境,特别适合于处理矩阵和数组运算。在高等应用数学中,MATLAB可以帮助我们求解各种难题,例如微积分、线性代数、偏微分方程、统计分析、优化问题等。薛定宇教授的书深入浅出地...

    基于C#矩阵运算,字符串和矩阵相互转换类

    本项目"基于C#矩阵运算,字符串和矩阵相互转换类"提供了一个高效且实用的工具集,旨在简化这些复杂的数学操作,并且实现了弧度与度之间的转换,这对于处理几何、物理或工程问题非常有用。下面将详细介绍其中的关键...

    abb.rar.rar_矩阵运算

    在IT领域,矩阵运算是一种基础且重要的数学工具,广泛应用于计算机图形学、机器学习、数据科学等多个领域。本文将深入探讨“矩阵运算”的概念、重要性以及如何进行矩阵的简化处理,即删除矩阵中的相同数并以标准形式...

    Matlab系列--学习数学实验与MATLAB中创建的代码.zip

    MATLAB,全称“Matrix Laboratory”,是工程、科学和经济领域广泛应用的计算环境,尤其适合于线性代数、矩阵运算、信号处理以及图像分析等任务。 一、MATLAB基础 MATLAB的基础在于其矩阵和数组的概念。在MATLAB中...

    Matlab系列--数学建模Matlab的学习.zip

    在本压缩包“Matlab系列--数学建模Matlab的学习.zip”中,主要涉及的是使用MATLAB进行数学建模的相关教程。MATLAB是一款强大的数学计算软件,广泛应用于工程计算、数据分析、图像处理、科学计算等领域,尤其在数学...

    MATLAB程序设计教程:第2章 MATLAB矩阵及其运算.ppt

    第2章主要讲解了MATLAB中的矩阵操作和相关数据处理,包括变量与数据操作、矩阵的建立、运算以及矩阵的特殊形式。 2.1 变量和数据操作 MATLAB允许用户创建具有字母、数字或下划线组成的最多63个字符的变量名,且区分...

    matlab课件(数学实验)

    这个"matlab课件(数学实验)"的压缩包提供了一系列的文档和幻灯片,适合初学者了解和学习MATLAB的基本概念和操作。下面将详细阐述这些文件中涉及的MATLAB知识点。 1. **实验1 Matlab初步.doc**: - MATLAB界面...

    矩阵运算基础PPT学习教案.pptx

    【矩阵运算基础】\n\n矩阵是数学和计算机科学中重要的数据结构,尤其在线性代数、图像处理和机器学习等领域中起着核心作用。矩阵由若干行和列组成的数组,可以用来表示向量、变换、系统方程等多个概念。\n\n1. **...

    VHDL数学运算库1.0.zip_vhdl 数学_vhdl 数学库_vhdl 设计 _数学运算

    描述中提到“这是一个VHDL写的数学运算的硬件设计库,还算比较完整”,这暗示了该库可能包含了各种基本和高级的数学运算模块,例如加法、减法、乘法、除法,以及可能的矩阵运算、傅立叶变换等。一个完整的库通常会...

    matlab矩阵及其运算

    矩阵的加、减、乘运算符分别为`+`、`-`和`*`,使用方法与普通数字运算相似,但需遵循矩阵运算的数学规则,如加减运算只适用于同型矩阵。 MATLAB中的矩阵除法有两种形式:左除`\`和右除`/`。右除是先计算矩阵的逆再...

    Mathcad数学运算向量和矩阵解读PPT教案学习.pptx

    Mathcad是一款强大的数学软件,它在处理向量和矩阵运算方面表现出色,特别适合于线性代数和工程计算。本教程主要介绍如何在Mathcad中创建和操作向量和矩阵。 1. 向量与矩阵的概念: 在Mathcad中,单个变量被视为...

    实验二 MATLAB的矩阵运算.pdf

    MATLAB是一款强大的数学计算软件,尤其在矩阵运算方面具有显著的优势。本实验旨在让学生了解MATLAB的基本计算功能,并熟练掌握矩阵的创建与基本运算。 一、MATLAB的基本计算功能 MATLAB提供了丰富的数学运算功能,...

    matlab-GUI矩阵计算器.pdf

    在GUI计算器中,可以通过编程实现错误的捕获和处理,以防止程序崩溃或产生不可预期的结果。 ### 知识点四:控件交互和回调函数 Matlab GUI中的控件与用户行为(如点击按钮、输入文本等)紧密相关。每个控件都有一...

Global site tag (gtag.js) - Google Analytics