Published on Tue Nov 21 2017

Constructive Preference Elicitation over Hybrid Combinatorial Spaces

Paolo Dragone, Stefano Teso, Andrea Passerini

Preference 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"

0
0
0
Abstract

Preference 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.

Wed Nov 22 2017
Machine Learning
Decomposition Strategies for Constructive Preference Elicitation
We tackle the problem of constructive preference elicitation. The user provides feedback to the algorithm in the form of an improvement to a suggested configuration. This type of interaction poses a significant cognitive burden on the user. We propose a decomposition technique relying exclusively on inference and feedback over partial configurations.
0
0
0
Tue Aug 18 2015
Artificial Intelligence
Learning Modulo Theories for preference elicitation in hybrid domains
CLEO is the first preference elicitation algorithm capable of dealing with hybrid domains. It uses Max-SMT technology, while retaining uncertainty in the DM utility and noisy feedback. Experimental results show the ability of CLEO to quickly focus towards optimal solutions.
0
0
0
Wed Jul 29 2020
Artificial Intelligence
Bayesian preference elicitation for multiobjective combinatorial optimization
We introduce a new incremental preference elicitation procedure able to deal with noisy responses of a Decision Maker (DM) The originality of the contribution is to propose a Bayesian approach for determining a preferred solution in a multiobjective decision problem involving a combinatorial set of alternatives.
0
0
0
Thu May 27 2021
Machine Learning
One Step Preference Elicitation in Multi-Objective Bayesian Optimization
We consider a multi-objective optimization problem with objective functions that are expensive to evaluate. The decision maker (DM) has unknownipientpreferences, and so the standard approach is to generate an approximation of the Pareto front and let the DM choose from the generated non-dominated
2
0
0
Thu Jan 16 2014
Artificial Intelligence
Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects
We present a method for using standard techniques from satisfiability checking to automatically verify and discover theorems in an area of economic theory known as ranking sets of objects. We first prove a general result that shows that for a wide range of such principles, characterised by their syntactic form
0
0
0
Wed Jan 30 2013
Artificial Intelligence
Towards Case-Based Preference Elicitation: Similarity Measures on Preference Structures
For many applications involving interactive systems this overhead precludes the use of formal decision-theoretic models of preference. Instead of performing elicitation in a vacuum, it would be useful if we could augment directly elicited preferences with some appropriate default information.
0
0
0