Learning Linear Utility Functions From Pairwise Comparison Queries

• URL: http://arxiv.org/abs/2405.02612v3
• Date: Wed, 19 Jun 2024 17:08:13 GMT
• Title: Learning Linear Utility Functions From Pairwise Comparison Queries
• Authors: Luise Ge, Brendan Juba, Yevgeniy Vorobeychik,
• Abstract summary: We study learnability of linear utility functions from pairwise comparison queries. We show that in the passive learning setting, linear utilities are efficiently learnable with respect to the first objective. In this case, we show that even the second objective is efficiently learnable, and present algorithms for both the noise-free and noisy query response settings.
• Score: 35.01228510505625
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study learnability of linear utility functions from pairwise comparison queries. In particular, we consider two learning objectives. The first objective is to predict out-of-sample responses to pairwise comparisons, whereas the second is to approximately recover the true parameters of the utility function. We show that in the passive learning setting, linear utilities are efficiently learnable with respect to the first objective, both when query responses are uncorrupted by noise, and under Tsybakov noise when the distributions are sufficiently "nice". In contrast, we show that utility parameters are not learnable for a large set of data distributions without strong modeling assumptions, even when query responses are noise-free. Next, we proceed to analyze the learning problem in an active learning setting. In this case, we show that even the second objective is efficiently learnable, and present algorithms for both the noise-free and noisy query response settings. Our results thus exhibit a qualitative learnability gap between passive and active learning from pairwise preference queries, demonstrating the value of the ability to select pairwise queries for utility learning.

Related papers

• Likelihood as a Performance Gauge for Retrieval-Augmented Generation [78.28197013467157]
  We show that likelihoods serve as an effective gauge for language model performance. We propose two methods that use question likelihood as a gauge for selecting and constructing prompts that lead to better performance.
  arXiv  Detail & Related papers  (2024-11-12T13:14:09Z)
• Prefer to Classify: Improving Text Classifiers via Auxiliary Preference Learning [76.43827771613127]
  In this paper, we investigate task-specific preferences between pairs of input texts as a new alternative way for such auxiliary data annotation. We propose a novel multi-task learning framework, called prefer-to-classify (P2C), which can enjoy the cooperative effect of learning both the given classification task and the auxiliary preferences.
  arXiv  Detail & Related papers  (2023-06-08T04:04:47Z)
• Efficient Utility Function Learning for Multi-Objective Parameter Optimization with Prior Knowledge [0.225596179391365]
  We learn a utility function offline, using expert knowledge by means of preference learning. In contrast to other works, we do not only use (pairwise) result preferences, but also coarse information about the utility function space. We show the sample efficiency and quality gains of the proposed method in 4 domains.
  arXiv  Detail & Related papers  (2022-08-22T13:26:03Z)
• Mind Your Outliers! Investigating the Negative Impact of Outliers on Active Learning for Visual Question Answering [71.15403434929915]
  We show that across 5 models and 4 datasets on the task of visual question answering, a wide variety of active learning approaches fail to outperform random selection. We identify the problem as collective outliers -- groups of examples that active learning methods prefer to acquire but models fail to learn. We show that active learning sample efficiency increases significantly as the number of collective outliers in the active learning pool decreases.
  arXiv  Detail & Related papers  (2021-07-06T00:52:11Z)
• Can Active Learning Preemptively Mitigate Fairness Issues? [66.84854430781097]
  dataset bias is one of the prevailing causes of unfairness in machine learning. We study whether models trained with uncertainty-based ALs are fairer in their decisions with respect to a protected class. We also explore the interaction of algorithmic fairness methods such as gradient reversal (GRAD) and BALD.
  arXiv  Detail & Related papers  (2021-04-14T14:20:22Z)
• Feature Importance Ranking for Deep Learning [7.287652818214449]
  We propose a novel dual-net architecture consisting of operator and selector for discovery of an optimal feature subset of a fixed size. During learning, the operator is trained for a supervised learning task via optimal feature subset candidates generated by the selector. In deployment, the selector generates an optimal feature subset and ranks feature importance, while the operator makes predictions based on the optimal subset for test data.
  arXiv  Detail & Related papers  (2020-10-18T12:20:27Z)
• On the Robustness of Active Learning [0.7340017786387767]
  Active Learning is concerned with how to identify the most useful samples for a Machine Learning algorithm to be trained with. We find that it is often applied with not enough care and domain knowledge. We propose the new "Sum of Squared Logits" method based on the Simpson diversity index and investigate the effect of using the confusion matrix for balancing in sample selection.
  arXiv  Detail & Related papers  (2020-06-18T09:07:23Z)
• Improving Multi-Turn Response Selection Models with Complementary Last-Utterance Selection by Instance Weighting [84.9716460244444]
  We consider utilizing the underlying correlation in the data resource itself to derive different kinds of supervision signals. We conduct extensive experiments in two public datasets and obtain significant improvement in both datasets.
  arXiv  Detail & Related papers  (2020-02-18T06:29:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.