Peference elicitation is the task of suggesting a highly preferred configuration to a decision maker. The preferences are typically learned by querying the user for choice feedback over pairs or sets of objects. In its constructive variant, new objects are synthesized "from scratch" by maximizing an estimate of the user utility over a combinatorial (possibly infinite) space of candidates. In the constructive setting, most existing elicitation techniques fail because they rely on exhaustive enumeration of the candidates. A previous solution explicitly designed for constructive tasks comes with no formal performance guarantees, and can be very expensive in (or unapplicable to) problems with non-Boolean attributes. We propose the Choice Perceptron, a Perceptron-like algorithm for learning user preferences from set-wise choice feedback over constructive domains and hybrid Boolean-numeric feature spaces. We provide a theoretical analysis on the attained regret that holds for a large class of query selection strategies, and devise a heuristic strategy that aims at optimizing the regret in practice. Finally, we demonstrate its effectiveness by empirical evaluation against existing competitors on constructive scenarios of increasing complexity.
Preference elicitation (PE) is a widely studied subject in AI @cite_21 @cite_13 . Most existing approaches to PE rely on regret theory @cite_18 @cite_11 or Bayesian estimation @cite_9 ; see @cite_12 for a brief overview. None of them are suitable for constructive settings, for different reasons. Regret-based methods maintain a version space of utility functions consistent with the collected feedback. However, inconsistent user responses, which are common in real-world recommendation, make the version space collapse. Bayesian methods gracefully deal with inconsistent feedback by employing a full distribution over the candidate utility functions. Unfortunately, selection of the query set (based on optimizing its Expected Value of Information or approximations thereof) is computationally expensive, preventing these approaches from scaling to larger combinatorial domains.
@cite_18 @cite_9 @cite_21 @cite_13 @cite_12 @cite_11
1991185257 2146412174 1988793717 2402248766 99692743
Current conversational recommender systems are unable to offer guarantees on the quality of their recommendations due to a lack of principled user utility models. We develop an approach to recommender systems that incorporates an explicit utility model into the recommendation process in a decision-theoretically sound fashion. The system maintains explicit constraints on user utility based on preferences revealed by the user's actions. We investigate a new decision criterion, setwise minimax regret (SMR), for constructing optimal recommendation sets: we develop algorithms for computing SMR, and prove that SMR determines choice sets for queries that are myopically optimal. This provides a natural basis for generating compound critiques in conversational recommender systems. Our simulation results suggest that this utility-theoretically sound approach to user modeling allows much more effective navigation of a product space than traditional approaches based on, for example, heuristic utility models and product similarity measures. Bayesian approaches to utility elicitation typically adopt (myopic) expected value of information (EVOI) as a natural criterion for selecting queries. However, EVOI-optimization is usually computationally prohibitive. In this paper, we examine EVOI optimization using choice queries, queries in which a user is ask to select her most preferred product from a set. We show that, under very general assumptions, the optimal choice query w.r.t. EVOI coincides with the optimal recommendation set, that is, a set maximizing the expected utility of the user selection. Since recommendation set optimization is a simpler, submodular problem, this can greatly reduce the complexity of both exact and approximate (greedy) computation of optimal choice queries. We also examine the case where user responses to choice queries are error-prone (using both constant and mixed multinomial logit noise models) and provide worst-case guarantees. Finally we present a local search technique for query optimization that works extremely well with large outcome spaces. This editorial of the special issue ''Representing, Processing, and Learning Preferences: Theoretical and Practical Challenges'' surveys past and ongoing research on preferences in AI, including references and pointers to the literature. It covers approaches to representation, reasoning and learning of preferences. Methods in AI are contrasted with those in related areas, such as operations research and databases. Finally, we also give a brief introduction to the contents of the special issue. Utility elicitation is an important component of many applications, such as decision support systems and recommender systems. Such systems query users about their preferences and offer recommendations based on the system's belief about the user's utility function. We analyze the connection between the problem of generating optimal recommendation sets and the problem of generating optimal choice queries, in the context of both Bayesian and regret-based elicitation. Our results show that, somewhat surprisingly, under very general circumstances, the optimal recommendation set coincides with the optimal query. We investigate robust decision-making under utility uncertainty, using the maximin criterion, which optimizes utility for the worst case setting. We show how it is possible to efficiently compute the maximin optimal recommendation in face of utility uncertainty, even in large configuration spaces. We then introduce a new decision criterion, setwise maximin utility SMMU, for constructing optimal recommendation sets: we develop algorithms for computing SMMU and present experimental results showing their performance. Finally, we discuss the problem of elicitation and prove analogously to previous results related to regret-based and Bayesian elicitation that SMMU leads to myopically optimal query sets.