IAN: Iterated Adaptive Neighborhoods for Manifold Learning and Dimensionality Estimation
IAN: Iterated Adaptive Neighborhoods for Manifold Learning and Dimensionality Estimation
复制标题
DOI：
10.1162/neco_a_01566
复制
发表时间：
2023-02-17
影响因子：
2.9
通讯作者：
Zucker, Steven W. W.
中科院分区：
文献类型：
--
作者：
Dyballa, Luciano;Zucker, Steven W. W.
在机器学习中验证流形假设需要了解流形的几何形状和尺寸，并且理论规定需要多少样本。然而，在大多数应用中，数据是有限的，采样可能不是均匀的，流形的属性是未知的;这意味着邻域必须适应局部结构。我们介绍了一种算法，用于推断自适应邻域的相似性核的数据。从一个局部保守邻域（Gabriel）图开始，我们根据一个加权对应图迭代地稀疏化它。在每一步中，线性规划产生全局最小邻域，并且体积统计揭示可能违反流形几何的邻域离群值。我们将我们的自适应邻域应用于非线性降维，测地线计算和维数估计。与标准算法的比较，例如，k-近邻，证明了我们的方法的有用性。
Invoking the manifold assumption in machine learning requires knowledge of the manifold's geometry and dimension, and theory dictates how many samples are required. However, in most applications, the data are limited, sampling may not be uniform, and the manifold's properties are unknown; this implies that neighborhoods must adapt to the local structure. We introduce an algorithm for inferring adaptive neighborhoods for data given by a similarity kernel. Starting with a locally conservative neighborhood (Gabriel) graph, we sparsify it iteratively according to a weighted counterpart. In each step, a linear program yields minimal neighborhoods globally, and a volumetric statistic reveals neighbor outliers likely to violate manifold geometry. We apply our adaptive neighborhoods to nonlinear dimensionality reduction, geodesic computation, and dimension estimation. A comparison against standard algorithms using, for example, k-nearest neighbors, demonstrates the usefulness of our approach.