Active Embedding Search via Noisy Paired Comparisons

Gregory Canal, Andy Massimino, Mark Davenport, Christopher Rozell
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:902-911, 2019.

Abstract

Suppose that we wish to estimate a user’s preference vector $w$ from paired comparisons of the form “does user $w$ prefer item $p$ or item $q$?,” where both the user and items are embedded in a low-dimensional Euclidean space with distances that reflect user and item similarities. Such observations arise in numerous settings, including psychometrics and psychology experiments, search tasks, advertising, and recommender systems. In such tasks, queries can be extremely costly and subject to varying levels of response noise; thus, we aim to actively choose pairs that are most informative given the results of previous comparisons. We provide new theoretical insights into the benefits and challenges of greedy information maximization in this setting, and develop two novel strategies that maximize lower bounds on information gain and are simpler to analyze and compute respectively. We use simulated responses from a real-world dataset to validate our strategies through their similar performance to greedy information maximization, and their superior preference estimation over state-of-the-art selection methods as well as random queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-canal19a, title = {Active Embedding Search via Noisy Paired Comparisons}, author = {Canal, Gregory and Massimino, Andy and Davenport, Mark and Rozell, Christopher}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {902--911}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/canal19a/canal19a.pdf}, url = {https://proceedings.mlr.press/v97/canal19a.html}, abstract = {Suppose that we wish to estimate a user’s preference vector $w$ from paired comparisons of the form “does user $w$ prefer item $p$ or item $q$?,” where both the user and items are embedded in a low-dimensional Euclidean space with distances that reflect user and item similarities. Such observations arise in numerous settings, including psychometrics and psychology experiments, search tasks, advertising, and recommender systems. In such tasks, queries can be extremely costly and subject to varying levels of response noise; thus, we aim to actively choose pairs that are most informative given the results of previous comparisons. We provide new theoretical insights into the benefits and challenges of greedy information maximization in this setting, and develop two novel strategies that maximize lower bounds on information gain and are simpler to analyze and compute respectively. We use simulated responses from a real-world dataset to validate our strategies through their similar performance to greedy information maximization, and their superior preference estimation over state-of-the-art selection methods as well as random queries.} }
Endnote
%0 Conference Paper %T Active Embedding Search via Noisy Paired Comparisons %A Gregory Canal %A Andy Massimino %A Mark Davenport %A Christopher Rozell %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-canal19a %I PMLR %P 902--911 %U https://proceedings.mlr.press/v97/canal19a.html %V 97 %X Suppose that we wish to estimate a user’s preference vector $w$ from paired comparisons of the form “does user $w$ prefer item $p$ or item $q$?,” where both the user and items are embedded in a low-dimensional Euclidean space with distances that reflect user and item similarities. Such observations arise in numerous settings, including psychometrics and psychology experiments, search tasks, advertising, and recommender systems. In such tasks, queries can be extremely costly and subject to varying levels of response noise; thus, we aim to actively choose pairs that are most informative given the results of previous comparisons. We provide new theoretical insights into the benefits and challenges of greedy information maximization in this setting, and develop two novel strategies that maximize lower bounds on information gain and are simpler to analyze and compute respectively. We use simulated responses from a real-world dataset to validate our strategies through their similar performance to greedy information maximization, and their superior preference estimation over state-of-the-art selection methods as well as random queries.
APA
Canal, G., Massimino, A., Davenport, M. & Rozell, C.. (2019). Active Embedding Search via Noisy Paired Comparisons. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:902-911 Available from https://proceedings.mlr.press/v97/canal19a.html.

Related Material