特征值分解與奇異值分解及其應用

SVD奇異值分解

正交矩陣

正交矩陣

  正交矩陣對應着正交變換，特點在于不改變向量的尺寸（模）和任意兩個向量的夾角。在x-y坐标系中，通俗地講，就是旋轉兩個坐标軸，得到新的互相垂直的坐标軸，求向量在新坐标系中的投影。

正交變換舉例

  圖檔摘自此處。 例如向量 OA O A ，在原始 e1−e2 e 1 − e 2 坐标系中表示為 (a,b)T ( a , b ) T ，在旋轉後的坐标系 e′1−e′2 e 1 ′ − e 2 ′ 中表示為 (a′,b′)T ( a ′ , b ′ ) T ，若存在一個矩陣 U U 使得(a′,b′)T=U(a,b)T(a′,b′)T=U(a,b)T，則矩陣 U U 是正交矩陣（可見對應着坐标系之間的正交變換）。

  可以代入求得矩陣UU，且可觀察到矩陣的行向量之間都是正交的，列向量之間也是正交的。

U=[cosθ−sinθsinθcosθ] U = [ cos ⁡ θ sin ⁡ θ − sin ⁡ θ cos ⁡ θ ]

正交矩陣的性質

正交陣的逆等于其轉置

ATA=I→AT=A−1 A T A = I → A T = A − 1

特征值分解

特征值分解

   A A 是 N×NN×N 滿秩對稱方陣（對稱陣的特征向量之間兩兩正交），有 N N 個特征值λiλi，對應 N N 個特征向量qiqi，有：

⎧⎩⎨⎪⎪⎪⎪⎪⎪Aq1=λ1q1Aq2=λ2q2⋯AqN=λNqN { A q 1 = λ 1 q 1 A q 2 = λ 2 q 2 ⋯ A q N = λ N q N

  可以了解為向量 qi q i 在 A A 的作用下，保持方向不變，隻進行比例為λiλi的縮放。特征向量所在的直線包含了所有特征向量（稱為特征空間）。

  以上 N N 個等式寫成矩陣形式（qiqi是 N×1 N × 1 的列向量！）

A[q1,q2,⋯,qN]=[q1,q2,⋯,qN]⎡⎣⎢⎢λ1⋮0⋯⋱⋯0⋮λN⎤⎦⎥⎥AQ=QΛ A [ q 1 , q 2 , ⋯ , q N ] = [ q 1 , q 2 , ⋯ , q N ] [ λ 1 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ λ N ] A Q = Q Λ

  等式兩邊右乘 Q Q 的逆，得到AA的特征值分解：

A=QΛQ−1 A = Q Λ Q − 1

  進一步，由于特征向量矩陣 Q Q 各列互相正交，是以QQ是正交陣，正交陣的逆等于其轉置:

A=QΛQT A = Q Λ Q T

A=[q1,q2,⋯,qN]⎡⎣⎢⎢λ1⋮0⋯⋱⋯0⋮λN⎤⎦⎥⎥[q1,q2,⋯,qN]T A = [ q 1 , q 2 , ⋯ , q N ] [ λ 1 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ λ N ] [ q 1 , q 2 , ⋯ , q N ] T

特征值分解的幾何意義

  矩陣 A A 是一個既有旋轉又有縮放的變換，用AA對向量 x x 進行矩陣變換AxAx，即對它進行旋轉操作和縮放操作。整個過程在矩陣做EVD之後，可以看成 QΛQTx Q Λ Q T x ，即 x x 依次經過QTQT， Λ Λ 和 Q Q 的變換，特别地，如果xx恰與矩陣 A A 的某個特征向量平行，那麼它将不會發生旋轉，隻發生縮放。

1. QTxQTx：将 x x 由原始空間變換到由QQ各兩兩正交的特征向量構成的空間中
   • ΛQTx Λ Q T x ：将變換後的 x x 在特征空間中縮放，軸qiqi的縮放因子正是對應的特征值 λi λ i
   • QΛQTx Q Λ Q T x ：将縮放過的 x x 變換回原始空間

矩陣變換舉例

A=[1−1−12]x=[0,1]TA=[1−1−12]x=[0,1]T

奇異值分解SVD

SVD定義

M×N M × N 矩陣 A A 的SVD：

A=U∑VTA=U∑VT

SVD推導

  首先把 A A 變成N×NN×N方陣 ATA A T A ，于是就能做EVD：

(ATA)vi=λivi(ATA)V=VΛ ( A T A ) v i = λ i v i ( A T A ) V = V Λ

  然後把 A A 變成方陣M×MM×M，于是就又能做EVD：

(AAT)ui=λiui(AAT)U=UΛ ( A A T ) u i = λ i u i ( A A T ) U = U Λ

  非方陣的秩最多為M和N較小值，兩種情況下非零特征值是一樣的，多餘的特征值都是0。現在假設 A A 可以分解成A=U′∑′V′TA=U′∑′V′T的形式，現在求出這三部分：

AT=V′∑′U′TATA=V′(∑′)2V′TAAT=U′(∑′)2U′T A T = V ′ ∑ ′ U ′ T A T A = V ′ ( ∑ ′ ) 2 V ′ T A A T = U ′ ( ∑ ′ ) 2 U ′ T

是以 V′=V V ′ = V ， U′=U U ′ = U ， ∑′=Λ−−√ ∑ ′ = Λ ，也就是說中間對角矩陣 ∑ ∑ 的元素可以這樣求：

σi=λi−−√ σ i = λ i

SVD性質

  對角陣 ∑ ∑ 的奇異值從左上到右下按從大到小排序，一般來說少量幾個奇異值（例如 k k 個）就占據了奇異值之和的絕大部分，是以可以隻用這kk個奇異值和對應的左右特征向量表示原矩陣 A A ：

A=UM×M∑M×NVTN×N≈UM×k∑k×kVTk×NA=UM×M∑M×NVN×NT≈UM×k∑k×kVk×NT

總結

  SVD可以把任意形狀的矩陣分解成 A=U∑VT A = U ∑ V T 的形式， U U 和VV都是有特征值分解得到的特征向量矩陣，它們都是正交陣， ∑ ∑ 可以由特征值開平方得到。隻選擇較大的奇異值就能很好地表示原矩陣。

EVD應用-PCA

初衷——最大方差投影

  希望找到一個新的正交坐标系，将樣本變換過去（投影過去），使得所有樣本之間盡可能地分開（方差最大）。

1. 樣本集 X X 在坐标系WW（W的每行就是一個标準正交基，即兩兩之間正交，且模為1）下的投影是 WTX W T X （原因參見正交變換）
2. 假設樣本是去中心化的（均值為0），投影的方差為 WTXXTW W T X X T W
3. 寫出有限制優化問題

maxs.t.tr(WTXXTW)WTW=I max t r ( W T X X T W ) s . t . W T W = I

用拉格朗日乘子法求解：

L(W)=WTXXTW+λ(I−WTW)∂L(W)∂W=2XTXW−2λW(XTX)W=λW L ( W ) = W T X X T W + λ ( I − W T W ) ∂ L ( W ) ∂ W = 2 X T X W − 2 λ W ( X T X ) W = λ W

  如此可見，我們所需的新坐标系正是樣本協方差 XTX X T X （ d×d d × d ）做特征值分解後的特征向量矩陣。總結一下PCA的流程：首先樣本去中心化，然後計算樣本協方差 XTX X T X ，再對 XTX X T X 做EVD，選取最大的部分特征值所對應的特征向量，構成投影矩陣 W W 。

SVD應用-LSA潛在語義分析

構造單詞-文檔矩陣

  假設有DD（Document）篇文章，每篇文章都是由很多個單詞構成的結構（bag-of-words，單詞的位置不重要，隻關心數量），而單詞來自于一個大小為 W W （Word）的字典，則構造W×DW×D矩陣，第 i i 行第jj清單示單詞 Wi W i 在文檔 j j 中出現的次數（或者tf-idf）。通常來說，該矩陣會相當地稀疏。

  具體地，會先周遊所有文章進行分詞，在這個過程中過濾掉停止詞（例如a、the之類的）和标點等，然後進行詞頻計數等操作。

SVD

  将單詞-文檔矩陣進行SVD，并且隻選取部分足夠大的奇異值（例如kk個），對應于不同的主題（語義）：

AW×D=UW×kSk×kVTD×k A W × D = U W × k S k × k V D × k T

  其中 UW×k U W × k 描述了每個單詞與不同主題之間的關系， Sk×k S k × k 描述了主題本身， VD×k V D × k 描述了每篇文章與不同主題之間的關系。我們可以從 UW×k U W × k 挖掘同義詞，從 VD×k V D × k 挖掘相似文檔。那麼到底為什麼需要做SVD呢？是因為單純地統計詞頻或tf-idf并不能描述單詞之間或文本之間的關系。然而SVD有一個問題，就是每一個語義具體是什麼不可解釋，隻知道他們是互相正交的。

從SVD到SVD++

SVD在電影推薦中的應用

問題提出

1. 稀疏矩陣沒法直接SVD，有很多資料是缺失的
2. SVD很慢，超過1000維的矩陣做SVD已經相當慢了

電影推薦

  現有一個矩陣，行表示使用者，清單示電影，矩陣中每個元素表示某個使用者對某個電影的打分，顯然這個矩陣是極其稀疏的（不是每個使用者都看過所有電影的，大多隻看過幾部），有大量缺失值。現在的問題是，如何預測這些缺失值？即如何預測一個使用者對他沒看過的電影的評分？

  首先，如果把U乘S看成一個矩陣，則SVD可以寫成兩個矩陣相乘：

AW×D=[UW×kSk×k]VTD×k A W × D = [ U W × k S k × k ] V D × k T

  那麼電影評分矩陣也存在這種分解：

RU×M=PU×kQk×M R U × M = P U × k Q k × M

  現在P和Q是未知的，如果能通過R中已知的評分訓練P和Q，使得P和Q相乘的結果能最好地拟合R中未缺失值，則缺失值就可以通過P的一行乘上Q的一列得到：

r^um=pTuqm r ^ u m = p u T q m

P和Q的訓練（基于梯度下降法）：Basic SVD

  要拟合真實的已知評分 rum r u m ，選取平方誤差：

E=12∑u∑m(rum−r^um)2=12∑u∑m(rum−∑jpujqjm)2 E = 1 2 ∑ u ∑ m ( r u m − r ^ u m ) 2 = 1 2 ∑ u ∑ m ( r u m − ∑ j p u j q j m ) 2

  計算梯度（當然隻能代入R矩陣中 rum r u m 有取值的計算），漂亮的對稱結構：

∂E∂puk=−(rum−r^um)qkm=−eumqkm∂E∂qkm=−(rum−r^um)puk=−eumpuk ∂ E ∂ p u k = − ( r u m − r ^ u m ) q k m = − e u m q k m ∂ E ∂ q k m = − ( r u m − r ^ u m ) p u k = − e u m p u k

  接下來隻需要将P和Q用随機數初始化，然後梯度下降疊代即可。

P和Q的訓練：RSVD

  引入正則化：

E=12∑u,me2um+12λ∑u,kp2uk+12λ∑k,mq2km E = 1 2 ∑ u , m e u m 2 + 1 2 λ ∑ u , k p u k 2 + 1 2 λ ∑ k , m q k m 2

  計算梯度：

∂E∂puk=−(rum−r^um)qkm=−eumqkm+λpuk∂E∂qkm=−(rum−r^um)puk=−eumpuk+λqkm ∂ E ∂ p u k = − ( r u m − r ^ u m ) q k m = − e u m q k m + λ p u k ∂ E ∂ q k m = − ( r u m − r ^ u m ) p u k = − e u m p u k + λ q k m

有偏置的RSVD：RSVD 改

  使用者對電影的打分不僅取決于使用者與電影之間的關系，還應該受到使用者自身 bu b u 和電影自身性質 bm b m 的影響：

r^um=pTuqm+bu+bm+μ r ^ u m = p u T q m + b u + b m + μ

  其中 μ μ 是全局平均分，他描述了整個打分網站的整體打分水準。

  引入正則化和懲罰：

E=12∑u,me2um+12λ∑u,kp2uk+12λ∑k,mq2km+12λ∑ub2u+12λ∑mb2m E = 1 2 ∑ u , m e u m 2 + 1 2 λ ∑ u , k p u k 2 + 1 2 λ ∑ k , m q k m 2 + 1 2 λ ∑ u b u 2 + 1 2 λ ∑ m b m 2

  如此對于P和Q的導數不變，新增加的三個參數中，兩個b是需要學習的，仍然用梯度下降疊代更新，初始值設0即可。

考慮鄰域影響的SVD++

P和Q的訓練：SVD++

  在有偏置RSVD的基礎上，還考慮了使用者對電影的曆史評分。ItemCF衡量使用者 u u 對電影mm的興趣：

r^′um=1|N(u)|−−−−−√∑j∈N(u)wmj r ^ u m ′ = 1 | N ( u ) | ∑ j ∈ N ( u ) w m j

  這裡 N(u) N ( u ) 是使用者 u u 喜歡的電影集合，wmjwmj是電影 m m 和電影jj的相似度（在ItemCF中，相似度通過統計所有使用者觀看的電影清單獲得，但注意在SVD++中 w w 實際上是需要學習的參數），這個式子中求和項的意思是使用者過去感興趣的所有電影和電影mm的整體相似程度，左邊分式用于歸一化。

  現在嫌矩陣 W W 太大，用SVD的思想它也能分解 W=XYW=XY，即用 xTmyj x m T y j 代替 wmj w m j ， xm x m 和 yj y j 都是向量

r^′um=1|N(u)|−−−−−√∑j∈N(u)xTmyj=1|N(u)|−−−−−√xTm∑j∈N(u)yj r ^ u m ′ = 1 | N ( u ) | ∑ j ∈ N ( u ) x m T y j = 1 | N ( u ) | x m T ∑ j ∈ N ( u ) y j

  将這個興趣加到RSVD上

r^um=bu+bm+μ+qTmpu+1|N(u)|−−−−−√xTm∑j∈N(u)yj r ^ u m = b u + b m + μ + q m T p u + 1 | N ( u ) | x m T ∑ j ∈ N ( u ) y j

  又嫌參數太多，讓 x=q x = q ：

r^um=bu+bm+μ+qTm⎛⎝pu+1|N(u)|−−−−−√∑j∈N(u)yj⎞⎠ r ^ u m = b u + b m + μ + q m T ( p u + 1 | N ( u ) | ∑ j ∈ N ( u ) y j )

  如此一來，需要疊代學習的參數包括 bu b u ， bm b m ， puk p u k ， qkm q k m ， yj y j 。手撸梯度之後，梯度下降求解。

總結

1. PCA和SVD都能用來降維，隻是PCA用的是特征值分解。
2. PCA需要對資料去中心化，可能使樣本由稀疏變稠密，提高計算複雜度。
3. PCA隻能獲得矩陣一個方向的分解，SVD能獲得兩個方向的分解。
4. SVD實際上很慢，而且無法處理缺失值，是以采取矩陣分解梯度下降拟合未缺失值
5. 梯度下降拟合可能會過拟合，是以采用RSVD
6. 有偏置的RSVD是出于對使用者和物品各自固有屬性的考慮
7. SVD++是在有偏置的RSVD基礎上，基于ItemCF考慮了使用者曆史喜好的SVD

參考資料

奇異值分解(SVD)原理詳解及推導

知乎-如何了解特征值

《推薦系統實踐》