Nonmyopic Value of Information in Graphical Models

Andreas Krause

Abstract

In decision making under uncertainty, where one can choose among several expensive queries, it is a central issue to decide which variables to observe in order to achieve a most effective increase in expected utility. This problem has previously only been approached myopically, without any known performance guarantees. In this talk, I will present efficient nonmyopic algorithms for selecting an optimal subset of observations and for computing an optimal conditional plan for a class of graphical models containing Hidden Markov Models. I will also show how our methods can be used for interactive structured classification and for sensor scheduling in a Civil Engineering domain. Many graphical models tasks which can be efficiently solved for chains, can be generalized to polytrees. I will present surprising hardness results, showing that the optimization problems are wildly intractable (NP^PP complete) even in the case of discrete polytrees. Addressing these theoretical limits, I will present efficient approximation algorithms for selecting informative subsets of variables. Our algorithms are applicable to a large class of graphical models, and provide a constant factor approximation guarantee of 1-1/e, which is provably the best constant factor achievable unless P = NP. I will sketch how our methods can be extended to optimal experimental design in Gaussian processes, and I will present extensive evaluation of our algorithms on several real-world data sets.

Back to the Main Page