最新經(jīng)驗(yàn)好文第一時間送達(dá)
2019.8.7
“第十章 降維與度量學(xué)習(xí)”
|二度簡并|
一．本章主體內(nèi)容
1.k近鄰學(xué)習(xí)
k 近鄰（k-Nearest Neighbor，簡稱kNN）學(xué)習(xí)是一種常用的監(jiān)督學(xué)習(xí)方法。
工作機(jī)制（重點(diǎn)理解）：給定測試樣本，基于某種距離度量找出訓(xùn)練集中與其距離最近的 k 個樣本，然后基于這 k 個鄰居的信息來進(jìn)行預(yù)測。通?？梢酝ㄟ^“投票法”或“平均法”來對測試樣本進(jìn)行預(yù)測（詳情請查看第八章集成學(xué)習(xí)）。
KNN學(xué)習(xí)算法的一個特點(diǎn)是它并不需要提前對模型進(jìn)行訓(xùn)練，只在預(yù)測時對訓(xùn)練樣本進(jìn)行計(jì)算即可得到預(yù)測結(jié)果，這是一個典型的“懶惰學(xué)習(xí)”的算法。下圖是一個 kNN 學(xué)習(xí)算法的示意圖：
顯然，k的選擇十分重要，因?yàn)椴煌?/span> k 的選擇會導(dǎo)致預(yù)測的結(jié)果截然不同，不同的距離度量方式也會因?yàn)檫x擇的鄰居不同而導(dǎo)致截然不同的結(jié)果。
在第一節(jié)介紹 kNN 學(xué)習(xí)的原因在于它的一個性質(zhì)，那就是如果滿足在任意小距離內(nèi)有一個樣本的條件時，其錯誤率最差不超過最優(yōu)貝葉斯分類器錯誤率的兩倍。
對于這么簡單的一個學(xué)習(xí)算法，竟然最差錯誤率不超過貝葉斯最優(yōu)分類器錯誤率的兩倍，關(guān)鍵這個學(xué)習(xí)算法還不用提前訓(xùn)練……
可惜，這個性質(zhì)是建立在一個假設(shè)上的，那就是在任意小距離內(nèi)測試樣本都能找到一個鄰居，而要滿足這個條件可不是那么容易的。
2.低維嵌入
對于之前的假設(shè)條件，如果歸一化后在0.001的距離內(nèi)都有一個鄰居結(jié)點(diǎn)的話，我們需要1000個樣本數(shù)量平均分布到樣本空間中才可行，這是屬性數(shù)量為1的情況。當(dāng)屬性數(shù)量為20時，我們需要1000的20次方也就是10的60次方的數(shù)據(jù)量，這是個天文數(shù)字，這個數(shù)量級的數(shù)據(jù)是不可能獲得的，更不要說在實(shí)際應(yīng)用中樣本的屬性可能成千上萬。
在高維情形下出現(xiàn)的樣本稀疏、距離計(jì)算困難等問題，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙，被稱為“維度災(zāi)難”（curse of dimensionality）
緩解維數(shù)災(zāi)難的一個重要途徑是降維（dimension reduction），亦稱“維數(shù)約簡”（在第11章會介紹另一個重要途徑：特征選擇），即通過某種數(shù)學(xué)變換將原始高維屬性空間轉(zhuǎn)變?yōu)橐粋€低維子空間，在這個子空間中樣本密度大幅提高，距離計(jì)算也變得更加容易。
為什么能降維？這是因?yàn)樵诤芏鄷r候，和學(xué)習(xí)任務(wù)密切相關(guān)的只是屬性空間的某個低維分布，即高維空間的某個低維嵌入。下圖給了一個直觀的例子，原始高維的樣本點(diǎn)在低維空間中更容易學(xué)習(xí)
若要求原始空間中樣本之間的距離在低維空間中得以保持，即得到“多維縮放”（Multiple Dimensional Scaling，簡稱MDS）這樣一個經(jīng)典的降維方法。
多維縮放的目標(biāo)是通過縮放后，樣本在新的低維空間上的歐式距離和其在原始空間的距離相等。
在現(xiàn)實(shí)中為了有效降維，往往僅需降維之后的距離與原始空間中的距離盡可能的相近，而不必嚴(yán)格相等。
MDS算法的具體流程：
［1］對映射到 X 空間的 m 個樣本的數(shù)據(jù)集，可輕易計(jì)算任意樣本 xi 到 xj 之間的距離，構(gòu)成 m*m 大小的距離矩陣 D，其中 dij 代表樣本 xi 到 xj 的距離
［2］因?yàn)榧僭O(shè)樣本映射到低維空間 Z 后距離相等，那么映射后任意兩個樣本 zi 和 zj 的內(nèi)積可以通過之前的距離矩陣 D 來計(jì)算得到，此時算出低維空間映射后的 m*m 的內(nèi)積矩陣 B
［3］通過對內(nèi)積矩陣 B 進(jìn)行特征分解，可以得到一組特征值和特征向量，取最大的 d' 個特征值構(gòu)成的對角矩陣 A 和對應(yīng)的特征向量矩陣 V
［4］通過對角矩陣 A 和特征向量矩陣 V，我們可以得到原始樣本在低維 d' 空間上的映射
MDS算法實(shí)際上在降維之前就進(jìn)行了大量的距離、內(nèi)積計(jì)算，這在數(shù)據(jù)樣本和屬性維度都十分大時是很耗資源和時間的，所以對于維度災(zāi)難來說，MDS的緩解作用并不大。一般來說要獲得低維子空間，最簡單的是對原始高維空間進(jìn)行線性變換。
但是這個線性變換的過程在機(jī)器學(xué)習(xí)領(lǐng)域十分的常見，無論是線性回歸算法、支持向量機(jī)還是神經(jīng)網(wǎng)絡(luò)都有用到線性變換。以神經(jīng)網(wǎng)絡(luò)來比喻我們這里的降維算法，將 d 維的屬性樣本降維到 d' 維的屬性空間上，其實(shí)等同為輸入神經(jīng)元為 d 個、輸出神經(jīng)元為 d' 個的淺層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，借用一下第五章的圖解釋一下
降維后的每個新的屬性 x' 其實(shí)是高維屬性 x1、x2、...、xn 根據(jù)權(quán)重 W 的線性組合。這種基于線性變換進(jìn)行降維的方法稱為線性降維方法，對低維子空間的性質(zhì)有不同的要求，相對于對權(quán)重 W 施加了不同的約束。對降維效果的評估，通常是比較降維前后學(xué)習(xí)器的性能，若性能提升了則認(rèn)為降維起到了效果。
前面的討論基于一個假設(shè): 對任意x和任意小正數(shù)δ, 在x附近δ距離范圍內(nèi)總能找到一個訓(xùn)練樣本. 但是遺憾的是現(xiàn)實(shí)中很難滿足這種情況, 且隨著特征維數(shù)的增長, 所需要的樣本數(shù)會飛速增長, 且高維特征也會使得距離運(yùn)算更加耗時。
這種在高維情況下出現(xiàn)的樣本稀疏, 計(jì)算困難等問題, 是許多ML方法都面臨的共同問題,稱為維數(shù)災(zāi)難。
緩解維數(shù)災(zāi)難的一種方法就是降維, 又稱維數(shù)約簡, 即將原始高維屬性空間轉(zhuǎn)變成一個低維子空間。
降維的依據(jù)在于, 雖然數(shù)據(jù)樣本是高維的,但是與學(xué)習(xí)任務(wù)密切相關(guān)的也許僅僅是某個低維分布。
3.主成分分析
主成分分析（Principle Component Analysis，簡稱PCA ）是最常用的一種降維方法，它是基于這樣的核心思想來設(shè)計(jì)的：對于一組樣本，如果存在一個超平面使得樣本在上邊的距離都足夠近或者投影都盡可能分開，那么這個超平面是對這組樣本的一個很恰當(dāng)?shù)谋硎尽?/span>
那么這個超平面本身可以被看作是降維的目標(biāo)空間，記該超平面由 n 維的正交基向量構(gòu)成的矩陣 W = {w1,w2,...,wn}，那么主成分分析降維法就是要找到這組正交基向量。
那么這組基向量我們應(yīng)該怎么求呢？這里用到了一個在機(jī)器學(xué)習(xí)算法中常用的邏輯：既然降維變換到的超平面能很好的代表樣本數(shù)據(jù)，那么我們從超平面上映射回到原始空間中的點(diǎn)應(yīng)該與沒映射之前的點(diǎn)距離相近。我們可以通過最小化這個變化誤差來算得最佳的正交基向量矩陣 W。
這種選擇邏輯在之前的機(jī)器學(xué)習(xí)算法中也有出現(xiàn)，比如在神經(jīng)網(wǎng)絡(luò)那一章的。Boltzmann機(jī)算法，其訓(xùn)練過程就是依照著這同樣的邏輯，其訓(xùn)練過程（對比散度 Contrastive Divergence 算法）如下：通過輸入層算出隱層分布，再通過隱層分布重新算出輸入層的新分布；并利用新分布與舊分布之間的差別調(diào)整連接權(quán)重。
幸運(yùn)的是，在這里我們不需要反復(fù)的調(diào)整權(quán)重來找到最佳的 W，通過課本中的公式計(jì)算可知，我們可以通過對樣本 X 的協(xié)方差矩陣進(jìn)行特征分解來求得 W。
特征值越大，說明該特征向量對應(yīng)的是方差變化越大的方向，針對這個方向進(jìn)行分解將能更好的表示樣本數(shù)據(jù)。所以，如果我們要降維到 d' 維度的話，我們只需要取出排序最高的 d' 個特征向量 (w1, w2,..., wd') 即可。這里 d' 的取值由用戶事先決定，我們可以通過交叉驗(yàn)證等方式來選擇出一個最好的 d' 取值。
4.核化線性降維
在現(xiàn)實(shí)任務(wù)中，有時候直接使用線性降維會導(dǎo)致部分信息丟失的，本書舉的例子是基于這樣的一個場景，低維空間映射到高維空間后，再次降維到低維空間會導(dǎo)致原始的低維結(jié)構(gòu)丟失。
核化線性降維的本質(zhì)是基于核技巧對線性降維方法進(jìn)行“核化”（kernelized），以前邊的主成分分析法線性降維為例，核化主成分分析算法是在主成分分析的基礎(chǔ)上將高維空間的樣本投射 X 轉(zhuǎn)換為被核化的 k(X) 來進(jìn)行計(jì)算，并對核函數(shù)對應(yīng)的核矩陣進(jìn)行特征分解來求得投影的 d' 維特征向量。
5.流形學(xué)習(xí)
流行學(xué)習(xí)的核心概念是：樣本雖然在高維空間上的分布看上去非常復(fù)雜，但是在局部上仍具有歐氏空間的性質(zhì)，所以我們可以通過在局部建立降維映射關(guān)系，然后再將局部映射推廣到全局去來簡化降維開銷。
根據(jù)選擇的歐氏空間性質(zhì)的不同可以有不同的流形學(xué)習(xí)方法，本章介紹了兩種著名的流形學(xué)習(xí)方法。
［1］歐氏空間距離性質(zhì)：等度量映射（Isometric Mapping，簡稱Isomap）
等度量映射試圖讓樣本在“流形”上的距離在降維之后仍能保持
等度量映射的基本出發(fā)點(diǎn)，是認(rèn)為低維流形嵌入到高維空間之后，直接在高維空間中計(jì)算直線距離具有誤導(dǎo)性，因?yàn)楦呔S空間中的直線距離在低維空間中是不可達(dá)的。
圖10.7(a)所示，假設(shè)紅色線段的兩端分別是A點(diǎn)和B點(diǎn)，對于一個生活在二維平面上的生物來說，其從A點(diǎn)到B點(diǎn)的距離是紅色線段的長度，而對于生活在三維平面上的生物來說，其從A點(diǎn)到B點(diǎn)的距離是黑色線段的長度。
顯然在S型的流行上，紅色線段的長度是更為恰當(dāng)?shù)木嚯x表示，該路徑也更貼合樣本數(shù)據(jù)的分布情況。
面對這種情況，等度量映射算法被設(shè)計(jì)為：
＊通過設(shè)定最近鄰 k 并計(jì)算出樣本 xi 與近鄰之間的距離，非近鄰之間距離為無限大
＊通過Dijkstra算法計(jì)算任意兩個樣本 xi 與 xj 之間的距離
＊利用算好的距離使用多維縮放算法來對樣本進(jìn)行降維
［2］歐氏空間的向量表示性質(zhì)：局部線性嵌入（Locally Linear Embedding，簡稱LLE）
與Isomap算法不同，LLE試圖保持鄰域內(nèi)樣本之間的線性關(guān)系，即一個樣本可以由其鄰域的樣本通過線性組合來進(jìn)行重構(gòu)，而且這種重構(gòu)關(guān)系在降維之后仍能保持。
值得注意的是，流形學(xué)習(xí)欲有效進(jìn)行鄰域保持則需樣本密采樣，而這恰是高維情形下的重大阻礙，因此流形學(xué)習(xí)方法在實(shí)踐中的降維性能往往沒有預(yù)期的好；但鄰域保持的想法很有意義，它對其它機(jī)器學(xué)習(xí)的分支也產(chǎn)生了重要的影響，例如半監(jiān)督學(xué)習(xí)中有著名的流行假設(shè)。
6.度量學(xué)習(xí)
在機(jī)器學(xué)習(xí)中，對高維數(shù)據(jù)進(jìn)行降維的主要目的是希望找到一個合適的低維空間，在此空間進(jìn)行學(xué)習(xí)能比原始空間要好。事實(shí)上，每個空間對應(yīng)了在樣本屬性上定義的一個合適的距離度量。那么，何不直接嘗試“學(xué)習(xí)”出一個合適的距離度量呢？這就是度量學(xué)習(xí)的基本動機(jī)
欲對距離度量進(jìn)行學(xué)習(xí)，我們需要為樣本之間的距離計(jì)算加上權(quán)重，并可以根據(jù)具體樣本來對權(quán)重進(jìn)行訓(xùn)練，這個權(quán)重構(gòu)成的矩陣我們稱為“度量矩陣”。
度量學(xué)習(xí)的目的就是計(jì)算出合適的“度量矩陣”，在實(shí)際計(jì)算時，我們可以將度量矩陣 M 直接嵌入到近鄰分類器的評價體系中去，通過優(yōu)化該性能指標(biāo)相應(yīng)的求得 M。
用一張圖來匯總一些降維方法:
二．基礎(chǔ)知識
懶惰學(xué)習(xí)（lazy learning）：此類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來，訓(xùn)練時間開銷為零，待收到測試樣本后再進(jìn)行處理
急切學(xué)習(xí)（eager learning）：與懶惰學(xué)習(xí)相反，此類學(xué)習(xí)技術(shù)在訓(xùn)練階段就對樣本進(jìn)行學(xué)習(xí)處理
維度災(zāi)難（curse of dimensionality）：在高維情形下出現(xiàn)的樣本稀疏、距離計(jì)算困難等問題，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙，被稱為“維度災(zāi)難”
矩陣的跡（trace）：在線性代數(shù)中，一個n×n矩陣A的主對角線（從左上方至右下方的對角線）上各個元素的總和被稱為矩陣A的跡（或跡數(shù)），一般記作tr(A)。
矩陣特征分解（Eigenvalue decomposition）：將矩陣分解為由其特征值和特征向量表示的矩陣之積的方法。需要注意只有對可對角化矩陣才可以施以特征分解。簡單理解就是將矩陣變換為幾個相互垂直的向量的和，比如在二維空間中，任意一個向量可以被表示為x軸和y軸的組合。
三．總結(jié)
1） k 近鄰學(xué)習(xí)是簡單常用的分類算法，在樣本分布充足時，其最差誤差不超過貝葉斯最優(yōu)分類器的兩倍
2）實(shí)際情況下由于屬性維度過大，會導(dǎo)致“維數(shù)災(zāi)難”，這是所有機(jī)器學(xué)習(xí)中的共同障礙
3）緩解維數(shù)災(zāi)難的有效途徑是降維，即將高維樣本映射到低維空間中，這樣不僅屬性維度降低減少了計(jì)算開銷，還增大了樣本密度
4）降維過程中必定會對原始數(shù)據(jù)的信息有所丟失，所以根據(jù)不同的降維目標(biāo)我們可以得到不同的降維方法
5）多維縮放的目標(biāo)是要保證降維后樣本之間的距離不變
6）線性降維方法目標(biāo)是要保證降維到的超平面能更好的表示原始數(shù)據(jù)
7）核線性降維方法目標(biāo)是通過核函數(shù)和核方法來避免采樣空間投影到高維空間再降維之后的低維結(jié)構(gòu)丟失
8）等度量映射的目標(biāo)是讓樣本在“流形”上的距離在降維之后仍能保持
9）局部線性嵌入的目標(biāo)是讓樣本由其鄰域向量重構(gòu)關(guān)系在降維后仍能保持
10）度量學(xué)習(xí)繞過降維的過程，將學(xué)習(xí)目標(biāo)轉(zhuǎn)化為對距離度量計(jì)算的權(quán)重矩陣的學(xué)習(xí)
有趣的小數(shù)據(jù)：宇宙間基本粒子的總數(shù)約為10的80次方，而一?；覊m中含有幾十億基本粒子，而要滿足k近鄰算法假設(shè)的屬性數(shù)量為20的樣本數(shù)量為10的60次方。
四．本章腦圖
END
