Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University


Optimal Nonmyopic Value of Information in Graphical Models -
Efficient Algorithms and Theoretical Limits

Andreas Krause, Carlos Guestrin

February 2005

Also appears as Computer Science Department
Technical Report CMU-CS-05-107.


Keywords: Uncertainty, probabilistic reasoning, decision theory, graphical models, value of information, complexity theory

Many real-world decision making tasks require us to choose among several expensive observations. In a sensor network, for example, it is important to select the subset of sensors that is expected to provide the highest reduction in uncertainty. It has been general practice to use heuristic-guided procedures for selecting observations. In this paper, we present the first efficient optimal algorithms for selecting observations for a class of graphical models containing Hidden Markov Models (HMMs). We provide results for both selecting the optimal subset of observations, and for obtaining an optimal conditional observation plan. We also prove a surprising result: In most graphical models tasks, if one designs an efficient algorithm for chain graphs, such as HMMs, this procedure can be generalized to polytrees. We prove that the value of information problem is NPPP-hard even for discrete polytrees. It also follows from our results that even computing conditional entropies, which are widely used to measure value of information, is a #P-complete problem on polytrees. Finally, we demonstrate the effectiveness of our approach on several real-world datasets.

8 pages

SCS Technical Report Collection
School of Computer Science homepage

This page maintained by