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
11/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 realworld data
sets.

Pradeep Ravikumar Last modified: Wed Oct 5 12:38:53 EDT 2005