Robust Optimization of Recommendation Sets with the Maximin Utility Criterion
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 uncer
- PDF / 351,252 Bytes
- 14 Pages / 439.363 x 666.131 pts Page_size
- 73 Downloads / 201 Views
CNRS-LIP6 and Univ. Pierre et Marie Curie, France [email protected] 2 Carnegie Mellon University, USA [email protected]
Abstract. 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.
1 Introduction Reasoning about preferences [9] is an important component of many systems, including decision support and recommender systems, personal agents and cognitive assistants. Because acquiring user preferences is expensive (with respect to time and cognitive cost), it is essential to provide techniques that can reason with partial preference (utility) information, and that can effectively elicit the most relevant preference information. Adaptive utility elicitation [3] tackles the challenges posed by preference elicitation by representing the system knowledge about the user in the form of beliefs, that are updated following user responses. Elicitation queries can be chosen adaptively given the current belief. In this way, one can often make good (or even optimal) recommendations with sparse knowledge of the user’s utility function. Since utility is uncertain, there is often value in recommending a set of options from which the user can choose her preferred option. Retrieving a “diverse” set of recommended options increases the odds that at least one recommended item has high utility. Intuitively, such a set of “shortlisted” recommendations should include options of high utility relative to a wide range of “likely” user utility functions (relative to the current belief) [10]. This stands in contrast to some recommender systems that define diversity relative to product attributes. “Top k” options (those with highest expected utility) do not generally result in good recommendation sets. Recommendation systems can be classified according to the way they represent the uncertainty about the user preferences (encoded by an utility function) and how such uncertainty is aggregated in order to produce recommendations that are believed to have P. Perny, M. Pirlot, and A. Tsouki`as (Eds.): ADT 2013, LNAI 8176, pp. 411–424, 2013. c Springer-Verlag Berlin Heidelberg 2013
412
P. Viappiani and C. Kroer
high utility. A common approach [4,10,3,14] is to consider a distribution over possible user preferences, and make recommendations based on expected utility. Another line of work [1,2,3,13] assumes no probabilistic prior is available (the strict uncertainty setting) and provides recom
Data Loading...
