通过问答学习平滑距离函数，高效逼近真实距离关系。
Learning Smooth Distance Functions via Queries
- 用三元组提问方式学习距离函数，可控制查询次数。
- 加法近似下查询复杂度为覆盖集大小的平方。
- 结合全局与局部方法，适合高维空间的距离学习。
本文研究在查询学习框架下学习距离函数的问题，其中学习者可提出形如“x_i 更接近 x_j 还是 x_k？”的三元组查询。针对两种近似标准——ω-加法近似和(1+ω)-乘法近似，建立了学习平滑但一般距离函数所需的查询复杂度的严格保证。对于加法近似，提出一种全局方法，其查询复杂度在样本空间有限覆盖集大小上呈二次关系。对于更强的乘法近似，引入一种结合全局与局部方法的策略，利用多个马氏距离函数捕捉局部几何结构，其查询复杂度在覆盖集大小和样本空间的环境维度上均呈二次增长。
原文摘要 · Abstract (English)
In this work, we investigate the problem of learning distance functions within the query-based learning framework, where a learner is able to pose triplet queries of the form: ``Is $x_i$ closer to $x_j$ or $x_k$?'' We establish formal guarantees on the query complexity required to learn smooth, but otherwise general, distance functions under two notions of approximation: $ω$-additive approximation and $(1 + ω)$-multiplicative approximation. For the additive approximation, we propose a global method whose query complexity is quadratic in the size of a finite cover of the sample space. For the (stronger) multiplicative approximation, we introduce a method that combines global and local approaches, utilizing multiple Mahalanobis distance functions to capture local geometry. This method has a query complexity that scales quadratically with both the size of the cover and the ambient space dimension of the sample space.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。