Optimizing Sensing: Challenges for Security and Privacy
Carnegie Mellon University
Where should we place sensors to quickly detect contamination in
drinking water distribution networks? Which data should we acquire
about web surfers in order to improve personalized search? These
problems share a fundamental challenge: How can we obtain the most
useful information about the state of the world, at minimum cost?
Such sensing, or active learning, problems are typically NP-hard, and
were commonly addressed using heuristics without theoretical
guarantees about the solution quality. In this talk, I will present
algorithms which efficiently find provably near-optimal solutions to
large, complex sensing 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 observations, our algorithms allow to address important
security and privacy challenges arising in practical sensing problems.
In security-critical applications such as protecting drinking water
from contamination, the sensor placements need to be robust against
adversaries and sensor failures. In the web search example, acquired
data about users should enable effective personalization, while
minimizing the incursion in privacy.
I will also present results applying our algorithms to several
real-world sensing tasks, including environmental monitoring using
robotic sensors, trading off utility and privacy in personalized
search, and a sensor placement competition.
This talk is mainly based on joint work with Carlos Guestrin and Eric Horvitz.
Andreas Krause is a Ph.D. Candidate at the Computer Science Department
of Carnegie Mellon University. He is a recipient of a Microsoft
Research Graduate Fellowship, and his research on sensor placement and
information acquisition received awards at several conferences (KDD
'07, IPSN '06, ICML '05 and UAI '05). He obtained his Diplom in
Computer Science and Mathematics from the Technische UniversitÃ¤t
MÃ¼nchen, where his research received the NRW Undergraduate Science
Award. He has accepted a tenure-track position at the California
Institute of Technology and will join their Computer Science faculty
in January 2009.