Many sensor management problems under power or bandwidth constraints require us to adaptively activate sensors to obtain the most useful information. Because it is uncertain what observations will be made by any particular sensor, to solve these problems we face a task of sequential stochastic optimization under partial observability -- a fundamental but notoriously difficult challenge. Fortunately, many sensor management problems have a structural property that makes them
far easier than general sequential stochastic optimization. In this
talk, I will introduce this structural property -- a new concept called adaptive submodularity -- which generalizes submodular set functions to adaptive policies.
In many respects adaptive submodularity plays the same role for adaptive problems as submodularity plays for nonadaptive problems.
Specifically, just as many nonadaptive problems with submodular objectives have efficient algorithms with good approximation guarantees, so too do adaptive problems with adaptive submodular objectives. I will illustrate the usefulness of the concept by giving several examples of adaptive submodular objectives arising in diverse applications including sensor selection, viral marketing and active learning. Proving adaptive submodularity for these problems allows us to recover existing results in these applications as special cases and handle natural generalizations. In an application to Bayesian experimental design, we show how greedy optimization of a novel adaptive submodular criterion outperforms standard myopic techniques such as information gain and value of information.
Joint work with Daniel Golovin and Debajyoti Ray
Copyright. All Rights Reserved.