Timezone: »

Scalable and Efficient Comparison-based Search without Features
Daniyar Chumbalov · Lucas Maystre · Matthias Grossglauser

Wed Jul 15 01:00 PM -- 01:45 PM & Thu Jul 16 02:00 AM -- 02:45 AM (PDT) @

We consider the problem of finding 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 efficient 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-the-art embedding methods. Finally, we demonstrate the efficacy of our framework by conducting a movie actors search experiment with real users.

Author Information

Daniyar Chumbalov (EPFL)
Lucas Maystre (Spotify)
Matthias Grossglauser (EPFL)

Matthias Grossglauser is Associate Professor in the School of Computer and Communication Sciences at EPFL. His current research interests are in machine learning for large social systems, stochastic models and algorithms for graph and mobility mining, and recommender systems. He is also the current director of the Doctoral School in Computer and Communication Sciences. From 2007-2010, he was with the Nokia Research Center (NRC) in Helsinki, Finland, serving as head of the Internet Laboratory, and later as head of a tech-transfer program focused on data mining, analytics, and machine learning. In addition, he served on Nokia's CEO Technology Council, a technology advisory group reporting to the CEO. Prior to this, he was Assistant Professor at EPFL, and a Research Scientist in the Networking and Distributed Systems Laboratory at AT&T Research in New Jersey. He received the 1998 Cor Baayen Award from the European Research Consortium for Informatics and Mathematics (ERCIM), the 2006 CoNEXT/SIGCOMM Rising Star Award, and two best paper awards. He served on the editorial board of IEEE/ACM Transactions on Networking, and on numerous Technical Program Committees.

More from the Same Authors