論文題目：UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
作者：Leland McInnes； John Healy赡模； James Melville
時間：December 7, 2018

UMAP (Uniform Manifold Approximation and Projection) 算法是一種創(chuàng)新的降維流形學(xué)習(xí)算法师抄。Ideas 來自于拓?fù)鋽?shù)據(jù)分析。

論文整體思路

• UMAP uses local manifold approximations and patches together their local fuzzy simplicial set representations to construct a topological representation of the high dimensional data.
• a similar process can be used to construct an equivalent topological representation.
• then minimize the cross-entropy between the two topological representations.

背景補(bǔ)充

單純形 (Simplices)

從幾何上講，單純形是構(gòu)建 k 維對象的一種非常簡單的方法瞬矩。 k 維單純形稱為 k-單純形锋玲。它是由??+1個獨(dú)立點(diǎn)的凸包構(gòu)成的景用。因此惭蹂，0-單純形是一 個點(diǎn)，1-單純形是一條線段 (在兩個零單純形之間)媚污，2-單純形是一個三角形 (其中三個1-單純形作為“面”)廷雅，而3-單純形是一個四面體 (四個2-單純形作為“面”)。

單純形

單純復(fù)形 (Simplicial complex)

A simplicial complex is a set of simplices that satisfies the following conditions:

1. Every face of a simplex from is also in .
2. The non-empty intersection of any two simplices is a face of both .

(The convex hull of any nonempty subset of the n + 1 points that define an n-simplex is called a face of the simplex. )

單純復(fù)形 K 是單純形的集合商架。任意單純形的任何面也在 K 中(確保所有面都存在)芥玉，并且 K 中任何兩個單純形的交集都是這兩個單純形的面。

單純復(fù)形

理論應(yīng)用

假設(shè)一個有限的數(shù)據(jù)樣本集來自一個拓?fù)淇臻g飞傀，如果要了解該空間的拓?fù)洌枰壬稍摽臻g的開覆蓋 (open cover)弃鸦。

若數(shù)據(jù)實際處于 metric space幢痘，一種近似開覆蓋的方法是對每個數(shù)據(jù)點(diǎn)形成固定半徑的球。

舉例颜说，有一批數(shù)據(jù)位于假設(shè)的流形中。如圖所示：

Test data set of a noisy sine wave

如果固定一個半徑喊积，就可以把覆蓋的開放集想象成一個個圓（考慮二維）玄妈。

A basic open cover of the test data

構(gòu)造單純復(fù)形髓梅。 具體是指構(gòu)造?ech 復(fù)形绎签。

具體方法是：

讓覆蓋 (cover) 中的每個集合都是0-單純形；如果兩個集合具有非空交集诡必，則在它們之間創(chuàng)建1-單純形；如果三個這樣的集合的三重交集都非空爸舒，則在集合之間創(chuàng)建2-單純形；以此類推愉老。

然后剖效，我們可以將0-焰盗、1-和2-單純形的單純復(fù)形描繪為點(diǎn)、線和三角形熬拒。如圖所示：

A simplicial complex built from the test data

通過這樣的方法捕獲拓?fù)浣Y(jié)構(gòu)。

一些改進(jìn)

理論可行蛀序，但在實際數(shù)據(jù)上的效果不佳活烙。

問題1：如何為開覆蓋選擇正確的球半徑徐裸？

半徑太小 ---> 單純復(fù)形分裂為許多相連的組件啸盏。
半徑太大 ---> 單純復(fù)形變成維度很高的單純形，無法捕捉流形結(jié)構(gòu)气笙。

解決方案：

Assumption: Data is uniformly distributed on the manifold.

Open balls over uniformly_distributed_data

數(shù)據(jù)在流行上均勻分布怯晕，就不難選擇一個好的半徑。

數(shù)據(jù)均勻分布的假設(shè)在流形學(xué)習(xí)的其他地方也有舟茶。比如：拉普拉斯映射要證明有效蛉谜，就要假設(shè)數(shù)據(jù)是均勻分布的崇堵。

但是，現(xiàn)實中的數(shù)據(jù)不會是均勻分布的狰贯。問題反過來：假設(shè)數(shù)據(jù)均勻分布在流形上赏廓，我們能得到關(guān)于流形的什么信息？

即：距離的概念在流形上是不一樣的 - 空間扭曲：在數(shù)據(jù)看起來更稀疏或更密集的地方來拉伸或縮小幔摸。

引入黎曼幾何。
在流形上定義一個 Riemannian metric 讓假設(shè)為真既忆。
在黎曼空間里數(shù)據(jù)點(diǎn)是均勻分布的，但是放到歐幾里得空間就變成非均勻分布了跃脊。

球的大小在不同的度量下是不一樣的苛吱。在黎曼度量下球的 size 是一樣的，但放在歐幾里德空間就不一樣了翠储。

Open balls of radius one with a locally varying metric

通過假設(shè)數(shù)據(jù)是均勻分布的，可以通過使用一些標(biāo)準(zhǔn)的黎曼幾何來計算每個點(diǎn)的局部距離概念(其近似值)庐舟。圍繞一個點(diǎn)的單位球延伸到該點(diǎn)的第 k 個最近的鄰居任斋，其中 k 是我們用來近似局部距離的樣本大小。

每個點(diǎn)都有自己唯一的距離函數(shù)废酷，我們可以簡單地選擇半徑為1的球作為局部距離函數(shù)！

于是我們發(fā)現(xiàn)這不就是 k-近鄰圖嗎墨辛？

這意味著數(shù)據(jù)集中的每個點(diǎn)都被賦予了到其k個最近鄰居的每個點(diǎn)的邊-這是我們使用半徑為1的球的局部變化度量的有效結(jié)果趴俘。

對 k 的拓?fù)浣忉屪嘧福琸 的選擇決定了我們希望在多大程度上局部地估計黎曼度量太惠。選擇很小的k意味著我們想要一個非常局部的解釋，它將更準(zhǔn)確地捕捉到黎曼度量的精細(xì)細(xì)節(jié)結(jié)構(gòu)和變化凿渊。選擇較大的 k 意味著我們的估計將基于更大的區(qū)域，可以有更多數(shù)據(jù)來估計埃脏。

基于黎曼度量的另一個好處

我們實際上有一個與每個點(diǎn)相關(guān)聯(lián)的局部度量空間，并且可以有意義地測量距離构舟，因此可以根據(jù)邊上的點(diǎn)之間的距離(根據(jù)局部度量)來加權(quán)可能生成的圖的邊堵幽。

用模糊拓?fù)涞闹R來理解：在一個覆蓋的開集合不再是是和否的概念，而是介于 0 和 1 的模糊值谐檀。點(diǎn)在給定半徑的球里的確定性會隨著我們離開球的中心的移動而衰減。我們可以把這樣一個模糊的 cover 想象成如圖所示的樣子：

Fuzzy open balls of radius one with a locally varying metric

問題2：更高的維度上的數(shù)據(jù)很多點(diǎn)是完全孤立的。

解決方法：局部連接刽肠。

Assumption:
The manifold is locally connected.

Local connectivity and fuzzy open sets

由于維數(shù)詛咒音五，高維空間的數(shù)據(jù)惫撰，距離更大膜宋，但彼此也可能更相似琐脏。這意味著到第一個最近鄰居的距離可能相當(dāng)大夯膀，但到第十個最近鄰居的距離通常只會稍微大一點(diǎn)(相對而言)苍蔬。局部連接的約束確保我們關(guān)注最近鄰居之間的距離差異，而不是絕對距離(這顯示鄰居之間的差別很小)俺猿。

問題3：局部度量標(biāo)準(zhǔn)不兼容性。

每個點(diǎn)都有與其相關(guān)聯(lián)的局部度量押袍，并且從點(diǎn)a的角度來看，從點(diǎn)a到點(diǎn)b的距離可能是1.5汽馋，但是從點(diǎn)b的角度來看午笛，從點(diǎn)b到點(diǎn)a的距離可能只有0.6惭蟋。

基于圖形的直覺药磺，可認(rèn)為這是具有不同權(quán)重的有向邊，如下圖所示：

Edges with incompatible weights

解決方法：

將權(quán)重為 a 和 b 的兩條不一致的邊合并在一起木缝，那么我們應(yīng)該有一條具有組合權(quán)重 的邊围辙。考慮這一點(diǎn)的方法是矫俺，權(quán)重實際上是邊 (1-單純形) 存在的概率。然后厘托，組合權(quán)重是至少一條邊存在的概率稿湿。

如果我們應(yīng)用這個過程將所有模糊單純集合并在一起，我們最終得到一個單一的模糊單純復(fù)合體饺藤，我們可以再次將其視為一個加權(quán)圖。在計算方面罗丰，我們只是將邊權(quán)重組合公式應(yīng)用于整個圖 (非邊的權(quán)重為0)咽袜。最后，我們得到了類似這樣的東西询刹。

Graph with combined edge weights

因此萎坷，最終只是構(gòu)造了一個加權(quán)圖沐兰。但是背后有強(qiáng)大的數(shù)學(xué)知識在支撐。

因此瓜浸，假設(shè)我們現(xiàn)在有了數(shù)據(jù)的模糊拓?fù)浔硎?(數(shù)學(xué)上說它將捕獲數(shù)據(jù)背后的流形的拓?fù)?比原，我們?nèi)绾螌⑵滢D(zhuǎn)換為低維表示呢？

找到一個低維表示

目的：希望低維表示具有盡可能相似的模糊拓?fù)浣Y(jié)構(gòu)量窘。
第一個問題是如何確定低維表示的模糊拓?fù)浣Y(jié)構(gòu);
第二個問題是如何找到一個好的拓?fù)浣Y(jié)構(gòu)。

第一個問題可遵循以上尋找數(shù)據(jù)模糊拓?fù)浣Y(jié)構(gòu)的過程蚌铜。

數(shù)據(jù)位于的流形是我們試圖嵌入的低維歐幾里德空間。因此囚痴，流形上的距離是相對于全局坐標(biāo)系的標(biāo)準(zhǔn)歐幾里得距離审葬，不再是變化的度量。

第二個問題涣觉，“如何找到一個好的低維表示”，即衡量模糊拓?fù)浣Y(jié)構(gòu)的匹配程度，最終可以轉(zhuǎn)化為一個優(yōu)化問題混驰。

采用的優(yōu)化方法是交叉熵函數(shù)。

回顧之前的權(quán)重處理方法昆汹，我們將權(quán)重解釋為單純形存在的概率婴栽。由于我們正在比較的兩個拓?fù)浣Y(jié)構(gòu)共享相同的0-單純形，可以想象我們正在比較由1-單純形索引的兩個概率向量愚争。假設(shè)這些都是伯努利變量 (最終單純形要么存在挤聘，要么不存在捅彻，而且概率是伯努利分布的參數(shù))，這里正確的選擇是交叉熵从隆。

如果所有可能的 1-單純形的集合是 缭裆，并且有權(quán)重函數(shù)使得 是高維情況下 的權(quán)重， 是低維情況下 權(quán)重澈驼，則交叉熵是：

從圖的角度來看，可將最小化交叉熵視為一種 力有向圖布局算法 (force directed graph layout algorithm)购桑。

第一項氏淑， 在點(diǎn) 跨度之間提供吸引力，當(dāng)在高維空間存在較大的權(quán)重時假残。最小化這一項時， 要盡可能大阳惹，這時點(diǎn)之間的距離是盡可能小的眶俩。

第二項， 在 兩段之間提供排斥力颠印，當(dāng) 較小時。通過使 盡可能小來最小化這一項止潮。

UMAP 算法

總結(jié)：構(gòu)建UMAP算法包括：第一階段包括構(gòu)建模糊拓?fù)浔硎境ィ缟纤觥５诙A段是簡單地優(yōu)化低維表示，使其具有盡可能接近的模糊拓?fù)浔硎舅舴⒂媒徊骒貋矶攘俊?/p>

構(gòu)建初始模糊拓?fù)浔硎?/strong>

在實踐中，由于模糊集隸屬度逐漸衰減到幾乎為零窗轩，我們只需要計算每個點(diǎn)的最近鄰域的隸屬度座咆。歸根結(jié)底，這意味著我們需要一種快速高效地計算(近似)最近鄰居的方法介陶，在高維空間中也是如此。

優(yōu)化低維嵌入

在實踐中舌缤，UMAP 使用 的曲線族某残。

由于拓?fù)浔硎镜睦绽顾阕邮橇餍蔚腖aplace-Beltrami算子的近似，我們可以使用譜嵌入初始化低維表示玻墅。

數(shù)學(xué)表達(dá)

UMAP can ultimately be described in terms of, construction of, and operations on weighted graphs.

高維空間的分布

用找最近鄰的算法，得到每個 的 k 最近鄰集合

對于每個 环础，確定 和 :

分布的計算

低維空間的分布

where and for default UMAP hyperparameters.

交叉熵作為代價函數(shù)

交叉熵函數(shù)

Algorithm description

總而言之线得，UMAP算法相對簡單(參見算法1)徐伐。

如算法1所述，UMAP算法采用四個超參數(shù)：

1. 办素，近似本地度量時要考慮的鄰居數(shù)量；

2. ，目標(biāo)嵌入維度粱哼；

3. min_dist，嵌入空間中閉合點(diǎn)之間的期望間隔胯舷；

4. 次迭代，即優(yōu)化低維表示時要使用的訓(xùn)練迭代的數(shù)目桑嘶。

下面將更詳細(xì)地描述用于構(gòu)造局部模糊單純集、確定譜嵌入以及關(guān)于模糊集交叉熵優(yōu)化嵌入的各個函數(shù)讨便。

算法 2 描述了局部模糊單純集以政。我們可以通過尋找n個最近鄰域，在流形上生成適當(dāng)?shù)臍w一化距離盈蛮，然后通過函子FinSing將有限度量空間轉(zhuǎn)換為單純集，在這種情況下殊轴，單純集轉(zhuǎn)化為負(fù)距離的指數(shù)袒炉，從而構(gòu)造出局部于給定點(diǎn) 的模糊單純集旁理。

如算法 3 所示韧拒。我們不是直接使用到第 n 個最近鄰居的距離作為歸一化，而是使用KNN距離的平滑版本叛溢，它將 1-單純形的模糊集合的基數(shù)固定為固定值劲适。為此，我們在實證實驗的基礎(chǔ)上選擇了log2(N)霞势。

算法4：通過將全局模糊拓?fù)浔硎镜?-骨架視為加權(quán)圖愕贡，并在對稱歸一化拉普拉斯算子上使用標(biāo)準(zhǔn)譜方法來執(zhí)行譜嵌入。

UMAP的最后一個主要組成部分是通過最小化模糊集交叉熵來優(yōu)化嵌入固以≈鼋恚回想一下诫钓，關(guān)于給定的隸屬函數(shù) 和 ，模糊集交叉熵由下式給出

通過最小化模糊集合的 cross entropy 來最優(yōu)化低維嵌入菌湃。

算法 5 通過隨機(jī)梯度下降來優(yōu)化整個過程惧所。

實驗結(jié)果

1. 對全局結(jié)構(gòu)和局部結(jié)構(gòu)的雙重捕捉

從圖中幾種降維算法的比較中可發(fā)現(xiàn):UMAP成功地反映了Laplacian特征映射和 PCA(特別是對于MNIST和Fashion-MNIST)所很好地表示的大部分大規(guī)模全局結(jié) 構(gòu)，同時也保留了類似于t-SNE和LargeVis的局部精細(xì)結(jié)構(gòu)纯路。

2. UMAP 運(yùn)行時間感人！

3. 受樣本大小約束較小

4. UMAP 在數(shù)萬維范圍內(nèi)仍然表現(xiàn)良好

UMAP、t-SNE叫编、FIT-SNE和Largevis相對于數(shù)據(jù)環(huán)境維度的運(yùn)行時性能縮放。當(dāng)環(huán)境維度增加到幾千維以上時搓逾，t-SNE、Fit-SNE和LargeVis的計算成本都會急劇增加世蔗，而 UMAP 在數(shù)萬維范圍內(nèi)仍然表現(xiàn)良好朗兵。

推薦閱讀

How Exactly UMAP Works

Why UMAP is Superior Over t-SNE