内容纲要

数据降维分成两个类别:一个是保留所有数据样本的成对的距离结构,另一个是在全局距离上的基础上保留局部距离。

PCA MDS和Sammon maping是前者,t-SNE,ISOMAP,LargeVis,Laplacian eigenmap和diffusion maps是后者。

Introduction

这篇文章中,我们提出一个新颖的流形学习技术用于降维。我们提供了一个健全的数学理论基础的技术和一个实用的可扩展的算法,适用于现实世界的数据。UMAP(统一流形逼近和投影)基于与Belkin和Niyogi在拉普拉斯特征图上的工作有关的数学基础。 我们力求通过结合黎曼几何和David Spivak [52]在模糊简单集的几何实现的类别理论方法中的工作来解决流形上均匀数据分布的问题。t-SNE是缩小可视化尺寸的最新技术。我们的算法在可视化质量上与t-SNE竞争,并且可以说以优异的运行时性能保留了更多的全局结构。此外,该算法能够扩展到比t-SNE可行的数据集大得多的数据集。 最后,UMAP对嵌入维度没有任何计算限制,使其可以用作机器学习的通用降维技术。

论文的布局如下。 在第2节中,我们描述了该算法的基础理论。 第2部分对于理解UMAP为何起作用的理论以及在开发算法时做出选择的动机都是必要的。 对拓扑数据分析,类别理论或UMAP的理论基础没有背景(或兴趣)的读者应跳过本节,直接进入第3节。

话虽这么说,我们认为强大的理论和数学上合理的算法决策在无监督学习领域中尤为重要。在本文中,我们要强调的是,UMAPs的设计决策都是基于扎实的理论基础,而不是通过针对特定任务的目标功能进行实验而得出的。 尽管所有基于邻域的流形学习算法都必须共享某些基本组件,但我们认为通过有充分根据的理论决策来选择这些组件是有利的。 本文的主要贡献之一是用另一种数学语言重新构造了流形学习和降维的问题,使从业人员可以对问题应用新的数学领域。

在第3节中,我们将提供有关UMAP的更多计算描述。第3节应为读者提供较少的拓扑数据分析基础,以帮助他们理解第2节中所述的理论。附录C将UMAP与更熟悉的算法t-SNE和LargeVis进行了对比,并以相似的语言描述了所有这些算法。 “本节”应该帮助已经熟悉这些技术的读者快速了解UMAP算法,尽管他们将在现场为UMAP算法提供理论基础。

在第4节中,我们讨论UMAP算法的实现细节。这包括更详细的算法描述,并讨论了所涉及的超参数及其实际效果。

在第5节中,我们将提供有关现实世界数据集的实际结果以及缩放实验,以证明与其他降维算法相比,该算法在现实世界中的性能。

在第6节中,我们讨论了算法的相对弱点以及UMAP可能不是最佳选择的应用。

最后,在第7节中,我们详细介绍了UMAP的许多潜在扩展,这些扩展是由于其基于扎实的数学基础而构建的。 进一步发展的途径包括半监督学习,度量学习和异构数据嵌入。

A Computational View of UMAP

为了从实用的角度理解UMAP算法实际上是在进行什么计算,理论上较少且计算量更多的描述可能对读者有所帮助。 对算法的描述缺乏做出许多选择的动机。

为此,请参阅第2节。该算法的理论描述是根据模糊简单集进行的。 从计算上来说,这仅对于一个骨架而言是易于处理的,最终可以将其描述为加权图。 这是指,从实际的计算角度来看,UMAP最终可以用加权图的构造,构造和操作来描述。特别地,这将UMAP定位在基于k邻居的图学习算法(例如Laplacian特征图,Isomap和t-SNE)类别中。

与其他基于k邻居图的算法一样,可以在两个阶段中描述UMAP。 在第一阶段,将构建一个特定的加权k邻居图。 在第二阶段,计算该图的低维布局。 此类中所有算法之间的区别在于如何构造图形和如何计算布局的特定细节。 如第2节所述,UMAP的理论基础为这两个阶段提供了新颖的方法,并为所涉及的选择提供了明确的动力。

最后,由于t-SNE通常不被描述为基于图的算法,因此在附录C中给出了UMAP与t-SNE的直接比较,使用通常用于表示t-SNE方程的相似性/概率表示法。

在第2节中,我们对数据做了一些基本假设。基于这些假设,我们利用类别理论推导了UMAP算法。 坦白地说,所有这些推论都假设这些公理是正确的。
1.文件存在一个流形,数据将在流形上均匀分布。
2.基础的相关歧管在本地连接。
3.保留该流形的拓扑结构是主要目标。
这些公理驱动第二节的拓扑理论,尤其是对建模和保留拓扑结构的兴趣。 特别是,第2.1节从拓扑理论的角度突出了将流形表示为k邻居图的潜在动机。

如附录C中突出显示的那样,任何试图使用类似于k邻域图的数学结构来近似流形的算法都必须遵循类似的基本结构。
•图的构建
1.构造加权的k邻图。
2.在边缘上应用一些变换到环境局部距离。
3.处理k邻域图的固有不对称性。
•图形布局
1.定义一个目标函数,该目标函数保留此k邻域图的所需特征。
2.找到优化该目标函数的低维表示。
许多降维算法可以分解为这些步骤,因为它们是特定解决方案类别的基础。 必须通过面向任务的实验或通过选择一组可信的公理并从中建立强有力的理论论据来选择每个步骤。 我们的信念是,基于强大的基础理论,我们的决策从长远来看将允许使用更具扩展性和通用性的算法。
从理论上讲,我们在第2.1节中选择使用k邻域图表示流形是合理的。 我们的内核变换对称函数的选择可以在第2.2节中找到。 最后,第2.3节概述了我们选择图形布局所依据的理由。

Graph Construction

UMAP的第一阶段可以认为是加权k邻域图的构造. 为了实现我们的UMAP,我们更喜欢使用[18]的最近邻居下降算法。
file
file
其中p是通过局部连接约束来选择,特别的,它保证了xi连接最少的一个数据点。特别地,它确保xi连接到权重为1的边缘的至少另一个数据点; 这等效于在xi处本地连接的结果模糊单形集。 实际上,这极大地改善了在非常高维数据上的表示,而其他算法(例如t-SNE)开始受到维数的困扰。
σi的选择对应于(平滑的)归一化因子,定义了点xi处局部的黎曼度量。
然后定义权重wfile
定义A为G邻接矩阵,然后考虑对称矩阵B
file
该公式是通过使用概率t-conorm合并模糊简单集而得出的。 如果将Aij的值解释为存在从xi到xj的有向边的概率,则Bij是两个有向边缘(从xi到xj和从xj到xi)中至少一个存在的概率。然后,UMAP图G是一个无向加权图,其邻接矩阵由B给出。第2节以拓扑学的方式解释了这种构造,并为该构造提供数据的适当模糊拓扑表示的理由提供了理由-即, 这种构造以忠实的方式捕获了数据的底层几何结构。

Graph Layout

实际上,UMAP在低维空间中使用力导向图布局算法。 力导向图布局利用沿边缘施加的一组拉力和在顶点之间施加的一组排斥力。任何以力为导向的布局算法都需要描述主动力和排斥力。该算法通过在每个边或顶点迭代施加反作用力和排斥力来进行。等于一个非凸优化问题。 通过以与模拟退火类似的方式缓慢降低自力和斥力,可以保证收敛到局部最小值。

在UMAP中,分别在坐标yi和yj处的两个顶点i和j之间的作用力由以下公式确定:
file
其中a b为超参数。
由于计算限制,排斥力是通过采样计算的。 因此,每当对边缘施加作用力时,该边缘的一个顶点就会被其他顶点的采样所排斥。 排斥力由
file
e是小说,来组织除以0,实际中设置为0.001
算法可以随机初始化,但实际上,由于图G的对称拉普拉斯算子是流形的LaplaceBeltrami算符的离散近似,因此我们可以使用频谱布局来初始化嵌入。它在算法内提供了更快的收敛性和更大的稳定性。
上述力是从优化加权图G和从点{yi} i = 1..N构造的等效加权图H之间的边沿交叉熵的梯度中得出的。我们正在寻求对点yi进行定位,以使这些点诱导的加权图最接近图G,在这里我们通过所有边存在概率的总交叉熵来衡量加权图之间的差异。由于加权图G捕获了源数据的拓扑,因此从点{yi} i = 1..N构造的等效加权图H在优化允许的情况下尽可能紧密地匹配拓扑,从而提供了良好的低维表示数据的整体拓扑。

Implementation and Hyper-parameters

总共的算法流程:算法1的输入是:X,要减小其维度的数据集;n,用于本地度量近似的邻域大小;d,目标缩小空间的尺寸;min-dist,算法参数用来控制布局;和n个时期,控制要执行的优化工作量。
file
算法2描述了构建了局部模糊单纯集。
file

file

file

时间复杂度:file

Hyper-parameters

超参数 n,d,min-dist, n-epochs
n 是邻居的数量。
d 是目标嵌入的维度
min-dist是两个相邻点的嵌入最小距离
n-epoch是迭代次数。

最后修改日期:2020年12月8日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。