Balancing Geometry and Density: Path Distances on High-Dimensional Data
Balancing Geometry and Density: Path Distances on High-Dimensional Data
复制标题
DOI：
10.1137/20m1386657
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
A. Little;Daniel Mckenzie;James M. Murphy
中科院分区：
文献类型：
--
作者：
A. Little;Daniel Mckenzie;James M. Murphy
提出了一种新的功率加权最短路径距离的几何和计算分析方法。通过阐明这些指标在基础数据中平衡密度和几何的方式，我们澄清了它们的关键参数，并讨论了在实践中如何选择它们。与相关的数据驱动指标进行了比较，这说明了密度在基于核的无监督和半监督机器学习中的更广泛作用。在计算上，我们将完全加权图上的pwspd与其加权最近邻图上的类似物联系起来，为它们的等价性提供了接近最优的高概率保证。结合渗流理论，建立了有限样本条件下pwspd偏差和方差的估计。理论结果得到了说明性实验的支持，证明了pwspd在广泛数据设置中的多功能性。在整个论文中，我们的结果只要求底层数据从低维流形中采样，并且关键地依赖于该流形的内在维度，而不是其环境维度。
New geometric and computational analyses of power-weighted shortest-path distances (PWSPDs) are presented. By illuminating the way these metrics balance density and geometry in the underlying data, we clarify their key parameters and discuss how they may be chosen in practice. Comparisons are made with related data-driven metrics, which illustrate the broader role of density in kernel-based unsupervised and semi-supervised machine learning. Computationally, we relate PWSPDs on complete weighted graphs to their analogues on weighted nearest neighbor graphs, providing high probability guarantees on their equivalence that are near-optimal. Connections with percolation theory are developed to establish estimates on the bias and variance of PWSPDs in the finite sample setting. The theoretical results are bolstered by illustrative experiments, demonstrating the versatility of PWSPDs for a wide range of data settings. Throughout the paper, our results require only that the underlying data is sampled from a low-dimensional manifold, and depend crucially on the intrinsic dimension of this manifold, rather than its ambient dimension.