原文鏈接
前言：
上一次寫了關(guān)于PCA與LDA的文章圣勒，PCA的實現(xiàn)一般有兩種，一種是用特征值分解去實現(xiàn)的摧扇，一種是用奇異值分解去實現(xiàn)的圣贸。在上篇文章中便是基于特征值分解的一種解釋。特征值和奇異值在大部分人的印象中扛稽，往往是停留在純粹的數(shù)學計算中吁峻。而且線性代數(shù)或者矩陣論里面，也很少講任何跟特征值與奇異值有關(guān)的應(yīng)用背景在张。奇異值分解是一個有著很明顯的物理意義的一種方法用含，它可以將一個比較復(fù)雜的矩陣用更小更簡單的幾個子矩陣的相乘來表示，這些小矩陣描述的是矩陣的重要的特性帮匾。就像是描述一個人一樣啄骇，給別人描述說這個人長得濃眉大眼，方臉瘟斜，絡(luò)腮胡缸夹，而且?guī)€黑框的眼鏡，這樣寥寥的幾個特征螺句，就讓別人腦海里面就有一個較為清楚的認識虽惭，實際上，人臉上的特征是有著無數(shù)種的蛇尚，之所以能這么描述芽唇，是因為人天生就有著非常好的抽取重要特征的能力，讓機器學會抽取重要的特征佣蓉，SVD是一個重要的方法披摄。
在機器學習領(lǐng)域亲雪，有相當多的應(yīng)用與奇異值都可以扯上關(guān)系，比如做feature reduction的PCA疚膊，做數(shù)據(jù)壓縮（以圖像壓縮為代表）的算法义辕，還有做搜索引擎語義層次檢索的LSI（Latent Semantic Indexing）
另外在這里抱怨一下，之前在百度里面搜索過SVD寓盗，出來的結(jié)果都是俄羅斯的一種狙擊槍（AK47同時代的）灌砖，是因為穿越火線這個游戲里面有一把狙擊槍叫做SVD，而在Google上面搜索的時候傀蚌，出來的都是奇異值分解（英文資料為主）基显。想玩玩戰(zhàn)爭游戲，玩玩COD不是非常好嗎善炫，玩山寨的CS有神馬意思啊撩幽。國內(nèi)的網(wǎng)頁中的話語權(quán)也被這些沒有太多營養(yǎng)的帖子所占據(jù)。真心希望國內(nèi)的氣氛能夠更濃一點箩艺，搞游戲的人真正是喜歡制作游戲窜醉，搞Data Mining的人是真正喜歡挖數(shù)據(jù)的，都不是僅僅為了混口飯吃艺谆，這樣談超越別人才有意義榨惰，中文文章中，能踏踏實實談?wù)劶夹g(shù)的太少了静汤，改變這個狀況琅催，從我自己做起吧。
前面說了這么多虫给，本文主要關(guān)注奇異值的一些特性藤抡，另外還會稍稍提及奇異值的計算，不過本文不準備在如何計算奇異值上展開太多狰右。另外杰捂，本文里面有部分不算太深的線性代數(shù)的知識，如果完全忘記了線性代數(shù)棋蚌，看本文可能會有些困難嫁佳。
一、奇異值與特征值基礎(chǔ)知識：
特征值分解和奇異值分解在機器學習領(lǐng)域都是屬于滿地可見的方法谷暮。兩者有著很緊密的關(guān)系蒿往，我在接下來會談到，特征值分解和奇異值分解的目的都是一樣湿弦，就是提取出一個矩陣最重要的特征瓤漏。先談?wù)勌卣髦捣纸獍桑?/p>
1）特征值：
如果說一個向量v是方陣A的特征向量，將一定可以表示成下面的形式：
這時候λ就被稱為特征向量v對應(yīng)的特征值，一個矩陣的一組特征向量是一組正交向量蔬充。特征值分解是將一個矩陣分解成下面的形式：
其中Q是這個矩陣A的特征向量組成的矩陣蝶俱，Σ是一個對角陣，每一個對角線上的元素就是一個特征值饥漫。我這里引用了一些參考文獻中的內(nèi)容來說明一下榨呆。首先，要明確的是庸队，一個矩陣其實就是一個線性變換积蜻，因為一個矩陣乘以一個向量后得到的向量，其實就相當于將這個向量進行了線性變換彻消。比如說下面的一個矩陣：
它其實對應(yīng)的線性變換是下面的形式： 因為這個矩陣M乘以一個向量(x,y)的結(jié)果是： 上面的矩陣是對稱的竿拆，所以這個變換是一個對x，y軸的方向一個拉伸變換（每一個對角線上的元素將會對一個維度進行拉伸變換宾尚，當值>1時丙笋，是拉長，當值<1時時縮短）煌贴，當矩陣不是對稱的時候不见，假如說矩陣是下面的樣子：
它所描述的變換是下面的樣子：
這其實是在平面上對一個軸進行的拉伸變換（如藍色的箭頭所示），在圖中崔步，藍色的箭頭是一個最主要的變化方向（變化方向可能有不止一個），如果我們想要描述好一個變換缎谷，那我們就描述好這個變換主要的變化方向就好了井濒。反過頭來看看之前特征值分解的式子，分解得到的Σ矩陣是一個對角陣列林，里面的特征值是由大到小排列的瑞你，這些特征值所對應(yīng)的特征向量就是描述這個矩陣變化方向（從主要的變化到次要的變化排列）
當矩陣是高維的情況下，那么這個矩陣就是高維空間下的一個線性變換希痴，這個線性變化可能沒法通過圖片來表示者甲，但是可以想象，這個變換也同樣有很多的變換方向砌创，我們通過特征值分解得到的前N個特征向量虏缸，那么就對應(yīng)了這個矩陣最主要的N個變化方向。我們利用這前N個變化方向嫩实，就可以近似這個矩陣（變換）刽辙。也就是之前說的：提取這個矩陣最重要的特征。總結(jié)一下甲献，特征值分解可以得到特征值與特征向量宰缤，特征值表示的是這個特征到底有多重要，而特征向量表示這個特征是什么，可以將每一個特征向量理解為一個線性的子空間慨灭，我們可以利用這些線性的子空間干很多的事情朦乏。不過，特征值分解也有很多的局限氧骤，比如說變換的矩陣必須是方陣呻疹。
（說了這么多特征值變換，不知道有沒有說清楚语淘，請各位多提提意見诲宇。）
2）奇異值：
下面談?wù)勂娈愔捣纸狻Ｌ卣髦捣纸馐且粋€提取矩陣特征很不錯的方法惶翻，但是它只是對方陣而言的姑蓝，在現(xiàn)實的世界中，我們看到的大部分矩陣都不是方陣吕粗，比如說有N個學生纺荧，每個學生有M科成績，這樣形成的一個N * M的矩陣就不可能是方陣颅筋，我們怎樣才能描述這樣普通的矩陣呢的重要特征呢宙暇？奇異值分解可以用來干這個事情，奇異值分解是一個能適用于任意的矩陣的一種分解的方法：
那么奇異值和特征值是怎么對應(yīng)起來的呢？首先谐宙，我們將一個矩陣A的轉(zhuǎn)置 * A烫葬，將會得到一個方陣，我們用這個方陣求特征值可以得到：
這里得到的v凡蜻，就是我們上面的右奇異向量搭综。此外我們還可以得到： 這里的σ就是上面說的奇異值，u就是上面說的左奇異向量划栓。奇異值σ跟特征值類似设凹，在矩陣Σ中也是從大到小排列，而且σ的減少特別的快茅姜，在很多情況下闪朱，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了月匣。也就是說，我們也可以用前r大的奇異值來近似描述矩陣奋姿，這里定義一下部分奇異值分解：
r是一個遠小于m锄开、n的數(shù)，這樣矩陣的乘法看起來像是下面的樣子：
右邊的三個矩陣相乘的結(jié)果將會是一個接近于A的矩陣称诗，在這兒萍悴，r越接近于n，則相乘的結(jié)果越接近于A寓免。而這三個矩陣的面積之和（在存儲觀點來說癣诱，矩陣面積越小，存儲量就越型嘞恪）要遠遠小于原始的矩陣A撕予，我們?nèi)绻胍獕嚎s空間來表示原矩陣A，我們存下這里的三個矩陣：U蜈首、Σ实抡、V就好了。
二欢策、奇異值的計算：
奇異值的計算是一個難題吆寨，是一個O(N^3)的算法。在單機的情況下當然是沒問題的踩寇，matlab在一秒鐘內(nèi)就可以算出1000 * 1000的矩陣的所有奇異值啄清，但是當矩陣的規(guī)模增長的時候，計算的復(fù)雜度呈3次方增長俺孙，就需要并行計算參與了盒延。Google的吳軍老師在數(shù)學之美系列談到SVD的時候，說起Google實現(xiàn)了SVD的并行化算法鼠冕，說這是對人類的一個貢獻，但是也沒有給出具體的計算規(guī)模胯盯，也沒有給出太多有價值的信息懈费。
其實SVD還是可以用并行的方式去實現(xiàn)的，在解大規(guī)模的矩陣的時候博脑，一般使用迭代的方法憎乙，當矩陣的規(guī)模很大（比如說上億）的時候，迭代的次數(shù)也可能會上億次叉趣，如果使用Map-Reduce框架去解泞边，則每次Map-Reduce完成的時候，都會涉及到寫文件疗杉、讀文件的操作阵谚。個人猜測Google云計算體系中除了Map-Reduce以外應(yīng)該還有類似于MPI的計算模型蚕礼，也就是節(jié)點之間是保持通信，數(shù)據(jù)是常駐在內(nèi)存中的梢什，這種計算模型比Map-Reduce在解決迭代次數(shù)非常多的時候奠蹬，要快了很多倍。
Lanczos迭代就是一種解對稱方陣部分特征值的方法（之前談到了嗡午，解A’* A得到的對稱方陣的特征值就是解A的右奇異向量）囤躁，是將一個對稱的方程化為一個三對角矩陣再進行求解。按網(wǎng)上的一些文獻來看荔睹，Google應(yīng)該是用這種方法去做的奇異值分解的狸演。請見Wikipedia上面的一些引用的論文，如果理解了那些論文僻他，也“幾乎”可以做出一個SVD了宵距。
由于奇異值的計算是一個很枯燥，純數(shù)學的過程中姜，而且前人的研究成果（論文中）幾乎已經(jīng)把整個程序的流程圖給出來了消玄。更多的關(guān)于奇異值計算的部分，將在后面的參考文獻中給出丢胚，這里不再深入翩瓜，我還是focus在奇異值的應(yīng)用中去。
三携龟、奇異值與主成分分析（PCA）：
主成分分析在上一節(jié)里面也講了一些兔跌，這里主要談?wù)勅绾斡肧VD去解PCA的問題。PCA的問題其實是一個基的變換峡蟋，使得變換后的數(shù)據(jù)有著最大的方差坟桅。方差的大小描述的是一個變量的信息量，我們在講一個東西的穩(wěn)定性的時候蕊蝗，往往說要減小方差仅乓，如果一個模型的方差很大，那就說明模型不穩(wěn)定了蓬戚。但是對于我們用于機器學習的數(shù)據(jù)（主要是訓練數(shù)據(jù)）夸楣，方差大才有意義，不然輸入的數(shù)據(jù)都是同一個點子漩，那方差就為0了豫喧，這樣輸入的多個數(shù)據(jù)就等同于一個數(shù)據(jù)了。以下面這張圖為例子：
這個假設(shè)是一個攝像機采集一個物體運動得到的圖片幢泼，上面的點表示物體運動的位置紧显，假如我們想要用一條直線去擬合這些點，那我們會選擇什么方向的線呢缕棵？當然是圖上標有signal的那條線孵班。如果我們把這些點單純的投影到x軸或者y軸上涉兽，最后在x軸與y軸上得到的方差是相似的（因為這些點的趨勢是在45度左右的方向，所以投影到x軸或者y軸上都是類似的）重父，如果我們使用原來的xy坐標系去看這些點花椭，容易看不出來這些點真正的方向是什么。但是如果我們進行坐標系的變化房午，橫軸變成了signal的方向矿辽，縱軸變成了noise的方向，則就很容易發(fā)現(xiàn)什么方向的方差大郭厌，什么方向的方差小了袋倔。
一般來說，方差大的方向是信號的方向折柠，方差小的方向是噪聲的方向宾娜，我們在數(shù)據(jù)挖掘中或者數(shù)字信號處理中，往往要提高信號與噪聲的比例扇售，也就是信噪比前塔。對上圖來說，如果我們只保留signal方向的數(shù)據(jù)承冰，也可以對原數(shù)據(jù)進行不錯的近似了华弓。
PCA的全部工作簡單點說，就是對原始的空間中順序地找一組相互正交的坐標軸困乒，第一個軸是使得方差最大的寂屏，第二個軸是在與第一個軸正交的平面中使得方差最大的，第三個軸是在與第1娜搂、2個軸正交的平面中方差最大的迁霎，這樣假設(shè)在N維空間中，我們可以找到N個這樣的坐標軸百宇，我們?nèi)∏皉個去近似這個空間考廉，這樣就從一個N維的空間壓縮到r維的空間了，但是我們選擇的r個坐標軸能夠使得空間的壓縮使得數(shù)據(jù)的損失最小携御。
還是假設(shè)我們矩陣每一行表示一個樣本昌粤，每一列表示一個feature，用矩陣的語言來表示因痛，將一個m * n的矩陣A的進行坐標軸的變化，P就是一個變換的矩陣從一個N維的空間變換到另一個N維的空間岸更，在空間中就會進行一些類似于旋轉(zhuǎn)鸵膏、拉伸的變化。
而將一個m * n的矩陣A變換成一個m * r的矩陣怎炊，這樣就會使得本來有n個feature的谭企，變成了有r個feature了（r < n)廓译，這r個其實就是對n個feature的一種提煉，我們就把這個稱為feature的壓縮债查。用數(shù)學語言表示就是：
但是這個怎么和SVD扯上關(guān)系呢非区？之前談到，SVD得出的奇異向量也是從奇異值由大到小排列的盹廷，按PCA的觀點來看征绸，就是方差最大的坐標軸就是第一個奇異向量，方差次大的坐標軸就是第二個奇異向量…我們回憶一下之前得到的SVD式子： 在矩陣的兩邊同時乘上一個矩陣V俄占，由于V是一個正交的矩陣管怠，所以V轉(zhuǎn)置乘以V得到單位陣I，所以可以化成后面的式子 將后面的式子與A * P那個m * n的矩陣變換為m * r的矩陣的式子對照看看缸榄，在這里渤弛，其實V就是P，也就是一個變化的向量甚带。這里是將一個m * n 的矩陣壓縮到一個m * r的矩陣她肯，也就是對列進行壓縮，如果我們想對行進行壓縮（在PCA的觀點下鹰贵，對行進行壓縮可以理解為晴氨，將一些相似的sample合并在一起，或者將一些沒有太大價值的sample去掉）怎么辦呢砾莱？同樣我們寫出一個通用的行壓縮例子： 這樣就從一個m行的矩陣壓縮到一個r行的矩陣了瑞筐，對SVD來說也是一樣的，我們對SVD分解的式子兩邊乘以U的轉(zhuǎn)置U' 這樣我們就得到了對行進行壓縮的式子腊瑟【奂伲可以看出，其實PCA幾乎可以說是對SVD的一個包裝闰非，如果我們實現(xiàn)了SVD膘格，那也就實現(xiàn)了PCA了，而且更好的地方是财松，有了SVD瘪贱，我們就可以得到兩個方向的PCA，如果我們對A’A進行特征值的分解辆毡，只能得到一個方向的PCA菜秦。
四、奇異值與潛在語義索引LSI：
潛在語義索引（Latent Semantic Indexing）與PCA不太一樣舶掖，至少不是實現(xiàn)了SVD就可以直接用的球昨，不過LSI也是一個嚴重依賴于SVD的算法，之前吳軍老師在矩陣計算與文本處理中的分類問題中談到：
-
“三個矩陣有非常清楚的物理含義眨攘。第一個矩陣X中的每一行表示意思相關(guān)的一類詞主慰，其中的每個非零元素表示這類詞中每個詞的重要性（或者說相關(guān)性）嚣州，數(shù)值越大越相關(guān)。最后一個矩陣Y中的每一列表示同一主題一類文章共螺，其中每個元素表示這類文章中每篇文章的相關(guān)性该肴。中間的矩陣則表示類詞和文章雷之間的相關(guān)性。因此藐不，我們只要對關(guān)聯(lián)矩陣A進行一次奇異值分解匀哄，w 我們就可以同時完成了近義詞分類和文章的分類。（同時得到每類文章和每類詞的相關(guān)性）佳吞」俺”*
上面這段話可能不太容易理解，不過這就是LSI的精髓內(nèi)容底扳，我下面舉一個例子來說明一下铸抑，下面的例子來自LSA tutorial，具體的網(wǎng)址我將在最后的引用中給出：
繼續(xù)看這個矩陣還可以發(fā)現(xiàn)一些有意思的東西，首先像樊，左奇異向量的第一列表示每一個詞的出現(xiàn)頻繁程度尤莺，雖然不是線性的，但是可以認為是一個大概的描述生棍，比如book是0.15對應(yīng)文檔中出現(xiàn)的2次颤霎，investing是0.74對應(yīng)了文檔中出現(xiàn)了9次，rich是0.36對應(yīng)文檔中出現(xiàn)了3次；
其次捷绑，右奇異向量中一的第一行表示每一篇文檔中的出現(xiàn)詞的個數(shù)的近似，比如說氢妈，T6是0.49粹污，出現(xiàn)了5個詞，T2是0.22首量，出現(xiàn)了2個詞壮吩。
然后我們反過頭來看，我們可以將左奇異向量和右奇異向量都取后2維（之前是3維的矩陣）加缘，投影到一個平面上鸭叙，可以得到：
在圖上，每一個紅色的點拣宏，都表示一個詞沈贝，每一個藍色的點，都表示一篇文檔勋乾，這樣我們可以對這些詞和文檔進行聚類，比如說stock 和 market可以放在一類，因為他們老是出現(xiàn)在一起碱璃，real和estate可以放在一類计济，dads，guide這種詞就看起來有點孤立了各吨，我們就不對他們進行合并了枝笨。按這樣聚類出現(xiàn)的效果，可以提取文檔集合中的近義詞揭蜒，這樣當用戶檢索文檔的時候横浑，是用語義級別（近義詞集合）去檢索了，而不是之前的詞的級別忌锯。這樣一減少我們的檢索伪嫁、存儲量，因為這樣壓縮的文檔集合和PCA是異曲同工的偶垮，二可以提高我們的用戶體驗张咳，用戶輸入一個詞，我們可以在這個詞的近義詞的集合中去找似舵，這是傳統(tǒng)的索引無法做到的脚猾。
不知道按這樣描述，再看看吳軍老師的文章砚哗，是不是對SVD更清楚了龙助？:-D
參考資料：
1）A Tutorial on Principal Component Analysis, Jonathon Shlens
這是我關(guān)于用SVD去做PCA的主要參考資料
2）http://www.ams.org/samplings/feature-column/fcarc-svd
關(guān)于svd的一篇概念好文，我開頭的幾個圖就是從這兒截取的
3）http://www.puffinwarellc.com/index.php/news-and-articles/articles/30-singular-value-decomposition-tutorial.html
另一篇關(guān)于svd的入門好文
4）http://www.puffinwarellc.com/index.php/news-and-articles/articles/33-latent-semantic-analysis-tutorial.html
svd與LSI的好文，我后面LSI中例子就是來自此
5）http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-1-understanding.html
另一篇svd與LSI的文章提鸟，也還是不錯军援，深一點，也比較長
6）Singular Value Decomposition and Principal Component Analysis, Rasmus Elsborg Madsen, Lars Kai Hansen and Ole Winther, 2004
跟1）里面的文章比較類似
