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 applications data are limited, sampling may not be uniform, and manifold properties are unknown and (possibly) non-pure; 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 non-linear dimensionality reduction, geodesic computation and dimension estimation. A comparison against standard algorithms using, e.g., k-nearest neighbors, demonstrates their usefulness.

本论文提出了一种基于相似性核的自适应邻域算法，可应用于非线性降维、测地线计算和维度估算，通过Gabriel邻域图进行迭代稀疏，并使用线性规划来全局地获得最小邻域和体积统计量以检测局外点。与基于k近邻的标准算法相比，实验表明这种自适应邻域算法的应用是有用的。

IAN: 迭代自适应邻域用于流形学习和维度估计