Dimensionality Reduction has Quantifiable Imperfections: Two Geometric Bounds
Dimensionality Reduction has Quantifiable Imperfections: Two Geometric Bounds
复制标题
降维具有可量化的缺陷：两个几何界限
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. McCann
中科院分区：
文献类型：
--
作者：
Kry Yik;G. Ding;Ruitong Huang;R. McCann
在本文中，我们研究了从定量拓扑学的角度来看，在信息检索设置的简化（DR）地图。特别是，我们表明，没有DR地图可以同时实现完美的精度和完美的召回。因此，连续的DR图必须具有不完美的精度。我们进一步证明了Lipschitz连续DR映射精度的一个上界。虽然精确度是信息检索设置中的一个自然度量，但它并不度量检索到的数据有“多”错。因此，我们提出了一个新的措施的基础上Wasserstein距离，具有类似的理论保证。在我们的证明中的一个关键技术步骤是一个特殊的优化问题的$L_2$-Wasserstein距离的分布约束集。我们提供了一个完整的解决方案，这个优化问题，这可以在技术方面的独立利益。
In this paper, we investigate Dimensionality reduction (DR) maps in an information retrieval setting from a quantitative topology point of view. In particular, we show that no DR maps can achieve perfect precision and perfect recall simultaneously. Thus a continuous DR map must have imperfect precision. We further prove an upper bound on the precision of Lipschitz continuous DR maps. While precision is a natural measure in an information retrieval setting, it does not measure `how' wrong the retrieved data is. We therefore propose a new measure based on Wasserstein distance that comes with similar theoretical guarantee. A key technical step in our proofs is a particular optimization problem of the $L_2$-Wasserstein distance over a constrained set of distributions. We provide a complete solution to this optimization problem, which can be of independent interest on the technical side.