奇異值的應(yīng)用-潛在語(yǔ)義索引

1、潛在語(yǔ)義索引（Latent Semantic Indexing）是一個(gè)嚴(yán)重依賴于SVD的算法，本文轉(zhuǎn)載自之前 吳軍老師數(shù)學(xué)之美和參考文獻(xiàn)機(jī)器學(xué)習(xí)中的數(shù)學(xué)匯總。在自然語(yǔ)言處理中，最常見(jiàn)的兩類的分類問(wèn)題分別是，將文本按主題歸類（比如將所有介紹 亞運(yùn)會(huì)的新聞歸到體育類）和將詞匯表中的字詞按意思?xì)w類（比如將各種體育運(yùn)動(dòng)的名稱個(gè) 歸成一類）。這兩種分類問(wèn)題都可用通過(guò)矩陣運(yùn)算來(lái)圓滿地、同時(shí)解決。為了說(shuō)明如何用矩 陣這個(gè)工具類解決這兩個(gè)問(wèn)題的，讓我們先來(lái)來(lái)回顧一下我們?cè)谟嘞叶ɡ砗托侣劮诸愔薪榻B 的方法。分類的關(guān)鍵是計(jì)算相關(guān)性。我們首先對(duì)兩個(gè)文本計(jì)算出它們的內(nèi)容詞，或者說(shuō)實(shí)詞的向量， 然后求這兩個(gè)向量的夾角。

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

3、ecomposition， 簡(jiǎn)稱SVD）。現(xiàn)在讓我們來(lái)看看奇異值分解是怎么回事。首先，我們可以用一個(gè)大矩陣A 來(lái)描述這一百萬(wàn)篇文章和五十萬(wàn)詞的關(guān)聯(lián)性。這個(gè)矩陣中，每一行對(duì)應(yīng)一篇文章，每一列對(duì) 應(yīng)一個(gè)詞。列的元素，是字典中第j個(gè)詞在在上面的圖中，M=l,000,000, N=500,000。第i行，第j列的元素，是字典中第j個(gè)詞在第i篇文章中出現(xiàn)的加權(quán)詞頻（比如，TF/IDF）。讀者可能已經(jīng)注意到了，這個(gè)矩陣非常大,有一百萬(wàn)乘以五十萬(wàn)，即五千億個(gè)元素。奇異值分解就是把上面這樣一個(gè)大矩陣，分解成三個(gè)小矩陣相乘，如下圖所示。比如把上面 的例子中的矩陣分解成一個(gè)一百萬(wàn)乘以一百的矩陣X，一個(gè)一百乘以一百

4、的矩陣B，和一個(gè) 一百乘以五十萬(wàn)的矩陣Y。這三個(gè)矩陣的元素總數(shù)加起來(lái)也不過(guò)1.5億，僅僅是原來(lái)的三千 分之一。相應(yīng)的存儲(chǔ)量和計(jì)算量都會(huì)小三個(gè)數(shù)量級(jí)以上。三個(gè)矩陣有非常清楚的物理含義。第一個(gè)矩陣X中的每一列表示一類主題，其中的每個(gè)非 零元素表示一個(gè)主題與一篇文章的相關(guān)性，數(shù)值越大越相關(guān)。最后一個(gè)矩陣Y中的每一列 表示100個(gè)關(guān)鍵詞，每個(gè)key word與500，000個(gè)詞的相關(guān)性。中間的矩陣則表示文章主題 和keyword之間的相關(guān)性。因此，我們只要對(duì)關(guān)聯(lián)矩陣A進(jìn)行一次奇異值分解，w我們就 可以同時(shí)完成了近義詞分類和文章的分類。（同時(shí)得到每類文章和每類詞的相關(guān)性）。比如降至2維（rank=2），

5、則document-term的關(guān)系可以在下面二維圖中展現(xiàn)：0 60.40,200-027 d-O.e-0,4-0.20,00.2o.d0.6Dimension 2在圖上，每一個(gè)紅色的點(diǎn)，都表示一個(gè)詞，每一個(gè)藍(lán)色的點(diǎn)，都表示一篇文檔，這樣我們可 以對(duì)這些詞和文檔進(jìn)行聚類，比如說(shuō)stock和market可以放在一類，因?yàn)樗麄兝鲜浅霈F(xiàn)在 一起，real和estate可以放在一類，dads，guide這種詞就看起來(lái)有點(diǎn)孤立了，我們就不對(duì)他 們進(jìn)行合并了。按這樣聚類出現(xiàn)的效果，可以提取文檔集合中的近義詞，這樣當(dāng)用戶檢索文 檔的時(shí)候，是用語(yǔ)義級(jí)別（近義詞集合）去檢索了，而不是之前的詞的級(jí)別。這樣一減少我

6、們的檢索、存儲(chǔ)量，因?yàn)檫@樣壓縮的文檔集合和PCA是異曲同工的，二可以提高我們的用 戶體驗(yàn)，用戶輸入一個(gè)詞，我們可以在這個(gè)詞的近義詞的集合中去找，這是傳統(tǒng)的索引無(wú)法 做到的?，F(xiàn)在剩下的唯一問(wèn)題，就是如何用計(jì)算機(jī)進(jìn)行奇異值分解。這時(shí)，線性代數(shù)中的許多概念， 比如矩陣的特征值等等，以及數(shù)值分析的各種算法就統(tǒng)統(tǒng)用上了。在很長(zhǎng)時(shí)間內(nèi)，奇異值分 解都無(wú)法并行處理。（雖然Google早就有了 MapReduce等并行計(jì)算的工具，但是由于奇 異值分解很難拆成不相關(guān)子運(yùn)算，即使在Google內(nèi)部以前也無(wú)法利用并行計(jì)算的優(yōu)勢(shì)來(lái)分 解矩陣。）最近，Google中國(guó)的張智威博士和幾個(gè)中國(guó)的工程師及實(shí)習(xí)生已經(jīng)實(shí)現(xiàn)了奇異 值分解的并行算法，我認(rèn)為這是Google中國(guó)對(duì)世界的一個(gè)貢獻(xiàn)。最后說(shuō)說(shuō)個(gè)人拙見(jiàn)，這里我們可以把document和term （word）中間加上一層latent semantics 項(xiàng)，那么上圖中的X和Y矩陣就可以分別表示同一個(gè)latent semantics對(duì)不同document之間 的相關(guān)性和同一 latent