Optimal Value of Information in Graphical Models

By Andreas Krause, Carlos Guestrin. 2009

129 citations recorded by the source corpus.

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. In medical decision making tasks, one needs to select which tests to administer before deciding on the most effective treatment. 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 probabilistic graphical models. For example, our algorithms allow to optimally label hidden variables in Hidden Markov Models (HMMs). We provide results for both selecting the optimal subset of observations, and for obtaining an optimal conditional observation plan. 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 poly-tree graphical models. We prove that the optimizing value of information is NPPP-hard even for polytrees. It also follows from our results that just computing decision theoretic value of information objective functions, which are commonly used in practice, is a #P-complete problem even on Naive Bayes models (a simple special case of polytrees). In addition, we consider several extensions, such as using our algorithms for scheduling observation selection for multiple sensors. We demonstrate the effectiveness of our approach on several real-world datasets, including a prototype sensor network deployment for energy conservation in buildings.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, background): “Speciﬁcally, we restrict ourselves to batch teaching with full knowledge of the learning algo-rithm.”
Near-optimal Observation Selection using Submodular Functions (2007, methodology): “In our recent work (Krause & Guestrin 2005c; Guestrin, Krause, & Singh 2005; Krause et al. 2006; 2007; Singh et al. 2007), we have presented several efficient algorithms for approximately solving these optimization problems .”
Robust Submodular Observation Selection (2008, background): “…example, the marginal variance at one location, or the information gain for a fixed set of parameters (Das and Kempe, 2008; Krause et al., 2007b; Krause and Guestrin, 2005; Guestrin et al., 2005), satisfy submodularity, an intuitive diminishing returns property: Adding a new observation helps…”