|
CMU-CS-05-107
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMU-CS-05-107
Optimal Nonmyopic Value of Information in Graphical Models -
Efficient Algorithms and Theoretical Limits
Andreas Krause, Carlos Guestrin
February 2005
Also appears as Center for Automated Learning and Discovery
Technical Report CMU-CALD-05-100.
CMU-CS-05-107.ps
CMU-CS-05-107.pdf
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
|