中国的博客，走近我们的产品、技术和文化
Google 中国的博客，走近我们的产品、技术和文化
数学之美 系列十八 － 矩阵运算和文本处理中的分类问题
2007年1月1日
发表者：Google 研究员，吴军
我在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在数值分析中又学了很多矩阵的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究，我才发现数学家们提出那些矩阵的概念和算法，是有实际应用的意义的。
在自然语言处理中，最常见的两类的分类问题分别是，将文本按主题归类（比如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的
方法
。
分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们垂直或者说正交时，新闻则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特别长。通常，我们要处理的文章的数量都很大，至少在百万篇以上，二次回标有非常长，比如说有五十万个词（包括人名地名产品名称等等）。如果想通过对一百万篇文章两篇两篇地成对比较，来找出所有共同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章的分类还要反复重复上述计算。
在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（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 中国对世界的一个贡献。
標籤
编程之夏，UR
创新
创意改善社会 公益温暖中国
促进智能能源利用
大学
谷歌翻译，即时相机翻译，Instant Camera Translation
谷歌十周年系列
谷歌艺术与文化
观妙中国，Shadow Art，智玩皮影
广告
广告安全
互联网，Internet
科技
女性开发者
社会
视频广告
数据中心
数字营销
搜索
网站管理员
文化研究所
艺术计划
音乐搜索
愚人节
增强型广告系列
智能隐形眼镜项目
中小企业
adexchange
Admob
admob sdk
Ads
Adsense
AdWords
android
android m
Android应用开发中国大学生挑战赛
App Inventor
Calendar
cardboard
CES
Chrome
Chrome Web Store
Chrome，Chrome实验
Chrome实验
CI
Code Jam
corporate
Creative
Cross-device
Cultural Institute
culture
Data Center
DevArt
Developer
display
diversity
Doodle
DoubleClick
G+
G2G，Culture
GA&C
gaming
Global Impact Awards
Gmail
Gogle科学挑战赛
Good to Know
Google Ads
Google AdWords
Google Analytics
Google Art Project
Google Arts & Culture
Google Code-in竞赛
Google Demo Day Asia
Google Docs
Google Doodle
Google Drive
Google Drive 云端硬盘
Google Fiber
Google Font
Google for Startups
Google Green
Google I/O
Google Image Search
Google Keep
Google partners
Google Play
Google Science Fair
Google Search
Google Top Contributor Summit
Google Translate
Google Trend
Google Trends
Google Zeitgeist 2012
Google安全系统
Google博士生奖研金
Google翻译
Google奖学金
Google杰出贡献者峰会
Google科学挑战赛
Google网站管理员
Google网站管理员，Webmaster
Google文化研究所
Google在线营销挑战赛
Google中国教育高峰会
IME 输入法
Innovation
Made with Code
maps
mobile ads
mobile ads sdk
Modoo
moonshot
native ads
Nexus
programmatic buying
Project X
Pwn20wn及Pwnium3 黑客大赛
Remarketing. Ads
Search
Security
smb
Solve for X
Street view
student
UR
VR
Web Platform Docs
web security
Webmaster
year in search 2014
YouTube
zeitgeist
博客归档
2024
11月
10月
8月
7月
6月
5月
4月
3月
2月
1月
2023
12月
11月
10月
9月
5月
4月
3月
2月
2022
11月
10月
5月
4月
2月
1月
2021
10月
9月
5月
4月
3月
2月
2020
12月
5月
4月
3月
2019
10月
8月
7月
6月
5月
4月
3月
2018
12月
10月
9月
8月
7月
6月
5月
3月
2月
1月
2017
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2016
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2015
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2014
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2013
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2012
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2011
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2010
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2009
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2008
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2007
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2006
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
Feed
