UMAP 工作原理
UMAP 是一种基于流形学习技术和拓扑数据分析思想的降维算法。它为流形学习和降维提供了一个非常通用的框架，同时也提供了具体的实现。本文将讨论该算法在实践中的工作原理。虽然存在更深层的数学基础，但为了方便普通读者阅读，本文仅进行引用和链接。如果您正在寻找数学描述，请参阅UMAP 论文。
为了理解 UMAP，我们需要一些代数拓扑和拓扑数据分析的数学背景知识。这将提供一个理论上表现良好，但在实践中效果不佳的基本算法。下一步将利用一些基本的黎曼几何，使真实世界的数据更接近拓扑数据分析算法的潜在假设。不幸的是，这将引入新的复杂性，需要通过深层数学（细节将被省略）和模糊逻辑相结合来解决。然后，我们可以将这些部分重新组合起来，并结合一种新的方法来寻找更适合当前新数据结构的低维表示。将这一切结合起来，我们就得到了基本的 UMAP 算法。
拓扑数据分析和单纯复形
单纯复形是一种用简单的组合组件构建拓扑空间的方法。这使得人们可以将处理拓扑空间的连续几何的复杂性简化为相对简单的组合学和计数任务。这种驾驭几何和拓扑的方法对于我们进行拓扑数据分析（特别是降维）的方法至关重要。
第一步是提供一些简单的组合构建块，称为*单纯形*。从几何上看，单纯形是构建 \(k\) 维物体的一种非常简单的方式。一个 \(k\) 维单纯形称为 \(k\)-单纯形，它由 \(k+1\) 个独立点的凸包形成。因此，0-单纯形是一个点，1-单纯形是一条线段（介于两个零单纯形之间），2-单纯形是一个三角形（有三个 1-单纯形作为“面”），3-单纯形是一个四面体（有四个 2-单纯形作为“面”）。这种简单的构造允许轻松推广到任意维度。
低维单纯形
这具有一个非常简单的组合底层结构，最终可以将 \(k\)-单纯形视为由适当大小的子集给出其面（以及面的面等）的任意 \(k+1\) 个对象的集合——通过构建相应的几何单纯形，总可以提供这种抽象集合描述的“几何实现”。
单纯形可以提供构建块，但要构建有趣的拓扑空间，我们需要能够将这些构建块粘合在一起。这可以通过构建*单纯复形*来实现。表面上看，单纯复形是一组沿面粘合在一起的单纯形。更明确地说，单纯复形 \(\mathcal{K}\) 是一个单纯形集合，其中 \(\mathcal{K}\) 中任何单纯形的任何面也在 \(\mathcal{K}\) 中（确保所有面都存在），并且 \(\mathcal{K}\) 中任何两个单纯形的交集是这两个单纯形的面。许多拓扑空间都可以通过这种方式构建——只需将不同维度的单纯形沿其面粘合在一起即可。再进一步抽象，会得到*单纯集*，它们是纯组合的，具有很好的范畴论表示，可以生成更广泛的拓扑空间类别，但这对于本文来说就跑题太远了。单纯复形的直觉足以说明相关的思想和动机。
如何将这些拓扑理论工具应用于有限的数据点集？首先，我们来看看如何从拓扑空间构建单纯复形。我们将考虑的工具是给定拓扑空间的开覆盖来构建Čech 复形。如果您没有做过太多拓扑学研究，这听起来可能很拗口，但对于我们的用例来说，我们可以很容易地分解它。开覆盖本质上只是一组集合，其并集是整个空间，而 Čech 复形是一种将开覆盖转换为单纯复形的组合方式。它的工作原理很简单：将覆盖中的每个集合视为一个 0-单纯形；如果两个集合有非空交集，则在这两个集合之间创建一个 1-单纯形；如果所有三个集合的三重交集非空，则在这三个集合之间创建一个 2-单纯形；依此类推。现在，这听起来不是很高级——只是看看集合的交集。关键在于，背景拓扑理论实际上保证了这种简单的过程可以有效地表示拓扑空间本身（Nerve 定理是相关结果，供有兴趣者参考）。显然，覆盖的质量很重要，更精细的覆盖提供了更高的精度，但事实是，尽管它很简单，但这个过程捕捉到了大部分拓扑结构。
接下来，我们需要了解如何将该过程应用于有限的数据样本集。如果我们假设数据样本是从某个潜在的拓扑空间中抽取出来的，那么为了了解该空间的拓扑结构，我们需要生成它的开覆盖。如果我们的数据实际上位于度量空间中（即我们可以测量点之间的距离），那么近似开覆盖的一种方法是简单地在每个数据点周围创建具有固定半径的球。由于我们只有有限的样本，而不是拓扑空间本身，我们无法确定它是否是真正的开覆盖，但这可能是我们可以合理期望的最好近似。这种方法还有一个优势，即与覆盖相关联的 Čech 复形对于每个数据点都有一个 0-单纯形。
为了演示这个过程，我们来看一个测试数据集，如下所示：
嘈杂正弦波的测试数据集
如果我们固定一个半径，那么可以将覆盖的开集想象成圆（因为我们处于易于可视化的二维情况）。结果如下图所示：
测试数据的基本开覆盖
然后我们可以将 0、1 和 2-单纯形构成的单纯复形描绘成点、线和三角形
从测试数据构建的单纯复形
更高维度的单纯形更难直观描绘，但您可以想象它们如何契合。这里有两点需要注意：首先，单纯复形在开始捕捉数据集基本拓扑方面做得不错；其次，大部分工作实际上是由 0- 和 1-单纯形完成的，它们在计算上更容易处理（它只是一个图，在节点和边的意义上）。第二个观察启发了Vietoris-Rips 复形，它与 Čech 复形相似，但完全由 0- 和 1-单纯形确定。Vietoris-Rips 复形在计算上更容易处理，特别是对于大型数据集，并且是拓扑数据分析的主要工具之一。
如果我们采用这种方法来获得拓扑表示，那么可以通过找到具有相似拓扑表示的数据的低维表示来构建降维算法。如果只关心 0- 和 1-单纯形，那么拓扑表示就是一个图，找到低维表示可以描述为一个图布局问题。例如，如果想使用谱方法进行图布局，就会得到诸如拉普拉斯特征映射和扩散映射之类的算法。力导向布局也是一种选择，提供了与MDS或Sammon 映射风味更接近的算法。
读到这里的人可能会疑惑，为什么我们要采取如此抽象的绕道，最终只是简单地在数据上构建一个邻域图，然后对其进行布局。这有几个原因。第一个原因是，虽然拓扑方法是抽象的，但它为我们所做的事情提供了可靠的理论依据。虽然构建邻域图并在低维空间中进行布局具有启发意义且计算上可行，但它并未提供忠实捕捉数据潜在拓扑结构的同样深层动机——为此，我们需要诉诸于我暗示存在的强大拓扑工具。第二个原因是，正是这种更抽象的拓扑方法，使我们能够推广这种方法，并克服上述算法所面临的一些困难。尽管最终我们将得到一个计算上相当简单的过程，但理解各种操作*为什么*重要，对于真正理解算法至关重要（而不是仅仅进行计算）。
适应真实世界数据
上面描述的方法为基于邻域图的方法在进行降维时应如何捕捉流形结构提供了一个很好的理论。问题往往出现在将理论付诸实践时。第一个明显的困难（即使在我们上面的例子中也能看到）是，为构成开覆盖的球选择合适的半径很困难。如果选择得太小，生成的单纯复形会分裂成许多连通分量。如果选择得太大，单纯复形会变成少数几个非常高维的单纯形（及其面等），并且不再能捕捉流形结构。该如何解决这个问题？
这个困境部分是由于提供我们理由证明这个过程捕捉拓扑结构的定理（称为Nerve 定理）。具体来说，该定理说单纯复形与覆盖的并集是（同伦）等价的。在我们的情况下，处理有限数据时，对于某些半径，覆盖并未覆盖我们想象中支撑数据的整个流形——正是这种覆盖不足导致了不连通分量。同样，在点过于密集的地方，我们的覆盖确实覆盖了“太多”，最终得到比理想情况更高维度的单纯形。如果数据在流形上是*均匀分布的*，那么选择合适的半径就很容易——点之间的平均距离就能很好地工作。此外，在均匀分布的情况下，我们可以保证我们的覆盖会实际覆盖整个流形，没有“间隙”，也没有不必要的断开连接的分量。同样，我们也无需遭受那些不幸的聚集效应，这些效应会导致不必要的高维度单纯形。
如果我们考虑沿着同一流形均匀分布的数据，那么选择一个好的半径（略高于点之间平均距离的一半）并不困难，得到的开覆盖看起来相当不错。
均匀分布数据上的开球
由于数据均匀分布，我们实际上覆盖了潜在的流形，并且不会出现聚集。换句话说，所有这些理论都很好地工作，前提是假设数据在流形上是均匀分布的。
不足为奇的是，这种均匀分布的假设在流形学习的其他地方也屡屡出现。拉普拉斯特征映射之所以效果好，其证明需要数据在流形上均匀分布的假设。显然，如果数据在流形上均匀分布，一切都会好得多——但事实并非如此！真实世界的数据根本没有那么好的表现。我们如何解决这个问题？通过逆向思维：假设数据在流形上均匀分布，然后问这告诉我们关于流形本身什么。如果数据*看起来*不像均匀分布的，那一定仅仅是因为距离的概念在流形上是变化的——空间本身正在扭曲：根据数据显得稀疏或密集的地方而伸展或收缩。
通过假设数据均匀分布，我们可以利用一些标准黎曼几何，实际计算出每个点的局部距离概念（或其近似）。在实践中，一旦您深入数学推导，这最终意味着点周围的单位球会拉伸到该点的第 *k* 个最近邻，其中 *k* 是我们用来近似局部距离感的样本大小。每个点都有自己独特的距离函数，我们可以简单地根据该局部距离函数选择半径为一的球！
局部度量变化的半径为一的开球
这个理论推导的结果与许多传统的基于图的算法很好地契合：这些算法的标准方法是使用 *k*-邻域图，而不是使用具有固定半径的球来定义连通性。这意味着数据集中每个点都与其 *k* 个最近邻之间建立一条边——这是我们使用半径为一的局部变化度量的有效结果。然而，现在我们可以从单纯复形和 Nerve 定理的角度解释它为什么有效。
当然，我们用选择球的半径换来了选择 *k* 值。然而，通常更容易根据邻居数量来选择分辨率尺度，而不是正确选择距离。这是因为选择距离很大程度上取决于数据集：需要查看数据集中距离的分布才能开始选择一个好的值。相比之下，虽然 *k* 值在一定程度上仍然取决于数据集，但存在合理的默认选择，例如 10 个最近邻，这对于大多数数据集来说都是可以接受的。
同时，这一切的拓扑解释为我们提供了对 *k* 更具意义的解释。选择 *k* 决定了我们希望在多大程度上局部估计黎曼度量。选择小的 *k* 意味着我们想要一个非常局部的解释，这将更准确地捕捉黎曼度量的精细细节结构和变化。选择大的 *k* 意味着我们的估计将基于更大的区域，因此，虽然会遗漏一些精细的细节结构，但它们在整个流形上将更广泛地准确，因为有更多的数据可用于估计。
这种基于黎曼度量的方法还带来了另一个好处：我们实际上为每个点关联了一个局部度量空间，并且可以有意义地测量距离，因此我们可以根据边上的点（在局部度量方面）相距多远来为可能生成的图的边加权。用稍微更数学化的术语来说，我们可以将这视为在模糊拓扑中工作，其中位于覆盖中的开集不再是二元的“是”或“否”，而是一个介于零和一之间的模糊值。显然，点位于给定半径球中的确定性会随着我们远离球心而衰减。我们可以将这种模糊覆盖可视化为这样子：
局部度量变化的半径为一的模糊开球
这些都不是非常具体或正式的——它仅仅是我们希望发生的事情的一个直观图像。事实证明，我们可以通过借用代数拓扑中的奇异集和几何实现函子，然后将它们应用于度量空间和模糊单纯集，来实际形式化这一切。其中涉及的数学超出了本文的范围，但对于有兴趣的人，可以查看David Spivak 关于此的原始工作以及我们的论文。只需说存在一些数学工具可以让我们以明确的方式实现这种直觉。
这解决了一些问题，但当我们将此类过程应用于真实数据（特别是在高维度数据）时，又出现了一个新问题：许多点基本上完全孤立了。人们可能会想，如果数据采样来源的流形不是病态的，就不应该发生这种情况。那么，我们期望该流形具备而当前方法某种程度上遗漏了什么属性呢？我们需要添加的是局部连通性的概念。
请注意，这并非要求整个流形是连通的——它可以由许多连通分量组成。相反，它要求在流形上的任何点，其某个足够小的邻域是*连通的*（这个“在足够小的邻域中”就是“局部”部分的含义）。对于我们正在处理的实际问题，即我们只有流形的有限近似，这意味着任何点都不应该是*完全*孤立的——它应该至少连接到另一个点。就模糊开集而言，这意味着我们应该完全确信开集会扩展到每个点的最近邻。我们可以通过简单地让模糊置信度根据与第一最近邻的距离*以外*的距离衰减来实现这一点。我们可以再次用我们的示例数据集来可视化结果。
局部连通性和模糊开集
同样，这可以用前面提到的代数拓扑数学工具来形式化。从实践角度来看，这对高维数据起着重要作用——在高维度中，距离往往更大，但也彼此更相似（参见维度诅咒）。这意味着到第一最近邻的距离可能相当大，但到第十最近邻的距离通常只稍微大一点（相对而言）。局部连通性约束确保我们关注最近邻之间距离的差异，而不是绝对距离（它在邻居之间显示出很少的区分）。
就在我们以为快要解决真实世界数据的一些问题时，又遇到了新的障碍：我们的局部度量不兼容！每个点都有其关联的局部度量，从点 *a* 的角度来看，点 *a* 到点 *b* 的距离可能是 1.5，但从点 *b* 的角度来看，点 *b* 到点 *a* 的距离可能只有 0.6。哪个点是对的？我们如何决定？回到我们基于图的直觉，我们可以将这视为具有不同权重的有向边，如下图所示。
权重不兼容的边
在任意两点之间，我们可能有多达两条边，并且这些边的权重彼此不一致。对于两个不一致的权重，有多种处理方法——我们可以取最大值、最小值、算术平均值、几何平均值，或者其他完全不同的方法。我们真正想要的是一个有原则的方式来做出决定。正是在这一点上，我们构建的数学工具发挥作用了。从数学上看，我们实际上有一族模糊单纯集，并且显而易见的选项是取它们的并集——这是一个明确定义的操作。有几种方法可以定义模糊并集，取决于所涉及逻辑的性质，但在本文中，我们有相对清晰的概率语义，这使得选择变得简单明了。用图的术语来说，我们得到的是：如果我们要合并两条权重分别为 *a* 和 *b* 的不一致的边，那么我们应该得到一条合并权重为 \(a + b - a \cdot b\) 的单条边。理解这一点的方式是，权重实际上是边（1-单纯形）存在的概率。合并后的权重就是至少一条边存在的概率。
如果我们应用这个过程将所有模糊单纯集并集起来，最终会得到一个单一的模糊单纯复形，我们可以再次将其视为一个加权图。在计算术语中，我们只是将边权重组合公式应用于整个图（没有边的权重为 0）。最终我们得到了类似这样的东西。
具有合并边权重的图
因此，从某种意义上说，最终我们只是简单地构建了一个加权图（尽管如果愿意，我们可以利用更高维度的单纯形，但这会带来显著的额外计算成本）。潜藏在背景中的数学理论为我们做的是确定我们*为什么*应该构建*这个*图。它还帮助我们决定具体*如何*进行计算，并提供了对这个图*意味着什么*的具体解释。所以，尽管最终我们只是构建了一个一个图，但数学回答了引导我们到这里的重要问题，并可以帮助我们决定下一步做什么。
那么，既然我们现在有了数据的模糊拓扑表示（数学表明这会捕捉数据潜在流形的拓扑结构），我们如何将其转换为低维表示呢？
寻找低维表示
理想情况下，我们希望低维表示具有尽可能相似的模糊拓扑结构。第一个问题是如何确定低维表示的模糊拓扑结构，第二个问题是如何找到一个好的低维表示。
第一个问题很大程度上已经回答了——我们理应遵循刚才用于寻找数据模糊拓扑结构的相同程序。然而，这里有一个怪异之处：这次数据不会躺在某个流形上，我们将有一个低维表示，它躺在一个非常特殊的流形上。当然，那个流形就是我们试图嵌入的低维欧几里得空间。这意味着我们之前在使距离概念在流形上变化所做的所有努力，在处理低维表示时将是不合适的。我们明确*想要*流形上的距离是相对于全局坐标系的标准欧几里得距离，而不是变化的度量。这省去了一些麻烦。另一个怪异之处是我们使用了到最近邻的距离，这也是我们给定数据计算出的东西。这也是我们在优化以获得好的低维表示时，希望在整个流形上全局成立的一个属性，所以我们将不得不接受它作为算法的超参数 min_dist。
第二个问题，“如何找到一个好的低维表示”，取决于我们衡量找到的模糊拓扑结构匹配程度的能力。给定这样一个衡量标准，我们可以将其转化为一个优化问题，即寻找具有最接近模糊拓扑结构的低维表示。显然，如果我们的接近度衡量标准具有各种特性，那么可以应用的优化技术的性质也会有所不同。
回到我们合并与单纯形相关联的冲突权重时，我们将权重解释为单纯形存在的概率。因此，由于我们比较的两种拓扑结构共享相同的 0-单纯形，我们可以想象我们正在比较由 1-单纯形索引的两个概率向量。鉴于这些是伯努利变量（最终单纯形要么存在，要么不存在，概率是伯努利分布的参数），这里正确的选择是交叉熵。
明确地说，如果所有可能的 1-单纯形集合是 \(E\)，并且我们有权重函数，使得 \(w_h(e)\) 是高维情况下 1-单纯形 \(e\) 的权重，\(w_l(e)\) 是低维情况下 \(e\) 的权重，那么交叉熵将是
这看起来可能很复杂，但如果我们回到用图的术语来思考，可以将最小化交叉熵视为一种力导向图布局算法。
第一项 \(w_h(e) \log\left(\frac{w_h(e)}{w_l(e)}\right)\) 在高维情况下关联的权重很大时，为点 \(e\) 所跨越的点之间提供了吸引力。这是因为当 \(w_l(e)\) 尽可能大时，这一项将被最小化，这发生在点之间的距离尽可能小时。
相比之下，第二项 \((1 - w_h(e)) \log\left(\frac{1 - w_h(e)}{1 - w_l(e)}\right)\) 在 \(w_h(e)\) 很小时，为 \(e\) 的两端提供了排斥力。这是因为通过使 \(w_l(e)\) 尽可能小，该项将被最小化。
总的来说，这种由高维数据拓扑表示的边权重调节的推拉过程，将使低维表示稳定在一个相对准确地代表原始数据整体拓扑结构的状态。
UMAP 算法
将所有这些部分组合起来，我们就可以构建 UMAP 算法。第一阶段包括构建模糊拓扑表示，基本如上所述。第二阶段仅仅是优化低维表示，使其具有尽可能接近的模糊拓扑表示，接近程度以交叉熵衡量。
在构建初始模糊拓扑表示时，我们可以采取一些捷径。实际上，由于模糊集隶属度强度衰减得非常小，我们只需要计算每个点的最近邻的隶属度。最终这意味着我们需要一种快速有效地计算（近似）最近邻的方法，即使在高维空间中。我们可以通过利用Dong 等人的最近邻下降算法来实现这一点。剩下的计算现在只处理每个点的局部邻居，因此非常高效。
在优化低维嵌入时，我们也可以采取一些捷径。我们可以使用随机梯度下降进行优化过程。为了使梯度下降问题更容易，如果最终目标函数是可微的，那是有益的。我们可以通过使用低维表示的实际隶属度强度函数的平滑近似，并从一个足够通用的族中选择来实现这一点。实际上，UMAP 使用形式为 \(\frac{1}{1 + a x^{2b}}\) 的曲线族。同样，我们不想处理所有可能的边，因此可以使用负采样技巧（如 word2vec 和 LargeVis 中使用的），只需根据需要采样负例即可。最后，由于拓扑表示的拉普拉斯算子是流形拉普拉斯-贝尔特拉米算子的近似，我们可以使用谱嵌入技术将低维表示初始化到一个好的状态。
将所有这些部分组合起来，我们就得到一个快速且可扩展的算法，它仍然基于健全的数学理论构建。希望本介绍有助于为读者提供对该潜在理论以及 UMAP 算法在实践中工作原理的一些直觉。