Actively Learning Hemimetrics with Applications to Eliciting User Preferences

Adish Singla, Sebastian Tschiatschek, Andreas Krause
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:412-420, 2016.

Abstract

Motivated by an application of eliciting users’ preferences, we investigate the problem of learning hemimetrics, i.e., pairwise distances among a set of n items that satisfy triangle inequalities and non-negativity constraints. In our application, the (asymmetric) distances quantify private costs a user incurs when substituting one item by another. We aim to learn these distances (costs) by asking the users whether they are willing to switch from one item to another for a given incentive offer. Without exploiting structural constraints of the hemimetric polytope, learning the distances between each pair of items requires Θ(n^2) queries. We propose an active learning algorithm that substantially reduces this sample complexity by exploiting the structural constraints on the version space of hemimetrics. Our proposed algorithm achieves provably-optimal sample complexity for various instances of the task. For example, when the items are embedded into K tight clusters, the sample complexity of our algorithm reduces to O(n K). Extensive experiments on a restaurant recommendation data set support the conclusions of our theoretical analysis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-singla16, title = {Actively Learning Hemimetrics with Applications to Eliciting User Preferences}, author = {Singla, Adish and Tschiatschek, Sebastian and Krause, Andreas}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {412--420}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/singla16.pdf}, url = {https://proceedings.mlr.press/v48/singla16.html}, abstract = {Motivated by an application of eliciting users’ preferences, we investigate the problem of learning hemimetrics, i.e., pairwise distances among a set of n items that satisfy triangle inequalities and non-negativity constraints. In our application, the (asymmetric) distances quantify private costs a user incurs when substituting one item by another. We aim to learn these distances (costs) by asking the users whether they are willing to switch from one item to another for a given incentive offer. Without exploiting structural constraints of the hemimetric polytope, learning the distances between each pair of items requires Θ(n^2) queries. We propose an active learning algorithm that substantially reduces this sample complexity by exploiting the structural constraints on the version space of hemimetrics. Our proposed algorithm achieves provably-optimal sample complexity for various instances of the task. For example, when the items are embedded into K tight clusters, the sample complexity of our algorithm reduces to O(n K). Extensive experiments on a restaurant recommendation data set support the conclusions of our theoretical analysis.} }
Endnote
%0 Conference Paper %T Actively Learning Hemimetrics with Applications to Eliciting User Preferences %A Adish Singla %A Sebastian Tschiatschek %A Andreas Krause %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-singla16 %I PMLR %P 412--420 %U https://proceedings.mlr.press/v48/singla16.html %V 48 %X Motivated by an application of eliciting users’ preferences, we investigate the problem of learning hemimetrics, i.e., pairwise distances among a set of n items that satisfy triangle inequalities and non-negativity constraints. In our application, the (asymmetric) distances quantify private costs a user incurs when substituting one item by another. We aim to learn these distances (costs) by asking the users whether they are willing to switch from one item to another for a given incentive offer. Without exploiting structural constraints of the hemimetric polytope, learning the distances between each pair of items requires Θ(n^2) queries. We propose an active learning algorithm that substantially reduces this sample complexity by exploiting the structural constraints on the version space of hemimetrics. Our proposed algorithm achieves provably-optimal sample complexity for various instances of the task. For example, when the items are embedded into K tight clusters, the sample complexity of our algorithm reduces to O(n K). Extensive experiments on a restaurant recommendation data set support the conclusions of our theoretical analysis.
RIS
TY - CPAPER TI - Actively Learning Hemimetrics with Applications to Eliciting User Preferences AU - Adish Singla AU - Sebastian Tschiatschek AU - Andreas Krause BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-singla16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 412 EP - 420 L1 - http://proceedings.mlr.press/v48/singla16.pdf UR - https://proceedings.mlr.press/v48/singla16.html AB - Motivated by an application of eliciting users’ preferences, we investigate the problem of learning hemimetrics, i.e., pairwise distances among a set of n items that satisfy triangle inequalities and non-negativity constraints. In our application, the (asymmetric) distances quantify private costs a user incurs when substituting one item by another. We aim to learn these distances (costs) by asking the users whether they are willing to switch from one item to another for a given incentive offer. Without exploiting structural constraints of the hemimetric polytope, learning the distances between each pair of items requires Θ(n^2) queries. We propose an active learning algorithm that substantially reduces this sample complexity by exploiting the structural constraints on the version space of hemimetrics. Our proposed algorithm achieves provably-optimal sample complexity for various instances of the task. For example, when the items are embedded into K tight clusters, the sample complexity of our algorithm reduces to O(n K). Extensive experiments on a restaurant recommendation data set support the conclusions of our theoretical analysis. ER -
APA
Singla, A., Tschiatschek, S. & Krause, A.. (2016). Actively Learning Hemimetrics with Applications to Eliciting User Preferences. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:412-420 Available from https://proceedings.mlr.press/v48/singla16.html.

Related Material