Title: Decomposition Strategies for Constructive Preference Elicitation,
Abstract: We tackle the problem of constructive preference elicitation, that is the
problem of learning user preferences over very large decision problems,
involving a combinatorial space of possible outcomes. In this setting, the
suggested configuration is synthesized on-the-fly by solving a constrained
optimization problem, while the preferences are learned itera tively by
interacting with the user. Previous work has shown that Coactive Learning is a
suitable method for learning user preferences in constructive scenarios. In
Coactive Learning the user provides feedback to the algorithm in the form of an
improvement to a suggested configuration. When the problem involves many
decision variables and constraints, this type of interaction poses a
significant cognitive burden on the user. We propose a decomposition technique
for large preference-based decision problems relying exclusively on inference
and feedback over partial configurations. This has the clear advantage of
drastically reducing the user cognitive load. Additionally, part-wise inference
can be (up to exponentially) less computationally demanding than inference over
full configurations. We discuss the theoretical implications of working with
parts and present promising empirical results on one synthetic and two
realistic constructive problems.