by ,
Abstract:
A fundamental issue in real-world systems, such as sen- sor 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 random- ized algorithm providing a constant factor (1 − 1/e − ε) approximation guarantee for any ε > 0 with high con- fidence. The algorithm leverages the theory of submod- ular 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 effective- ness of our method on two complex real-world datasets.
Reference:
Near-optimal Nonmyopic Value of Information in Graphical Models A. Krause, C. GuestrinIn Conference on Uncertainty in Artificial Intelligence (UAI), 2005Winner of the Best Paper Runner-Up Award
Bibtex Entry:
@inproceedings{krause05near,
	Author = {Andreas Krause and Carlos Guestrin},
	Booktitle = {Conference on Uncertainty in Artificial Intelligence (UAI)},
	Month = {July},
	Title = {Near-optimal Nonmyopic Value of Information in Graphical Models},
	Year = {2005}}