Select Lab Publications


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

By: Andreas Krause and Carlos Guestrin

Abstract: 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 strongest 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. For both problems, we present algorithms for the filtering case, where only observations made in the past are taken into account, and the smoothing case, where all observations are utilized. Furthermore we 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 NP^PP-hard even for discrete polytrees. It also follows from our results that even computing value of information objective functions is a #P-complete problem on polytrees. Finally, we demonstrate the effectiveness of our approach on several realworld datasets.

Download Information
Andreas Krause and Carlos Guestrin (2005). "Optimal Nonmyopic Value of Information in Graphical Models - Efficient Algorithms and Theoretical Limits." International Joint Conference on Artificial Intelligence (IJCAI). pdf   talk        
BibTeX citation

@inproceedings{Krause+Guestrin:ijcai05optimal,
author = {Andreas Krause and Carlos Guestrin},
title = {Optimal Nonmyopic Value of Information in Graphical Models - Efficient
Algorithms and Theoretical Limits},
booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)},
month = {July},
year = {2005},
wwwfilebase = {ijcai2005-krause-guestrin},
wwwtopic = {Observation Selection},
}



full list