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

作者: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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券