1. 章節(jié)主要內(nèi)容
本章的主要內(nèi)容是降維與度量學(xué)習(xí)梳庆，這是機(jī)器學(xué)習(xí)領(lǐng)域很重要的一塊內(nèi)容。在進(jìn)入具體的介紹之前惧所，對(duì)降維與度量學(xué)習(xí)不清楚的小伙伴們其實(shí)可以嘗試從字面意思上理解一下降維與度量學(xué)習(xí)是干什么的闽颇，而它們又與機(jī)器學(xué)習(xí)有什么關(guān)系。
我相信看過科幻小說的人埠对，應(yīng)該都對(duì)降維度打擊這個(gè)概念不陌生吧，在某些科幻小說中裁替，生活在更高維度的外星人可以通過降低自己的維度來打擊低緯度的生命體项玛，而這種方式的打擊由于帶有部分高緯度的特性，所以低緯度的生物往往很難抵抗（雖然也有的科幻文章說高緯度的生物是無法直接接觸到低緯度生命的弱判，這里不做爭論）襟沮。基于同樣的理解昌腰，在機(jī)器學(xué)習(xí)領(lǐng)域中开伏，我們是否也可以通過降低維度來獲得某種優(yōu)勢呢？抱著這樣的疑問遭商，我們進(jìn)入這一章的內(nèi)容吧固灵。
1）在開始真正介紹降維和度量學(xué)習(xí)之前，我們先來了解一個(gè)簡單的機(jī)器學(xué)習(xí)算法：k 近鄰學(xué)習(xí)
k 近鄰（k-Nearest Neighbor株婴，簡稱kNN）學(xué)習(xí)是一種常用的監(jiān)督學(xué)習(xí)方法怎虫，其工作機(jī)制非常簡單：給定測試樣本暑认，基于某種距離度量找出訓(xùn)練集中與其距離最近的 k 個(gè)樣本困介，然后基于這 k 個(gè)鄰居的信息來進(jìn)行預(yù)測。通痴杭剩可以通過“投票法”或“平均法”來對(duì)測試樣本進(jìn)行預(yù)測（詳情請查看第八章集成學(xué)習(xí)）座哩。
kNN學(xué)習(xí)算法的一個(gè)特點(diǎn)是它并不需要提前對(duì)模型進(jìn)行訓(xùn)練，只在預(yù)測時(shí)對(duì)訓(xùn)練樣本進(jìn)行計(jì)算即可得到預(yù)測結(jié)果粮彤，這是一個(gè)典型的“懶惰學(xué)習(xí)”的算法根穷。下圖是一個(gè) kNN 學(xué)習(xí)算法的示意圖：
顯然，k的選擇十分重要导坟，因?yàn)椴煌?k 的選擇會(huì)導(dǎo)致預(yù)測的結(jié)果截然不同屿良，同樣的，不同的距離度量方式也會(huì)因?yàn)檫x擇的鄰居不同而導(dǎo)致截然不同的結(jié)果惫周。
我們在第一節(jié)介紹 kNN 學(xué)習(xí)的原因在于它的一個(gè)性質(zhì)尘惧，那就是如果滿足在任意小距離內(nèi)有一個(gè)樣本的條件時(shí)，其錯(cuò)誤率最差不超過最優(yōu)貝葉斯分類器錯(cuò)誤率的兩倍递递。
對(duì)于這么簡單的一個(gè)學(xué)習(xí)算法喷橙，竟然最差錯(cuò)誤率不超過貝葉斯最優(yōu)分類器錯(cuò)誤率的兩倍啥么，關(guān)鍵這個(gè)學(xué)習(xí)算法還不用提前訓(xùn)練，多么美好呀贰逾！
可惜悬荣，這個(gè)性質(zhì)是建立在一個(gè)假設(shè)上的，那就是在任意小距離內(nèi)測試樣本都能找到一個(gè)鄰居疙剑，而要滿足這個(gè)條件可不是那么容易的氯迂。這個(gè)不容易性可是和我們這章的主要內(nèi)容“維度”息息相關(guān)的呢！
2）屬性數(shù)量線性提升帶來的困難程度的指數(shù)提升問題：維度災(zāi)難
對(duì)于上節(jié)的假設(shè)條件核芽，如果歸一化后在0.001的距離內(nèi)都有一個(gè)鄰居結(jié)點(diǎn)的話囚戚，我們需要1000個(gè)樣本數(shù)量平均分布到樣本空間中才可行，這是屬性數(shù)量為1的情況轧简。當(dāng)屬性數(shù)量為20時(shí)驰坊，我們需要1000的20次方也就是10的60次方的數(shù)據(jù)量，這是個(gè)天文數(shù)字哮独，這個(gè)數(shù)量級(jí)的數(shù)據(jù)是不可能獲得的拳芙，更不要說在實(shí)際應(yīng)用中樣本的屬性可能成千上萬。
在高維情形下出現(xiàn)的樣本稀疏皮璧、距離計(jì)算困難等問題舟扎，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙，被稱為“維度災(zāi)難”（curse of dimensionality）
緩解維數(shù)災(zāi)難的一個(gè)重要途徑是降維（dimension reduction）悴务，亦稱“維數(shù)約簡”（在第11章會(huì)介紹另一個(gè)重要途徑：特征選擇）睹限，即通過某種數(shù)學(xué)變換將原始高維屬性空間轉(zhuǎn)變?yōu)橐粋€(gè)低維子空間，在這個(gè)子空間中樣本密度大幅提高讯檐，距離計(jì)算也變得更加容易羡疗。
為什么能降維？這是因?yàn)樵诤芏鄷r(shí)候别洪，和學(xué)習(xí)任務(wù)密切相關(guān)的只是屬性空間的某個(gè)低維分布叨恨，即高維空間的某個(gè)低維嵌入。下圖給了一個(gè)直觀的例子挖垛，原始高維的樣本點(diǎn)在低維空間中更容易學(xué)習(xí)
若要求原始空間中樣本之間的距離在低維空間中得以保持痒钝，即得到“多維縮放”（Multiple Dimensional Scaling，簡稱MDS）這樣一個(gè)經(jīng)典的降維方法痢毒。
多維縮放的目標(biāo)是通過縮放后送矩，樣本在新的低維空間上的歐式距離和其在原始空間的距離相等
在現(xiàn)實(shí)中為了有效降維，往往僅需降維之后的距離與原始空間中的距離盡可能的相近哪替，而不必嚴(yán)格相等栋荸。
MDS算法的具體流程是：
［1］對(duì)映射到 X 空間的 m 個(gè)樣本的數(shù)據(jù)集，可輕易計(jì)算任意樣本 xi 到 xj 之間的距離，構(gòu)成 m*m 大小的距離矩陣 D蒸其，其中 dij 代表樣本 xi 到 xj 的距離
［2］因?yàn)榧僭O(shè)樣本映射到低維空間 Z 后距離相等敏释，那么映射后任意兩個(gè)樣本 zi 和 zj 的內(nèi)積可以通過之前的距離矩陣 D 來計(jì)算得到，此時(shí)算出低維空間映射后的 m*m 的內(nèi)積矩陣 B
［3］通過對(duì)內(nèi)積矩陣 B 進(jìn)行特征分解摸袁，可以得到一組特征值和特征向量钥顽，取最大的 d' 個(gè)特征值構(gòu)成的對(duì)角矩陣 A 和對(duì)應(yīng)的特征向量矩陣 V
［4］通過對(duì)角矩陣 A 和特征向量矩陣 V，我們可以得到原始樣本在低維 d' 空間上的映射
個(gè)人想法：MDS算法實(shí)際上在降維之前就進(jìn)行了大量的距離靠汁、內(nèi)積計(jì)算蜂大，這在數(shù)據(jù)樣本和屬性維度都十分大時(shí)是很耗資源和時(shí)間的，所以對(duì)于維度災(zāi)難來說蝶怔，MDS的緩解作用并不大奶浦。
一般來說要獲得低維子空間，最簡單的是對(duì)原始高維空間進(jìn)行線性變換踢星。個(gè)人想法：這個(gè)線性變換的過程在機(jī)器學(xué)習(xí)領(lǐng)域十分的常見澳叉，無論是線性回歸算法、支持向量機(jī)還是神經(jīng)網(wǎng)絡(luò)都有用到線性變換沐悦。以神經(jīng)網(wǎng)絡(luò)來比喻我們這里的降維算法成洗，將 d 維的屬性樣本降維到 d' 維的屬性空間上，其實(shí)等同為輸入神經(jīng)元為 d 個(gè)藏否、輸出神經(jīng)元為 d' 個(gè)的淺層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)瓶殃，借用一下第五章的圖解釋一下
降維后的每個(gè)新的屬性 x' 其實(shí)是高維屬性 x1、x2副签、...遥椿、xn 根據(jù)權(quán)重 W 的線性組合。這種基于線性變換進(jìn)行降維的方法稱為線性降維方法淆储，對(duì)低維子空間的性質(zhì)有不同的要求冠场，相對(duì)于對(duì)權(quán)重 W 施加了不同的約束。對(duì)降維效果的評(píng)估遏考，通常是比較降維前后學(xué)習(xí)器的性能慈鸠，若性能提升了則認(rèn)為降維起到了效果蓝谨。
3）一種常用的線性降維方法：主成分分析（Principle Component Analysis灌具，簡稱PCA ）
主成分分析法是最常用的一種降維方法，它是基于這樣的核心思想來設(shè)計(jì)的：對(duì)于一組樣本譬巫，如果存在一個(gè)超平面使得樣本在上邊的距離都足夠近或者投影都盡可能分開咖楣，那么這個(gè)超平面是對(duì)這組樣本的一個(gè)很恰當(dāng)?shù)谋硎尽?/p>
那么這個(gè)超平面本身可以被看作是降維的目標(biāo)空間，記該超平面由 n 維的正交基向量構(gòu)成的矩陣 W = {w1,w2,...,wn}芦昔，那么主成分分析降維法就是要找到這組正交基向量诱贿。
那么這組基向量我們應(yīng)該怎么求呢？這里用到了一個(gè)在機(jī)器學(xué)習(xí)算法中常用的邏輯：既然降維變換到的超平面能很好的代表樣本數(shù)據(jù)，那么我們從超平面上映射回到原始空間中的點(diǎn)應(yīng)該與沒映射之前的點(diǎn)距離相近珠十。我們可以通過最小化這個(gè)變化誤差來算得最佳的正交基向量矩陣 W
這種選擇邏輯在之前的機(jī)器學(xué)習(xí)算法中也有出險(xiǎn)料扰，比如在神經(jīng)網(wǎng)絡(luò)那一章的
Boltzmann機(jī)算法，其訓(xùn)練過程就是依照著這同樣的邏輯焙蹭，其訓(xùn)練過程（對(duì)比散度 Contrastive Divergence 算法）如下：通過輸入層算出隱層分布晒杈，再通過隱層分布重新算出輸入層的新分布；并利用新分布與舊分布之間的差別調(diào)整連接權(quán)重孔厉。
幸運(yùn)的是拯钻，在這里我們不需要反復(fù)的調(diào)整權(quán)重來找到最佳的 W，通過課本中的公式計(jì)算可知撰豺，我們可以通過對(duì)樣本 X 的協(xié)方差矩陣進(jìn)行特征分解來求得 W粪般。
特征值越大，說明該特征向量對(duì)應(yīng)的是方差變化越大的方向污桦，針對(duì)這個(gè)方向進(jìn)行分解將能更好的表示樣本數(shù)據(jù)亩歹。所以，如果我們要降維到 d' 維度的話凡橱，我們只需要取出排序最高的 d' 個(gè)特征向量 (w1, w2,..., wd') 即可捆憎。這里 d' 的取值由用戶事先決定，我們可以通過交叉驗(yàn)證等方式來選擇出一個(gè)最好的 d' 取值
上邊是基于線性變換的降維方法梭纹，那么針對(duì)非線性情況時(shí)躲惰，下節(jié)我們將對(duì)非線性情況的降維進(jìn)行介紹
4）一種常用的非線性降維方法：核化線性降維
在現(xiàn)實(shí)任務(wù)中，有時(shí)候直接使用線性降維會(huì)導(dǎo)致部分信息丟失的变抽，本書舉的例子是基于這樣的一個(gè)場景础拨，低維空間映射到高維空間后，再次降維到低維空間會(huì)導(dǎo)致原始的低維結(jié)構(gòu)丟失绍载。
核化線性降維的本質(zhì)是基于核技巧對(duì)線性降維方法進(jìn)行“核化”（kernelized）诡宗，以前邊的主成分分析法線性降維為例，核化主成分分析算法是在主成分分析的基礎(chǔ)上將高維空間的樣本投射 X 轉(zhuǎn)換為被核化的 k(X) 來進(jìn)行計(jì)算击儡，并對(duì)核函數(shù)對(duì)應(yīng)的核矩陣進(jìn)行特征分解來求得投影的 d' 維特征向量
5）一種借鑒拓?fù)淞餍胃拍畹慕稻S方法：流形學(xué)習(xí)（manifold learning）
流行學(xué)習(xí)的核心概念是：樣本雖然在高維空間上的分布看上去非常復(fù)雜塔沃，但是在局部上仍具有歐氏空間的性質(zhì)，所以我們可以通過在局部建立降維映射關(guān)系阳谍，然后再將局部映射推廣到全局去來簡化降維開銷蛀柴。
個(gè)人想法：流行學(xué)習(xí)的本質(zhì)是要使得降維前后的樣本分布在歐氏空間上的性質(zhì)保持不變。
根據(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)综液，對(duì)于一個(gè)生活在二維平面上的生物來說，其從A點(diǎn)到B點(diǎn)的距離是紅色線段的長度儒飒，而對(duì)于生活在三維平面上的生物來說意乓，其從A點(diǎn)到B點(diǎn)的距離是黑色線段的長度。
顯然在S型的流行上约素，紅色線段的長度是更為恰當(dāng)?shù)木嚯x表示届良，該路徑也更貼合樣本數(shù)據(jù)的分布情況。
面對(duì)這種情況圣猎，等度量映射算法被設(shè)計(jì)為：
＊ 通過設(shè)定最近鄰 k 并計(jì)算出樣本 xi 與近鄰之間的距離士葫，非近鄰之間距離為無限大
＊ 通過Dijkstra算法計(jì)算任意兩個(gè)樣本 xi 與 xj 之間的距離
＊ 利用算好的距離使用多維縮放算法來對(duì)樣本進(jìn)行降維
［2］歐氏空間的向量表示性質(zhì)：局部線性嵌入（Locally Linear Embedding，簡稱LLE）
與Isomap算法不同送悔，LLE試圖保持鄰域內(nèi)樣本之間的線性關(guān)系慢显，即一個(gè)樣本可以由其鄰域的樣本通過線性組合來進(jìn)行重構(gòu)，而且這種重構(gòu)關(guān)系在降維之后仍能保持欠啤。
值得注意的是荚藻，流形學(xué)習(xí)欲有效進(jìn)行鄰域保持則需樣本密采樣，而這恰是高維情形下的重大阻礙洁段，因此流形學(xué)習(xí)方法在實(shí)踐中的降維性能往往沒有預(yù)期的好应狱；但鄰域保持的想法很有意義，它對(duì)其它機(jī)器學(xué)習(xí)的分支也產(chǎn)生了重要的影響祠丝，例如半監(jiān)督學(xué)習(xí)中有著名的流行假設(shè)
6）降維的替代方案疾呻，直接學(xué)習(xí)距離度量：度量學(xué)習(xí)（metric learning）
在機(jī)器學(xué)習(xí)中，對(duì)高維數(shù)據(jù)進(jìn)行降維的主要目的是希望找到一個(gè)合適的低維空間写半，在此空間進(jìn)行學(xué)習(xí)能比原始空間要好岸蜗。事實(shí)上，每個(gè)空間對(duì)應(yīng)了在樣本屬性上定義的一個(gè)合適的距離度量叠蝇。那么璃岳，何不直接嘗試“學(xué)習(xí)”出一個(gè)合適的距離度量呢？這就是度量學(xué)習(xí)的基本動(dòng)機(jī)
欲對(duì)距離度量進(jìn)行學(xué)習(xí)悔捶，我們需要為樣本之間的距離計(jì)算加上權(quán)重铃慷，并可以根據(jù)具體樣本來對(duì)權(quán)重進(jìn)行訓(xùn)練，這個(gè)權(quán)重構(gòu)成的矩陣我們稱為“度量矩陣”炎功。
度量學(xué)習(xí)的目的就是計(jì)算出合適的“度量矩陣”枚冗，在實(shí)際計(jì)算時(shí)缓溅，我們可以將度量矩陣 M 直接嵌入到近鄰分類器的評(píng)價(jià)體系中去蛇损，通過優(yōu)化該性能指標(biāo)相應(yīng)的求得 M.
2. 基礎(chǔ)知識(shí)
1）懶惰學(xué)習(xí)（lazy learning）
此類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來，訓(xùn)練時(shí)間開銷為零，待收到測試樣本后再進(jìn)行處理
2）急切學(xué)習(xí)（eager learning）
與懶惰學(xué)習(xí)相反淤齐，此類學(xué)習(xí)技術(shù)在訓(xùn)練階段就對(duì)樣本進(jìn)行學(xué)習(xí)處理
3）維度災(zāi)難（curse of dimensionality）
在高維情形下出現(xiàn)的樣本稀疏股囊、距離計(jì)算困難等問題，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙更啄，被稱為“維度災(zāi)難”
4）矩陣的跡（trace）
在線性代數(shù)中稚疹，一個(gè)n×n矩陣A的主對(duì)角線（從左上方至右下方的對(duì)角線）上各個(gè)元素的總和被稱為矩陣A的跡（或跡數(shù)），一般記作tr(A)祭务。
5）矩陣特征分解（Eigenvalue decomposition）
將矩陣分解為由其特征值和特征向量表示的矩陣之積的方法内狗。需要注意只有對(duì)可對(duì)角化矩陣才可以施以特征分解。簡單理解就是將矩陣變換為幾個(gè)相互垂直的向量的和义锥，比如在二維空間中柳沙，任意一個(gè)向量可以被表示為x軸和y軸的組合。
3. 總結(jié)
1）?k 近鄰學(xué)習(xí)是簡單常用的分類算法拌倍，在樣本分布充足時(shí)赂鲤，其最差誤差不超過貝葉斯最優(yōu)分類器的兩倍
2）實(shí)際情況下由于屬性維度過大，會(huì)導(dǎo)致“維數(shù)災(zāi)難”柱恤，這是所有機(jī)器學(xué)習(xí)中的共同障礙
3）緩解維數(shù)災(zāi)難的有效途徑是降維数初，即將高維樣本映射到低維空間中，這樣不僅屬性維度降低減少了計(jì)算開銷梗顺，還增大了樣本密度
4）降維過程中必定會(huì)對(duì)原始數(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)化為對(duì)距離度量計(jì)算的權(quán)重矩陣的學(xué)習(xí)
有趣的小數(shù)據(jù)：宇宙間基本粒子的總數(shù)約為10的80次方寺谤，而一琳涞拢灰塵中含有幾十億基本粒子，而要滿足k近鄰算法假設(shè)的屬性數(shù)量為20的樣本數(shù)量為10的60次方矗漾。
