SVD個人心得

04-12

SVD是線性代數中最讓人激動的技巧之一。在機器學習領域有著廣泛的應用，而且將很多知識串聯在了一起。之前看過不少人寫的blog，感覺一般般~~~，所以個人想從數學和ML應用的角度寫點東西。以後還可以回頭再看看，當時有那些理解不到位的地方可以再改改，哈哈~

SVD(singular value decomposition): $A=USigma V^{T}$

數學上的動機是將行空間的一組標準正交基V, 通過線性變換A, 得到列空間的一組標準正交基U， $Sigma$ 是列空間正交基的放縮因子構成的對角矩陣。成立的關鍵是找到這樣的一組U,V滿足上式。求解的具體方法是構造對稱矩陣 $A^{T}A$ ，因為對稱陣滿足可對角化的條件，所以求解特徵方程即可得到對應的兩個正交陣U，V。與變換最密切的是矩陣A的四個基本空間(列空間，行空間，零空間，左零空間)。V是由行空間的正交基(共有r個，若rank(A)=r)和與行空間垂直的左零空間正交基(n-r個，因為齊次方程Ax=0的基礎解系的個數是n-r) 構成的。U是由列空間的正交基和零空間的正交基構成的，若rank(A)=r，則對角陣 $Sigma$ 的後(n-r)列都是0(放縮因子為0)。SVD最突出的作用體現在求解廣義逆矩陣和PCA降維。

SVD在機器學習上最主要的應用體現在對原始數據的降維，即提取最關鍵的特徵。假定A是m個樣本，n個特徵構成的輸入矩陣 $Ain R^{m imes n}$ ，m $gg$ n。則行空間可以理解成樣本空間。列空間可以理解成特徵空間。對角陣上的奇異值的大小反映了特徵空間上不同標準正交基(坐標軸)的重要程度對於構建樣本空間而言，也就從側面反映了不同特徵的重要程度。我們可以將奇異值按降序排列，得到前K個奇異值。同時也就選擇了U矩陣里前K列，故U矩陣的子矩陣 $Fin R^{m imes k}$ 就是我們新構建的矩陣，可以用來代表原來的輸入矩陣A。

在NLP領域，通過對co-occurrence matrix或者word-document matrix進行SVD，同樣可以捕獲單詞的語義相似性。

論文見：

An improved model of semantic similarity based on lexical co-occurrence.(Stanford 2005)

但是由於關聯矩陣非常大而且很稀疏，SVD分解的代價很高。還是以word2vector為代表的language model更勝一籌。