最新經(jīng)驗(yàn)好文第一時(shí)間送達(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)理解）：給定測(cè)試樣本，基于某種距離度量找出訓(xùn)練集中與其距離最近的 k 個(gè)樣本,，然后基于這 k 個(gè)鄰居的信息來進(jìn)行預(yù)測(cè),。通常可以通過“投票法”或“平均法”來對(duì)測(cè)試樣本進(jìn)行預(yù)測(cè)（詳情請(qǐng)查看第八章集成學(xué)習(xí)）,。

KNN學(xué)習(xí)算法的一個(gè)特點(diǎn)是它并不需要提前對(duì)模型進(jìn)行訓(xùn)練,，只在預(yù)測(cè)時(shí)對(duì)訓(xùn)練樣本進(jìn)行計(jì)算即可得到預(yù)測(cè)結(jié)果，這是一個(gè)典型的“懶惰學(xué)習(xí)”的算法,。下圖是一個(gè) kNN 學(xué)習(xí)算法的示意圖：

顯然,，k的選擇十分重要，因?yàn)椴煌?/span> k 的選擇會(huì)導(dǎo)致預(yù)測(cè)的結(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)測(cè)試樣本都能找到一個(gè)鄰居，而要滿足這個(gè)條件可不是那么容易的,。

2.低維嵌入

對(duì)于之前的假設(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' 空間上的映射

MDS算法實(shí)際上在降維之前就進(jìn)行了大量的距離,、內(nèi)積計(jì)算,，這在數(shù)據(jù)樣本和屬性維度都十分大時(shí)是很耗資源和時(shí)間的，所以對(duì)于維度災(zāi)難來說,，MDS的緩解作用并不大,。一般來說要獲得低維子空間，最簡單的是對(duì)原始高維空間進(jìn)行線性變換,。

但是這個(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)為降維起到了效果。

前面的討論基于一個(gè)假設(shè): 對(duì)任意x和任意小正數(shù)δ, 在x附近δ距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本. 但是遺憾的是現(xiàn)實(shí)中很難滿足這種情況, 且隨著特征維數(shù)的增長, 所需要的樣本數(shù)會(huì)飛速增長, 且高維特征也會(huì)使得距離運(yùn)算更加耗時(shí),。

這種在高維情況下出現(xiàn)的樣本稀疏, 計(jì)算困難等問題, 是許多ML方法都面臨的共同問題,稱為維數(shù)災(zāi)難,。

緩解維數(shù)災(zāi)難的一種方法就是降維, 又稱維數(shù)約簡, 即將原始高維屬性空間轉(zhuǎn)變成一個(gè)低維子空間。
降維的依據(jù)在于, 雖然數(shù)據(jù)樣本是高維的,但是與學(xué)習(xí)任務(wù)密切相關(guān)的也許僅僅是某個(gè)低維分布,。

3.主成分分析

主成分分析（Principle Component Analysis,，簡稱PCA ）是最常用的一種降維方法，它是基于這樣的核心思想來設(shè)計(jì)的：對(duì)于一組樣本,，如果存在一個(gè)超平面使得樣本在上邊的距離都足夠近或者投影都盡可能分開,，那么這個(gè)超平面是對(duì)這組樣本的一個(gè)很恰當(dāng)?shù)谋硎尽?/span>

那么這個(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' 取值。

4.核化線性降維

在現(xiàn)實(shí)任務(wù)中,，有時(shí)候直接使用線性降維會(huì)導(dǎo)致部分信息丟失的,，本書舉的例子是基于這樣的一個(gè)場(chǎng)景，低維空間映射到高維空間后,，再次降維到低維空間會(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.流形學(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),，對(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í)

在機(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。

用一張圖來匯總一些降維方法:

二．基礎(chǔ)知識(shí)

懶惰學(xué)習(xí)（lazy learning）：此類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來,，訓(xùn)練時(shí)間開銷為零,，待收到測(cè)試樣本后再進(jìn)行處理

急切學(xué)習(xí)（eager learning）：與懶惰學(xué)習(xí)相反，此類學(xué)習(xí)技術(shù)在訓(xùn)練階段就對(duì)樣本進(jìn)行學(xué)習(xí)處理

維度災(zāi)難（curse of dimensionality）：在高維情形下出現(xiàn)的樣本稀疏,、距離計(jì)算困難等問題,，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙，被稱為“維度災(zāi)難”

矩陣的跡（trace）：在線性代數(shù)中,，一個(gè)n×n矩陣A的主對(duì)角線（從左上方至右下方的對(duì)角線）上各個(gè)元素的總和被稱為矩陣A的跡（或跡數(shù)）,，一般記作tr(A)。

矩陣特征分解（Eigenvalue decomposition）：將矩陣分解為由其特征值和特征向量表示的矩陣之積的方法,。需要注意只有對(duì)可對(duì)角化矩陣才可以施以特征分解,。簡單理解就是將矩陣變換為幾個(gè)相互垂直的向量的和，比如在二維空間中,，任意一個(gè)向量可以被表示為x軸和y軸的組合,。

三．總結(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次方，而一?；覊m中含有幾十億基本粒子,，而要滿足k近鄰算法假設(shè)的屬性數(shù)量為20的樣本數(shù)量為10的60次方。

四．本章腦圖

END