數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)中的一些數(shù)學(xué)方法

1、FROM:http:/leftnoteasycnblogscom/機(jī)器學(xué)習(xí)中的數(shù)學(xué)(1)-回歸(regression)、梯度下降(gradientdescent)版權(quán)聲明：本文由LeftNotEasy所有，發(fā)布于 HYPERLINK 。如果轉(zhuǎn)載，請(qǐng)注明出處，在未經(jīng)作者同意下將本文用于商業(yè)用途，將追究其法律責(zé)任。前言:上次寫過一篇關(guān)于貝葉斯概率論的數(shù)學(xué)，最近時(shí)間比較緊，coding的任務(wù)比較重，不過還是抽空看了一些機(jī)器學(xué)習(xí)的書和視頻，其中很推薦兩個(gè)：一個(gè)是stanford的machinelearning公開課，在verycd可下載，可惜沒有翻譯。不過還是可以看。另外一個(gè)是prml-pattern

2、recognitionandmachinelearning,Bishop的一部反響不錯(cuò)的書，而且是2008年的，算是比較新的一本書了。前幾天還準(zhǔn)備寫一個(gè)分布式計(jì)算的系列，只寫了個(gè)開頭，又換到寫這個(gè)系列了。以后看哪邊的心得更多，就寫哪一個(gè)系列吧。最近干的事情比較雜，有跟機(jī)器學(xué)習(xí)相關(guān)的，有跟數(shù)學(xué)相關(guān)的，也有跟分布式相關(guān)的。這個(gè)系列主要想能夠用數(shù)學(xué)去描述機(jī)器學(xué)習(xí)，想要學(xué)好機(jī)器學(xué)習(xí)，首先得去理解其中的數(shù)學(xué)意義，不一定要到能夠輕松自如的推導(dǎo)中間的公式，不過至少得認(rèn)識(shí)這些式子吧，不然看一些相關(guān)的論文可就看不懂了，這個(gè)系列主要將會(huì)著重于去機(jī)器學(xué)習(xí)的數(shù)學(xué)描述這個(gè)部分，將會(huì)覆蓋但不一定局限于回歸、聚類、分類等算

3、法?；貧w與梯度下降：回歸在數(shù)學(xué)上來說是給定一個(gè)點(diǎn)集，能夠用一條曲線去擬合之，如果這個(gè)曲線是一條直線，那就被稱為線性回歸，如果曲線是一條二次曲線，就被稱為二次回歸，回歸還有很多的變種，如locallyweighted回歸，logistic回歸，等等，這個(gè)將在后面去講。用一個(gè)很簡(jiǎn)單的例子來說明回歸，這個(gè)例子來自很多的地方，也在很多的opensource的軟件中看到，比如說weka。大概就是，做一個(gè)房屋價(jià)值的評(píng)估系統(tǒng)，一個(gè)房屋的價(jià)值來自很多地方，比如說面積、房間的數(shù)量(幾室?guī)讖d)、地段、朝向等等，這些影響房屋價(jià)值的變量被稱為特征(feature),feature在機(jī)器學(xué)習(xí)中是一個(gè)很重要的概念，有很多

4、的論文專門探討這個(gè)東西。在此處，為了簡(jiǎn)單，假設(shè)我們的房屋就是一個(gè)變量影響的，就是房屋的面積。假設(shè)有一個(gè)房屋銷售的數(shù)據(jù)如下：面積(m2)銷售價(jià)錢(萬元)12325015032087160102220這個(gè)表類似于帝都5環(huán)左右的房屋價(jià)錢，我們可以做出一個(gè)圖，x軸是房屋的面積。y軸是房屋的售價(jià)，如下：如果來了一個(gè)新的面積，假設(shè)在銷售價(jià)錢的記錄中沒有的，我們?cè)趺崔k呢？我們可以用一條曲線去盡量準(zhǔn)的擬合這些數(shù)據(jù)，然后如果有新的輸入過來，我們可以在將曲線上這個(gè)點(diǎn)對(duì)應(yīng)的值返回。如果用一條直線去擬合，可能是下面的樣子：綠色的點(diǎn)就是我們想要預(yù)測(cè)的點(diǎn)。首先給出一些概念和常用的符號(hào)，在不同的機(jī)器學(xué)習(xí)書籍中可能有一定的差

5、別。房屋銷售記錄表-訓(xùn)練集(trainingset)或者訓(xùn)練數(shù)據(jù)(trainingdata),是我們流程中的輸入數(shù)據(jù)，一般稱為x房屋銷售價(jià)錢-輸出數(shù)據(jù)，一般稱為y擬合的函數(shù)(或者稱為假設(shè)或者模型)，一般寫做y=h(x)訓(xùn)練數(shù)據(jù)的條目數(shù)(#trainingset),一條訓(xùn)練數(shù)據(jù)是由一對(duì)輸入數(shù)據(jù)和輸出數(shù)據(jù)組成的輸入數(shù)據(jù)的維度(特征的個(gè)數(shù)，#features)，n下面是一個(gè)典型的機(jī)器學(xué)習(xí)的過程，首先給出一個(gè)輸入數(shù)據(jù)，我們的算法會(huì)通過一系列的過程得到一個(gè)估計(jì)的函數(shù)，這個(gè)函數(shù)有能力對(duì)沒有見過的新數(shù)據(jù)給出一個(gè)新的估計(jì)，也被稱為構(gòu)建一個(gè)模型。就如同上面的線性回歸函數(shù)。我們用X1,X2.Xn去描述featur

6、e里面的分量，比如x1=房間的面積，x2=房間的朝向，等等，我們可以做出一個(gè)估計(jì)函數(shù)：A(x)=(x)=6+ff2x29在這兒稱為參數(shù)，在這兒的意思是調(diào)整feature中每個(gè)分量的影響力，就是到底是房屋的面積更重要還是房屋的地段更重要。為了如果我們令X0=1,就可以用向量的方式來表示了：h&(x)=GTX我們程序也需要一個(gè)機(jī)制去評(píng)估我們9是否比較好，所以說需要對(duì)我們做出的h函數(shù)進(jìn)行評(píng)估一般這個(gè)函數(shù)稱為損失函數(shù)(lossfunction)或者錯(cuò)誤函數(shù)(errorfunction)，描述h函數(shù)不好的程度，在下面，我們稱這個(gè)函數(shù)為J函數(shù)在這兒我們可以做出下面的一個(gè)錯(cuò)誤函數(shù)：這個(gè)錯(cuò)誤估計(jì)函數(shù)是去對(duì)x(

7、i)的估計(jì)值與真實(shí)值y(i)差的平方和作為錯(cuò)誤估計(jì)函數(shù)，前面乘上的1/2是為了在求導(dǎo)的時(shí)候，這個(gè)系數(shù)就不見了。如何調(diào)整9以使得J(9)取得最小值有很多方法，其中有最小二乘法(minsquare)，是一種完全是數(shù)學(xué)描述的方法，在stanford機(jī)器學(xué)習(xí)開放課最后的部分會(huì)推導(dǎo)最小二乘法的公式的來源，這個(gè)來很多的機(jī)器學(xué)習(xí)和數(shù)學(xué)書上都可以找到，這里就不提最小二乘法，而談?wù)勌荻认陆捣?。梯度下降法是按下面的流程進(jìn)行的：首先對(duì)9賦值，這個(gè)值可以是隨機(jī)的，也可以讓9是一個(gè)全零的向量。改變9的值，使得J(9)按梯度下降的方向進(jìn)行減少。為了更清楚，給出下面的圖：GradientDescent這是一個(gè)表示參數(shù)e與誤

8、差函數(shù)J（e）的關(guān)系圖，紅色的部分是表示J（e）有著比較高的取值,我們需要的是，能夠讓J（e）的值盡量的低。也就是深藍(lán)色的部分。eo,ei表示e向量的兩個(gè)維度。在上面提到梯度下降法的第一步是給e給一個(gè)初值，假設(shè)隨機(jī)給的初值是在圖上的十字點(diǎn)。然后我們將e按照梯度下降的方向進(jìn)行調(diào)整，就會(huì)使得j（e）往更低的方向進(jìn)行變化，如圖所示，算法的結(jié)束將是在e下降到無法繼續(xù)下降為止。當(dāng)然，可能梯度下降的最終點(diǎn)并非是全局最小點(diǎn)，可能是一個(gè)局部最小點(diǎn)，可能是下面的情況：面這張圖就是描述的一個(gè)局部最小點(diǎn)，這是我們重新選擇了一個(gè)初始點(diǎn)得到的，看來我們這個(gè)算法將會(huì)在很大的程度上被初始點(diǎn)的選擇影響而陷入局部最小點(diǎn)下面我將

9、用一個(gè)例子描述一下梯度減少的過程，對(duì)于我們的函數(shù)J（e）求偏導(dǎo)j：（求導(dǎo)的過程如果不明白，可以溫習(xí)一下微積分）磊=話扭（福（力-刃2=（柘（X）-刃X下面是更新的過程，也就是ei會(huì)向著梯度最小的方向進(jìn)行減少。ei表示更新之前的值，-后面的部分表示按梯度方向減少的量，a表示步長(zhǎng)，也就是每次按照梯度減少的方向變化多少。=3一。務(wù)丿F一。）尹W一個(gè)很重要的地方值得注意的是，梯度是有方向的，對(duì)于一個(gè)向量e,每一維分量ei都可以求出一個(gè)梯度的方向，我們就可以找到一個(gè)整體的方向，在變化的時(shí)候，我們就朝著下降最多的方向進(jìn)行變化就可以達(dá)到一個(gè)最小點(diǎn)，不管它是局部的還是全局的。用更簡(jiǎn)單的數(shù)學(xué)語言進(jìn)行描述步驟2）

10、是這樣的：倒三角形表示梯度，按這種方式來表示，ei就不見了，看看用好向量和矩陣，真的會(huì)大大的簡(jiǎn)化數(shù)學(xué)的描述啊?？偨Y(jié)與預(yù)告：本文中的內(nèi)容主要取自stanford的課程第二集，希望我把意思表達(dá)清楚了：）本系列的下一篇文章也將會(huì)取自stanford課程的第三集，下一次將會(huì)深入的講講回歸、logistic回歸、和Newton法，不過本系列并不希望做成stanford課程的筆記版，再往后面就不一定完全與stanford課程保持一致了。機(jī)器學(xué)習(xí)中的數(shù)學(xué)（2）-線性回歸，偏差、方差權(quán)衡版權(quán)聲明：本文由LeftNotEasy所有，發(fā)布于。如果轉(zhuǎn)載，請(qǐng)注明出處，在未經(jīng)作者同意下將本文用于商業(yè)用途，將追究其法律責(zé)

11、任。如果有問題，請(qǐng)聯(lián)系作者 HYPERLINK mailto:wheeleast wheeleast前言：距離上次發(fā)文章，也快有半個(gè)月的時(shí)間了，這半個(gè)月的時(shí)間里又在學(xué)習(xí)機(jī)器學(xué)習(xí)的道路上摸索著前進(jìn)，積累了一點(diǎn)心得，以后會(huì)慢慢的寫寫這些心得。寫文章是促進(jìn)自己對(duì)知識(shí)認(rèn)識(shí)的一個(gè)好方法，看書的時(shí)候往往不是非常細(xì)，所以有些公式、知識(shí)點(diǎn)什么的就一帶而過，里面的一些具體意義就不容易理解了。而寫文章，特別是寫科普性的文章，需要對(duì)里面的具體意義弄明白，甚至還要能舉出更生動(dòng)的例子，這是一個(gè)挑戰(zhàn)。為了寫文章，往往需要把之前自己認(rèn)為看明白的內(nèi)容重新理解一下。機(jī)器學(xué)習(xí)可不是一個(gè)完全的技術(shù)性的東西，之前和部門老大在outi

12、ng的時(shí)候一直在聊這個(gè)問題，機(jī)器學(xué)習(xí)絕對(duì)不是一個(gè)一個(gè)孤立的算法堆砌起來的，想要像看算法導(dǎo)論這樣看機(jī)器學(xué)習(xí)是個(gè)不可取的方法，機(jī)器學(xué)習(xí)里面有幾個(gè)東西一直貫穿全書，比如說數(shù)據(jù)的分布、最大似然（以及求極值的幾個(gè)方法，不過這個(gè)比較數(shù)學(xué)了），偏差、方差的權(quán)衡，還有特征選擇，模型選擇，混合模型等等知識(shí)，這些知識(shí)像磚頭、水泥一樣構(gòu)成了機(jī)器學(xué)習(xí)里面的一個(gè)個(gè)的算法。想要真正學(xué)好這些算法，一定要靜下心來將這些基礎(chǔ)知識(shí)弄清楚，才能夠真正理解、實(shí)現(xiàn)好各種機(jī)器學(xué)習(xí)算法。今天的主題是線性回歸，也會(huì)提一下偏差、方差的均衡這個(gè)主題。線性回歸定義：在上一個(gè)主題中，也是一個(gè)與回歸相關(guān)的，不過上一節(jié)更側(cè)重于梯度這個(gè)概念，這一節(jié)更側(cè)重

13、于回歸本身與偏差和方差的概念?；貧w最簡(jiǎn)單的定義是，給出一個(gè)點(diǎn)集D,用一個(gè)函數(shù)去擬合這個(gè)點(diǎn)集，并且使得點(diǎn)集與擬合函數(shù)間的誤差最小。上圖所示，給出一個(gè)點(diǎn)集(x,y),需要用一個(gè)函數(shù)去擬合這個(gè)點(diǎn)集，藍(lán)色的點(diǎn)是點(diǎn)集中的點(diǎn)，而紅色的曲線是函數(shù)的曲線，第一張圖是一個(gè)最簡(jiǎn)單的模型，對(duì)應(yīng)的函數(shù)為y=f(x)=ax+b,這個(gè)就是一個(gè)線性函數(shù)，第二張圖是二次曲線，對(duì)應(yīng)的函數(shù)是y=f(x)=ax2+b。第三張圖我也不知道是什么函數(shù)，瞎畫的。第四張圖可以認(rèn)為是一個(gè)N次曲線，N=M-1M是點(diǎn)集中點(diǎn)的個(gè)數(shù)，有一個(gè)定理是，對(duì)于給定的M個(gè)點(diǎn)，我們可以用一個(gè)M-1次的函數(shù)去完美的經(jīng)過這個(gè)點(diǎn)集。真正的線性回歸，不僅會(huì)考慮使得曲線

14、與給定點(diǎn)集的擬合程度最好，還會(huì)考慮模型最簡(jiǎn)單，這個(gè)話題我們將在本章后面的偏差、方差的權(quán)衡中深入的說，另外這個(gè)話題還可以參考我之前的一篇文章：貝葉斯、概率分布與機(jī)器學(xué)習(xí)，里面對(duì)模型復(fù)雜度的問題也進(jìn)行了一些討論。線性回歸(linearregression)，并非是指的線性函數(shù)，也就是f(X)4=7X(.為了方便起噸，以后向量我就不在上面加箭頭了)x0,x1表示一個(gè)點(diǎn)不同的維度，比如說上一節(jié)中提到的，房子的價(jià)錢是由包括面積、房間的個(gè)數(shù)、房屋的朝向等等因素去決定的。而是用廣義的線性函數(shù)：y.-iH工悴)=wl=%+叫叭(工)尸Iwj是系數(shù)，w就是這個(gè)系數(shù)組成的向量，它影響著不同維度的j(x)在回歸函數(shù)

15、中的影響度，比如說對(duì)于房屋的售價(jià)來說，房間朝向的w一定比房間面積的w更小。(X)是可以換成不同的函數(shù)，不一定要求(x)=x，這樣的模型我們認(rèn)為是廣義線性模型。最小二乘法與最大似然：這個(gè)話題在此處有一個(gè)很詳細(xì)的討論，我這里主要談?wù)勥@個(gè)問題的理解。最小二乘法是線性回歸中一個(gè)最簡(jiǎn)單的方法，它的推導(dǎo)有一個(gè)假設(shè)，就是回歸函數(shù)的估計(jì)值與真實(shí)值間的誤差假設(shè)是一個(gè)高斯分布。這個(gè)用公式來表示是下面的樣子：；，y(x,w)就是給定了w系數(shù)向量下的回歸函數(shù)的估計(jì)值，而t就是真實(shí)值了，E表示誤差。我們可以接下來推出下面的式子：這是一個(gè)簡(jiǎn)單的條件概率表達(dá)式，表示在給定了x，w，B的情況下，得到真實(shí)值t的概率,由于e服從

16、高斯分布，則從估計(jì)值到真實(shí)值間的概率也是高斯分布的，看起來像下面的樣子：貝葉斯、概率分布與機(jī)器學(xué)習(xí)這篇文章中對(duì)分布影響結(jié)果這個(gè)話題討論比較多，可以回過頭去看看，由于最小二乘法有這樣一個(gè)假設(shè)，則會(huì)導(dǎo)致，如果我們給出的估計(jì)函數(shù)y(x,w)與真實(shí)值t不是高斯分布的，甚至是一個(gè)差距很大的分布，那么算出來的模型一定是不正確的，當(dāng)給定一個(gè)新的點(diǎn)x想要求出一個(gè)估計(jì)值y,與真實(shí)值t可能就非常的遠(yuǎn)了。概率分布是一個(gè)可愛又可恨的東西，當(dāng)我們能夠準(zhǔn)確的預(yù)知某些數(shù)據(jù)的分布時(shí)，那我們可以做出一個(gè)非常精確的模型去預(yù)測(cè)它，但是在大多數(shù)真實(shí)的應(yīng)用場(chǎng)景中，數(shù)據(jù)的分布是不可知的，我們也很難去用一個(gè)分布、甚至多個(gè)分布的混合去表示數(shù)

17、據(jù)的真實(shí)分布，比如說給定了1億篇網(wǎng)頁(yè)，希望用一個(gè)現(xiàn)有的分布(比如說混合高斯分布)去匹配里面詞頻的分布，是不可能的。在這種情況下，我們只能得到詞的出現(xiàn)概率，比如P(的)的概率是0.5,也就是一個(gè)網(wǎng)頁(yè)有1/2的概率出現(xiàn)“的”。如果一個(gè)算法，是對(duì)里面的分布進(jìn)行了某些假設(shè)，那么可能這個(gè)算法在真實(shí)的應(yīng)用中就會(huì)表現(xiàn)欠佳。最小二乘法對(duì)于類似的一個(gè)復(fù)雜問題，就很無力了偏差、方差的權(quán)衡(trade-off):偏差(bias)和方差(varianee)是統(tǒng)計(jì)學(xué)的概念，剛進(jìn)公司的時(shí)候，看到每個(gè)人的嘴里隨時(shí)蹦出這兩個(gè)詞，覺得很可怕。首先得明確的，方差是多個(gè)模型間的比較，而非對(duì)一個(gè)模型而言的，對(duì)于單獨(dú)的一個(gè)模型，比如說

18、:這樣的一個(gè)給定了具體系數(shù)的估計(jì)函數(shù)，是不能說f(x)的方差是多少。而偏差可以是單個(gè)數(shù)據(jù)集中的，也可以是多個(gè)數(shù)據(jù)集中的，這個(gè)得看具體的定義。方差和偏差一般來說，是從同一個(gè)數(shù)據(jù)集中，用科學(xué)的采樣方法得到幾個(gè)不同的子數(shù)據(jù)集，用這些子數(shù)據(jù)集得到的模型，就可以談他們的方差和偏差的情況了。方差和偏差的變化一般是和模型的復(fù)雜程度成正比的，就像本文一開始那四張小圖片一樣，當(dāng)我們一味的追求模型精確匹配，則可能會(huì)導(dǎo)致同一組數(shù)據(jù)訓(xùn)練出不同的模型，它們之間的差異非常大。這就叫做方差，不過他們的偏差就很小了，如下圖所示：上圖的藍(lán)色和綠色的點(diǎn)是表示一個(gè)數(shù)據(jù)集中采樣得到的不同的子數(shù)據(jù)集，我們有兩個(gè)N次的曲線去擬合這些點(diǎn)集

19、，則可以得到兩條曲線(藍(lán)色和深綠色)，它們的差異就很大，但是他們本是由同一個(gè)數(shù)據(jù)集生成的，這個(gè)就是模型復(fù)雜造成的方差大。模型越復(fù)雜，偏差就越小，而模型越簡(jiǎn)單，偏差就越大，方差和偏差是按下面的方式進(jìn)行變化的:當(dāng)方差和偏差加起來最優(yōu)的點(diǎn)，就是我們最佳的模型復(fù)雜度。用一個(gè)很通俗的例子來說，現(xiàn)在咱們國(guó)家一味的追求GDP，GDP就像是模型的偏差，國(guó)家希望現(xiàn)有的GDP和目標(biāo)的GDP差異盡量的小，但是其中使用了很多復(fù)雜的手段，比如說倒賣土地、強(qiáng)拆等等，這個(gè)增加了模型的復(fù)雜度，也會(huì)使得偏差（居民的收入分配）變大，窮的人越窮（被趕出城市的人與進(jìn)入城市買不起房的人），富的人越富（倒賣土地的人與賣房子的人）。其實(shí)本

20、來模型不需要這么復(fù)雜，能夠讓居民的收入分配與國(guó)家的發(fā)展取得一個(gè)平衡的模型是最好的模型。最后還是用數(shù)學(xué)的語言來描述一下偏差和方差：p（x.i）dxdtE（L）是損失函數(shù)，h（x）表示真實(shí)值的平均，第一部分是與y（模型的估計(jì)函數(shù)）有關(guān)的，這個(gè)部分是由于我們選擇不同的估計(jì)函數(shù)（模型）帶來的差異，而第二部分是與y無關(guān)的，這個(gè)部分可以認(rèn)為是模型的固有噪聲。對(duì)于上面公式的第一部分，我們可以化成下面的形式：這個(gè)部分在PRML的1.5.5推導(dǎo)，前一半是表示偏差，而后一半表示方差，我們可以得出：損失函數(shù)=偏差人2+方差+固有噪音。下圖也來自PRML：這是一個(gè)曲線擬合的問題，對(duì)同分布的不同的數(shù)據(jù)集進(jìn)行了多次的曲線

21、擬合，左邊表示方差，右邊表示偏差，綠色是真實(shí)值函數(shù)。Inlambda表示模型的復(fù)雜程度，這個(gè)值越小，表示模型的復(fù)雜程度越高，在第一行，大家的復(fù)雜度都很低（每個(gè)人都很窮）的時(shí)候，方差是很小的，但是偏差同樣很?。▏?guó)家也很窮），但是到了最后一幅圖，我們可以得到，每個(gè)人的復(fù)雜程度都很高的情況下，不同的函數(shù)就有著天壤之別了（貧富差異大），但是偏差就很小了（國(guó)家很富有）。機(jī)器學(xué)習(xí)中的數(shù)學(xué)（3）-模型組合（ModelCombining）之Boosting與GradientBoosting版權(quán)聲明：本文由LeftNotEasy發(fā)布于,本文可以被全部的轉(zhuǎn)載或者部分使用，但請(qǐng)注明出處，如果有問題，請(qǐng)聯(lián)系 HYPE

22、RLINK mailto:wheeleast wheeleast前言：本來上一章的結(jié)尾提到，準(zhǔn)備寫寫線性分類的問題，文章都已經(jīng)寫得差不多了，但是突然聽說最近Team準(zhǔn)備做一套分布式的分類器，可能會(huì)使用RandomForest來做，下了幾篇論文看了看，簡(jiǎn)單的randomforest還比較容易弄懂，復(fù)雜一點(diǎn)的還會(huì)與boosting等算法結(jié)合（參見iccv09），對(duì)于boosting也不甚了解，所以臨時(shí)抱佛腳的看了看。說起boosting,強(qiáng)哥之前實(shí)現(xiàn)過一套GradientBoostingDecisionTree（GBDT）算法，正好參考一下。最近看的一些論文中發(fā)現(xiàn)了模型組合的好處，比如GBDT或者

23、rf，都是將簡(jiǎn)單的模型組合起來，效果比單個(gè)更復(fù)雜的模型好。組合的方式很多，隨機(jī)化（比如randomforest），Boosting（比如GBDT）都是其中典型的方法，今天主要談?wù)凣radientBoosting方法（這個(gè)與傳統(tǒng)的Boosting還有一些不同）的一些數(shù)學(xué)基礎(chǔ)，有了這個(gè)數(shù)學(xué)基礎(chǔ)，上面的應(yīng)用可以看Freidman的GradientBoostingMachine。本文要求讀者學(xué)過基本的大學(xué)數(shù)學(xué)，另外對(duì)分類、回歸等基本的機(jī)器學(xué)習(xí)概念了解。本文主要參考資料是prml與GradientBoostingMachine。Boosting方法：Boosting這其實(shí)思想相當(dāng)?shù)暮?jiǎn)單，大概是，對(duì)一份數(shù)

24、據(jù)，建立M個(gè)模型（比如分類），一般這種模型比較簡(jiǎn)單，稱為弱分類器（weaklearner）每次分類都將上一次分錯(cuò)的數(shù)據(jù)權(quán)重提高一點(diǎn)再進(jìn)行分類，這樣最終得到的分類器在測(cè)試數(shù)據(jù)與訓(xùn)練數(shù)據(jù)上都可以得到比較好的成績(jī)。22O0O000OOO00000m=10上圖（圖片來自prmlp660）就是一個(gè)Boosting的過程，綠色的線表示目前取得的模型（模型是由前m次得到的模型合并得到的），虛線表示當(dāng)前這次模型。每次分類的時(shí)候，會(huì)更關(guān)注分錯(cuò)的數(shù)據(jù)，上圖中，紅色和藍(lán)色的點(diǎn)就是數(shù)據(jù)，點(diǎn)越大表示權(quán)重越高，看看右下角的圖片，當(dāng)m=150的時(shí)候，獲取的模型已經(jīng)幾乎能夠?qū)⒓t色和藍(lán)色的點(diǎn)區(qū)分開了。Boosting可以用下面

25、的公式來表示：M訓(xùn)練集中一共有n個(gè)點(diǎn)，我們可以為里面的每一個(gè)點(diǎn)賦上一個(gè)權(quán)重Wi(O=iYj,的時(shí)候，我們就說x屬于類別k。對(duì)于每一個(gè)分類，都有一個(gè)公式去算一個(gè)分值，在所有的公式得到的分值中，找一個(gè)最大的，就是所屬的分類了。上式實(shí)際上就是一種投影，是將一個(gè)高維的點(diǎn)投影到一條高維的直線上，LDA最求的目標(biāo)是，給出一個(gè)標(biāo)注了類別的數(shù)據(jù)集，投影到了一條直線之后，能夠使得點(diǎn)盡量的按類別區(qū)分開，當(dāng)k=2即二分類問題的時(shí)候，如下圖所示：紅色的方形的點(diǎn)為0類的原始點(diǎn)、藍(lán)色的方形點(diǎn)為1類的原始點(diǎn)，經(jīng)過原點(diǎn)的那條線就是投影的直線，從圖上可以清楚的看到，紅色的點(diǎn)和藍(lán)色的點(diǎn)被原點(diǎn)明顯的分開了，這個(gè)數(shù)據(jù)只是隨便畫的，如

26、果在高維的情況下，看起來會(huì)更好一點(diǎn)。下面我來推導(dǎo)一下二分類LDA問題的公式：假設(shè)用來區(qū)分二分類的直線（投影函數(shù)）為：LDA分類的一個(gè)目標(biāo)是使得不同類別之間的距離越遠(yuǎn)越好，同一類別之中的距離越近越好所以我們需要定義幾個(gè)關(guān)鍵的值。類別i的原始中心點(diǎn)為：（Di表示屬于類別i的點(diǎn)）類別i投影后的中心點(diǎn)為：衡量類別i投影后，類別點(diǎn)之間的分散程度（方差）為：彳=工（”-云）2最終我們可以得到一個(gè)下面的公式，表示LDA投影到w后的損失函數(shù):我們分類的目標(biāo)是，使得類別內(nèi)的點(diǎn)距離越近越好(集中)，類別間的點(diǎn)越遠(yuǎn)越好。分母表示每一個(gè)類別內(nèi)的方差之和，方差越大表示一個(gè)類別內(nèi)的點(diǎn)越分散，分子為兩個(gè)類別各自的中心點(diǎn)的距

27、離的平方，我們最大化J(w)就可以求出最優(yōu)的W了。想要求出最優(yōu)的W,可以使用拉格朗日乘子法，但是現(xiàn)在我們得到的J(w)里面，W是不能被單獨(dú)提出來的，我們就得想辦法將W單獨(dú)提出來。我們定義一個(gè)投影前的各類別分散程度的矩陣，這個(gè)矩陣看起來有一點(diǎn)麻煩，其實(shí)意思是，如果某一個(gè)分類的輸入點(diǎn)集Di里面的點(diǎn)距離這個(gè)分類的中心店mi越近，則Si里面元素的值就越小，如果分類的點(diǎn)都緊緊地圍繞著mi，則Si里面的元素值越更接近0.Sj=-叫)(工-叫y帶入Si,將J(w)分母化為：=工(vi/兀一列)=乞d(x叫)(x一Yw=hj/wX/)rxeDt$2+22=(S十SJw=W7SwW同樣的將J(w)分子化為：|2

28、=wi(朋-%)w=w1Sffw這樣損失函數(shù)可以化成下面的形式：這樣就可以用最喜歡的拉格朗日乘子法了，但是還有一個(gè)問題，如果分子、分母是都可以取任意值的，那就會(huì)使得有無窮解，我們將分母限制為長(zhǎng)度為1(這是用拉格朗日乘子法一個(gè)很重要的技巧，在下面將說的PCA里面也會(huì)用到，如果忘記了，請(qǐng)復(fù)習(xí)一下高數(shù))，并作為拉格朗日乘子法的限制條件，帶入得到：c(w)=wfSw-Siew-)=2Vv-2ZSm.w=0dwnSHw=AS.w這樣的式子就是一個(gè)求特征值的問題了。對(duì)于N(N2)分類的問題，我就直接寫出下面的結(jié)論了:siv=3%=弘血嗆（叫-刖i=i%甘叫=見比旳這同樣是一個(gè)求特征值的問題，我們求出的第i

29、大的特征向量，就是對(duì)應(yīng)的Wi了。這里想多談?wù)勌卣髦?，特征值在純?shù)學(xué)、量子力學(xué)、固體力學(xué)、計(jì)算機(jī)等等領(lǐng)域都有廣泛的應(yīng)用，特征值表示的是矩陣的性質(zhì)，當(dāng)我們?nèi)〉骄仃嚨那癗個(gè)最大的特征值的時(shí)候，我們可以說提取到的矩陣主要的成分（這個(gè)和之后的PCA相關(guān)，但是不是完全一樣的概念）。在機(jī)器學(xué)習(xí)領(lǐng)域，不少的地方都要用到特征值的計(jì)算，比如說圖像識(shí)別、pagerank、LDA、還有之后將會(huì)提到的PCA等等。下圖是圖像識(shí)別中廣泛用到的特征臉（eigenface），提取出特征臉有兩個(gè)目的，首先是為了壓縮數(shù)據(jù)，對(duì)于一張圖片，只需要保存其最重要的部分就是了，然后是為了使得程序更容易處理，在提取主要特征的時(shí)候，很多的噪聲都

30、被過濾掉了。跟下面將談到的PCA的作用非常相關(guān)。特征值的求法有很多，求一個(gè)D*D的矩陣的時(shí)間復(fù)雜度是0（D3）,也有一些求TopM的方法，比如說powermethod，它的時(shí)間復(fù)雜度是O（DT*M）,總體來說，求特征值是一個(gè)很費(fèi)時(shí)間的操作，如果是單機(jī)環(huán)境下，是很局限的。PCA：主成分分析（PCA）與LDA有著非常近似的意思，LDA的輸入數(shù)據(jù)是帶標(biāo)簽的，而PCA的輸入數(shù)據(jù)是不帶標(biāo)簽的，所以PCA是一種unsupervisedlearning。LDA通常來說是作為一個(gè)獨(dú)立的算法存在，給定了訓(xùn)練數(shù)據(jù)后，將會(huì)得到一系列的判別函數(shù)（discriminatefunction）,之后對(duì)于新的輸入，就可以進(jìn)行

31、預(yù)測(cè)了。而PCA更像是一個(gè)預(yù)處理的方法，它可以將原本的數(shù)據(jù)降低維度，而使得降低了維度的數(shù)據(jù)之間的方差最大（也可以說投影誤差最小，具體在之后的推導(dǎo)里面會(huì)談到）。方差這個(gè)東西是個(gè)很有趣的，有些時(shí)候我們會(huì)考慮減少方差（比如說訓(xùn)練模型的時(shí)候，我們會(huì)考慮到方差-偏差的均衡），有的時(shí)候我們會(huì)盡量的增大方差。方差就像是一種信仰（強(qiáng)哥的話），不一定會(huì)有很嚴(yán)密的證明，從實(shí)踐來說，通過盡量增大投影方差的PCA算法，確實(shí)可以提高我們的算法質(zhì)量。說了這么多，推推公式可以幫助我們理解。我下面將用兩種思路來推導(dǎo)出一個(gè)同樣的表達(dá)式。首先是最大化投影后的方差，其次是最小化投影后的損失（投影產(chǎn)生的損失最?。?。最大化方差法：假設(shè)

32、我們還是將一個(gè)空間中的點(diǎn)投影到一個(gè)向量中去。首先，給出原空間的中心點(diǎn)：假設(shè)U1為投影向量，投影之后的方差為：籟論-珂竊=可S叫上面這個(gè)式子如果看懂了之前推導(dǎo)LDA的過程，應(yīng)該比較容易理解，如果線性代數(shù)里面的內(nèi)容忘記了，可以再溫習(xí)一下，優(yōu)化上式等號(hào)右邊的內(nèi)容，還是用拉格朗日乘子法：+人（1嗎丁升）將上式求導(dǎo)，使之為0，得到：這是一個(gè)標(biāo)準(zhǔn)的特征值表達(dá)式了，入對(duì)應(yīng)的特征值，u對(duì)應(yīng)的特征向量。上式的左邊取得最大值的條件就是入1最大，也就是取得最大的特征值的時(shí)候。假設(shè)我們是要將一個(gè)D維的數(shù)據(jù)空間投影到M維的數(shù)據(jù)空間中（MD）,那我們?nèi)∏癕個(gè)特征向量構(gòu)成的投影矩陣就是能夠使得方差最大的矩陣了。最小化損失法

33、：假設(shè)輸入數(shù)據(jù)x是在D維空間中的點(diǎn)，那么，我們可以用D個(gè)正交的D維向量去完全的表示這個(gè)空間（這個(gè)空間中所有的向量都可以用這D個(gè)向量的線性組合得到）。在D維空間中，有無窮多種可能找這D個(gè)正交的D維向量，哪個(gè)組合是最合適的呢？假設(shè)我們已經(jīng)找到了這D個(gè)向量，可以得到：1我們可以用近似法來表示投影后的點(diǎn)：孫=工召網(wǎng)+2勺碼/-If-.V+l上式表示，得到的新的x是由前M個(gè)基的線性組合加上后D-M個(gè)基的線性組合，注意這里的Z是對(duì)于每個(gè)X都不同的，而b對(duì)于每個(gè)X是相同的，這樣我們就可以用M個(gè)數(shù)來表示空間中的一個(gè)點(diǎn)，也就是使得數(shù)據(jù)降維了。但是這樣降維后的數(shù)據(jù)，必然會(huì)產(chǎn)生一些扭曲，我們用J描述這種扭曲，我們的

34、目標(biāo)是，使得J最小：亦習(xí)比FII2上式的意思很直觀，就是對(duì)于每一個(gè)點(diǎn)，將降維后的點(diǎn)與原始的點(diǎn)之間的距離的平方和加起來，求平均值，我們就要使得這個(gè)平均值最小。我們令：將上面得到的z與b帶入降維的表達(dá)式：-D-%一總=S（%_現(xiàn)執(zhí)將上式帶入J的表達(dá)式得到：1NDyD/誌刀刀（心-人Y疥網(wǎng)再用上拉普拉斯乘子法（此處略），可以得到，取得我們想要的投影基的表達(dá)式為：這里又是一個(gè)特征值的表達(dá)式，我們想要的前M個(gè)向量其實(shí)就是這里最大的M個(gè)特征值所對(duì)應(yīng)的特征向量。證明這個(gè)還可以看看，我們J可以化為:也就是當(dāng)誤差J是由最小的D-M個(gè)特征值組成的時(shí)候，J取得最小值。跟上面的意思相同。下圖是PCA的投影的一個(gè)表示，

35、黑色的點(diǎn)是原始的點(diǎn)，帶箭頭的虛線是投影的向量，Pci表示特征值最大的特征向量，pc2表示特征值次大的特征向量，兩者是彼此正交的，因?yàn)檫@原本是一個(gè)2維的空間，所以最多有兩個(gè)投影的向量，如果空間維度更高，則投影的向量會(huì)更多?？偨Y(jié)：本次主要講了兩種方法，PCA與LDA,兩者的思想和計(jì)算方法非常類似，但是一個(gè)是作為獨(dú)立的算法存在，另一個(gè)更多的用于數(shù)據(jù)的預(yù)處理的工作。另外對(duì)于PCA和LDA還有核方法,本次的篇幅比較大了，先不說了，以后有時(shí)間再談：機(jī)器學(xué)習(xí)中的數(shù)學(xué)(5)-強(qiáng)大的矩陣奇異值分解(SVD)及其應(yīng)用版權(quán)聲明：本文由LeftNotEasy發(fā)布于,本文可以被全部的轉(zhuǎn)載或者部分使用，但請(qǐng)注明出處，如果

36、有問題，請(qǐng)聯(lián)系 HYPERLINK mailto:wheeleast wheeleast前言：上一次寫了關(guān)于PCA與LDA的文章，PCA的實(shí)現(xiàn)一般有兩種，一種是用特征值分解去實(shí)現(xiàn)的，一種是用奇異值分解去實(shí)現(xiàn)的。在上篇文章中便是基于特征值分解的一種解釋。特征值和奇異值在大部分人的印象中，往往是停留在純粹的數(shù)學(xué)計(jì)算中。而且線性代數(shù)或者矩陣論里面，也很少講任何跟特征值與奇異值有關(guān)的應(yīng)用背景。奇異值分解是一個(gè)有著很明顯的物理意義的一種方法，它可以將一個(gè)比較復(fù)雜的矩陣用更小更簡(jiǎn)單的幾個(gè)子矩陣的相乘來表示，這些小矩陣描述的是矩陣的重要的特性。就像是描述一個(gè)人一樣，給別人描述說這個(gè)人長(zhǎng)得濃眉大眼，方臉，絡(luò)腮

37、胡，而且?guī)€(gè)黑框的眼鏡，這樣寥寥的幾個(gè)特征，就讓別人腦海里面就有一個(gè)較為清楚的認(rèn)識(shí)，實(shí)際上，人臉上的特征是有著無數(shù)種的，之所以能這么描述，是因?yàn)槿颂焐陀兄浅：玫某槿≈匾卣鞯哪芰?，讓機(jī)器學(xué)會(huì)抽取重要的特征，SVD是一個(gè)重要的方法。在機(jī)器學(xué)習(xí)領(lǐng)域，有相當(dāng)多的應(yīng)用與奇異值都可以扯上關(guān)系，比如做featurereduction的PCA,做數(shù)據(jù)壓縮(以圖像壓縮為代表)的算法，還有做搜索引擎語義層次檢索的LSI(LatentSemanticIndexing)另外在這里抱怨一下，之前在百度里面搜索過SVD，出來的結(jié)果都是俄羅斯的一種狙擊槍(AK47同時(shí)代的)，是因?yàn)榇┰交鹁€這個(gè)游戲里面有一把狙擊槍叫做

38、SVD，而在Google上面搜索的時(shí)候，出來的都是奇異值分解（英文資料為主）。想玩玩戰(zhàn)爭(zhēng)游戲，玩玩COD不是非常好嗎，玩山寨的CS有神馬意思啊。國(guó)內(nèi)的網(wǎng)頁(yè)中的話語權(quán)也被這些沒有太多營(yíng)養(yǎng)的帖子所占據(jù)。真心希望國(guó)內(nèi)的氣氛能夠更濃一點(diǎn)，搞游戲的人真正是喜歡制作游戲，搞DataMining的人是真正喜歡挖數(shù)據(jù)的，都不是僅僅為了混口飯吃，這樣談超越別人才有意義，中文文章中，能踏踏實(shí)實(shí)談?wù)劶夹g(shù)的太少了，改變這個(gè)狀況，從我自己做起吧。前面說了這么多，本文主要關(guān)注奇異值的一些特性，另外還會(huì)稍稍提及奇異值的計(jì)算，不過本文不準(zhǔn)備在如何計(jì)算奇異值上展開太多。另外，本文里面有部分不算太深的線性代數(shù)的知識(shí)，如果完全忘記

39、了線性代數(shù)，看本文可能會(huì)有些困難。一、奇異值與特征值基礎(chǔ)知識(shí)：特征值分解和奇異值分解在機(jī)器學(xué)習(xí)領(lǐng)域都是屬于滿地可見的方法。兩者有著很緊密的關(guān)系，我在接下來會(huì)談到，特征值分解和奇異值分解的目的都是一樣，就是提取出一個(gè)矩陣最重要的特征。先談?wù)勌卣髦捣纸獍桑?）特征值：如果說一個(gè)向量v是方陣A的特征向量，將一定可以表示成下面的形式：這時(shí)候入就被稱為特征向量v對(duì)應(yīng)的特征值，一個(gè)矩陣的一組特征向量是一組正交向量。特征值分解是將一個(gè)矩陣分解成下面的形式：A二0其中Q是這個(gè)矩陣A的特征向量組成的矩陣，三是一個(gè)對(duì)角陣，每一個(gè)對(duì)角線上的元素就是一個(gè)特征值。我這里引用了一些參考文獻(xiàn)中的內(nèi)容來說明一下。首先，要明確

40、的是，一個(gè)矩陣其實(shí)就是一個(gè)線性變換，因?yàn)橐粋€(gè)矩陣乘以一個(gè)向量后得到的向量，其實(shí)就相當(dāng)于將這個(gè)向量進(jìn)行了線性變換。比如說下面的一個(gè)矩陣：因?yàn)檫@個(gè)矩陣M乘以一個(gè)向量（x,y）的結(jié)果是:上面的矩陣是對(duì)稱的，所以這個(gè)變換是一個(gè)對(duì)x，y軸的方向一個(gè)拉伸變換（每一個(gè)對(duì)角線上的元素將會(huì)對(duì)一個(gè)維度進(jìn)行拉伸變換，當(dāng)值1時(shí)，是拉長(zhǎng)，當(dāng)值1時(shí)時(shí)縮短），當(dāng)矩陣不是對(duì)稱的時(shí)候，假如說矩陣是下面的樣子：它所描述的變換是下面的樣子：這其實(shí)是在平面上對(duì)一個(gè)軸進(jìn)行的拉伸變換（如藍(lán)色的箭頭所示），在圖中，藍(lán)色的箭頭是一個(gè)最主要的變化方向（變化方向可能有不止一個(gè)），如果我們想要描述好一個(gè)變換，那我們就描述好這個(gè)變換主要的變化方向就

41、好了。反過頭來看看之前特征值分解的式子，分解得到的工矩陣是一個(gè)對(duì)角陣，里面的特征值是由大到小排列的，這些特征值所對(duì)應(yīng)的特征向量就是描述這個(gè)矩陣變化方向（從主要的變化到次要的變化排列）當(dāng)矩陣是高維的情況下，那么這個(gè)矩陣就是高維空間下的一個(gè)線性變換，這個(gè)線性變化可能沒法通過圖片來表示，但是可以想象，這個(gè)變換也同樣有很多的變換方向，我們通過特征值分解得到的前N個(gè)特征向量，那么就對(duì)應(yīng)了這個(gè)矩陣最主要的N個(gè)變化方向。我們利用這前N個(gè)變化方向，就可以近似這個(gè)矩陣（變換）。也就是之前說的：提取這個(gè)矩陣最重要的特征?？偨Y(jié)一下，特征值分解可以得到特征值與特征向量，特征值表示的是這個(gè)特征到底有多重要，而特征向量表

42、示這個(gè)特征是什么，可以將每一個(gè)特征向量理解為一個(gè)線性的子空間，我們可以利用這些線性的子空間干很多的事情。不過，特征值分解也有很多的局限，比如說變換的矩陣必須是方陣。（說了這么多特征值變換，不知道有沒有說清楚，請(qǐng)各位多提提意見。）2）奇異值：下面談?wù)勂娈愔捣纸?。特征值分解是一個(gè)提取矩陣特征很不錯(cuò)的方法，但是它只是對(duì)方陣而言的，在現(xiàn)實(shí)的世界中，我們看到的大部分矩陣都不是方陣，比如說有N個(gè)學(xué)生，每個(gè)學(xué)生有M科成績(jī)，這樣形成的一個(gè)N*M的矩陣就不可能是方陣，我們?cè)鯓硬拍苊枋鲞@樣普通的矩陣呢的重要特征呢？奇異值分解可以用來干這個(gè)事情，奇異值分解是一個(gè)能適用于任意的矩陣的一種分解的方法：假設(shè)A是一個(gè)N*M

43、的矩陣，那么得到的U是一個(gè)N*N的方陣（里面的向量是正交的，U里面的向量稱為左奇異向量），三是一個(gè)N*M的矩陣（除了對(duì)角線的元素都是0對(duì)角線上的元素稱為奇異值），V（V的轉(zhuǎn)置）是一個(gè)N*N的矩陣，里面的向量也是正交的，V里面的向量稱為右奇異向量），從圖片來反映幾個(gè)相乘的矩陣的大小可得下面的圖片那么奇異值和特征值是怎么對(duì)應(yīng)起來的呢？首先，我們將一個(gè)矩陣A的轉(zhuǎn)置*A，將會(huì)得到一個(gè)方陣，我們用這個(gè)方陣求特征值可以得到：這里得到的V,就是我們上面的右奇異向量。此外我們還可以得到:6=返ui=6這里的o就是上面說的奇異值，u就是上面說的左奇異向量。奇異值o跟特征值類似，在矩陣Z中也是從大到小排列，而且o

44、的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，這里定義一下部分奇異值分解：r是一個(gè)遠(yuǎn)小于m、n的數(shù)，這樣矩陣的乘法看起來像是下面的樣子:右邊的三個(gè)矩陣相乘的結(jié)果將會(huì)是一個(gè)接近于A的矩陣，在這兒，r越接近于n,則相乘的結(jié)果越接近于A。而這三個(gè)矩陣的面積之和（在存儲(chǔ)觀點(diǎn)來說，矩陣面積越小，存儲(chǔ)量就越?。┮h(yuǎn)遠(yuǎn)小于原始的矩陣A,我們?nèi)绻胍獕嚎s空間來表示原矩陣A,我們存下這里的三個(gè)矩陣:U、三、V就好了。二、奇異值的計(jì)算：奇異值的計(jì)算是一個(gè)難題，是一個(gè)0（N3）的算法。在單機(jī)的情況下當(dāng)然是沒問題的，

45、matlab在一秒鐘內(nèi)就可以算出1000*1000的矩陣的所有奇異值，但是當(dāng)矩陣的規(guī)模增長(zhǎng)的時(shí)候，計(jì)算的復(fù)雜度呈3次方增長(zhǎng)，就需要并行計(jì)算參與了。Google的吳軍老師在數(shù)學(xué)之美系列談到SVD的時(shí)候，說起Google實(shí)現(xiàn)了SVD的并行化算法，說這是對(duì)人類的一個(gè)貢獻(xiàn)，但是也沒有給出具體的計(jì)算規(guī)模，也沒有給出太多有價(jià)值的信息。其實(shí)SVD還是可以用并行的方式去實(shí)現(xiàn)的，在解大規(guī)模的矩陣的時(shí)候，一般使用迭代的方法，當(dāng)矩陣的規(guī)模很大（比如說上億）的時(shí)候，迭代的次數(shù)也可能會(huì)上億次，如果使用Map-Reduce框架去解，則每次Map-Reduce完成的時(shí)候，都會(huì)涉及到寫文件、讀文件的操作。個(gè)人猜測(cè)Google

46、云計(jì)算體系中除了Map-Reduce以外應(yīng)該還有類似于MPI的計(jì)算模型，也就是節(jié)點(diǎn)之間是保持通信，數(shù)據(jù)是常駐在內(nèi)存中的，這種計(jì)算模型比Map-Reduce在解決迭代次數(shù)非常多的時(shí)候，要快了很多倍。Lanczos迭代就是一種解對(duì)稱方陣部分特征值的方法（之前談到了，解A*A得到的對(duì)稱方陣的特征值就是解A的右奇異向量），是將一個(gè)對(duì)稱的方程化為一個(gè)三對(duì)角矩陣再進(jìn)行求解。按網(wǎng)上的一些文獻(xiàn)來看，Google應(yīng)該是用這種方法去做的奇異值分解的。請(qǐng)見Wikipedia上面的一些引用的論文，如果理解了那些論文，也幾乎”可以做出一個(gè)SVD了。由于奇異值的計(jì)算是一個(gè)很枯燥，純數(shù)學(xué)的過程，而且前人的研究成果（論文中）

47、幾乎已經(jīng)把整個(gè)程序的流程圖給出來了。更多的關(guān)于奇異值計(jì)算的部分，將在后面的參考文獻(xiàn)中給出，這里不再深入，我還是focus在奇異值的應(yīng)用中去。三、奇異值與主成分分析（PCA）:主成分分析在上一節(jié)里面也講了一些，這里主要談?wù)勅绾斡肧VD去解PCA的問題。PCA的問題其實(shí)是一個(gè)基的變換，使得變換后的數(shù)據(jù)有著最大的方差。方差的大小描述的是一個(gè)變量的信息量，我們?cè)谥v一個(gè)東西的穩(wěn)定性的時(shí)候，往往說要減小方差，如果一個(gè)模型的方差很大，那就說明模型不穩(wěn)定了。但是對(duì)于我們用于機(jī)器學(xué)習(xí)的數(shù)據(jù)（主要是訓(xùn)練數(shù)據(jù)），方差大才有意義，不然輸入的數(shù)據(jù)都是同一個(gè)點(diǎn)，那方差就為0了，這樣輸入的多個(gè)數(shù)據(jù)就等同于一個(gè)數(shù)據(jù)這個(gè)假設(shè)是

48、一個(gè)攝像機(jī)采集一個(gè)物體運(yùn)動(dòng)得到的圖片，上面的點(diǎn)表示物體運(yùn)動(dòng)的位置，假如我們想要用一條直線去擬合這些點(diǎn)，那我們會(huì)選擇什么方向的線呢？當(dāng)然是圖上標(biāo)有signal的那條線。如果我們把這些點(diǎn)單純的投影到x軸或者y軸上，最后在x軸與y軸上得到的方差是相似的（因?yàn)檫@些點(diǎn)的趨勢(shì)是在45度左右的方向，所以投影到x軸或者y軸上都是類似的），如果我們使用原來的xy坐標(biāo)系去看這些點(diǎn)，容易看不出來這些點(diǎn)真正的方向是什么。但是如果我們進(jìn)行坐標(biāo)系的變化，橫軸變成了signal的方向，縱軸變成了noise的方向，則就很容易發(fā)現(xiàn)什么方向的方差大，什么方向的方差小了。一般來說，方差大的方向是信號(hào)的方向，方差小的方向是噪聲的方向

49、，我們?cè)跀?shù)據(jù)挖掘中或者數(shù)字信號(hào)處理中，往往要提高信號(hào)與噪聲的比例，也就是信噪比。對(duì)上圖來說，如果我們只保留signal方向的數(shù)據(jù)，也可以對(duì)原數(shù)據(jù)進(jìn)行不錯(cuò)的近似了。PCA的全部工作簡(jiǎn)單點(diǎn)說，就是對(duì)原始的空間中順序地找一組相互正交的坐標(biāo)軸，第一個(gè)軸是使得方差最大的，第二個(gè)軸是在與第一個(gè)軸正交的平面中使得方差最大的，第三個(gè)軸是在與第1、2個(gè)軸正交的平面中方差最大的，這樣假設(shè)在N維空間中，我們可以找到N個(gè)這樣的坐標(biāo)軸，我們?nèi)∏皉個(gè)去近似這個(gè)空間，這樣就從一個(gè)N維的空間壓縮到r維的空間了，但是我們選擇的r個(gè)坐標(biāo)軸能夠使得空間的壓縮使得數(shù)據(jù)的損失最小。還是假設(shè)我們矩陣每一行表示一個(gè)樣本，每一列表示一個(gè)fe

50、ature，用矩陣的語言來表示，將一個(gè)m*n的矩陣A的進(jìn)行坐標(biāo)軸的變化，P就是一個(gè)變換的矩陣從一個(gè)N維的空間變換到另一個(gè)N維的空間，在空間中就會(huì)進(jìn)行一些類似于旋轉(zhuǎn)、拉伸的變化。而將一個(gè)m*n的矩陣A變換成一個(gè)m*r的矩陣，這樣就會(huì)使得本來有n個(gè)feature的,變成了有r個(gè)feature了（rn）,這r個(gè)其實(shí)就是對(duì)n個(gè)feature的一種提煉，我們就把這個(gè)稱為feature的壓縮。用數(shù)學(xué)語言表示就是：Aftixr但是這個(gè)怎么和SVD扯上關(guān)系呢？之前談到，SVD得出的奇異向量也是從奇異值由大到小排列的，按PCA的觀點(diǎn)來看，就是方差最大的坐標(biāo)軸就是第一個(gè)奇異向量，方差次大的坐標(biāo)軸就是第二個(gè)奇異向量

51、我們回憶一下之前得到的SVD式子：在矩陣的兩邊同時(shí)乘上一個(gè)矩陣V,由于V是一個(gè)正交的矩陣，所以V轉(zhuǎn)置乘以V得到單位陣I,所以可以化成后面的式子將后面的式子與A*P那個(gè)m*n的矩陣變換為m*r的矩陣的式子對(duì)照看看，在這里，其實(shí)V就是P,也就是一個(gè)變化的向量。這里是將一個(gè)m*n的矩陣壓縮到一個(gè)m*r的矩陣，也就是對(duì)列進(jìn)行壓縮，如果我們想對(duì)行進(jìn)行壓縮（在PCA的觀點(diǎn)下，對(duì)行進(jìn)行壓縮可以理解為，將一些相似的sample合并在一起，或者將一些沒有太大價(jià)值的sample去掉）怎么辦呢？同樣我們寫出一個(gè)通用的行壓縮例子：這樣就從一個(gè)m行的矩陣壓縮到一個(gè)r行的矩陣了，對(duì)SVD來說也是一樣的，我們對(duì)SVD分解的

52、式子兩邊乘以U的轉(zhuǎn)置U這樣我們就得到了對(duì)行進(jìn)行壓縮的式子?？梢钥闯觯鋵?shí)PCA幾乎可以說是對(duì)SVD的一個(gè)包裝，如果我們實(shí)現(xiàn)了SVD，那也就實(shí)現(xiàn)了PCA了，而且更好的地方是，有了SVD，我們就可以得到兩個(gè)方向的PCA，如果我們對(duì)AA進(jìn)行特征值的分解，只能得到一個(gè)方向的PCA。四、奇異值與潛在語義索引LSI:潛在語義索引（LatentSemanticIndexing）與PCA不太一樣，至少不是實(shí)現(xiàn)了SVD就可以直接用的，不過LSI也是一個(gè)嚴(yán)重依賴于SVD的算法，之前吳軍老師在矩陣計(jì)算與文本處理中的分類問題中談到：三個(gè)矩陣有非常清楚的物理含義第一個(gè)矩陣X中的每一行表示意思相關(guān)的一類詞，其中的每個(gè)非零

53、元素表示這類詞中每個(gè)詞的重要性（或者說相關(guān)性），數(shù)值越大越相關(guān)。最后一個(gè)矩陣中的每一列表示同一主題一類文章，其中每個(gè)元素表示這類文章中每篇文章的相關(guān)性。中間的矩陣則表示類詞和文章雷之間的相關(guān)性。因此，我們只要對(duì)關(guān)聯(lián)矩陣力進(jìn)行一次奇異值分解,W我們就可以同時(shí)完成了近義詞分類和文章的分類。（同時(shí)得到每類文章和每類詞的相關(guān)性）”。上面這段話可能不太容易理解，不過這就是LSI的精髓內(nèi)容，我下面舉一個(gè)例子來說明一下，下面的例子來自LSAtutorial，具體的網(wǎng)址我將在最后的引用中給出：這就是一個(gè)矩陣，不過不太一樣的是，這里的一行表示一個(gè)詞在哪些title中出現(xiàn)了（一行就是之前說的一維feature），

54、一列表示一個(gè)title中有哪些詞，（這個(gè)矩陣其實(shí)是我們之前說的那種一行是一個(gè)sample的形式的一種轉(zhuǎn)置，這個(gè)會(huì)使得我們的左右奇異向量的意義產(chǎn)生變化，但是不會(huì)影響我們計(jì)算的過程）。比如說T1這個(gè)title中就有g(shù)uide、investing、market、stock四個(gè)詞，各出現(xiàn)了一次，我們將這個(gè)矩陣進(jìn)行SVD，得到下面的矩陣：左奇異向量表示詞的一些特性，右奇異向量表示文檔的一些特性，中間的奇異值矩陣表示左奇異向量的一行與右奇異向量的一列的重要程序，數(shù)字越大越重要。book0.15-0,270,04dads0.24038-0.09dummies0.13-0J70.07estate0.180J9

55、0.4&guide0.220.09-0.46investing0.74-0.210.21market0.18-0.30-0.2Breal5rich0.360.59-0.34stock0.25-0.42-0.28value0.12-10002.S10002.00D.350.220340.260.220.490.28029044-032-0.15-0.46-0.24-0.140.550.070310.44-0.410.14-oie0250.220.510.550.00034繼續(xù)看這個(gè)矩陣還可以發(fā)現(xiàn)一些有意思的東西，首先，左奇異向量的第一列表示每一個(gè)詞的出

56、現(xiàn)頻繁程度，雖然不是線性的，但是可以認(rèn)為是一個(gè)大概的描述，比如book是0.15對(duì)應(yīng)-0.27d-0.4-0,20,00.2Dimension20.6在圖每一個(gè)藍(lán)色的點(diǎn)，都表示一篇文檔，這樣我們可以對(duì)這些market可以放在一類，因?yàn)樗麄兝鲜浅霈F(xiàn)在一起，real文檔中出現(xiàn)的2次，investing是0.74對(duì)應(yīng)了文檔中出現(xiàn)了9次，rich是0.36對(duì)應(yīng)文檔中出現(xiàn)了3次；其次，右奇異向量中一的第一行表示每一篇文檔中的出現(xiàn)詞的個(gè)數(shù)的近似，比如說，T6是0.49,出現(xiàn)了5個(gè)詞，T2是0.22,出現(xiàn)了2個(gè)詞。然后我們反過頭來看，我們可以將左奇異向量和右奇異向量都取后2維（之前是3維的矩陣），投影到一個(gè)

57、平面上，可以得到：XYPlotofWordsandTitles上，每一個(gè)紅色的點(diǎn)，都表示一個(gè)詞，詞和文檔進(jìn)行聚類，比如說stock和和estate可以放在一類，dads，guide這種詞就看起來有點(diǎn)孤立了，我們就不對(duì)他們進(jìn)行合并了。按這樣聚類出現(xiàn)的效果，可以提取文檔集合中的近義詞，這樣當(dāng)用戶檢索文檔的時(shí)候，是用語義級(jí)別（近義詞集合）去檢索了，而不是之前的詞的級(jí)別。這樣一減少我們的檢索、存儲(chǔ)量，因?yàn)檫@樣壓縮的文檔集合和PCA是異曲同工的，二可以提高我們的用戶體驗(yàn)，用戶輸入一個(gè)詞，我們可以在這個(gè)詞的近義詞的集合中去找，這是傳統(tǒng)的索引無法做到的。不知道按這樣描述，再看看吳軍老師的文章，是不是對(duì)SVD

58、更清楚了？:-D參考資料：ATutorialonPrincipalComponentAnalysis,JonathonShlens這是我關(guān)于用SVD去做PCA的主要參考資料 HYPERLINK /samplings/feature-column/fcarc-svd /samplings/feature-column/fcarc-svd關(guān)于svd的一篇概念好文，我開頭的幾個(gè)圖就是從這兒截取的3) HYPERLINK /index.php/news-and-articles/articles/30-singular-v /index.php/news-and-articles/articles/3

59、0-singular-value-decomposition-tutorial.html另一篇關(guān)于svd的入門好文4) HYPERLINK /index.php/news-and-articles/articles/33-latent-se /index.php/news-and-articles/articles/33-latent-semantic-analysis-tutorial.htmlsvd與LSI的好文，我后面LSI中例子就是來自此5) HYPERLINK /information-retrieval-tutorial/svd-lsi-tutorial-1-understa /i

60、nformation-retrieval-tutorial/svd-lsi-tutorial-1-understanding.html另一篇svd與LSI的文章，也還是不錯(cuò)，深一點(diǎn)，也比較長(zhǎng)6)SingularValueDecompositionandPrincipalComponentAnalysis,RasmusElsborgMadsen,LarsKaiHansenandOleWinther,2004跟1)里面的文章比較類似機(jī)器學(xué)習(xí)中的算法（1）-決策樹模型組合之隨機(jī)森林與GBDT版權(quán)聲明：本文由LeftNotEasy發(fā)布于 HYPERLINK ,本文可以被全部的轉(zhuǎn)載或者部分使用，但請(qǐng)注明