Seminar on Computational Learning and Adaptation

and

Decision Analysis Working Group

 
Learning the Structure of Utility Functions

Urszula Chajewska
Department of Computer Science
Stanford University
urszula@cs.stanford.edu

Utility functions are defined over a space which is exponential in the number of variables on which the utility depends.  More compact representations of the utility are possible if we make certain assumptions about additive independence among the variables.  These assumptions allow the function to be decomposed into smaller components, thus reducing the number of parameters needed to specify it completely.  Decomposable utility functions support more efficient inference and are easier to elicit from people.  However, it can be difficult to know which decomposition is appropriate in a given setting.  We hypothesize that there is some commonality to the utilities exhibited by a population of users; more precisely, we assume that the population is divided (in an unknown way) into subpopulations, each of which is statistically coherent.  We can view the problem of discovering the structure of this distribution over utilities in a population as a statistical learning task.  We show how we can apply Bayesian learning techniques to learn the distribution over factored utility functions from a set of fully specified utility functions elicited from a population of users.  Our approach can be used for a wide range of independence types, including "conditional additive independence" and "generalized additive independence."  We show how to choose a utility decomposition appropriate to a large subpopulation by performing statistical model selection, using an approximation to the Bayesian score.  The factorization of the utilities in the learned model facilitates utility elicitation by allowing fully specified utility functions to be assessed using a significantly smaller number of questions.  The generalization obtained from learning a model for a population of similar people allows smoother estimates of the utility function, thereby reducing the noise unavoidable in utility assessment.

Return to the seminar schedule