标签与嵌入：关于距离的分布式表示

作者：Arnold Filtser,Lee-Ad Gottlieb,Robert Krauthgamer

摘要：我们研究了距离标记和l∞嵌入的性能不同的度量空间，以及这种差异有多大。回想一下，距离标记是度量空间（X，d）中距离的分布式表示，其中每个点x∈X被赋予简洁的标签，使得任意两个点x，y∈X之间的距离可以近似给定只有他们的标签。高度结构化的特殊情况是嵌入到l∞中，其中每个点x∈X被赋予向量f（x），使得∥f（x）-f（y）∥∞近似为d（x，y）。距离标记或π∞嵌入的性能通过其变形和标签尺寸/尺寸来测量。

我们还研究了这两个指标的优先版本的类似问题。这里，给出了点集X的优先级顺序π=（x1，...，xn），并且较高优先级的点应该具有较短的标签。形式上，如果每个xj的标签大小最多为α（j），则距离标记优先考虑标签大小α（。）。类似地，如果f（xj）仅在第一个α（j）坐标中非零，则嵌入f：X→l∞优先考虑尺寸α（。）。此外，我们将这些优先级度量与经典（最坏情况）版本进行比较。

我们在几个场景中回答了这些问题，揭示了各种各样的行为。首先，在某些情况下，标签和嵌入​​具有非常相似的最坏情况性能，但在其他情况下，存在巨大差异。然而，在优先设置中，我们经常发现标签和嵌入​​的性能之间存在严格的分离。最后，在比较经典和优先级设置时，我们发现标签大小的最坏情况通常会“转换”为优先级，但也是这个规则的一个令人惊讶的例外。

原文标题：Labelings vs. Embeddings: On Distributed Representations of Distances

原文摘要：

地址：https://arxiv.org/abs/1907.06857