澄※雨妳的一切

轉載自http://blog.csdn.net/afgh2587849/article/details/6792262

SVD分解是LSA的數學基礎，本文是我的LSA學習筆記的一部分，之所以單獨拿出來，是因為SVD可以說是LSA的基礎，要理解LSA必須瞭解SVD，因此將LSA筆記的SVD一節單獨作為一篇文章。本節討論SVD分解相關數學問題，一個分為3個部分，第一部分討論線性代數中的一些基礎知識，第二部分討論SVD矩陣分解，第三部分討論低階近似。本節討論的矩陣都是實數矩陣。

基礎知識

1. 矩陣的秩：矩陣的秩是矩陣中線性無關的行或列的個數

2. 對角矩陣：對角矩陣是除對角線外所有元素都為零的方陣

3. 單位矩陣：如果對角矩陣中所有對角線上的元素都為零，該矩陣稱為單位矩陣

4. 特徵值：對一個M x M矩陣C和向量X，如果存在λ使得下式成立

則稱λ為矩陣C的特徵值，X稱為矩陣的特徵向量。非零特徵值的個數小於等於矩陣的秩。

5. 特徵值和矩陣的關係：考慮以下矩陣

該矩陣特徵值λ1 = 30,λ2 = 20,λ3 = 1。對應的特徵向量

假設V^T=(2,4,6) 計算S x V^T

有上面計算結果可以看出，矩陣與向量相乘的結果與特徵值，特徵向量有關。觀察三個特徵值λ1 = 30,λ2 = 20,λ3 = 1，λ3值最小，對計算結果的影響也最小，如果忽略λ3，那麼運算結果就相當於從(60,80,6)轉變為(60,80,0)，這兩個向量十分相近。這也表示了數值小的特徵值對矩陣-向量相乘的結果貢獻小，影響小。這也是後面談到的低階近似的數學基礎。

矩陣分解

1. 方陣的分解

1) 設S是M x M方陣，則存在以下矩陣分解

其中U 的列為S的特徵向量，為對角矩陣，其中對角線上的值為S的特徵值，按從大到小排列：

2) 設S是M x M 方陣，並且是對稱矩陣，有M個特徵向量。則存在以下分解

其中Q的列為矩陣S的單位正交特徵向量，仍表示對角矩陣，其中對角線上的值為S的特徵值，按從大到小排列。最後，Q^T=Q^-1，因為正交矩陣的逆等於其轉置。

2. 奇異值分解

上面討論了方陣的分解，但是在LSA中，我們是要對Term-Document矩陣進行分解，很顯然這個矩陣不是方陣。這時需要奇異值分解對Term-Document進行分解。奇異值分解的推理使用到了上面所講的方陣的分解。

假設C是M x N矩陣，U是M x M矩陣，其中U的列為CC^T的正交特徵向量，V為N x N矩陣，其中V的列為C^TC的正交特徵向量，再假設r為C矩陣的秩，則存在奇異值分解：

其中CC^T和C^TC的特徵值相同，為

Σ為M X N，其中，其餘位置數值為0，的值按大小降序排列。以下是Σ的完整數學定義：

σ_i稱為矩陣C的奇異值。

用C乘以其轉置矩陣C^T得：

上式正是在上節中討論過的對稱矩陣的分解。

奇異值分解的圖形表示：

從圖中可以看到Σ雖然為M x N矩陣，但從第N+1行到M行全為零，因此可以表示成N x N矩陣，又由於右式為矩陣相乘，因此U可以表示為M x N矩陣，V^T可以表示為N x N矩陣

3. 低階近似

LSA潛在語義分析中，低階近似是為了使用低維的矩陣來表示一個高維的矩陣，並使兩者之差儘可能的小。本節主要討論低階近似和F-范數。

給定一個M x N矩陣C(其秩為r)和正整數k，我們希望找到一個M x N矩陣C_k，其秩不大於K。設X為C與C_k之間的差，X=C – C_k，X的F-范數為

當k遠小於r時，稱C_k為C的低階近似，其中X也就是兩矩陣之差的F范數要儘可能的小。

SVD可以被用與求低階近似問題，步驟如下：

1. 給定一個矩陣C，對其奇異值分解：

2. 構造，它是將的第k+1行至M行設為零，也就是把的最小的r-k個(the r-k smallest)奇異值設為零。

3. 計算C_k：

回憶在基礎知識一節裡曾經講過，特徵值數值的大小對矩陣-向量相乘影響的大小成正比，而奇異值和特徵值也是正比關係，因此這裡選取數值最小的r-k個特徵值設為零合乎情理，即我們所希望的C-C_k儘可能的小。完整的證明可以在Introduction to Information Retrieval^[2]中找到。

我們現在也清楚了LSA的基本思路：LSA希望通過降低傳統向量空間的維度來去除空間中的「噪音」，而降維可以通過SVD實現，因此首先對Term-Document矩陣進行SVD分解，然後降維並構造語義空間。