奇異值分解(Singular Value Decompostion, SVD)是在機器學習領域廣泛應用的算法，不光可以用于降維算法中的特征分解，還可以用于推薦系統，以及自然語言處理等領域，是很多機器學習算法的基石。本篇文章對SVD原理做主要講解，在學習之前，確定你已經熟悉線性代數中的基本知識，包括特征值、特征向量、相似矩陣相關知識點。如果不太熟悉的話，推薦閱讀如下兩篇文章，如何了解矩陣特征值？知乎馬同學的回答和如何了解相似矩陣？馬同學高等數學，讀完之後再看本篇文章會有很大幫助。
1. 回顧特征值和特征向量
我們首先回顧下特征值和特征向量的定義，如下所示。其中A是一個n×n的矩陣，x是一個n維向量，則我們說λ是矩陣A的一個特征值，x是矩陣A的特征值λ所對應的特征向量。但是求出特征值和特征向量有什麼好處呢?
上面矩陣能夠進行特征分解，需要滿足矩陣A必須為方陣。那麼如果A不是方陣，即行和列不相同時，我們還可以進行矩陣分解嗎？
2. 奇異值分解(SVD)
當矩陣A不是方陣時，可以用奇異值進行分解，假設我們的的矩陣A時一個m×n的矩陣，那麼我們定義矩陣A的SVD為
其中U時一個m×m的矩陣，Σ是一個m×n的矩陣，除了主對角線上的元素以外全為0，主對角線上的每個元素都稱為奇異值，V時一個n×n的矩陣。U和V都是酉矩陣，即滿足
下圖可以形象的表示出上述SVD的定義，但我們如何求出SVD分解後的U,Σ,V這三個矩陣呢?
U和V都已經求出，現在隻有奇異值矩陣Σ沒有求出。由于Σ除了對角線上是奇異值，其他位置都是0，是以我們隻需要求出每個奇異值σ就可以了。我們注意到
通過上式，我們便可以求出每個奇異值，進而求出奇異值矩陣Σ。
3. SVD示例
下面我們通過一個簡單例子來說明矩陣式如何進行奇異值分解的，假設矩陣A為
4. SVD性質
對于SVD有哪些重要的性質值得我們注意呢? 對于奇異值，它跟特征分解中的特征值類似，在奇異值矩陣中也是按照從大到小排列，而且奇異值的減少特别的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部奇異值之和的99%以上的比例。也就是說，我們可以用最大的k個奇異值和對應的左右奇異向量來近似描述矩陣，即
由于這個重要的性質，是以SVD可以用于PCA降維，用來做資料壓縮和去噪。也可以用于推薦算法，将使用者和喜好對應的矩陣做特征分解，進而得到隐含的使用者需求來做推薦。同時也可以用于NLP之中的算法，比如潛在語義索引(LSI)。
5. SVD在PCA之中的應用
在機器學習降維之主成分分析(PCA)之中，我們講到PCA降維時，需要找到樣本協方差矩陣X^TX最大的d個特征向量，然後用着最大的d個特征向量組成的矩陣來做低維投影降維。可以看出，在這個過程中需要先求出協方差矩陣X^TX，當樣本數多、樣本特征數也多的時候，比如10000*10000的矩陣，這個計算量是很大的。
注意到SVD也可以求出協方差矩陣X^TX最大的d個特征向量組成的矩陣，但是SVD有個好處，就是可以不求出協方差矩陣X^TX，也能通過某些算法求出右奇異矩陣V，比如https://arxiv.org/abs/0909.4061。也就是說，PCA算法可以不用做特征分解，而是用SVD來進行完成。
另一方面，PCA僅僅使用了SVD的右奇異矩陣，沒有使用左奇異矩陣，那麼左奇異矩陣有什麼用呢？假如我們的樣本是m×n的矩陣X，如果通過SVD找到矩陣XX^T最大的d個特征向量組成的m×d的矩陣U，則我們進行如下處理
可以得到一個d×n的矩陣X'，這個矩陣和我們原來的m×n維樣本矩陣X相比，行數從m減到了d，可見對行數進行了壓縮。也就是說，左奇異矩陣可以用于行數的壓縮，右奇異矩陣可以用于列數壓縮，即特征降維。
6. SVD算法總結
SVD作為一個很基本的算法，在很多機器學習算法中都有它的身影，特别是在現在的大資料時代，由于SVD可以實作并行化，是以更是大展身手。當然，SVD的缺點是分解出的矩陣解釋性往往不強，不過這不影響它的使用。
參考
劉建平Pinard-奇異值分解(SVD)原理轉載降維中的應用
你看到的這篇文章來自于公衆号「謂之小一」，歡迎關注我閱讀更多文章。