Metric Learning from Limited Pairwise Preference Comparisons
Zhi Wang, Geelon So, Ramya Korlakai Vinayak
Abstract
We study metric learning from preference comparisons under the ideal point model, in which a user prefers an item over another if it is closer to their latent ideal item. These items are embedded into $\mathbb{R}^d$ equipped with an unknown Mahalanobis distance shared across users. While recent work shows that it is possible to simultaneously recover the metric and ideal items given $\mathcal{O}(d)$ pairwise comparisons per user, in practice we often have a limited budget of $o(d)$ comparisons. We study whether the metric can still be recovered, even though learning individual ideal items is now no longer possible. We show that, on the one hand, $o(d)$ comparisons may not reveal any information about the metric, even with infinitely many users. On the other hand, when comparisons are made over items that exhibit low-dimensional structure, each user can contribute to learning the metric restricted to a low-dimensional subspace so that the metric can be jointly identified. We present a divide-and-conquer approach that achieves this, and provide theoretical recovery guarantees and empirical validation.
BibTeX
@InProceedings{pmlr-v244-wang24d,
title = {Metric Learning from Limited Pairwise Preference Comparisons},
author = {Wang, Zhi and So, Geelon and Vinayak, Ramya Korlakai},
booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence},
pages = {3571--3602},
year = {2024},
editor = {Kiyavash, Negar and Mooij, Joris M.},
volume = {244},
series = {Proceedings of Machine Learning Research},
month = {15--19 Jul},
publisher = {PMLR},
pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/wang24d/wang24d.pdf},
url = {https://proceedings.mlr.press/v244/wang24d.html},
abstract = {We study metric learning from preference comparisons under the ideal point model, in which a user prefers an item over another if it is closer to their latent ideal item. These items are embedded into $\mathbb{R}^d$ equipped with an unknown Mahalanobis distance shared across users. While recent work shows that it is possible to simultaneously recover the metric and ideal items given $\mathcal{O}(d)$ pairwise comparisons per user, in practice we often have a limited budget of $o(d)$ comparisons. We study whether the metric can still be recovered, even though learning individual ideal items is now no longer possible. We show that, on the one hand, $o(d)$ comparisons may not reveal any information about the metric, even with infinitely many users. On the other hand, when comparisons are made over items that exhibit low-dimensional structure, each user can contribute to learning the metric restricted to a low-dimensional subspace so that the metric can be jointly identified. We present a divide-and-conquer approach that achieves this, and provide theoretical recovery guarantees and empirical validation.}
}