機器學習系列-SVD篇

01-30

SVD全稱Singular value decomposition，奇異值分解。線性代數里重要的一種分解形式，其矩陣的特殊含義可以用來做處理線性相關。如在自然語言處理中，對新聞的分類，就可以採用SVD的方法，而且已取得不錯的效果。把新聞中的核心詞，用一個向量進行表示，每條新聞一個向量，組成一個矩陣，對矩陣進行SVD分解。如：可以用一個大矩陣A來描述這一百萬篇文章和五十萬詞的關聯性。這個矩陣中，每一行對應一篇文章，每一列對應一個詞。

在上面的圖中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 個詞在第 i 篇文章中出現的加權詞頻（比如，TF/IDF)。讀者可能已經注意到了，這個矩陣非常大，有一百萬乘以五十萬，即五千億個元素。

奇異值分解就是把上面這樣一個大矩陣，分解成三個小矩陣相乘，如下圖所示。比如把上面的例子中的矩陣分解成一個一百萬乘以一百的矩陣X，一個一百乘以一百的矩陣B，和一個一百乘以五十萬的矩陣Y。這三個矩陣的元素總數加起來也不過1.5億，僅僅是原來的三千分之一。相應的存儲量和計算量都會小三個數量級以上。

三個矩陣有非常清楚的物理含義：

第一個矩陣X中的每一行表示意思相關的一類詞，其中的每個非零元素表示這類詞中每個詞的重要性（或者說相關性），數值越大越相關。
第三個矩陣Y中的每一列表示同一主題一類文章，其中每個元素表示這類文章中每篇文章的相關性。
第二個矩陣B則表示類詞和文章之間的相關性。因此，我們只要對關聯矩陣A進行一次奇異值分解，我們就可以同時完成了近義詞分類和文章的分類。（同時得到每類文章和每類詞的相關性）。

特徵向量物理意義

我國著名數學家華羅庚曾說過：「數缺形時少直觀,形少數時難入微；數形結合百般好,隔離分家萬事休」。數學中,數和形是兩個最主要的研究對象,它們之間有著十分密切的聯繫,在一定條件下,數和形之間可以相互轉化,相互滲透。數形結合的基本思想,就是在研究問題的過程中,注意把數和形結合起來考察,斟酌問題的具體情形,把圖形性質的問題轉化為數量關係的問題,或者把數量關係的問題轉化為圖形性質的問題,使複雜問題簡單化,抽象問題具體化,化難為易,獲得簡便易行的成功方案。

我們知道，矩陣乘法對應了一個變換，是把任意一個向量變成另一個方向或長度都大多不同的新向量。在這個變換的過程中，原向量主要發生旋轉、伸縮的變化。如果矩陣對某一個向量或某些向量只發生伸縮變換，不對這些向量產生旋轉的效果，那麼這些向量就稱為這個矩陣的特徵向量，伸縮的比例就是特徵值。

來看一個只有兩行兩列的簡單矩陣。第一個例子是對角矩陣:

從幾何的角度，矩陣可以描述為一個變換：用矩陣乘法將平面上的點（x, y）變換成另外一個點（3x, y）：

這種變換的效果如下：平面在水平方向被拉伸了3倍，在豎直方向無變化。

再看下這個矩陣

它會產生如下的效果

這其實是在平面上對一個軸進行的拉伸變換（如藍色的箭頭所示），在圖中，藍色的箭頭是一個最主要的變化方向（變化方向可能有不止一個）。如果我們想要描述好一個變換，那我們就描述好這個變換主要的變化方向就好了。

如果說一個向量v是方陣A的特徵向量，這時候λ就被稱為特徵向量v對應的特徵值。

其中Q是這個矩陣A的特徵向量組成的矩陣，Σ是一個對角陣，每一個對角線上的元素就是一個特徵值。

意義

分解得到的Σ矩陣是一個對角陣，裡面的特徵值是由大到小排列的，這些特徵值所對應的特徵向量就是描述這個矩陣變化方向（從主要的變化到次要的變化排列）。

也就是說矩陣A的信息可以由其特徵值和特徵向量表示。

對於矩陣為高維的情況下，那麼這個矩陣就是高維空間下的一個線性變換。可以想像，這個變換也同樣有很多的變換方向，我們通過特徵值分解得到的前N個特徵向量，那麼就對應了這個矩陣最主要的N個變化方向。我們利用這前N個變化方向，就可以近似這個矩陣（變換）。

總結一下，特徵值分解可以得到特徵值與特徵向量，特徵值表示的是這個特徵到底有多重要，而特徵向量表示這個特徵是什麼。不過，特徵值分解也有很多的局限，比如說變換的矩陣必須是方陣。

奇異值分解

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

假設A是一個N * M的矩陣，那麼得到的U是一個N * N的方陣（裡面的向量是正交的，U裡面的向量稱為左奇異向量），Σ是一個N * M的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值），V』(V的轉置)是一個N * N的矩陣，裡面的向量也是正交的，V裡面的向量稱為右奇異向量），從圖片來反映幾個相乘的矩陣的大小可得下面的圖片：

三個矩陣有非常清楚的物理含義。

第一個矩陣X中的每一行表示意思相關的一類詞，其中的每個非零元素表示這類詞中每個詞的重要性（或者說相關性），數值越大越相關。最後一個矩陣Y中的每一列表示同一主題一類文章，其中每個元素表示這類文章中每篇文章的相關性。中間的矩陣則表示類詞和文章雷之間的相關性。因此，我們只要對關聯矩陣A進行一次奇異值分解，w 我們就可以同時完成了近義詞分類和文章的分類。（同時得到每類文章和每類詞的相關性）。

例子

對物品進行推薦，某些用戶買了某些東西，要來算出，物品跟物品之間的相識度，這是很常見的推薦問題，用 SVD 演算法，在 python中numpy 的 linalg 可以計算矩陣的 SVD。分解完矩陣就可以用距離演算法或者其他，可以求出相識性。

代碼如下：

奇異值與潛在語義索引LSI

Latent Semantic Analysis (LSA)也被叫做Latent Semantic Indexing (LSI)，從字面上的意思理解就是通過分析文檔去發現這些文檔中潛在的意思和概念。假設每個詞僅表示一個概念，並且每個概念僅僅被一個詞所描述，LSA將非常簡單（從詞到概念存在一個簡單的映射關係）

不幸的是，這個問題並沒有如此簡單，因為存在不同的詞表示同一個意思（同義詞），一個詞表示多個意思，所有這種二義性（多義性）都會混淆概念以至於有時就算是人也很難理解。

潛語義分析（Latent Semantic Analysis）源自問題：如何從搜索query中找到相關的文檔。當我們試圖通過比較詞來找到相關的文本時，存在著難以解決的局限性，那就是在搜索中我們實際想要去比較的不是詞，而是隱藏在詞之後的意義和概念。潛語義分析試圖去解決這個問題，它把詞和文檔都映射到一個『概念』空間並在這個空間內進行比較（註：也就是一種降維技術）。

為了讓這個難題更好解決，LSA引入一些重要的簡化：

文檔被表示為」一堆詞（bags of words）」，因此詞在文檔中出現的位置並不重要，只有一個詞的出現次數。
概念被表示成經常出現在一起的一些詞的某種模式。例如「leash」（栓狗的皮帶）、「treat」、「obey」（服從）經常出現在關於訓練狗的文檔中。
詞被認為只有一個意思。這個顯然會有反例（bank表示河岸或者金融機構），但是這可以使得問題變得更加容易。（這個簡化會有怎樣的缺陷呢？）

這就是一個矩陣，不過不太一樣的是，這裡的一行表示一個詞在哪些title中出現了（一行就是之前說的一維feature），一列表示一個title中有哪些詞，（這個矩陣其實是我們之前說的那種一行是一個sample的形式的一種轉置，這個會使得我們的左右奇異向量的意義產生變化，但是不會影響我們計算的過程）。比如說T1這個title中就有guide、investing、market、stock四個詞，各出現了一次，我們將這個矩陣進行SVD，得到下面的矩陣：

左奇異向量表示詞的一些特性，右奇異向量表示文檔的一些特性，中間的奇異值矩陣表示左奇異向量的一行與右奇異向量的一列的重要程序，數字越大越重要。

繼續看這個矩陣還可以發現一些有意思的東西，首先，左奇異向量的第一列表示每一個詞的出現頻繁程度，雖然不是線性的，但是可以認為是一個大概的描述，比如book是0.15對應文檔中出現的2次，investing是0.74對應了文檔中出現了9次，rich是0.36對應文檔中出現了3次；

其次，右奇異向量中一的第一行表示每一篇文檔中的出現詞的個數的近似，比如說，T6是0.49，出現了5個詞，T2是0.22，出現了2個詞。

然後我們反過頭來看，我們可以將左奇異向量和右奇異向量都取後2維（之前是3維的矩陣），投影到一個平面上，可以得到：

在圖上，每一個紅色的點，都表示一個詞，每一個藍色的點，都表示一篇文檔，這樣我們可以對這些詞和文檔進行聚類，比如說stock 和 market可以放在一類，因為他們老是出現在一起，real和estate可以放在一類，dads，guide這種詞就看起來有點孤立了，我們就不對他們進行合併了。按這樣聚類出現的效果，可以提取文檔集合中的近義詞，這樣當用戶檢索文檔的時候，是用語義級別（近義詞集合）去檢索了，而不是之前的詞的級別。這樣一減少我們的檢索、存儲量，因為這樣壓縮的文檔集合和PCA是異曲同工的，二可以提高我們的用戶體驗，用戶輸入一個詞，我們可以在這個詞的近義詞的集合中去找，這是傳統的索引無法做到的。

代碼如下：

MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS

MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS是一種類似於SVD的推薦演算法。它是一種學習演算法。

假如要預測Zero君對一部電影M的評分，而手上只有Zero君對若干部電影的評分和風炎君對若干部電影的評分（包含M的評分）。那麼能預測出Zero君對M的評分嗎？答案顯然是能。最簡單的方法就是直接將預測分定為平均分。不過這時的準確度就難說了。本文將介紹一種比這個最簡單的方法要准上許多，並且也不算複雜的演算法。

根據已有的評分情況，分析出評分者對各個因子的喜好程度以及電影包含各個因子的程度，最後再反過來根據分析結果預測評分。電影中的因子可以理解成這些東西：電影的搞笑程度，電影的愛情愛得死去活來的程度，電影的恐怖程度。。。。。。SVD的想法抽象點來看就是將一個N行M列的評分矩陣R（R[u][i]代表第u個用戶對第i個物品的評分），分解成一個N行F列的用戶因子矩陣P（P[u][k]表示用戶u對因子k的喜好程度）和一個M行F列的物品因子矩陣Q（Q[i][k]表示第i個物品的因子k的程度）。用公式來表示就是

R = P * T(Q) //T(Q)表示Q矩陣的轉置

下面是將評分矩陣R分解成用戶因子矩陣P與物品因子矩陣Q的一個例子。R的元素數值越大，表示用戶越喜歡這部電影。P的元素數值越大，表示用戶越喜歡對應的因子。Q的元素數值越大，表示物品對應的因子程度越高。分解完後，就能利用P，Q來預測Zero君對《七夜》的評分了。按照這個例子來看，Zero君應該會給《七夜》較低的分數。因為他不喜歡恐怖片。注意不要糾結圖中的具體數值，因為那些數值是我隨便填上去的。

實際上，我們給一部電影評分時，除了考慮電影是否合自己口味外，還會受到自己是否是一個嚴格的評分者和這部電影已有的評分狀況影響。例如：一個嚴格評分者給的分大多數情況下都比一個寬鬆評分者的低。你看到這部電影的評分大部分較高時，可能也傾向於給較高的分。在SVD中，口味問題已經有因子來表示了，但是剩下兩個還沒有相關的式子表示。因此有必要加上相關的部分，提高模型的精準度。改進後的SVD的公式如下： R = OverallMean + biasU + biasI + P * T(Q)　　　　（1）其中OverallMean表示所有電影的平均分，biasU表示用戶評分偏離OverallMean的程度，biasI表示電影評分偏離OverallMean的程度，P，Q意思不變。特別注意，這裡除了OverallMean之後，其它幾個都是矩陣。

這就就是一個最優值優化問題了。

tensorflow 代碼如下：

aHR0cDovL3dlaXhpbi5xcS5jb20vci9Xa01DR3F2RW9QYmZyZTk1OXhaSQ== (二維碼自動識別)