導(dǎo)言
數(shù)據(jù)降維算法是機器學(xué)習(xí)算法中的大家族，與分類、回歸、聚類等算法不同，它的目標(biāo)是將向量投影到低維空間，以達到某種目的如可視化，或是做分類。本文對數(shù)據(jù)降維算法做了較為詳細的總結(jié)，是對《機器學(xué)習(xí)與應(yīng)用》，清華大學(xué)出版社，雷明著一書第1版的補充，該書自2019年1月份出版以來，已經(jīng)重印4次，最近一次重印修正了之前已經(jīng)發(fā)現(xiàn)的所有筆誤與印刷錯誤，優(yōu)化后的第2版將在上半年出版。本文所列的大部分內(nèi)容都將在第2版中詳細講述。對于流形學(xué)習(xí)，之前SIGAI已經(jīng)寫過一篇簡單的文章“流形學(xué)習(xí)概述”，由于當(dāng)時的時間倉促，還不夠全面，本文更為全面。限于篇幅，對每種算法不做具體的推導(dǎo)，詳細的推導(dǎo)和證明可以閱讀《機器學(xué)習(xí)與應(yīng)用》的第1版或第2版。
什么是降維問題
數(shù)據(jù)降維從字面看很容易理解，就是把向量變換到低維空間中，即降低向量的維數(shù)。初學(xué)者可能會有一個疑問：為什么要這個事情？下面我們來看一個例子。大家都知道MNIST手寫數(shù)字?jǐn)?shù)據(jù)集，它們是這樣的黑白圖像
該數(shù)據(jù)集包括0-9這10個阿拉伯?dāng)?shù)字，每張圖像為28x28像素。如果將這些像素拼接起來，則為784維的向量。你是否想過，在784維的空間中，這些樣本是如何分布的？。按道理來說，同樣的字，如“1”，應(yīng)該有規(guī)律的分布在784維空間中的某一或幾個區(qū)域中。單我們只能“想象”，因為人能直觀看到的空間，最多為3維。通過數(shù)據(jù)降維，可以將這些數(shù)字投影到3維空間中并進行可視化，下圖是投影后的效果：
在低維空間中，相同的數(shù)字往往分布在一起，如果這種投影保持了高維空間中的數(shù)據(jù)分布特性，則我們可認(rèn)為在高維空間中相同的數(shù)字也分布在某一或多個區(qū)域內(nèi)。
人臉圖像也是高維空間中的向量，它在空間中的分布受人臉的身份（不同的人的臉有不同的外觀），光照，角度等因素的影響。通過對人臉數(shù)據(jù)進行降維，可以觀察這些因素對人臉在空間中的分布所產(chǎn)生的影響，下圖形象了說明了這一做法。
這里的橫軸是人臉相對于成像平面左右旋轉(zhuǎn)的角度，縱軸為上下旋轉(zhuǎn)的角度， 另外哈加上了光照方向信息。從這張圖中我們可以清晰的看到這些因素是如何影響人臉在高維空間中分布的。
再舉一個例子。Google DeepMind公司當(dāng)年提出的DQN（用深度強化學(xué)習(xí)打Atari游戲）開深度強化學(xué)習(xí)之先河，為了驗證CNN學(xué)習(xí)到的特征的有效性，論文里用t-SNE對各種游戲畫面下CNN提取的特征進行了可視化。結(jié)果發(fā)現(xiàn)，需要采取相同動作的游戲畫面經(jīng)過CNN映射之后，其特征圖像用t-SNE投影后聚集在一起，這說明CNN確實學(xué)習(xí)得到了有用的游戲畫面信息。下圖是他們的實驗結(jié)果：
除了便于可視化，數(shù)據(jù)降維算法還可以提升分類、聚類算的精度，避免維數(shù)災(zāi)難問題。抽象來看，數(shù)據(jù)降維就是尋找一個映射函數(shù)f，將高維向量x映射成低維向量y
如何確定這個映射函數(shù)，是各降維算法核心，它們往往根據(jù)不同的準(zhǔn)則進行構(gòu)造。
降維算法的分類
目前已經(jīng)存在大量的數(shù)據(jù)降維算法，可以從另個不同的維度對它們進行分類。按照是否有使用樣本的標(biāo)簽值，可以將降維算法分為有監(jiān)督降維和無監(jiān)督降維；按照降維算法使用的映射函數(shù)，可以將算法分為線性降維與非線性降維。
無監(jiān)督降維算法不使用樣本標(biāo)簽值，因此是一種無監(jiān)督學(xué)習(xí)算法，其典型代表是PCA。有監(jiān)督的降維算法則使用了樣本標(biāo)簽值，是一種有監(jiān)督學(xué)習(xí)算法，其典型代表是LDA。
線性降維算根據(jù)樣本集構(gòu)造出線性函數(shù)完成向低維空間的映射。一般通過對向量x進行線性變換即左乘一個投影矩陣W而得到結(jié)果向量y
非線性降維算法則構(gòu)造一個非線性映射完成數(shù)據(jù)的降維。很多時候數(shù)據(jù)是非線性的，因此需要使用非線性降維算法以取得更好的效果。
PCA
PCA[1]是最基礎(chǔ)的無監(jiān)督降維算法，其目標(biāo)是向數(shù)據(jù)變化最大的方向投影，或者說向重構(gòu)誤差最小化的方向投影。如果要將向量投影到d' 維的空間，每個向量可以表示成
在這里ei 都是單位向量，并且相互正交，是PCA的投影方向。重構(gòu)誤差函為
使得該函數(shù)取最小值的ej 為散度矩陣最大的d' 個特征值對應(yīng)的單位長度特征向量。通過拉格朗日乘數(shù)法可以證明，最小化重構(gòu)誤差等價于求解下面的特征值問題
其中tr為矩陣的跡，I為單位矩陣，S是樣本的協(xié)方差矩陣。等式約束保證投影基向量是標(biāo)準(zhǔn)正交基。矩陣W的ej 列是要求解的基向量。在得到投影矩陣W之后，先將x減掉均值向量m，然后左乘矩陣W即可完成降維。
下圖是用PCA對MNIST數(shù)據(jù)集投影后的結(jié)果
LDA
LDA[2-3]的目標(biāo)是向最大化內(nèi)間差異，最小化類內(nèi)差異的方向投影，以利于分類等任務(wù)即將不同類的樣本有效的分開。這歸結(jié)為求解下面的優(yōu)化問題
其中tr為矩陣的跡，SB為類間散度矩陣，Sw為類內(nèi)散度矩陣，W為投影矩陣。分子反映了類間差異，需要最大化；分母反映了類內(nèi)差異，需要最小化。這個問題存在冗余，加上約束條件消掉冗余，等價于優(yōu)化下面的問題
使該目標(biāo)函數(shù)最大的W的列w必須滿足
通過拉格朗日乘數(shù)法可以證明，最優(yōu)解是矩陣Sw-1SB的特征值和特征向量。矩陣Sw-1SB可能有d個特征值和特征向量，要將向量投影到c-1維，為此挑選出最大的c-1個特征值以及它們對應(yīng)的特征向量，組成投影矩陣W。
下圖是將MNIST數(shù)據(jù)集投影到3維空間后的結(jié)果。
LDA是一種有監(jiān)督的線性降維算法，因為在計算散度矩陣的時候使用了樣本標(biāo)簽值。
MDS
MDS（multidimensional scaling）[4]通過計算任意兩個樣本點之間的距離，使得投影到低維空間之后能夠保持這種相對距離而實現(xiàn)投影。
首選計算任意兩個樣本xi 以及xj 之間的距離，然后通過求解下面的最優(yōu)化問題得到投影結(jié)果y
上面目標(biāo)函數(shù)的含義是，投影到低維空間之后，要保證樣本之間的距離|| yi -yj ||與在原始空間中它們之間的距離dij 盡量接近，否則會產(chǎn)生一個大的損失。這就保證了距離較遠的樣本投影之后依然距離較遠，距離較近的樣本投影之后距離依然較近。
相比之下非線性降維算法的家族更為龐大。可以分為使用核（kernel）技術(shù)的方法，基于流形的降維算法，以及使用神經(jīng)網(wǎng)絡(luò)的降維算法。這里介紹前面兩類方法，基于神經(jīng)網(wǎng)絡(luò)的算法在本文中則不做介紹。
基于核技術(shù)的方法
核是機器學(xué)習(xí)中一種技術(shù)，通過對原始數(shù)據(jù)進行非線性的映射，使得原本線性不可解的問題在另外一個空間中變得可能會線性可解。典型的代表是支持向量機中的核函數(shù)，它將原本線性不可分的問題變得可能會線性可分。下圖是用高斯核函數(shù)的支持向量機所擬合出來的分類邊界線，為曲線
將核技術(shù)用于降維算法，可以使得PCA與LDA這樣的線性降維算法能夠處理非線性降維問題。
直接用一個函數(shù)將x映射為另一個空間中的向量y不易構(gòu)造，核函數(shù)巧妙的避開了此問題，通過用核函數(shù)K對兩個向量進行映射，等價于先對兩個向量進行映射后再做內(nèi)積
對于核函數(shù)以及支持向量機的介紹，可以閱讀SIGAI之前的公眾號文章“用一張圖理解支持向量機的脈絡(luò)”或閱讀《機器學(xué)習(xí)與應(yīng)用》一書，相信這是市面上已知的對SVM最清晰透徹的闡述。(小編推薦：詳解支持向量機)
KPCA
KPCA（kernel PCA）[5]是核技術(shù)與PCA結(jié)合的產(chǎn)物。主要的改進在于計算協(xié)方差矩陣時使用了核函數(shù)，即是經(jīng)過核函數(shù)映射之后的協(xié)方差矩陣。與支持向量機類似，可以采用高斯核，多項式核。由于整體原理與PCA類似，在這里不做詳細介紹。
KLDA
與KPCA類似，KLDA（kernel PCA）[6-7]是核技術(shù)與PCA結(jié)合的產(chǎn)物。相對于LDA的主要改進是計算類內(nèi)散度矩陣與類間散度矩陣的時候使用了核函數(shù)。由于整體原理與LDA類似，在這里不做詳細介紹。
流形學(xué)習(xí)
流形是幾何中的一個概念，是高維空間中的某種幾何結(jié)構(gòu)即空間中的點構(gòu)成的集合，可以簡單的將流形理解成二維空間的曲線，三維空間的曲面等幾何體在更高維空間的推廣。下圖是三維空間中的一個流形
這是一個卷曲的面。我們相信很多應(yīng)用問題的數(shù)據(jù)在高維空間中的分布具有某種幾何形狀，即位于一個低維的流形附近。同一個人的人臉圖像向量在高維空間中可能是一個復(fù)雜的形狀。流形學(xué)習(xí)假設(shè)原始數(shù)據(jù)在高維空間的分布位于某一更低維的流形上，基于這個假設(shè)來進行數(shù)據(jù)的分析。對于降維，要保證降維之后的數(shù)據(jù)同樣滿足與高維空間流形有關(guān)的幾何約束關(guān)系，由此演化出各種流形降維算法。
LLE
局部線性嵌入[8]（locally linear embedding，簡稱LLE）將高維數(shù)據(jù)投影到低維空間中，保持?jǐn)?shù)據(jù)點之間的局部線性關(guān)系。核心思想是每個點可以由與它相鄰的多個點的線性組合而近似重構(gòu)，投影到低維空間之后要保持這種線性重構(gòu)關(guān)系，即有相同的重構(gòu)系數(shù)。
假設(shè)數(shù)據(jù)集由n個D維向量xi 組成，它們分布于D維空間中的某一流形附近。每個數(shù)據(jù)點和它的鄰居位于或者接近于流形的一個局部線性片段上，即可以用鄰居點的線性組合近似重構(gòu)
權(quán)重wij 為第j個數(shù)據(jù)點對第i個點的組合權(quán)重。權(quán)重系數(shù)通過最小化下面的重構(gòu)誤差確定
這里附加了兩個約束條件：每個點只由它的鄰居來重構(gòu)，如果xj 不在xi 的鄰居集合里則權(quán)重值為0。另外權(quán)重矩陣的每一行元素之和為1，即
求解該問題可以得到權(quán)重系數(shù)。
假設(shè)算法將向量從D維空間的x映射為d維空間的y。每個點在d維空間中的坐標(biāo)由下面的最優(yōu)化問題確定
這里的權(quán)重和上一個優(yōu)化問題的值相同，在前面已經(jīng)得到，是已知量。這里優(yōu)化的目標(biāo)是yi ，此優(yōu)化問題等價于求解稀疏矩陣的特征值問題。得到y(tǒng)之后，即完成了降維。
下圖是用LLE對MNIST數(shù)據(jù)集降維后的結(jié)果。
拉普拉斯特征映射
拉普拉斯特征映[9]射通過對圖的拉普拉斯矩陣進行特征值分解而完成數(shù)據(jù)降維。它為樣本集構(gòu)造相似度圖，然后計算拉普拉斯矩陣。如果圖的鄰接矩陣為W，加權(quán)度矩陣為D，拉普拉斯矩陣定義為
算法為樣本點構(gòu)造加權(quán)圖，圖的節(jié)點是每一個樣本點，邊為每個節(jié)點與它的鄰居節(jié)點之間的相似度，每個節(jié)點只和它的鄰居有連接關(guān)系。降維的目標(biāo)是投影之后保持在高維空間中的距離關(guān)系，假設(shè)投影后到低維空間后的坐標(biāo)為y，它通過最小化如下目標(biāo)函數(shù)實現(xiàn)
此函數(shù)的含義是如果樣本xi 和xj 的相似度很高即在高維空間中距離很近，則它們之間的邊的權(quán)重wij 很大，因此投影到低維空間中后兩個點要離得很近，即yi 和yj 要很接近，否則會產(chǎn)生一大個的損失值。求解該目標(biāo)函數(shù)等價于下面的優(yōu)化問題
其中
為投影后的坐標(biāo)按列構(gòu)成的矩陣，這里加上了等式約束條件以消掉y的冗余，選用矩陣D來構(gòu)造等式約束是因為其主對角線元素即節(jié)點的加權(quán)度反映了圖的每個節(jié)點的重要性。通過拉格朗日乘數(shù)法可以證明，這個問題的最優(yōu)解是如下廣義值問題的解
這個廣義特征值問題的所有特征值非負(fù)。最優(yōu)解為這個廣義特征值問題除去0之外的最小的d個廣義特征值對應(yīng)的特征向量，這些向量按照列構(gòu)成矩陣Y，即為投影結(jié)果。
局部保持投影
局部保持投影（Locality preserving projections，簡稱LPP）[10]通過最好的保持一個數(shù)據(jù)集的鄰居結(jié)構(gòu)信息來構(gòu)造投影映射，其思路和拉普拉斯特征映射類似，區(qū)別在于不是直接得到投影結(jié)果而是求解投影矩陣。
假設(shè)有樣本集x1 ,...,xm。這里的目標(biāo)是尋找一個變換矩陣A，將這些樣本點映射到更低維的空間，得到向量y1 ,...,ym，使得yi 能夠代表xi
目標(biāo)函數(shù)與拉普拉斯特征映射相同，定義為
所有矩陣的定義與拉普拉斯特征映射相同。投影變換矩陣為
即
假設(shè)矩陣x為所有樣本按照列構(gòu)成的矩陣。上面的最優(yōu)化問題等價于求解下面的問題
通過拉格朗日乘數(shù)法可以證明，此問題的最優(yōu)解是下面廣義特征值問題的解
該問題的解即為投影方向。
等距映射
等距映射（Isomap）[11]使用了微分幾何中測地線的概念，它希望數(shù)據(jù)在向低維空間映射之后能夠保持流形上的測地線距離。測地線源自于大地測量學(xué)，是地球上任意兩點之間在球面上的最短路徑。在三維空間中兩點之間的最短距離是它們之間線段的長度，但如果要沿著地球表面走，最短距離就是測地線的長度，因為不能從地球內(nèi)部穿過去。這里的測地線就是球面上兩點之間大圓上劣弧的長度。算法計算任意兩個樣本之間的測地距離，然后根據(jù)這個距離構(gòu)造距離矩陣。最后通過距離矩陣求解優(yōu)化問題完成數(shù)據(jù)的降維，降維之后的數(shù)據(jù)保留了原始數(shù)據(jù)點之間的距離信息。
同樣的需要先為樣本集構(gòu)造圖，然后計算任意兩個節(jié)點之間的測地距離，這通過經(jīng)典的Dijkstra算法實現(xiàn)。假設(shè)最短路徑長度為dG(i, j)，由它構(gòu)造如下矩陣：
其元素是所有節(jié)點對之間的最短路徑長度。然后根據(jù)矩陣DG構(gòu)造d維嵌入y，這通過求解如下最優(yōu)化問題實現(xiàn)
這個問題的解y即為降維之后的向量。可以看到，這個目標(biāo)函數(shù)與MDS及其類似，不同的是用測地距離替代了常用的距離。這個目標(biāo)函數(shù)的意義是向量降維之后任意兩點之間的距離要盡量的接近在原始空間中這兩點之間的最短路徑長度，因此可以認(rèn)為降維盡量保留了數(shù)據(jù)點之間的測地距離信息。
下圖是用等距映射對MNIST數(shù)據(jù)集降維后的結(jié)果。
SNE
隨機近鄰嵌入（stochastic neighbor embedding，簡稱SNE）[12]是一種基于概率的算法，基于如下思想：在高維空間中距離很近的點投影到低維空間中之后也要保持這種近鄰關(guān)系，在這里距離通過概率體現(xiàn)。假設(shè)在高維空間中有兩個點樣本點xi 和xj，xj 以pj\i 的概率作為xi 的鄰居，將樣本之間的歐氏距離轉(zhuǎn)化成概率值，借助于正態(tài)分布，此概率的計算公式為
假設(shè)xi 和xj 投影之后對應(yīng)的點為yi 和yj ，在低維空間中對應(yīng)的近鄰概率記為qj\i，計算公式與上面類似，即
上面定義的是一個點與它的一個鄰居點的概率關(guān)系，如果考慮所有其他點，這些概率值構(gòu)成一個離散型概率分布Pi ，是所有樣本點成為xi 的鄰居的概率。在低維空間中對應(yīng)的概率分布為Qi ，投影的目標(biāo)是這兩個概率分布盡可能接近，因此需要衡量兩個概率分布之間的相似度或距離。在機器學(xué)習(xí)中一般用KL（Kullback-Leibler）散度衡量兩個概率分布之間的距離。
由此得到投影的目標(biāo)為最小化如下函數(shù)
這里對所有樣本點的KL散度求和，l為樣本數(shù)。把概率的計算公式代入KL散度，可以將目標(biāo)函數(shù)寫成所有yi 的函數(shù)。得到的最優(yōu)值yi 即為xi 投影后的結(jié)果。
t-SNE
雖然SNE有較好的效果，但訓(xùn)練時難以優(yōu)化，且容易導(dǎo)致?lián)頂D問題（crowding problem）。t分布隨機近鄰嵌入（t-distributed Stochastic Neighbor Embedding，簡稱t-SNE）[13]是對SNE的改進。t-SNE采用了對稱的概率計算公式，另外在低維空間中計算樣本點之間的概率時使用t分布代替了正態(tài)分布。
在SNE中pi\j 和pj\i 是不相等的，因此概率值不對稱?？梢杂脙蓚€樣本點的聯(lián)合概率替代它們之間的條件概率解決此問題。在高維空間中兩個樣本點的聯(lián)合概率定義為
顯然這個定義是對稱的，即pij =pji 。同樣的，低維空間中兩個點的聯(lián)合概率為
目標(biāo)函數(shù)采用KL散度，定義為
但這樣定義聯(lián)合概率會存在異常值問題。如果某一個樣本xi 是異常點即離其他點很遠，則所有的
這樣能確保對所有的xi有
目標(biāo)函數(shù)同樣采用KL散度。下圖是t-SNE對MNIST數(shù)據(jù)集投影的結(jié)果。
LargeVis
t-SNE雖然效果好，但有計算量大的問題。從名字就可以看出，LargeVis[14]的目標(biāo)是大規(guī)模數(shù)據(jù)集的可視化，是對t-SNE的改進。主要改進點是高效的構(gòu)建kNN圖的算法，以及低維空間的概率計算公式，目標(biāo)函數(shù)。
借助于隨機投影樹，LargeVis可以高效的計算kNN圖，以此加速樣本點概率值的計算速度。LargeVis在原始空間中計算樣本概率分布的方法與t-SNE相同，但計算低維空間中概率分布時做了改進，兩個點之間有邊連接的概率為
其中
目標(biāo)函數(shù)定義為
其中E為圖的邊的集合，
參考文獻
[1] Ian T. Jolliffe. Principal Component Analysis. Springer Verlag, New York, 1986.
[2] Ronald A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7 Part 2: 179-188, 1936.
[3] Geoffrey J. McLachlan. Discriminant Analysis and Statistical Pattern Recognition. Wiley, New York, 1992.
[4] Torgerson, Warren S. (1958). Theory & Methods of Scaling. New York: Wiley. ISBN 978-0-89874-722-5.
[5] Scholkopf, B.,Smola,A.,Mulller,K.-P. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10(5), 1299-1319, 1998.
[6] Mika, S; R?tsch, G.; Weston, J.; Sch?lkopf, B.; Müller, KR (1999). Fisher discriminant analysis with kernels. Neural Networks for Signal Processing. IX. pp. 41–48.
[7] Baudat, G.; Anouar, F. (2000). Generalized discriminant analysis using a kernel approach. Neural Computation. 12 (10): 2385–2404.
[8] Roweis, Sam T and Saul, Lawrence K. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500). 2000: 2323-2326.
[9] Belkin, Mikhail and Niyogi, Partha. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation. 15(6). 2003:1373-1396.
[10] He Xiaofei and Niyogi, Partha. Locality preserving projections. NIPS. 2003:234-241.
[11] Tenenbaum, Joshua B and De Silva, Vin and Langford, John C. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500). 2000: 2319-2323.
[12] Geoffrey E Hinton, Sam T Roweis. Stochastic Neighbor Embedding. neural information processing systems, 2002.
[13] Maaten, Laurens van der, and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research 9.Nov (2008): 2579-2605.
[14] Visualizing Large-scale and High-dimensional Data. Jian Tang, Jingzhou Liu, Ming Zhang, Qiaozhu Mei. 2016, the web conference.
