Metric Learning from Limited Pairwise Preference Comparisons

Zhi Wang, Geelon So, Ramya Korlakai Vinayak
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:3571-3602, 2024.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Metric Learning from Limited Pairwise Preference Comparisons %A Zhi Wang %A Geelon So %A Ramya Korlakai Vinayak %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-wang24d %I PMLR %P 3571--3602 %U https://proceedings.mlr.press/v244/wang24d.html %V 244 %X 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.
APA
Wang, Z., So, G. & Vinayak, R.K.. (2024). Metric Learning from Limited Pairwise Preference Comparisons. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:3571-3602 Available from https://proceedings.mlr.press/v244/wang24d.html.

Related Material