SVD 於資訊檢索與文本搜尋的應用

Posted on 11/04/2009 by

本文的閱讀等級：高級

線性代數學習者或多或少可能曾經感到一種莫名的疑惑：針對一個特定主題，既使我們明白符號的定義，也瞭解如何執行計算程序，但卻苦於不能清楚掌握該主題的深層涵義。我相信最有效的解惑處方是選擇適當的應用來釋疑，一方面藉由附著於實例的情境闡述符號所代表的概念，另一方面透過回答一連串的問題引導我們理解計算程序背後的故事。本文就以奇異值分解為例，借用它在資訊檢索與文本搜尋的應用來說明矩陣的奇異值分解的功能與意義。繼續閱讀之前，請讀者先參考背景文章“奇異值分解 (SVD)”。

 
隱含語義索引 (latent semantic indexing)，簡稱 LSI，是潛在語義學應用於資訊檢索的一項技術，目的是探討隱藏在字詞背後的某種關係，這種關係並非以詞典中的定義為基礎，而是參考字詞的使用環境。LSI 的運作理論建基於奇異值分解，也就是以向量空間為分析模型，利用基底來呈現語料庫中不同字詞以及文件之間的關係。

 
LSI 以字詞—文件矩陣 (term-document matrix) 表示字詞與文件之間的關聯，習慣以列 (row) 代表字詞 (term)，以行 (column) 代表文件 (document)。考慮一給定的語料庫，字詞記為 t_i，i=1,\ldots,m，文件記為 d_j，j=1,\ldots,n。設 A=[a_{ij}] 為 m\times n 階字詞—文件矩陣，a_{ij} 代表字詞 t_i 與文件 d_j 的相關權重值。第一個問題是如何從給定的 n 個文件以及選定的 m 個字詞得到字詞—文件矩陣 A？

 
TF-IDF (term frequency-inverse document frequency) 是一種常用於資訊檢索的權重計算方法。詞頻 (term frequency，TF) 代表局部權重，即某字詞在一份特定文件的重要性，逆向文件頻率 (inverse document frequency，IDF) 代表全域權重，即某字詞在整個語料庫中的普遍重要性。對於給定文件 d_j，TF 是字詞 t_i 在該文件中出現的次數，以 n_{ij} 表示。為排除文件長度的影響，我們將 TF 正規化：

\displaystyle tf_{ij}=\frac{n_{ij}}{\sum_{k=1}^m n_{kj}}

上式中分母是文件 d_j 中所有字詞出現的次數總和。

 
一般來說，字詞的普遍重要性隨著它在語料庫中出現的頻率成反比；例如，字詞「我」的普遍重要性遠比「甜點」要低。針對字詞 t_i，IDF 定義為總文件數 (n) 和包含字詞 t_i 的文件數目 (記為 df_i) 比值的對數值，如下：

\displaystyle idf_{i}=\log_{2}\frac{n}{df_{i}}+1

上式中加入常數 1 的目的是當字詞 t_i 出現於語料庫裡的每一份文件時，亦即 n=df_{i}，IDF 仍保有一個基本量。TF-IDF 定義為 TF 和 IDF 的乘積：

tfidf_{ij}=tf_{ij}\cdot idf_i

TF-IDF 的意義是字詞相對一份文件的重要性隨著它在該文件中出現的頻率增加，但隨著它在語料庫中出現的頻率減少。

 
考慮下面這個小型語料庫，稱為「我的語料庫」，它包含選自本網站的 5 份文件：“特殊矩陣 (1)：冪零矩陣”、“特殊矩陣 (2)：正規矩陣”、“特殊矩陣 (3)：么正矩陣（酉矩陣）”、“特殊矩陣 (4)：Householder 矩陣”和“特殊矩陣 (5)：冪等矩陣”。我們挑選的 10 個字詞依序是：「秩」、「行列式」、「行空間」、「正交」、「特徵值」、「對稱」、「對角化」、「投影」、「相似」和「正定」。表一整理了「我的語料庫」裡每個字詞於各文件中出現的次數 (n_{ij})，每份文件的字詞總數 (\sum_k n_{kj})，以及包含某字詞的文件數目 (df_i)。字詞「正定」並未出現於任何文件中，我們可以將它由字詞—文件關聯矩陣中刪除。從表一的的統計資料可計算出 TF-IDF，「我的語料庫」的 9\times 5 階字詞—文件關聯矩陣如下：

A=\begin{bmatrix} 0.000 &0.000 &0.000 &0.000 &0.107\\ 0.767 &0.000 &0.000 &0.000 &0.000\\ 0.357 &0.000 &0.000 &0.000 &0.375\\ 0.000 &0.575 &0.661 &0.305 &0.341\\ 0.462 &0.130 &0.214 &0.385 &0.129\\ 0.000 &0.302 &0.000 &0.401 &0.056\\ 0.000 &0.453 &0.496 &0.134 &0.000\\ 0.000 &0.000 &0.000 &0.000 &1.286\\ 0.357 &0.000 &0.000 &0.179 &0.000 \end{bmatrix}

LSI1

表一 文件的字詞頻率表

 
接下來是線性代數的工作，假設 \mathrm{rank}A=r，我們計算字詞—文件矩陣 A 的「瘦」奇異值分解 (SVD)：

A=T\Sigma D^T

其中 m\times r 階矩陣 T 與 r\times n 階矩陣 D^T 分別滿足 T^TT=I_r 和 D^TD=I_r，且 \Sigma=\hbox{diag}(\sigma_1,\ldots,\sigma_r)，主對角元 \sigma_{1}\ge\sigma_{2}\ge\cdots\ge\sigma_{r}>0 為非零奇異值。寫出 T=\begin{bmatrix} \mathbf{t}_1&\cdots&\mathbf{t}_r \end{bmatrix} 和 D=\begin{bmatrix} \mathbf{d}_1&\cdots&\mathbf{d}_r \end{bmatrix}，其中 \mathbf{t}_1,\ldots,\mathbf{t}_r 組成一個單範正交 (orthonormal) 向量集，故可當作字詞空間的基底，\mathbf{d}_1,\ldots,\mathbf{d}_r 也組成一個單範正交集，可作為文件空間的基底。奇異值分解也可以用 r 個秩-1 (rank-one) 矩陣之和的形式表示：

A=\sigma_1\mathbf{t}_1\mathbf{d}_1^T+\sigma_2\mathbf{t}_2\mathbf{d}_2^T+\cdots+\sigma_r\mathbf{t}_r\mathbf{d}_r^T

奇異值 \sigma_1,\ldots,\sigma_r 反映了字詞—文件矩陣 A 裡隱藏的 r 個獨立的概念強度。對應第 j 個概念，\mathbf{t}_j 代表構成此概念的 m 個字詞權重，\mathbf{d}_j 代表 n 個文件包含此概念的權重，而 \mathbf{t}_j\mathbf{d}_j^T 則表示此概念的字詞—文件關聯矩陣。因此，T 稱為字詞—概念矩陣，D 稱為概念—文件矩陣。

 
利用本網站提供的友好連結 Online Matrix Calculator 計算上述「我的語料庫」的字詞—文件矩陣 A 的奇異值分解，結果如下 (m=9，n=r=5)：

T=\begin{bmatrix} -0.058 &-0.053& 0.008& -0.003& 0.001\\ -0.116 & 0.127& -0.712& 0.305& 0.402\\ -0.258 &-0.127& -0.303& 0.133& 0.190\\ -0.512& 0.459& 0.309& 0.196& -0.095\\ -0.282& 0.281& -0.355& -0.295& -0.640\\ -0.163& 0.226& 0.059& -0.782& 0.548\\ -0.234& 0.451& 0.222& 0.334& 0.224\\ -0.698& -0.638& 0.100& -0.030& 0.010\\ -0.084& 0.115& -0.341& -0.198& -0.185 \end{bmatrix}

\Sigma=\begin{bmatrix} 1.499& 0.000& 0.000& 0.000& 0.000\\ 0.000& 1.160& 0.000& 0.000& 0.000\\ 0.000& 0.000& 1.006& 0.000& 0.000\\ 0.000& 0.000& 0.000& 0.433& 0.000\\ 0.000& 0.000& 0.000& 0.000& 0.168 \end{bmatrix}

D^T=\begin{bmatrix} -0.228& -0.324& -0.343& -0.251& -0.814\\ 0.192& 0.494& 0.507& 0.362& -0.576\\ -0.935& 0.248& 0.237& -0.050& 0.078\\ 0.172& -0.024& 0.536& -0.826& -0.010\\ 0.088& 0.767& -0.531& -0.349& 0.001 \end{bmatrix}

 
得到了字詞—文件矩陣的 SVD 後，LSI 採用降低維度的近似作法，僅保留前面數值較大的 k (k<r) 個奇異值，原矩陣 A 因此近似於

A\approx A_k=\sigma_1\mathbf{t}_1\mathbf{d}_1^T+\sigma_2\mathbf{t}_2\mathbf{d}_2^T+\cdots+\sigma_k\mathbf{t}_k\mathbf{d}_k^T=T_k\Sigma_k D_k^T

上式中 T_k 是 m\times k 階，\Sigma_k 是 k\times k 階，D_k^T 是 k\times n 階。採用低維矩陣近似的作法有兩個主要原因，第一是減少計算量與儲存量，第二是去除雜音。雜音的強度較主要訊息微弱，省略較小的奇異值雖然遺失部分訊息，但遺失的訊息多屬於雜訊，所以用低維近似反而能夠提高資訊檢索的效能。以下為方便說明，「我的語料庫」僅保留 2 個獨立概念 (k=2)，低維矩陣 T_2，\Sigma_2 和 D_2^T 分別是

T_2=\begin{bmatrix} -0.058 &-0.053\\ -0.116 & 0.127\\ -0.258 &-0.127\\ -0.512& 0.459\\ -0.282& 0.281\\ -0.163& 0.226\\ -0.234& 0.451\\ -0.698& -0.638\\ -0.084& 0.115 \end{bmatrix},~\Sigma_2=\begin{bmatrix} 1.499& 0.000\\ 0.000& 1.160 \end{bmatrix}

D_2^T=\begin{bmatrix} -0.228& -0.324& -0.343& -0.251& -0.814\\ 0.192& 0.494& 0.507& 0.362& -0.576 \end{bmatrix}

 
利用字詞—文件矩陣的 SVD 形式可回答與字詞分類、文件分類和資訊檢索密切相關的問題：

  1. 文件的相似度問題：文件 d_i 和 d_j 有多相似？
  2. 字詞的相似度問題：字詞 t_i 和 t_j 有多相似？
  3. 文件查詢問題：給出若干查詢字詞，哪些是最相關聯的文件？

 
透過比對文件所隱含的概念可度量文件之間的相似度。考慮特定文件 d_j，該文件的相關字詞向量近似於 A_k=T_k\Sigma_k D_k^T 的第 j 行，也就是 T_k\Sigma_k 與 D_k^T 的第 j 行乘積；換句話說，以 T_k\Sigma_k 的行向量為基底，文件 d_j 的座標向量就是 D_k^T 的第 j 行。下圖為「我的語料庫」中 5 份文件的座標散布圖 (由 D_2^T 的行向量繪得)。

LSI2

文件座標

 
下一個問題是從文件的座標向量判斷兩份文件之間的相似性。餘弦相似性 (cosine similarity) 是一種常用的方法，文件 d_i 和 d_j 的相似度定義為其座標向量夾角的餘弦，因此兩座標向量的夾角愈小其相似度愈高。計算方式是先將 D_k^T 的每個行向量予以正規化，使各行向量長度為 1，記為 \tilde{D}_k^T。兩文件的餘弦相似性等於 \tilde{D}_k^T 裡兩行向量的內積，「我的語料庫」之文件相似度矩陣 \tilde{D}_k\tilde{D}_k^T 如下：

\begin{matrix} 1.000 & 0.958 & 0.962 & 0.965 & 0.252\\ 0.958 & 1.000 & 1.000 & 1.000 &-0.035\\ 0.962 & 1.000 & 1.000 & 1.000 &-0.021\\ 0.965 & 1.000 & 1.000 & 1.000 &-0.010\\ 0.252 &-0.035 &-0.021 &-0.010 & 1.000 \end{matrix}

檢視文件相似度矩陣並配合座標散布圖，「我的語料庫」裡的文件分為二類：第一類包含文件一、二、三和四，第二類包含文件五。

 
仿照文件相似度的計算程序，字詞之間的相似度也可經由比對字詞所隱含的概念來度量，將 T_k 的列向量予以正規化，記為 \tilde{T}_k，字詞相似度矩陣為 \tilde{T}_k\tilde{T}_k^T，即

\begin{matrix} 1.000 & 0.000 & 0.960 & 0.099 & 0.047& -0.115& -0.259 & 1.000 &-0.109\\ 0.000 & 1.000 & 0.279 & 0.995 & 0.999 & 0.993 & 0.966 & 0.000 & 0.994\\ 0.960 & 0.279 & 1.000 & 0.373 & 0.324 & 0.167 & 0.021 & 0.960 & 0.173\\ 0.099 & 0.995 & 0.373 & 1.000 & 0.999 & 0.977 & 0.935 & 0.099 & 0.978\\ 0.047 & 0.999 & 0.324 & 0.999 & 1.000 & 0.987 & 0.953 & 0.047 & 0.988\\ -0.115 & 0.993 & 0.167 & 0.977 & 0.987 & 1.000 & 0.989 &-0.115 & 1.000\\ -0.259 & 0.966 & 0.021 & 0.935 & 0.953 & 0.989 & 1.000 &-0.259 & 0.988\\ 1.000 & 0.000 & 0.960 & 0.099 & 0.047 &-0.115& -0.259 & 1.000& -0.109\\ -0.109 & 0.994 & 0.173 & 0.978 & 0.988 & 1.000 & 0.988 &-0.109 & 1.000 \end{matrix}

由字詞相似度矩陣推知「我的語料庫」裡的字詞可區分為二類，第一類包含「秩」、「行空間」、「投影」，第二類包含「行列式」、「正交」、「特徵值」、「對稱」、「對角化」、「相似」。

 
最後我們回答資訊檢索問題：給出若干查詢字詞，哪些是最相關聯的文件？方法很簡單，我們可以將查詢字詞集合視為一份虛擬文件，將此虛擬文件的座標向量求出，再以類似文件之間相似度的比對方式即可找出符合的文件。例如，假定輸入查詢關鍵字詞「對稱」、「正交」和「對角化」，此虛擬文件的查詢字詞向量為

\mathbf{q}=\begin{bmatrix} 0&0&0&1&0&1&1&0&0 \end{bmatrix}^T

令查詢虛擬文件參考新基底 (即 T_k\Sigma_k 的行向量集合) 的座標向量為 [\mathbf{q}]，就有

\mathbf{q}=T_k\Sigma_k[\mathbf{q}]

因為 \Sigma_k 是可逆的，等號兩端左乘 \Sigma_k^{-1}T_k^T 就得到

[\mathbf{q}]=\Sigma_k^{-1}T_k^T\mathbf{q}

代入數值計算出

[\mathbf{q}]=\begin{bmatrix} -0.607\\ 0.081 \end{bmatrix}

下圖為查詢虛擬文件與 5 份文件的座標散布圖，查詢虛擬文件與語料庫中 5 份文件的餘弦相似性依序為

(0.843,~0.654,~0.665,~0.673,~0.733)

結果顯示在「我的語料庫」中，“特殊矩陣 (1)：冪零矩陣”最符合給定的查詢意圖。

LSI3

虛擬文件與查詢文件座標

 
本文的目的是通過 SVD 在 LSI 的應用認識如何解讀矩陣的奇異值分解，並非強調 LSI 在資訊檢索與文本搜尋的效能，有興趣進一步瞭解 LSI 效能和限制的讀者，請參見維基百科 http://en.wikipedia.org/wiki/Latent_semantic_indexing ，關於 TF-IDF 的介紹，請見 http://en.wikipedia.org/wiki/Tf%E2%80%93idf。此外，對於查詢網頁排名有興趣的讀者，建議閱讀“Google 搜尋引擎使用的矩陣運算”。

 
後記：
交大電機系的兩位同仁──林源倍教授和楊谷洋教授──不約而同地懷疑我撰寫「無關線代」雜文的興趣遠大於那些繞著線性代數打轉的「主題專欄」。為澄清誤會，我決心投入一整個工作天完成這篇介紹 SVD 實務應用的專文，藉此表明我對線性代數理論與應用始終如一未曾改變的熱愛。

廣告
本篇發表於 線性代數專欄, 應用之道 並標籤為 , , , , , , 。將永久鏈結加入書籤。

16 Responses to SVD 於資訊檢索與文本搜尋的應用

  1. 蔡金剛 說道：
    03/12/2012 at 9:12 下午

    T稱為字詞—概念矩陣
    D稱為概念—文件矩陣

    請問老師 如何知道T是字詞概念矩陣 D是文件矩陣

    回應
    • ccjou 說道：
      03/12/2012 at 10:32 下午

      A是9×5矩陣，由9個字詞在5份文件的詞頻構成，A的行空間C(A)屬於R^9，列空間C(A^T)屬於 R^5。A的SVD：A=T\Sigma D^T告訴我們以下訊息：

      rank(A)=非零奇異值數目，它代表獨立的概念數，奇異值\sigma_i則代表每個概念的強度。

      T的行向量(t1,t2,…,t5)是行空間C(A)基底，行向量t_i告訴我們第i個概念對應哪些字詞分配，譬如說t1中數值較大的元是0.512和0.698即知第一個概念包含最主要的字詞是「正交」和「投影」，所以我們稱T是字詞-概念矩陣。

      同理D的行向量(d1,…,d5)是列空間C(A^T)基底，故D是文件-概念矩陣(或者說D^T是概念-文件矩陣)。

      回應
      • 李昀叡 說道：
        01/20/2016 at 8:36 下午

        教授你好
        我不懂T的行向量(t1,t2,…,t5)是行空間C(A)基底
        和行向量t_i告訴我們第i個概念對應哪些字詞分配
        中間的關聯性要怎麼看？

        回應
        • ccjou 說道：
          01/21/2016 at 8:26 上午

          我不確定這是不是你要的答案：t1是組成第1個概念的字詞成分，數值(絕對值)越大則該字詞所佔的權重越大。假設一個向量表示長方體的(有號)長寬高，譬如 (0.987, 0.012, -0.893)，這是甚麼樣子的長方體？

          回應
  2. Daniel Tsai 說道：
    07/10/2013 at 11:01 下午

    周老師您好，本文範例中字詞－文字矩陣輸入文中所提供的online matrix calculator
    實際運算出來的T矩陣如下：
    0.058 0.053 -0.008 -0.003 0.001
    0.117 -0.127 0.712 0.306 0.402
    0.258 0.127 0.303 0.133 0.190
    0.512 -0.459 -0.309 0.197 -0.095
    0.282 -0.282 0.356 -0.295 -0.640
    0.163 -0.226 -0.059 -0.782 0.548
    0.234 -0.451 -0.222 0.333 0.222
    0.698 0.638 -0.100 -0.031 0.010
    0.084 -0.115 0.340 -0.199 -0.185
    跟本文產生出來的結果不同，例如第T[1,1]，本文產生的結果是，-0.058但是online calculator產生的結果是0.058
    以下是我用Sparse Matrix計算出來的結果
    0.058 0.053 0.008 0.003 0.001
    0.117 -0.127 -0.712 -0.306 0.402
    0.258 0.127 -0.303 -0.133 0.190
    0.512 -0.459 0.309 -0.197 -0.095
    0.282 -0.282 -0.356 0.295 -0.640
    0.163 -0.226 0.059 0.782 0.548
    0.234 -0.451 0.222 -0.333 0.222
    0.698 0.638 0.100 0.031 0.010
    0.084 -0.115 -0.340 0.199 -0.185
    T[1,4]文中產生的結果是-0.003 online matrix calculator -0.003我的結果是0.003
    我很好奇的是，數字都一樣，但是結果有些會正負號相反，想請問老師，這是因為SVD有不同的解，還是有其中有一個是計算錯誤？
    哪一個是正確的？

    回應
    • Daniel Tsai 說道：
      07/11/2013 at 12:00 上午

      我仔細看了一下老師的文章，原來是沒有唯一解的原因。抱歉，在沒有看清老師提供的文章前，就先問問題。

      回應
  3. moonape1226 說道：
    05/09/2014 at 5:19 下午

    老師想請問您，
    這邊的文件作標的橫軸與縱軸，
    是不是就是這些文件最強的兩項特徵了呢？

    回應
  4. 謝旻樺 說道：
    05/15/2014 at 11:11 上午

    BRAVO！
    原來奇異值分解可以這樣應用，大開眼界了！

    回應
  5. Hategold 說道：
    05/07/2015 at 9:33 下午

    想請問D^T是"概念—文件"矩陣
    其根據SVD分解，是按照eigenvalue大小由左至右排出的原矩陣特徵向量建構而成
    這樣的順序跟原本term i 及term j的對應順序會一樣嗎?
    為什麼呢?

    如果順序一樣那我不太懂按照奇異值進行的排序為何不會影響原本term在矩陣上的順序
    可是如果順序不一樣，那該怎麼找到對應的位置去計算term相似度呢?

    還是我的理解有錯誤..
    對於SVD實在不太理解

    回應
    • ccjou 說道：
      05/08/2015 at 7:04 上午

      T 是字詞(term)-概念矩陣，\Sigma 是概念矩陣，D^T 是文件(document)-概念矩陣。因為 A=T\Sigma D^T，A 的字詞(列)順序對應 T 的字詞順序，A 的文件(行)順序對應 D^T 的文件順序。

      回應
  6. 胡哲維 說道：
    08/21/2016 at 4:39 下午

    老師你好:
    請問這篇內容如果用主成分分析或因素分析加以詮釋的話應該是如何呢?

    回應
  7. yhvh 說道：
    04/18/2018 at 12:04 下午

    老師您好，對於最後面虛擬文件的座標的問題，我實際計算了一下，但出現的結果有些差異。如下：

    q = T Sig [q], [q] = Sig^-1 * T^T * q
    Sig^-1 * T^T =
    -0.039 -0.078 -0.172 -0.341 -0.188 -0.109 -0.156 -0.466 -0.056
    -0.046 0.110 -0.109 0.396 0.243 0.195 0.389 -0.550 0.099
    q = [0; 0; 0; 1; 0; 1; 1; 0; 0]
    T * Sig * q =
    -0.606
    0.980

    由於計算器提供了solveLinearEquation的方法，用 AX=B 的方法求 [q], T * Sig [q] = q,
    T * Sig = A =
    -0.087 -0.062
    -0.175 0.148
    -0.387 -0.147
    -0.767 0.533
    -0.422 0.327
    -0.244 0.262
    -0.351 0.523
    -1.047 -0.740
    -0.126 0.134
    B = q = [0; 0; 0; 1; 0; 1; 1; 0; 0]
    X =
    -0.606
    0.979

    這兩個結果幾乎差不多，應該是小數點的問題，但該解與文章上述的不同，不知道是哪裡算錯了？
    我用的計算器也是本文中付的連結 Online Matrix Calculator

    請指教 m(_ _)m

    回應

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入：

Gravatar
WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 ( 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 ( 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 ( 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 ( 登出 /  變更 )

w
取消

連結到 %s