Scalable and Efficient Comparison-based Search without Features - LEARN2SEARCH 框架与噪声比较检索方法

Aug 5, 2026

Upload by Oliver

研究利用成对比较获取目标对象 t：通过“在一对对象(i,j)中，哪个更接近 t”的对比提问，oracle 基于潜在特征空间给出带噪声的回答。首先在非盲设定中，特征可见，提出一种具有低计算复杂度且查询高效的贝叶斯比较检索算法，并证明最优查询形式及几乎必然收敛。随后在盲设定中，特征隐藏于算法之外，结合新的分布式三元组嵌入学习，构建可扩展框架 LEARN2SEARCH，并在两个真实数据集上展示查询复杂度与非盲相当的效果；同时通过用户检索电影演员实验验证有效性。

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages11

Reading Time28 min

AccessFree to download

Abstract

Introduction

Scalable and Efﬁcient Comparison-based Search without Features Daniyar Chumbalov 1 Lucas Maystre 2 Matthias Grossglauser 1 Abstract We consider the problem of ﬁnding a target object t using pairwise comparisons, by asking an oracle questions of the form “Which object from the pair (i; j) is more similar to t?”. Objects live in a space of latent features, from which the oracle generates noisy answers. First, we consider the non-blind setting where these features are accessible. We propose a new Bayesian comparison-based search algorithm with noisy answers; it has low computational complexity yet is efﬁcient in the number of queries. We provide theoretical guarantees, deriving the form of the optimal query and proving almost sure convergence to the target t. Second, we consider the blind setting, where the object features are hidden from the search algorithm. In this setting, we combine our search method and a new distributional triplet embedding algorithm into one scalable learning framework called LEARN2SEARCH. We show that the query complexity of our approach on two real-world datasets is on par with the non-blind setting, which is not achievable using any of the current state-of-theart embedding methods. Finally, we demonstrate the efﬁcacy of our framework by conducting an experiment with users searching for movie actors. 1. Introduction Finding a target object among a large collection of n objects is the central problem addressed in information retrieval (IR) . For example, in web search, one ﬁnds relevant webpages through a query expressed as one or several keywords. Of course, the form of the query depends on the object type; other forms of search queries in the literature include ﬁnding images similar to a query image (Datta et al., 2008), and ﬁnding subgraphs of a large network isomorphic to a query graph (Sun et al., 2012) . A common feature of this classic 1 School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland. 2 Spotify. Correspondence to: Daniyar Chumbalov . Proceedings of the 37th International Conference on Machine Learning, Online, PMLR 119, 2020 . Copyright 2020 by the author(s) . formulation of the search problem is the need to express a meaningful query. However, this is often a non-trivial task for a human user. For example, most people would struggle to draw the face of a friend accurately enough that it could be used as a query image. But they would be able to conﬁrm with near-total certainty whether a photograph is of their friend—we have no real doppelgängers in the world. In other words, comparing is cognitively much easier than formulating a query. This is true for many complex or unstructured types of data, such as music, abstract concepts, images, videos, ﬂavors, etc. In this work, we develop models and algorithms for searching a large database by comparing a sequence of sample objects relative to the target, thereby obviating the need for any explicit query. The central problem concerns the choice of the sequence of samples (e.g., pairs of faces that the user compares with a target face she remembers) . These query objects have to be chosen in such a way that we learn as much as possible about the target, i.e., shrink the set of potential targets as quickly as possible. This is closely related to a classic problem in active learning (Settles, 2012; MacKay, 1992), assuming we have a meaningful set of features available for each object in the database. It is natural to assume that the universe of objects lives in some low-dimensional latent feature space, even thoughthe raw objects might be high-dimensional (images, videos, sequences of musical notes, etc.) . For example, a human face, for the purposes of a similarity comparison, could be quite accurately described by a few tens of features, capturing head shape, eye color, fullness of lips, gender, age, and the like (Chang & Tsao, 2017) . The key component of our framework is a n

FAQs

该研究如何通过比较问题来定位目标对象 t？

通过向 oracle 询问“在对象(i,j)中哪个更接近目标 t”的成对比较问题，利用目标与对象在潜在特征空间中的相对相似性来逐步缩小候选集合。

非盲设定中提出的检索算法有哪些理论保证？

在特征可见的非盲设定下，算法给出最优查询形式，并证明与目标 t 的几乎必然收敛；同时还强调其具有低计算复杂度与高查询效率。

盲设定下如何在特征不可见时仍提升检索效率？

将搜索方法与分布式三元组嵌入算法结合，构建 LEARN2SEARCH，通过利用历史搜索逐步学习并改进对象的潜在嵌入，使后续搜索所需查询次数更少。

Aug 5, 2026

Upload by Oliver