期刊
ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY
卷 2, 期 4, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1989734.1989736
关键词
Algorithms; Measurement; Information gathering; submodular functions; environmental monitoring; information overload; blogs; active learning; sensor networks; computational sustainability
资金
- NSF [CNS-0509383, CNS-0625518, IIS-0953413]
- ARO MURI [W911NF0710287]
- Alfred P. Sloan Fellowship
- IBM
- ONR Young Investigator Award [N00014-08-1-0752]
- Microsoft Research Graduate Fellowship
- Okawa Foundation
- ONR [N000140911044]
Where should we place sensors to efficiently monitor natural drinking water resources for contamination? Which blogs should we read to learn about the biggest stories on the Web? These problems share a fundamental challenge: How can we obtain the most useful information about the state of the world, at minimum cost? Such information gathering, or active learning, problems are typically NP-hard, and were commonly addressed using heuristics without theoretical guarantees about the solution quality. In this article, we describe algorithms which efficiently find provably near-optimal solutions to large, complex information gathering. problems. Our algorithms exploit submodularity, an intuitive notion of diminishing returns common to many sensing problems: the more sensors we have already deployed, the less we learn by placing another sensor. In addition to identifying the most informative sensing locations, our algorithms can handle more challenging settings, where sensors need to be able to reliably communicate over lossy links, where mobile robots are used for collecting data, or where solutions need to be robust against adversaries and sensor failures. We also present results applying our algorithms to several real-world sensing tasks, including environmental monitoring using robotic sensors, activity recognition using a built sensing chair, a sensor placement challenge, and deciding which blogs to read on the Web.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据