Learning Combinatorial Functions from Pairwise Comparisons

Maria-Florina Balcan, Ellen Vitercik, Colin White

29th Annual Conference on Learning Theory, PMLR 49:310-335, 2016.

Abstract

A large body of work in machine learning has focused on the problem of learning a close approximation to an underlying combinatorial function, given a small set of labeled examples. However, for real-valued functions, cardinal labels might not be accessible, or it may be difficult for an expert to consistently assign real-valued labels over the entire set of examples. For instance, it is notoriously hard for consumers to reliably assign values to bundles of merchandise. Instead, it might be much easier for a consumer to report which of two bundles she likes better. With this motivation in mind, we consider an alternative learning model, wherein the algorithm must learn the underlying function up to pairwise comparisons, from pairwise comparisons. In this model, we present a series of novel algorithms that learn over a wide variety of combinatorial function classes. These range from graph functions to broad classes of valuation functions that are fundamentally important in microeconomic theory, the analysis of social networks, and machine learning, such as coverage, submodular, XOS, and subadditive functions, as well as functions with sparse Fourier support.

Cite this Paper

BibTeX

@InProceedings{pmlr-v49-balcan16b,
title = {Learning Combinatorial Functions from Pairwise Comparisons},
author = {Balcan, Maria-Florina and Vitercik, Ellen and White, Colin},
booktitle = {29th Annual Conference on Learning Theory},
pages = {310--335},
year = {2016},
editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad},
volume = {49},
series = {Proceedings of Machine Learning Research},
address = {Columbia University, New York, New York, USA},
month = {23--26 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v49/balcan16b.pdf},
url = {https://proceedings.mlr.press/v49/balcan16b.html},
abstract = {A large body of work in machine learning has focused on the problem of learning a close approximation to an underlying combinatorial function, given a small set of labeled examples. However, for real-valued functions, cardinal labels might not be accessible, or it may be difficult for an expert to consistently assign real-valued labels over the entire set of examples. For instance, it is notoriously hard for consumers to reliably assign values to bundles of merchandise. Instead, it might be much easier for a consumer to report which of two bundles she likes better. With this motivation in mind, we consider an alternative learning model, wherein the algorithm must learn the underlying function up to pairwise comparisons, from pairwise comparisons. In this model, we present a series of novel algorithms that learn over a wide variety of combinatorial function classes. These range from graph functions to broad classes of valuation functions that are fundamentally important in microeconomic theory, the analysis of social networks, and machine learning, such as coverage, submodular, XOS, and subadditive functions, as well as functions with sparse Fourier support.}
}

Endnote

%0 Conference Paper
%T Learning Combinatorial Functions from Pairwise Comparisons
%A Maria-Florina Balcan
%A Ellen Vitercik
%A Colin White
%B 29th Annual Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2016
%E Vitaly Feldman
%E Alexander Rakhlin
%E Ohad Shamir
%F pmlr-v49-balcan16b
%I PMLR
%P 310--335
%U https://proceedings.mlr.press/v49/balcan16b.html
%V 49
%X A large body of work in machine learning has focused on the problem of learning a close approximation to an underlying combinatorial function, given a small set of labeled examples. However, for real-valued functions, cardinal labels might not be accessible, or it may be difficult for an expert to consistently assign real-valued labels over the entire set of examples. For instance, it is notoriously hard for consumers to reliably assign values to bundles of merchandise. Instead, it might be much easier for a consumer to report which of two bundles she likes better. With this motivation in mind, we consider an alternative learning model, wherein the algorithm must learn the underlying function up to pairwise comparisons, from pairwise comparisons. In this model, we present a series of novel algorithms that learn over a wide variety of combinatorial function classes. These range from graph functions to broad classes of valuation functions that are fundamentally important in microeconomic theory, the analysis of social networks, and machine learning, such as coverage, submodular, XOS, and subadditive functions, as well as functions with sparse Fourier support.

RIS

TY - CPAPER
TI - Learning Combinatorial Functions from Pairwise Comparisons
AU - Maria-Florina Balcan
AU - Ellen Vitercik
AU - Colin White
BT - 29th Annual Conference on Learning Theory
DA - 2016/06/06
ED - Vitaly Feldman
ED - Alexander Rakhlin
ED - Ohad Shamir
ID - pmlr-v49-balcan16b
PB - PMLR
DP - Proceedings of Machine Learning Research
VL - 49
SP - 310
EP - 335
L1 - http://proceedings.mlr.press/v49/balcan16b.pdf
UR - https://proceedings.mlr.press/v49/balcan16b.html
AB - A large body of work in machine learning has focused on the problem of learning a close approximation to an underlying combinatorial function, given a small set of labeled examples. However, for real-valued functions, cardinal labels might not be accessible, or it may be difficult for an expert to consistently assign real-valued labels over the entire set of examples. For instance, it is notoriously hard for consumers to reliably assign values to bundles of merchandise. Instead, it might be much easier for a consumer to report which of two bundles she likes better. With this motivation in mind, we consider an alternative learning model, wherein the algorithm must learn the underlying function up to pairwise comparisons, from pairwise comparisons. In this model, we present a series of novel algorithms that learn over a wide variety of combinatorial function classes. These range from graph functions to broad classes of valuation functions that are fundamentally important in microeconomic theory, the analysis of social networks, and machine learning, such as coverage, submodular, XOS, and subadditive functions, as well as functions with sparse Fourier support.
ER -

APA

Balcan, M., Vitercik, E. & White, C.. (2016). Learning Combinatorial Functions from Pairwise Comparisons. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:310-335 Available from https://proceedings.mlr.press/v49/balcan16b.html.