Local Utility Elicitation in GAI Models

Darius Braziunas, Craig BoutilierUAI 2005 · OpenReview

TL;DR

This paper introduces a novel method for eliciting user preferences in complex decision-making scenarios modeled by Generalized Additive Independence (GAI) utility functions. By leveraging the structure of GAI models and focusing on "local" queries about small subsets of attributes, the authors significantly reduce the cognitive burden on users and enable efficient elicitation even in very large domains.

What Problem Does This Paper Address?

Automated decision support systems often rely on understanding a user's preferences, typically modeled by utility functions. For complex problems with many attributes, specifying these utility functions directly is infeasible due to the exponential growth of possible outcomes. While structural assumptions like additive independence simplify this, Generalized Additive Independence (GAI) models offer more flexibility by allowing dependencies between subsets of attributes. However, existing methods for eliciting parameters of GAI models often still require users to make difficult judgments about full outcomes, negating some of the benefits of GAI's structure. This paper addresses the challenge of developing practical and efficient elicitation procedures for GAI models that minimize user effort.

Methods

The core contribution is a two-pronged approach to GAI utility elicitation:

  • Local Elicitation: Instead of asking users to compare entire outcomes, the method focuses on "local" queries. These queries involve comparing suboutcomes (partial outcomes restricted to a subset of attributes) against local gambles (lotteries over these suboutcomes). This is made possible by Theorem 3, which shows that under GAI, preferences over local outcomes are independent of other attributes when conditioning attributes are fixed at their default levels. This allows for eliciting local value functions for each GAI factor independently.
  • Global Scaling: After local elicitation, a procedure for "global scaling" is used to combine these local preferences into a coherent global utility function. This involves a limited number of queries about anchor outcomes (specific combinations of attribute levels) to calibrate the overall utility. The authors also propose a graphical representation of GAI models (GAI graphs) to systematically identify the necessary local suboutcomes for elicitation.
  • Elicitation Under Uncertainty: The paper extends this by considering scenarios where utility parameters are not precisely known but are described by prior probability distributions. They propose a myopic Expected Value of Information (EVOI) strategy to select the most informative queries. This involves optimizing over both the choice of query and the query point itself, aiming to maximize the expected reduction in uncertainty about the optimal decision.

Datasets

The paper evaluates its approach on a "realistic car-rental problem" with 26 variables and over 61 billion possible configurations. This problem is modeled using a GAI structure with 13 local factors. The authors do not introduce a new benchmark dataset but use an existing problem to demonstrate their method's scalability and effectiveness.

Key Insights and Ideas

  • "Local" is the Key: The most significant insight is that GAI models' structure allows for breaking down complex preference elicitation into manageable, "local" queries. This drastically reduces the cognitive load on the user compared to methods requiring judgments on full outcomes.
  • GAI Graphs Simplify Structure: Representing GAI models as graphs provides a systematic way to understand attribute dependencies and identify the specific suboutcomes relevant for elicitation, simplifying the process.
  • EVOI for Intelligent Queries: When utility parameters are uncertain, a myopic EVOI strategy intelligently guides the elicitation process by selecting queries that are most likely to reduce uncertainty about the optimal decision. This is more efficient than random querying.
  • Scalability is Achieved: The proposed methods are shown to be computationally efficient enough to support interactive elicitation, even for very large and complex problems.

Key Results

  • The proposed local elicitation method significantly reduces the number of queries and the complexity of judgments required from the user.
  • The EVOI strategy, when applied to GAI models, demonstrates superior performance compared to random query strategies in reducing utility error. For instance, with Gaussian priors, the EVOI strategy reduces error by over 80% after 50 queries, whereas random strategies achieve at best 20% reduction.
  • The method is computationally efficient, with EVOI computations for the car-rental problem taking around 1 second, enabling interactive use.

Limitations and Future Work

  • GAI Structure Assumption: The method relies on the assumption that the user's preferences can be accurately represented by a GAI model. Determining the appropriate GAI structure itself is a separate, important research direction.
  • Noise and Inconsistency: The current method assumes consistent user responses. Future work could explore methods for dealing with noisy or inconsistent user input.
  • Non-Myopic EVOI: The paper uses a myopic EVOI strategy. Developing computationally tractable approximations for non-myopic EVOI could lead to even more optimal elicitation policies.
  • Other Decision Criteria: Exploring decision criteria beyond maximizing expected utility, such as minimax regret, is suggested for future work.
  • More Realistic Queries: While focusing on local gambles, the paper mentions considering "more realistic local comparison queries" as a future step.

Summary updated

Abstract

Structured utility models are essential for the effective representation and elicitation of complex multiattribute utility functions. Generalized additive independence (GAI) models provide an attractive structural model of user preferences, offering a balanced tradeoff between simplicity and applicability. While representation and inference with such models is reasonably well understood, elicitation of the parameters of such models has been studied less from a practical perspective. We propose a procedure to elicit GAI model parameters using only "local" utility queries rather than "global" queries over full outcomes. Our local queries take full advantage of GAI structure and provide a sound framework for extending the elicitation procedure to settings where the uncertainty over utility parameters is represented probabilistically. We describe experiments using a myopic value-of-information approach to elicitation in a large GAI model.
BibTeX
@inproceedings{braziunas2005local,
  author = {Darius Braziunas and Craig Boutilier},
  title = {{Local Utility Elicitation in GAI Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=2M384MhXoPF},
}
Figure