發(fā)表者：Google 研究員，吳軍

我在大學(xué)學(xué)習(xí)線性代數(shù)時(shí)，實(shí)在想不出它除了告訴我們?nèi)绾谓饩€性方程外，還能有什么別的用途。關(guān)于矩陣的許多概念，比如特征值等等，更是脫離日常生活。后來在數(shù)值分析中又學(xué)了很多矩陣的近似算法，還是看不到可以應(yīng)用的地方。當(dāng)時(shí)選這些課，完全是為了混學(xué)分的學(xué)位。我想，很多同學(xué)都多多少少有過類似的經(jīng)歷。直到后來長(zhǎng)期做自然語言處理的研究，我才發(fā)現(xiàn)數(shù)學(xué)家們提出那些矩陣的概念和算法，是有實(shí)際應(yīng)用的意義的。

在自然語言處理中，最常見的兩類的分類問題分別是，將文本按主題歸類（比如將所有介紹亞運(yùn)會(huì)的新聞歸到體育類）和將詞匯表中的字詞按意思?xì)w類（比如將各種體育運(yùn)動(dòng)的名稱個(gè)歸成一類）。這兩種分類問題都可用通過矩陣運(yùn)算來圓滿地、同時(shí)解決。為了說明如何用矩陣這個(gè)工具類解決這兩個(gè)問題的，讓我們先來來回顧一下我們?cè)谟嘞叶ɡ砗托侣劮诸愔薪榻B的方法。

分類的關(guān)鍵是計(jì)算相關(guān)性。我們首先對(duì)兩個(gè)文本計(jì)算出它們的內(nèi)容詞，或者說實(shí)詞的向量，然后求這兩個(gè)向量的夾角。當(dāng)這兩個(gè)向量夾角為零時(shí)，新聞就相關(guān)；當(dāng)它們垂直或者說正交時(shí)，新聞則無關(guān)。當(dāng)然，夾角的余弦等同于向量的內(nèi)積。從理論上講，這種算法非常好。但是計(jì)算時(shí)間特別長(zhǎng)。通常，我們要處理的文章的數(shù)量都很大，至少在百萬篇以上，二次回標(biāo)有非常長(zhǎng)，比如說有五十萬個(gè)詞（包括人名地名產(chǎn)品名稱等等）。如果想通過對(duì)一百萬篇文章兩篇兩篇地成對(duì)比較，來找出所有共同主題的文章，就要比較五千億對(duì)文章。現(xiàn)在的計(jì)算機(jī)一秒鐘最多可以比較一千對(duì)文章，完成這一百萬篇文章相關(guān)性比較就需要十五年時(shí)間。注意，要真正完成文章的分類還要反復(fù)重復(fù)上述計(jì)算。

在文本分類中，另一種辦法是利用矩陣運(yùn)算中的奇異值分解（Singular Value Decomposition，簡(jiǎn)稱 SVD)。現(xiàn)在讓我們來看看奇異值分解是怎么回事。首先，我們可以用一個(gè)大矩陣A來描述這一百萬篇文章和五十萬詞的關(guān)聯(lián)性。這個(gè)矩陣中，每一行對(duì)應(yīng)一篇文章，每一列對(duì)應(yīng)一個(gè)詞。

在上面的圖中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 個(gè)詞在第 i 篇文章中出現(xiàn)的加權(quán)詞頻（比如，TF/IDF)。讀者可能已經(jīng)注意到了，這個(gè)矩陣非常大，有一百萬乘以五十萬，即五千億個(gè)元素。

奇異值分解就是把上面這樣一個(gè)大矩陣，分解成三個(gè)小矩陣相乘，如下圖所示。比如把上面的例子中的矩陣分解成一個(gè)一百萬乘以一百的矩陣X，一個(gè)一百乘以一百的矩陣B，和一個(gè)一百乘以五十萬的矩陣Y。這三個(gè)矩陣的元素總數(shù)加起來也不過1.5億，僅僅是原來的三千分之一。相應(yīng)的存儲(chǔ)量和計(jì)算量都會(huì)小三個(gè)數(shù)量級(jí)以上。

三個(gè)矩陣有非常清楚的物理含義。第一個(gè)矩陣X中的每一行表示意思相關(guān)的一類詞，其中的每個(gè)非零元素表示這類詞中每個(gè)詞的重要性（或者說相關(guān)性），數(shù)值越大越相關(guān)。最后一個(gè)矩陣Y中的每一列表示同一主題一類文章，其中每個(gè)元素表示這類文章中每篇文章的相關(guān)性。中間的矩陣則表示類詞和文章雷之間的相關(guān)性。因此，我們只要對(duì)關(guān)聯(lián)矩陣A進(jìn)行一次奇異值分解，w 我們就可以同時(shí)完成了近義詞分類和文章的分類。（同時(shí)得到每類文章和每類詞的相關(guān)性）。

現(xiàn)在剩下的唯一問題，就是如何用計(jì)算機(jī)進(jìn)行奇異值分解。這時(shí)，線性代數(shù)中的許多概念，比如矩陣的特征值等等，以及數(shù)值分析的各種算法就統(tǒng)統(tǒng)用上了。在很長(zhǎng)時(shí)間內(nèi)，奇異值分解都無法并行處理。（雖然 Google 早就有了MapReduce 等并行計(jì)算的工具，但是由于奇異值分解很難拆成不相關(guān)子運(yùn)算，即使在 Google 內(nèi)部以前也無法利用并行計(jì)算的優(yōu)勢(shì)來分解矩陣。）最近，Google 中國(guó)的張智威博士和幾個(gè)中國(guó)的工程師及實(shí)習(xí)生已經(jīng)實(shí)現(xiàn)了奇異值分解的并行算法，我認(rèn)為這是 Google 中國(guó)對(duì)世界的一個(gè)貢獻(xiàn)。