Near-optimal Nonmyopic Value of Information in Graphical Models

By Andreas Krause, Carlos Guestrin. 2005

483 citations recorded by the source corpus.

A fundamental issue in real-world systems, such as sensor networks, is the selection of observations which most effectively reduce uncertainty. More specifically, we address the long standing problem of nonmyopically selecting the most informative subset of variables in a graphical model. We present the first efficient randomized algorithm providing a constant factor (1 - 1/e – e) approximation guarantee for any e > 0 with high confidence. The algorithm leverages the theory of submodular functions, in combination with a polynomial bound on sample complexity. We furthermore prove that no polynomial time algorithm can provide a constant factor approximation better than (1 - 1/e) unless P = NP. Finally, we provide extensive evidence of the effectiveness of our method on two complex real-world datasets.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, methodology): “Discrete optimization methods, such as those based on submodularity, may be applicable here (Krause and Golovin 2014; Iyer and Bilmes 2013; Bach 2013; Feige 1998; Krause and Guestrin 2005; Nemhauser, Wolsey, and Fisher 1978).”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, background): “These properties are monotonicity (adding an element x to the set A cannot decrease the mutual information between f and the corresponding set of observations yA) and submodularity (the increase in mutual information between f and yA with the addition of an element x to set A cannot be greater than ”
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2009, methodology): “This is because F ( A ) satisﬁes a diminishing returns property called submodularity (Krause & Guestrin, 2005), and the greedy approximation guarantee (5) holds for any submodular function (Nemhauser et al., 1978).”
Near-optimal Observation Selection using Submodular Functions (2007, methodology): “These optimization problems are generally NP-hard (Krause & Guestrin 2005b).”
Online Submodular Maximization with Preemption (2015, methodology): “In machine learning, submodular maximization has been used for document summarization [46, 47], sensor placement [41, 42, 44], and information gathering [43].”
Guarantees for Greedy Maximization of Non-submodular Functions with Applications (2017, background): “Although log F ( S ) is submodular (Krause & Guestrin, 2005), F ( S ) is in general not submodular.”
Submodular Function Maximization (2014, background): “However, if the variables X are conditionally independent given Y , i.e., for all disjoint sets A, B ⊂ V if holds that X A ⊥ X B | Y , then f is monotone submodular (Krause and Guestrin, 2005).”
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…”
The strategic student approach for life-long exploration and learning (2012, background): “to minimize is indeed monotonic submodular (see [33] for the analysis of different measures of uncertainty).”
Near-optimal Supervised Feature Selection among Frequent Subgraphs (2009, background): “The quality criterion used for those two is information gain, which can be submodular, given certain preconditions [18].”
Learning Mixtures of Submodular Shells with Application to Document Summarization (2012, background): “While they have a long history in operations research, game theory, econometrics, and electrical engineering, they are still beginning to be studied in machine learning for a variety of tasks including sensor placement [19, 20], structure learning of graphical models [34], document summarization [27”
A Class of Submodular Functions for Document Summarization (2011, background): “…functions have started receiving attention in the machine learning and computer vision community (Kempe et al., 2003; Narasimhan and Bilmes, 2005; Krause and Guestrin, 2005; Narasimhan and Bilmes, 2007; Krause et al., 2008; Kolmogorov and Zabin, 2004) and have recently been introduced to natural…”
Combinatorial Penalties: Structure preserved by convex relaxations (2017, background): “To that end we recall the concept of discrete stable sets [1], also referred to as flat or closed sets [25].”
A Hilbert Space Embedding for Distributions (2007, background): “Recent examples include [7] in the context of construction of graphical models, [8] in the context of feature extraction, and [9] in the context of independent component analysis.”
Lazier Than Lazy Greedy (2014, background): “It can be shown that this choice of f is monotone submodular (Krause and Guestrin 2005).”
Submodular Maximization with Cardinality Constraints (2014, methodology): “In machine learning, maximization of submodular functions has been used for document summarization [41, 42], sensor placement [36, 38, 35], and information gathering [37] (consult the references therein for additional applications in AI).”