今天是機器學習專題第28篇文章，我們來聊聊SVD算法。

SVD的英文全稱是Singular Value Decomposition，翻譯過來是奇異值分解。這其實是一種線性代數算法，用來對矩陣進行拆分。拆分之後可以提取出關鍵信息，從而降低原數據的規模。因此廣泛利用在各個領域當中，例如信号處理、金融領域、統計領域。在機器學習當中也有很多領域用到了這個算法，比如推薦系統、搜索引擎以及數據壓縮等等。

SVD簡介

我們假設原始數據集矩陣D是一個mxn的矩陣，那麼利用SVD算法，我們可以将它分解成三個部分：

這三個矩陣當中U是一個m x n的矩陣，∑是一個m x n的對角矩陣，除了對角元素全為0，對角元素為該矩陣的奇異值。V是一個n x n的矩陣。U和V都是酉矩陣，即滿足U^TU = I, V^T V = I。也就是它乘上它的轉置等于單位對角矩陣。

我們可以看下下圖，從直觀上感知一下這三個矩陣。

下面我們來簡單推導一下SVD的求解過程，看起來很複雜，概念也不少，但是真正求解起來卻并不難。會需要用到矩陣特征值分解的相關概念，如果不熟悉的同學可以先看下線性代數專題相關内容做個回顧：

線性代數精華——講透矩陣的初等變換與矩陣的秩

首先，如果我們計算A^TA可以得到一個n x n的方陣。對于方陣我們可以對它進行特征分解，假設得到特征值是lambda_i，特征向量是v_i，代入特征值的性質可以得到：

這樣的特征值和特征向量一共會有n個，我們把它所有的特征向量組合在一起，可以得到一個n x n的矩陣V。它也就是我們SVD分解結果之後的V，所以有些書上會把它叫做右奇異向量。

同理，我們計算AA^T可以得到一個m x m的方陣，我們同樣可以對他進行特征值分解，得到一個特征矩陣U。U應該是一個m x m的矩陣，也就是SVD公式中的U，我們可以将它稱為A的左奇異向量。

U和V都有了，我們隻剩下∑還沒求出來了。由于它是一個對角矩陣，除了對角元素全為0，所以我們隻需要求出它當中的每一個對角元素，也就是奇異值就可以了，我們假設奇異值是 σ，我們對SVD的式子進行變形：

這個推導當中利用了V是酉矩陣的性質，所以我們乘上了V将它消除，就推導得到了奇異值的公式，∑矩陣也就不難求了。

整個推導的過程不難，但是有一個問題沒解決，為什麼AA^T的特征矩陣就是SVD中的U矩陣了，原理是什麼？這一步是怎麼推導來的？說實話我也不知道天才數學家們這一步是怎麼推導得到的，我實在腦補不出來當時經過了怎樣的思考才得到了這個結果，但是想要證明它是正确的倒不難。

這裡也同樣利用了酉矩陣的性質，還有對角矩陣乘法的性質。我們可以看出來，U的确是AA^T特征向量組成的矩陣，同樣也可以證明V。其實如果眼尖一點還可以發現特征值矩陣等于奇異值矩陣的平方，所以

所以，我們求解∑矩陣可以不用很麻煩地通過矩陣去計算，而是可以通過AA^T的特征值取平方根來求了。

SVD的用途

我們推導了這麼多公式，那麼這個SVD算法究竟有什麼用呢？

看來看去好像看不出什麼用途，因為我們把一個矩陣變成了三個，這三個矩陣的規模也并沒有降低，反而增加了。但是如果去研究一下分解出來的奇異值，會發現奇異值降低的特别快。隻要10%甚至是1%的奇異值就占據了全部奇異值之和的99%以上的比例。

換句話說，我們并不需要完整的SVD分解結果，而是隻需要篩選出其中很少的k個奇異值，和對應的左右奇異向量就可以近似描述原矩陣了。

我們看下下圖，相當于我們從分解出來的矩陣當中篩選一小部分來代替整體，并且保留和整體近似的信息。

我們把式子寫出來：

這裡的k遠小于n，所以我們可以大大降低SVD分解之後得到的矩陣參數的數量。

也就是說，我們通過SVD分解，将一個m x n的大矩陣，分解成了三個小得多的小矩陣。并且通過這三個小矩陣，我們可以還原出原矩陣大部分的信息。不知道大家有沒有想到什麼？是了，這個和我們之前介紹的PCA算法如出一轍。不僅思路相似，就連計算的過程也重合度非常高，實際上PCA算法的求解方法之一就是通過SVD矩陣分解。

SVD與PCA

我們來簡單看看SVD和PCA之間的關聯。

首先複習一下PCA算法，我們首先計算出原始數據的協方差矩陣X，再對X^TX進行矩陣分解，找到最大的K個特征值。然後用這K個特征值對應的特征向量組成的矩陣來對原始數據做矩陣變換。

在這個過程當中，我們需要計算X^TX，當X的規模很大的時候，這個計算開銷也是很大的。注意到我們在計算SVD中V矩陣的時候，也用到了A^TA矩陣的特征值分解。然而關鍵是一些計算SVD的算法可以不先求出協方差矩陣X^TX也能得到V，就繞開了這個開銷很大的步驟。

所以目前流行的PCA幾乎都是以SVD為底層機制實現的，比如sklearn庫中的PCA工具就是用的SVD。

代碼實現

關于SVD算法我們并不需要自己實現，因為numpy當中封裝了現成的SVD分解方法。

我們直接調用np.linalg.svd接口即能完成矩陣的分解：

這裡的Sigma返回的是一個向量，代替了對角矩陣，節省了存儲開銷。我們可以通過找出最小的K，使得K個奇異值占據整體奇異值95%以上的和。這裡可以看到，我們選出了5個奇異值就占據所有奇異值和的99%以上：

總結

我們今天和大家分享了SVD算法的原理，以及一種常規的計算方法。SVD和PCA一樣底層都是基于矩陣的線性操作完成的，通過SVD的性質，我們可以對原數據進行壓縮和轉化。基于這一點，衍生出了許多的算法和應用場景，其中最經典的要屬推薦系統中的協同過濾了。由于篇幅限制，我們将會在下一篇文章當中和大家分享這一點，實際了解一下SVD的應用，加深一下理解。

由于SVD可以實現并行化計算，使得在實際當中它更受歡迎。但SVD也不是萬能的，它一個很大的缺點就是和PCA一樣解釋性很差，我們無法得知某些值或者是某些現象的原因。關于這一點，我們也會在下一篇文章當中加以體現。

今天的文章到這裡就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支持吧（關注、轉發、點贊）。

本文始發于公衆号：TechFlow

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!