導(dǎo)言

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

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

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

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

這里的橫軸是人臉相對于成像平面左右旋轉(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對各種游戲畫面下CNN提取的特征進(jìn)行了可視化。結(jié)果發(fā)現(xiàn)，需要采取相同動作的游戲畫面經(jīng)過CNN映射之后，其特征圖像用t-SNE投影后聚集在一起，這說明CNN確實(shí)學(xué)習(xí)得到了有用的游戲畫面信息。下圖是他們的實(shí)驗(yàn)結(jié)果：

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

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

目前已經(jīng)存在大量的數(shù)據(jù)降維算法，可以從另個(gè)不同的維度對它們進(jìn)行分類。按照是否有使用樣本的標(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進(jìn)行線性變換即左乘一個(gè)投影矩陣W而得到結(jié)果向量y

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

局部線性嵌入[8]（locally linear embedding，簡稱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)對第i個(gè)點(diǎn)的組合權(quán)重。權(quán)重系數(shù)通過最小化下面的重構(gòu)誤差確定

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

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

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

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

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

拉普拉斯特征映[9]射通過對圖的拉普拉斯矩陣進(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，它通過最小化如下目標(biāo)函數(shù)實(shí)現(xiàn)

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

其中

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

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

局部保持投影（Locality preserving projections，簡稱LPP）[10]通過最好的保持一個(gè)數(shù)據(jù)集的鄰居結(jié)構(gòu)信息來構(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)化問題等價(jià)于求解下面的問題

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

該問題的解即為投影方向。

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

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

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

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

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

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

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

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

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

這里對所有樣本點(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問題（crowding problem）。t分布隨機(jī)近鄰嵌入（t-distributed Stochastic Neighbor Embedding，簡稱t-SNE）[13]是對SNE的改進(jìn)。t-SNE采用了對稱的概率計(jì)算公式，另外在低維空間中計(jì)算樣本點(diǎn)之間的概率時(shí)使用t分布代替了正態(tài)分布。

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

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

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

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

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

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

t-SNE雖然效果好，但有計(jì)算量大的問題。從名字就可以看出，LargeVis[14]的目標(biāo)是大規(guī)模數(shù)據(jù)集的可視化，是對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è)為LargeVis的降維結(jié)果。