從奇異值分解(SVD)看潛在語(yǔ)義索引(LSI)

1. SVD 簡(jiǎn)介

SVD中文稱為“奇異值分解”，是一種矩陣分解方法。其公式如下：

定理：設(shè)A為m*n階復(fù)矩陣，則存在m階矩陣U和n階矩陣V，使得：

　　    A = U*S*V’　　   其中S=diag(σi,σ2,……,σr)，σi>0 (i=1,…,r)，r=rank(A)。

其中 A 矩陣是我們初始的特征矩陣，在文本挖掘中：A就是 t (term) 行 d (document) 列的矩陣，每列是一篇文章，每行是一個(gè)單詞，每個(gè)單元格的當(dāng)前單詞在當(dāng)前文章里的出現(xiàn)次數(shù)。 U 是一個(gè) t 行 r 列 的矩陣， V 是一個(gè) r 行 d 列 的矩陣， S 是一個(gè) r 行 r 列的對(duì)角矩陣。這里 r 的大小是 A的秩。那么U和V中分別是A的奇異向量，而S是A的奇異值。AA'的正交單位特征向量組成U，特征值組成S'S，A'A的正交單位特征向量組成V，特征值（與AA'相同）組成SS'。( 關(guān)于秩是什么，特征值是什么，這個(gè)分解是怎么得到的，可以暫不去管）

注意，這個(gè)公式是等號(hào)，也就是等號(hào)左邊完全等價(jià)于等號(hào)右邊。換句話說(shuō)我們只是把原來(lái)的A換了一種表示形式而已，并沒(méi)有丟失任何信息。就好像 24 = 2 * 3 * 4 一樣。 也正是因此，如果 LSI 直接使用 SVD 的話，不僅 r 是不可控的，而且 r 很可能很大以至于起不到降維效果，事實(shí)上這樣做不僅沒(méi)降維而且耗費(fèi)了大量的運(yùn)算時(shí)間。而 SVD 作為一種矩陣分解方法，也并非僅僅用在 LSI 中。Matlab中有直接的svd函數(shù)可以使用：[U,S,V] = svd(A) 

2. LSI 對(duì) SVD 的使用

LSI 對(duì) SVD 做了一點(diǎn)改變，就是對(duì) S 的 r 個(gè)對(duì)角線元素進(jìn)行了排序，并只保留前 k 個(gè)值 ( k < r )， 后 r - k 個(gè)置零。此時(shí)，可以證明等式右邊是在最小二乘意義下對(duì)等式左邊的最佳近似。事實(shí)上這個(gè)過(guò)程是把數(shù)據(jù)集的特征值（在SVD中用奇異值表征）按照重要性排列，降維的過(guò)程就是舍棄不重要的特征向量的過(guò)程，而剩下的特征向量張成空間為降維后的空間。

看到這里，我們能得到最重要的啟發(fā)就是，LSI 是通過(guò)舍棄不重要的特征向量來(lái)達(dá)到降維效果的，而又由于特征向量是根據(jù)矩陣運(yùn)算得出的，因此 LSI 在降維的過(guò)程中不僅丟失了信息，而且還改變了信息。降維后的數(shù)據(jù)集僅僅是對(duì)原數(shù)據(jù)集的一種近似而非等價(jià)形式。且降維幅度越大，與原信息的偏離就越大。

3. LSI 的適用性

1） 特征降維

LSI 本質(zhì)上是把每個(gè)特征映射到了一個(gè)更低維的子空間（sub space)，所以用來(lái)做降維可以說(shuō)是天造地設(shè)。在降維這塊土地上還有另一位辛勤的耕耘者那就是TFIDF，TFIDF通過(guò)一個(gè)簡(jiǎn)單的公式（兩個(gè)整數(shù)相乘）得到不同單詞的重要程度，并取前k個(gè)最重要的單詞，而丟棄其它單詞，這里只有信息的丟失，并沒(méi)有信息的改變。從執(zhí)行效率上 TFIDF 遠(yuǎn)遠(yuǎn)高于 LSI，不過(guò)從效果上（至少在學(xué)術(shù)界）LSI 要優(yōu)于TFIDF。

不過(guò)必須提醒的是，無(wú)論是上述哪一種降維方法，都會(huì)造成信息的偏差，進(jìn)而影響后續(xù)分類/聚類的準(zhǔn)確率。 降維是希望以可接受的效果損失下，大大提高運(yùn)行效率和節(jié)省內(nèi)存空間。然而能不降維的時(shí)候還是不要降維（比如你只有幾千篇文檔要處理，那樣真的沒(méi)有必要降維）

2）單詞相關(guān)度計(jì)算

LSI 的結(jié)果通過(guò)簡(jiǎn)單變換就能得到不同單詞之間的相關(guān)度( 0 ~ 1 之間的一個(gè)實(shí)數(shù)），相關(guān)度非常高的單詞往往擁有相同的含義。不過(guò)不要被“潛在語(yǔ)義”的名稱所迷惑，所謂的潛在語(yǔ)義只不過(guò)是統(tǒng)計(jì)意義上的相似，如果想得到同義詞還是使用同義詞詞典靠譜。LSI 得到的近義詞的特點(diǎn)是它們不一定是同義詞（甚至詞性都可能不同），但它們往往出現(xiàn)在同類情景下（比如“魔獸” 和 “dota”)。不過(guò)事實(shí)上直接使用LSI做單詞相關(guān)度計(jì)算的并不多，一方面在于現(xiàn)在有一些灰常好用的同義詞詞典，另外相對(duì)無(wú)監(jiān)督的學(xué)習(xí)大家還是更信任有監(jiān)督的學(xué)習(xí)（分類）得到的結(jié)果。

3）聚類

直接用 LSI 聚類的情景我還沒(méi)有見(jiàn)過(guò)，但使用該系列算法的后續(xù)變種 PLSI, LDA 進(jìn)行聚類的的確有一些。其中LDA聚類還有些道理（因?yàn)樗旧砭图僭O(shè)了潛在topic的聯(lián)合概率分布），用 LSI 進(jìn)行聚類其實(shí)并不合適。本質(zhì)上 LSI 在找特征子空間，而聚類方法要找的是實(shí)例分組。 LSI 雖然能得到看起來(lái)貌似是聚類的結(jié)果，但其意義不見(jiàn)得是聚類所想得到的。一個(gè)明顯的例子就是，對(duì)于分布不平均的樣本集（比如新聞?lì)惖奈恼掠?000篇，而文學(xué)類的文章只有10篇）， LSI/PLSI 得到的往往是相對(duì)平均的結(jié)果(A類500篇，B類600篇)，這種情況下根本無(wú)法得到好的聚類結(jié)果。相對(duì)傳統(tǒng)聚類方法k-means， LSI 系列算法不僅存在信息的偏差（丟失和改變），而且不能處理分布不均的樣本集。

對(duì)于 LSI/PLSI 來(lái)說(shuō)，聚類的意義不在于文檔，而在于單詞。所以對(duì)于聚類的一種變型用法是，當(dāng) k 設(shè)的足夠大時(shí)，LSI/PLSI 能夠給出落在不同子空間的單詞序列，基本上這些單詞之間擁有較為緊密的語(yǔ)義聯(lián)系。其實(shí)這種用法本質(zhì)上還是在利用降維做單詞相關(guān)度計(jì)算。