今天是機器學(xué)習(xí)專題第28篇文章，我們來聊聊SVD算法。

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

SVD簡介

我們假設(shè)原始數(shù)據(jù)集矩陣D是一個mxn的矩陣，那么利用SVD算法，我們可以將它分解成三個部分：

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

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

下面我們來簡單推導(dǎo)一下SVD的求解過程，看起來很復(fù)雜，概念也不少，但是真正求解起來卻并不難。會需要用到矩陣特征值分解的相關(guān)概念，如果不熟悉的同學(xué)可以先看下線性代數(shù)專題相關(guān)內(nèi)容做個回顧：

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

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

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

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

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

這個推導(dǎo)當(dāng)中利用了V是酉矩陣的性質(zhì)，所以我們乘上了V將它消除，就推導(dǎo)得到了奇異值的公式，∑矩陣也就不難求了。

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

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

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

SVD的用途

我們推導(dǎo)了這么多公式，那么這個SVD算法究竟有什么用呢？

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

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

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

我們把式子寫出來：

這里的k遠小于n，所以我們可以大大降低SVD分解之后得到的矩陣參數(shù)的數(shù)量。

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

SVD與PCA

我們來簡單看看SVD和PCA之間的關(guān)聯(lián)。

首先復(fù)習(xí)一下PCA算法，我們首先計算出原始數(shù)據(jù)的協(xié)方差矩陣X，再對X^TX進行矩陣分解，找到最大的K個特征值。然后用這K個特征值對應(yīng)的特征向量組成的矩陣來對原始數(shù)據(jù)做矩陣變換。

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

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

代碼實現(xiàn)

關(guān)于SVD算法我們并不需要自己實現(xiàn)，因為numpy當(dāng)中封裝了現(xiàn)成的SVD分解方法。

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

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

總結(jié)

我們今天和大家分享了SVD算法的原理，以及一種常規(guī)的計算方法。SVD和PCA一樣底層都是基于矩陣的線性操作完成的，通過SVD的性質(zhì)，我們可以對原數(shù)據(jù)進行壓縮和轉(zhuǎn)化?；谶@一點，衍生出了許多的算法和應(yīng)用場景，其中最經(jīng)典的要屬推薦系統(tǒng)中的協(xié)同過濾了。由于篇幅限制，我們將會在下一篇文章當(dāng)中和大家分享這一點，實際了解一下SVD的應(yīng)用，加深一下理解。

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

今天的文章到這里就結(jié)束了，如果喜歡本文的話，請來一波素質(zhì)三連，給我一點支持吧（關(guān)注、轉(zhuǎn)發(fā)、點贊）。

本文始發(fā)于公眾號：TechFlow