從SVD到PCA

來自專欄 深度學習的一點一滴

一、特徵值

如果說一個向量v是方陣A的特徵向量，將一定可以表示成下面的形式：

這時候λ就被稱為特徵向量v對應的特徵值，一個矩陣的一組特徵向量是一組正交向量。特徵值分解是將一個矩陣分解成下面的形式：

其中Q是這個矩陣A的特徵向量組成的矩陣，Σ是一個對角陣，每一個對角線上的元素就是一個特徵值。首先，要明確的是，一個矩陣其實就是一個線性變換，因為一個矩陣乘以一個向量後得到的向量，其實就相當於將這個向量進行了線性變換。比如說下面的一個矩陣：

它其實對應的線性變換是下面的形式:

因為這個矩陣M乘以一個向量(x,y)的結果是：

上面的矩陣是對稱的，所以這個變換是一個對x，y軸的方向一個拉伸變換（每一個對角線上的元素將會對一個維度進行拉伸變換，當值>1時，是拉長，當值<1時時縮短），當矩陣不是對稱的時候，假如說矩陣是下面的樣子：

它所描述的變換是下面的樣子：

這其實是在平面上對一個軸進行的拉伸變換（如藍色的箭頭所示），在圖中，藍色的箭頭是一個最主要的變化方向（變化方向可能有不止一個），如果我們想要描述好一個變換，那我們就描述好這個變換主要的變化方向就好了。反過頭來看看之前特徵值分解的式子，分解得到的Σ矩陣是一個對角陣，裡面的特徵值是由大到小排列的，這些特徵值所對應的特徵向量就是描述這個矩陣變化方向（從主要的變化到次要的變化排列）。

當矩陣是高維的情況下，那麼這個矩陣就是高維空間下的一個線性變換，這個線性變化可能沒法通過圖片來表示，但是可以想像，這個變換也同樣有很多的變換方向，我們通過特徵值分解得到的前N個特徵向量，那麼就對應了這個矩陣最主要的N個變化方向。我們利用這前N個變化方向，就可以近似這個矩陣（變換）。也就是之前說的：提取這個矩陣最重要的特徵。總結一下，特徵值分解可以得到特徵值與特徵向量，特徵值表示的是這個特徵到底有多重要，而特徵向量表示這個特徵是什麼，可以將每一個特徵向量理解為一個線性的子空間，我們可以利用這些線性的子空間干很多的事情。不過，特徵值分解也有很多的局限，比如說變換的矩陣必須是方陣。

二、奇異值

特徵值分解是一個提取矩陣特徵很不錯的方法，但是它只是對方陣而言的，在現實的世界中，我們看到的大部分矩陣都不是方陣，比如說有M個學生，每個學生有N科成績，這樣形成的一個M * N的矩陣就不可能是方陣，我們怎樣才能描述這樣普通的矩陣呢的重要特徵呢？奇異值分解可以用來干這個事情，奇異值分解是一個能適用於任意的矩陣的一種分解的方法：

假設A是一個M * N的矩陣，那麼得到的U是一個M * M的方陣（裡面的向量是正交的，U裡面的向量稱為左奇異向量），Σ是一個M * N的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值），V』(V的轉置)是一個N * N的矩陣，裡面的向量也是正交的，V裡面的向量稱為右奇異向量）

那麼奇異值和特徵值是怎麼對應起來的呢？首先，我們將一個矩陣A的轉置乘上 A，將會得到一個方陣，我們用這個方陣求特徵值可以得到：

這裡得到的v，就是我們上面的右奇異向量。此外我們還可以得到：

這裡的σ就是上面說的奇異值，u就是上面說的左奇異向量。奇異值σ跟特徵值類似，在矩陣Σ中也是從大到小排列，而且σ的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就佔了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，這裡定義一下部分奇異值分解：

r是一個遠小於m、n的數，這樣矩陣的乘法看起來像是下面的樣子：

右邊的三個矩陣相乘的結果將會是一個接近於A的矩陣，在這兒，r越接近於n，則相乘的結果越接近於A。而這三個矩陣的面積之和（在存儲觀點來說，矩陣面積越小，存儲量就越小）要遠遠小於原始的矩陣A，我們如果想要壓縮空間來表示原矩陣A，我們存下這裡的三個矩陣：U、Σ、V就好了。

三、主成分分析(PCA)

PCA的問題其實是一個基的變換，使得變換後的數據有著最大的方差。方差的大小描述的是一個變數的信息量，我們在講一個東西的穩定性的時候，往往說要減小方差，如果一個模型的方差很大，那就說明模型不穩定了。但是對於我們用於機器學習的數據（主要是訓練數據），方差大才有意義，不然輸入的數據都是同一個點，那方差就為0了，這樣輸入的多個數據就等同於一個數據了。以下面這張圖為例子：

這個假設是一個攝像機採集一個物體運動得到的圖片，上面的點表示物體運動的位置，假如我們想要用一條直線去擬合這些點，那我們會選擇什麼方向的線呢？當然是圖上標有signal的那條線。如果我們把這些點單純的投影到x軸或者y軸上，最後在x軸與y軸上得到的方差是相似的（因為這些點的趨勢是在45度左右的方向，所以投影到x軸或者y軸上都是類似的），如果我們使用原來的xy坐標系去看這些點，容易看不出來這些點真正的方向是什麼。但是如果我們進行坐標系的變化，橫軸變成了signal的方向，縱軸變成了noise的方向，則就很容易發現什麼方向的方差大，什麼方向的方差小了。

一般來說，方差大的方向是信號的方向，方差小的方向是雜訊的方向，我們在數據挖掘中或者數字信號處理中，往往要提高信號與雜訊的比例，也就是信噪比。對上圖來說，如果我們只保留signal方向的數據，也可以對原數據進行不錯的近似了。

PCA的全部工作簡單點說，就是對原始的空間中順序地找一組相互正交的坐標軸，第一個軸是使得方差最大的，第二個軸是在與第一個軸正交的平面中使得方差最大的，第三個軸是在與第1、2個軸正交的平面中方差最大的，這樣假設在N維空間中，我們可以找到N個這樣的坐標軸，我們取前r個去近似這個空間，這樣就從一個N維的空間壓縮到r維的空間了，但是我們選擇的r個坐標軸能夠使得空間的壓縮使得數據的損失最小。

假設我們矩陣每一行表示一個樣本，每一列表示一個feature，用矩陣的語言來表示，將一個m * n的矩陣A的進行坐標軸的變化，P就是一個變換的矩陣從一個N維的空間變換到另一個N維的空間，在空間中就會進行一些類似於旋轉、拉伸的變化。

而將一個m * n的矩陣A變換成一個m * r的矩陣，這樣就會使得本來有n個feature的，變成了有r個feature了（r < n)，這r個其實就是對n個feature的一種提煉，我們就把這個稱為feature的壓縮。用數學語言表示就是：

但是這個怎麼和SVD扯上關係呢？之前談到，SVD得出的奇異向量也是從奇異值由大到小排列的，按PCA的觀點來看，就是方差最大的坐標軸就是第一個奇異向量，方差次大的坐標軸就是第二個奇異向量…我們回憶一下之前得到的SVD式子：

在矩陣的兩邊同時乘上一個矩陣V，由於V是一個正交的矩陣，所以V轉置乘以V得到單位陣I，所以可以化成後面的式子：

將後面的式子與A * P那個m * n的矩陣變換為m * r的矩陣的式子對照看看，在這裡，其實V就是P，也就是一個變化的向量。這裡是將一個m * n 的矩陣壓縮到一個m * r的矩陣，也就是對列進行壓縮，如果我們想對行進行壓縮（在PCA的觀點下，對行進行壓縮可以理解為，將一些相似的sample合併在一起，或者將一些沒有太大價值的sample去掉）怎麼辦呢？同樣我們寫出一個通用的行壓縮例子：

這樣就從一個m行的矩陣壓縮到一個r行的矩陣了，對SVD來說也是一樣的，我們對SVD分解的式子兩邊乘以U的轉置U：

這樣我們就得到了對行進行壓縮的式子。可以看出，其實PCA幾乎可以說是對SVD的一個包裝，如果我們實現了SVD，那也就實現了PCA了，而且更好的地方是，有了SVD，我們就可以得到兩個方向的PCA，如果我們對A』A進行特徵值的分解，只能得到一個方向的PCA。