導(dǎo)言

數(shù)據(jù)降維從字面看很容易理解，就是把向量變換到低維空間中，即降低向量的維數(shù)。初學(xué)者可能會(huì)有一個(gè)疑問(wèn)：為什么要這個(gè)事情？下面我們來(lái)看一個(gè)例子。大家都知道MNIST手寫數(shù)字?jǐn)?shù)據(jù)集，它們是這樣的黑白圖像

該數(shù)據(jù)集包括0-9這10個(gè)阿拉伯?dāng)?shù)字，每張圖像為28x28像素。如果將這些像素拼接起來(lái)，則為784維的向量。你是否想過(guò)，在784維的空間中，這些樣本是如何分布的？。按道理來(lái)說(shuō)，同樣的字，如“1”，應(yīng)該有規(guī)律的分布在784維空間中的某一或幾個(gè)區(qū)域中。單我們只能“想象”，因?yàn)槿四苤庇^看到的空間，最多為3維。通過(guò)數(shù)據(jù)降維，可以將這些數(shù)字投影到3維空間中并進(jìn)行可視化，下圖是投影后的效果：

在低維空間中，相同的數(shù)字往往分布在一起，如果這種投影保持了高維空間中的數(shù)據(jù)分布特性，則我們可認(rèn)為在高維空間中相同的數(shù)字也分布在某一或多個(gè)區(qū)域內(nèi)。

人臉圖像也是高維空間中的向量，它在空間中的分布受人臉的身份（不同的人的臉有不同的外觀），光照，角度等因素的影響。通過(guò)對(duì)人臉數(shù)據(jù)進(jìn)行降維，可以觀察這些因素對(duì)人臉在空間中的分布所產(chǎn)生的影響，下圖形象了說(shuō)明了這一做法。

這里的橫軸是人臉相對(duì)于成像平面左右旋轉(zhuǎn)的角度，縱軸為上下旋轉(zhuǎn)的角度， 另外哈加上了光照方向信息。從這張圖中我們可以清晰的看到這些因素是如何影響人臉在高維空間中分布的。

再舉一個(gè)例子。Google DeepMind公司當(dāng)年提出的DQN（用深度強(qiáng)化學(xué)習(xí)打Atari游戲）開深度強(qiáng)化學(xué)習(xí)之先河，為了驗(yàn)證CNN學(xué)習(xí)到的特征的有效性，論文里用t-SNE對(duì)各種游戲畫面下CNN提取的特征進(jìn)行了可視化。結(jié)果發(fā)現(xiàn)，需要采取相同動(dòng)作的游戲畫面經(jīng)過(guò)CNN映射之后，其特征圖像用t-SNE投影后聚集在一起，這說(shuō)明CNN確實(shí)學(xué)習(xí)得到了有用的游戲畫面信息。下圖是他們的實(shí)驗(yàn)結(jié)果：

除了便于可視化，數(shù)據(jù)降維算法還可以提升分類、聚類算的精度，避免維數(shù)災(zāi)難問(wèn)題。抽象來(lái)看，數(shù)據(jù)降維就是尋找一個(gè)映射函數(shù)f，將高維向量x映射成低維向量y

如何確定這個(gè)映射函數(shù)，是各降維算法核心，它們往往根據(jù)不同的準(zhǔn)則進(jìn)行構(gòu)造。

目前已經(jīng)存在大量的數(shù)據(jù)降維算法，可以從另個(gè)不同的維度對(duì)它們進(jìn)行分類。按照是否有使用樣本的標(biāo)簽值，可以將降維算法分為有監(jiān)督降維和無(wú)監(jiān)督降維；按照降維算法使用的映射函數(shù)，可以將算法分為線性降維與非線性降維。

無(wú)監(jiān)督降維算法不使用樣本標(biāo)簽值，因此是一種無(wú)監(jiān)督學(xué)習(xí)算法，其典型代表是PCA。有監(jiān)督的降維算法則使用了樣本標(biāo)簽值，是一種有監(jiān)督學(xué)習(xí)算法，其典型代表是LDA。

線性降維算根據(jù)樣本集構(gòu)造出線性函數(shù)完成向低維空間的映射。一般通過(guò)對(duì)向量x進(jìn)行線性變換即左乘一個(gè)投影矩陣W而得到結(jié)果向量y

非線性降維算法則構(gòu)造一個(gè)非線性映射完成數(shù)據(jù)的降維。很多時(shí)候數(shù)據(jù)是非線性的，因此需要使用非線性降維算法以取得更好的效果。

PCA[1]是最基礎(chǔ)的無(wú)監(jiān)督降維算法，其目標(biāo)是向數(shù)據(jù)變化最大的方向投影，或者說(shuō)向重構(gòu)誤差最小化的方向投影。如果要將向量投影到d' 維的空間，每個(gè)向量可以表示成

在這里ei 都是單位向量，并且相互正交，是PCA的投影方向。重構(gòu)誤差函為

使得該函數(shù)取最小值的ej 為散度矩陣最大的d' 個(gè)特征值對(duì)應(yīng)的單位長(zhǎng)度特征向量。通過(guò)拉格朗日乘數(shù)法可以證明，最小化重構(gòu)誤差等價(jià)于求解下面的特征值問(wèn)題

其中tr為矩陣的跡，I為單位矩陣，S是樣本的協(xié)方差矩陣。等式約束保證投影基向量是標(biāo)準(zhǔn)正交基。矩陣W的ej 列是要求解的基向量。在得到投影矩陣W之后，先將x減掉均值向量m，然后左乘矩陣W即可完成降維。

下圖是用PCA對(duì)MNIST數(shù)據(jù)集投影后的結(jié)果

LDA[2-3]的目標(biāo)是向最大化內(nèi)間差異，最小化類內(nèi)差異的方向投影，以利于分類等任務(wù)即將不同類的樣本有效的分開。這歸結(jié)為求解下面的優(yōu)化問(wèn)題

其中tr為矩陣的跡，SB為類間散度矩陣，Sw為類內(nèi)散度矩陣，W為投影矩陣。分子反映了類間差異，需要最大化；分母反映了類內(nèi)差異，需要最小化。這個(gè)問(wèn)題存在冗余，加上約束條件消掉冗余，等價(jià)于優(yōu)化下面的問(wèn)題

使該目標(biāo)函數(shù)最大的W的列w必須滿足

通過(guò)拉格朗日乘數(shù)法可以證明，最優(yōu)解是矩陣Sw-1SB的特征值和特征向量。矩陣Sw-1SB可能有d個(gè)特征值和特征向量，要將向量投影到c-1維，為此挑選出最大的c-1個(gè)特征值以及它們對(duì)應(yīng)的特征向量，組成投影矩陣W。

下圖是將MNIST數(shù)據(jù)集投影到3維空間后的結(jié)果。

LDA是一種有監(jiān)督的線性降維算法，因?yàn)樵谟?jì)算散度矩陣的時(shí)候使用了樣本標(biāo)簽值。

MDS（multidimensional scaling）[4]通過(guò)計(jì)算任意兩個(gè)樣本點(diǎn)之間的距離，使得投影到低維空間之后能夠保持這種相對(duì)距離而實(shí)現(xiàn)投影。

首選計(jì)算任意兩個(gè)樣本xi 以及xj 之間的距離，然后通過(guò)求解下面的最優(yōu)化問(wèn)題得到投影結(jié)果y

上面目標(biāo)函數(shù)的含義是，投影到低維空間之后，要保證樣本之間的距離|| yi -yj ||與在原始空間中它們之間的距離dij 盡量接近，否則會(huì)產(chǎn)生一個(gè)大的損失。這就保證了距離較遠(yuǎn)的樣本投影之后依然距離較遠(yuǎn)，距離較近的樣本投影之后距離依然較近。

相比之下非線性降維算法的家族更為龐大?？梢苑譃槭褂煤耍╧ernel）技術(shù)的方法，基于流形的降維算法，以及使用神經(jīng)網(wǎng)絡(luò)的降維算法。這里介紹前面兩類方法，基于神經(jīng)網(wǎng)絡(luò)的算法在本文中則不做介紹。

核是機(jī)器學(xué)習(xí)中一種技術(shù)，通過(guò)對(duì)原始數(shù)據(jù)進(jìn)行非線性的映射，使得原本線性不可解的問(wèn)題在另外一個(gè)空間中變得可能會(huì)線性可解。典型的代表是支持向量機(jī)中的核函數(shù)，它將原本線性不可分的問(wèn)題變得可能會(huì)線性可分。下圖是用高斯核函數(shù)的支持向量機(jī)所擬合出來(lái)的分類邊界線，為曲線

將核技術(shù)用于降維算法，可以使得PCA與LDA這樣的線性降維算法能夠處理非線性降維問(wèn)題。

直接用一個(gè)函數(shù)將x映射為另一個(gè)空間中的向量y不易構(gòu)造，核函數(shù)巧妙的避開了此問(wèn)題，通過(guò)用核函數(shù)K對(duì)兩個(gè)向量進(jìn)行映射，等價(jià)于先對(duì)兩個(gè)向量進(jìn)行映射后再做內(nèi)積

對(duì)于核函數(shù)以及支持向量機(jī)的介紹，可以閱讀SIGAI之前的公眾號(hào)文章“用一張圖理解支持向量機(jī)的脈絡(luò)”或閱讀《機(jī)器學(xué)習(xí)與應(yīng)用》一書，相信這是市面上已知的對(duì)SVM最清晰透徹的闡述。(小編推薦：詳解支持向量機(jī))

KPCA（kernel PCA）[5]是核技術(shù)與PCA結(jié)合的產(chǎn)物。主要的改進(jìn)在于計(jì)算協(xié)方差矩陣時(shí)使用了核函數(shù)，即是經(jīng)過(guò)核函數(shù)映射之后的協(xié)方差矩陣。與支持向量機(jī)類似，可以采用高斯核，多項(xiàng)式核。由于整體原理與PCA類似，在這里不做詳細(xì)介紹。

與KPCA類似，KLDA（kernel PCA）[6-7]是核技術(shù)與PCA結(jié)合的產(chǎn)物。相對(duì)于LDA的主要改進(jìn)是計(jì)算類內(nèi)散度矩陣與類間散度矩陣的時(shí)候使用了核函數(shù)。由于整體原理與LDA類似，在這里不做詳細(xì)介紹。

流形是幾何中的一個(gè)概念，是高維空間中的某種幾何結(jié)構(gòu)即空間中的點(diǎn)構(gòu)成的集合，可以簡(jiǎn)單的將流形理解成二維空間的曲線，三維空間的曲面等幾何體在更高維空間的推廣。下圖是三維空間中的一個(gè)流形

這是一個(gè)卷曲的面。我們相信很多應(yīng)用問(wèn)題的數(shù)據(jù)在高維空間中的分布具有某種幾何形狀，即位于一個(gè)低維的流形附近。同一個(gè)人的人臉圖像向量在高維空間中可能是一個(gè)復(fù)雜的形狀。流形學(xué)習(xí)假設(shè)原始數(shù)據(jù)在高維空間的分布位于某一更低維的流形上，基于這個(gè)假設(shè)來(lái)進(jìn)行數(shù)據(jù)的分析。對(duì)于降維，要保證降維之后的數(shù)據(jù)同樣滿足與高維空間流形有關(guān)的幾何約束關(guān)系，由此演化出各種流形降維算法。

局部線性嵌入[8]（locally linear embedding，簡(jiǎn)稱LLE）將高維數(shù)據(jù)投影到低維空間中，保持?jǐn)?shù)據(jù)點(diǎn)之間的局部線性關(guān)系。核心思想是每個(gè)點(diǎn)可以由與它相鄰的多個(gè)點(diǎn)的線性組合而近似重構(gòu)，投影到低維空間之后要保持這種線性重構(gòu)關(guān)系，即有相同的重構(gòu)系數(shù)。

假設(shè)數(shù)據(jù)集由n個(gè)D維向量xi 組成，它們分布于D維空間中的某一流形附近。每個(gè)數(shù)據(jù)點(diǎn)和它的鄰居位于或者接近于流形的一個(gè)局部線性片段上，即可以用鄰居點(diǎn)的線性組合近似重構(gòu)

權(quán)重wij 為第j個(gè)數(shù)據(jù)點(diǎn)對(duì)第i個(gè)點(diǎn)的組合權(quán)重。權(quán)重系數(shù)通過(guò)最小化下面的重構(gòu)誤差確定

這里附加了兩個(gè)約束條件：每個(gè)點(diǎn)只由它的鄰居來(lái)重構(gòu)，如果xj 不在xi 的鄰居集合里則權(quán)重值為0。另外權(quán)重矩陣的每一行元素之和為1，即

求解該問(wèn)題可以得到權(quán)重系數(shù)。

假設(shè)算法將向量從D維空間的x映射為d維空間的y。每個(gè)點(diǎn)在d維空間中的坐標(biāo)由下面的最優(yōu)化問(wèn)題確定

這里的權(quán)重和上一個(gè)優(yōu)化問(wèn)題的值相同，在前面已經(jīng)得到，是已知量。這里優(yōu)化的目標(biāo)是yi ，此優(yōu)化問(wèn)題等價(jià)于求解稀疏矩陣的特征值問(wèn)題。得到y(tǒng)之后，即完成了降維。

下圖是用LLE對(duì)MNIST數(shù)據(jù)集降維后的結(jié)果。

拉普拉斯特征映[9]射通過(guò)對(duì)圖的拉普拉斯矩陣進(jìn)行特征值分解而完成數(shù)據(jù)降維。它為樣本集構(gòu)造相似度圖，然后計(jì)算拉普拉斯矩陣。如果圖的鄰接矩陣為W，加權(quán)度矩陣為D，拉普拉斯矩陣定義為

算法為樣本點(diǎn)構(gòu)造加權(quán)圖，圖的節(jié)點(diǎn)是每一個(gè)樣本點(diǎn)，邊為每個(gè)節(jié)點(diǎn)與它的鄰居節(jié)點(diǎn)之間的相似度，每個(gè)節(jié)點(diǎn)只和它的鄰居有連接關(guān)系。降維的目標(biāo)是投影之后保持在高維空間中的距離關(guān)系，假設(shè)投影后到低維空間后的坐標(biāo)為y，它通過(guò)最小化如下目標(biāo)函數(shù)實(shí)現(xiàn)

此函數(shù)的含義是如果樣本xi 和xj 的相似度很高即在高維空間中距離很近，則它們之間的邊的權(quán)重wij 很大，因此投影到低維空間中后兩個(gè)點(diǎn)要離得很近，即yi 和yj 要很接近，否則會(huì)產(chǎn)生一大個(gè)的損失值。求解該目標(biāo)函數(shù)等價(jià)于下面的優(yōu)化問(wèn)題

其中

為投影后的坐標(biāo)按列構(gòu)成的矩陣，這里加上了等式約束條件以消掉y的冗余，選用矩陣D來(lái)構(gòu)造等式約束是因?yàn)槠渲鲗?duì)角線元素即節(jié)點(diǎn)的加權(quán)度反映了圖的每個(gè)節(jié)點(diǎn)的重要性。通過(guò)拉格朗日乘數(shù)法可以證明，這個(gè)問(wèn)題的最優(yōu)解是如下廣義值問(wèn)題的解

這個(gè)廣義特征值問(wèn)題的所有特征值非負(fù)。最優(yōu)解為這個(gè)廣義特征值問(wèn)題除去0之外的最小的d個(gè)廣義特征值對(duì)應(yīng)的特征向量，這些向量按照列構(gòu)成矩陣Y，即為投影結(jié)果。

局部保持投影（Locality preserving projections，簡(jiǎn)稱LPP）[10]通過(guò)最好的保持一個(gè)數(shù)據(jù)集的鄰居結(jié)構(gòu)信息來(lái)構(gòu)造投影映射，其思路和拉普拉斯特征映射類似，區(qū)別在于不是直接得到投影結(jié)果而是求解投影矩陣。

假設(shè)有樣本集x1 ,...,xm。這里的目標(biāo)是尋找一個(gè)變換矩陣A，將這些樣本點(diǎn)映射到更低維的空間，得到向量y1 ,...,ym，使得yi 能夠代表xi

目標(biāo)函數(shù)與拉普拉斯特征映射相同，定義為

所有矩陣的定義與拉普拉斯特征映射相同。投影變換矩陣為

即

假設(shè)矩陣x為所有樣本按照列構(gòu)成的矩陣。上面的最優(yōu)化問(wèn)題等價(jià)于求解下面的問(wèn)題

通過(guò)拉格朗日乘數(shù)法可以證明，此問(wèn)題的最優(yōu)解是下面廣義特征值問(wèn)題的解

該問(wèn)題的解即為投影方向。

等距映射（Isomap）[11]使用了微分幾何中測(cè)地線的概念，它希望數(shù)據(jù)在向低維空間映射之后能夠保持流形上的測(cè)地線距離。測(cè)地線源自于大地測(cè)量學(xué)，是地球上任意兩點(diǎn)之間在球面上的最短路徑。在三維空間中兩點(diǎn)之間的最短距離是它們之間線段的長(zhǎng)度，但如果要沿著地球表面走，最短距離就是測(cè)地線的長(zhǎng)度，因?yàn)椴荒軓牡厍騼?nèi)部穿過(guò)去。這里的測(cè)地線就是球面上兩點(diǎn)之間大圓上劣弧的長(zhǎng)度。算法計(jì)算任意兩個(gè)樣本之間的測(cè)地距離，然后根據(jù)這個(gè)距離構(gòu)造距離矩陣。最后通過(guò)距離矩陣求解優(yōu)化問(wèn)題完成數(shù)據(jù)的降維，降維之后的數(shù)據(jù)保留了原始數(shù)據(jù)點(diǎn)之間的距離信息。

同樣的需要先為樣本集構(gòu)造圖，然后計(jì)算任意兩個(gè)節(jié)點(diǎn)之間的測(cè)地距離，這通過(guò)經(jīng)典的Dijkstra算法實(shí)現(xiàn)。假設(shè)最短路徑長(zhǎng)度為dG(i, j)，由它構(gòu)造如下矩陣：

其元素是所有節(jié)點(diǎn)對(duì)之間的最短路徑長(zhǎng)度。然后根據(jù)矩陣DG構(gòu)造d維嵌入y，這通過(guò)求解如下最優(yōu)化問(wèn)題實(shí)現(xiàn)

這個(gè)問(wèn)題的解y即為降維之后的向量?？梢钥吹?，這個(gè)目標(biāo)函數(shù)與MDS及其類似，不同的是用測(cè)地距離替代了常用的距離。這個(gè)目標(biāo)函數(shù)的意義是向量降維之后任意兩點(diǎn)之間的距離要盡量的接近在原始空間中這兩點(diǎn)之間的最短路徑長(zhǎng)度，因此可以認(rèn)為降維盡量保留了數(shù)據(jù)點(diǎn)之間的測(cè)地距離信息。

下圖是用等距映射對(duì)MNIST數(shù)據(jù)集降維后的結(jié)果。

隨機(jī)近鄰嵌入（stochastic neighbor embedding，簡(jiǎn)稱SNE）[12]是一種基于概率的算法，基于如下思想：在高維空間中距離很近的點(diǎn)投影到低維空間中之后也要保持這種近鄰關(guān)系，在這里距離通過(guò)概率體現(xiàn)。假設(shè)在高維空間中有兩個(gè)點(diǎn)樣本點(diǎn)xi 和xj，xj 以pj\i 的概率作為xi 的鄰居，將樣本之間的歐氏距離轉(zhuǎn)化成概率值，借助于正態(tài)分布，此概率的計(jì)算公式為

假設(shè)xi 和xj 投影之后對(duì)應(yīng)的點(diǎn)為yi 和yj ，在低維空間中對(duì)應(yīng)的近鄰概率記為qj\i，計(jì)算公式與上面類似，即

上面定義的是一個(gè)點(diǎn)與它的一個(gè)鄰居點(diǎn)的概率關(guān)系，如果考慮所有其他點(diǎn)，這些概率值構(gòu)成一個(gè)離散型概率分布Pi ，是所有樣本點(diǎn)成為xi 的鄰居的概率。在低維空間中對(duì)應(yīng)的概率分布為Qi ，投影的目標(biāo)是這兩個(gè)概率分布盡可能接近，因此需要衡量?jī)蓚€(gè)概率分布之間的相似度或距離。在機(jī)器學(xué)習(xí)中一般用KL（Kullback-Leibler）散度衡量?jī)蓚€(gè)概率分布之間的距離。

由此得到投影的目標(biāo)為最小化如下函數(shù)

這里對(duì)所有樣本點(diǎn)的KL散度求和，l為樣本數(shù)。把概率的計(jì)算公式代入KL散度，可以將目標(biāo)函數(shù)寫成所有yi 的函數(shù)。得到的最優(yōu)值yi 即為xi 投影后的結(jié)果。

雖然SNE有較好的效果，但訓(xùn)練時(shí)難以優(yōu)化，且容易導(dǎo)致?lián)頂D問(wèn)題（crowding problem）。t分布隨機(jī)近鄰嵌入（t-distributed Stochastic Neighbor Embedding，簡(jiǎn)稱t-SNE）[13]是對(duì)SNE的改進(jìn)。t-SNE采用了對(duì)稱的概率計(jì)算公式，另外在低維空間中計(jì)算樣本點(diǎn)之間的概率時(shí)使用t分布代替了正態(tài)分布。

在SNE中pi\j 和pj\i 是不相等的，因此概率值不對(duì)稱?？梢杂脙蓚€(gè)樣本點(diǎn)的聯(lián)合概率替代它們之間的條件概率解決此問(wèn)題。在高維空間中兩個(gè)樣本點(diǎn)的聯(lián)合概率定義為

顯然這個(gè)定義是對(duì)稱的，即pij =pji 。同樣的，低維空間中兩個(gè)點(diǎn)的聯(lián)合概率為

目標(biāo)函數(shù)采用KL散度，定義為

但這樣定義聯(lián)合概率會(huì)存在異常值問(wèn)題。如果某一個(gè)樣本xi 是異常點(diǎn)即離其他點(diǎn)很遠(yuǎn)，則所有的都很大，因此與xi 有關(guān)的pij 很小，從而導(dǎo)致低維空間中的yi 對(duì)目標(biāo)函數(shù)影響很小。解決方法是重新定義高維空間中的聯(lián)合概率，具體為

這樣能確保對(duì)所有的xi有，因此每個(gè)樣本點(diǎn)都對(duì)目標(biāo)函數(shù)有顯著的貢獻(xiàn)。這種方法稱為對(duì)稱SNE。對(duì)稱SNE雖然對(duì)SNE做了改進(jìn)，但還存在擁擠問(wèn)題，各類樣本降維后聚集在一起而缺乏區(qū)分度。解決方法是用t分布替代高斯分布，計(jì)算低維空間中的概率值。相比于正態(tài)分布，t分布更長(zhǎng)尾。如果在低維空間中使用t分布，則在高維空間中距離近的點(diǎn)，在低維空間中距離也要近；但在高維空間中距離遠(yuǎn)的點(diǎn)，在低維空間中距離要更遠(yuǎn)。因此可以有效的拉大各個(gè)類之間的距離。使用t分布之后，低維空間中的概率計(jì)算公式為

目標(biāo)函數(shù)同樣采用KL散度。下圖是t-SNE對(duì)MNIST數(shù)據(jù)集投影的結(jié)果。

t-SNE雖然效果好，但有計(jì)算量大的問(wèn)題。從名字就可以看出，LargeVis[14]的目標(biāo)是大規(guī)模數(shù)據(jù)集的可視化，是對(duì)t-SNE的改進(jìn)。主要改進(jìn)點(diǎn)是高效的構(gòu)建kNN圖的算法，以及低維空間的概率計(jì)算公式，目標(biāo)函數(shù)。

借助于隨機(jī)投影樹，LargeVis可以高效的計(jì)算kNN圖，以此加速樣本點(diǎn)概率值的計(jì)算速度。LargeVis在原始空間中計(jì)算樣本概率分布的方法與t-SNE相同，但計(jì)算低維空間中概率分布時(shí)做了改進(jìn)，兩個(gè)點(diǎn)之間有邊連接的概率為

其中

目標(biāo)函數(shù)定義為

其中E為圖的邊的集合，為其補(bǔ)集。下圖是LargeVis與t-SNE的效果比較，左側(cè)為t-SNE的降維結(jié)果，右側(cè)為L(zhǎng)argeVis的降維結(jié)果。