Submodularity. We identify a key structural property of many observation selection problems: submodularity, an intuitive diminishing returns property. Exploiting this property allows to obtain efficient approximation algorithms with provable guarantees, as well as drastically speeding up algorithms. Here's a short overview paper on this topic.

In [UAI'05], we show that, for a large class of graphical models, the problem of selecting a set of informative attributes (features) A maximizing the information gain I(U;A) with respect to target variables U, can be approximated efficiently for a large class of graphical models. Using the concept of submodularity, we show that the simple greedy algorithm provides a constant factor (1-1/e) approximation. Moreover, we show that this guarantee is essentially the best we can hope for. We apply our algorithms to select sensors for best predicting the Bay Area traffic. Here, A would be the selected sensors, and U the minimum traffic flow in certain regions.

Spatial monitoring. For monitoring spatial phenomena, such as temperature in a building, which can frequently be modeled using Gaussian Processes, mutual information, I(A;V\A) is an effective criterion for quantifying the informativeness of a sensor placement, avoiding the wasted information effect of the commonly used maximum entropy sampling. In [JMLR'07] we use submodularity to show that the greedy algorithm generates near-optimal placements under this criterion. We also show how we can exploit structure in the kernel to make this algorithm very efficient.

Outbreak detection. In [KDD'07], we study two seemingly very different problems: placing sensors in a municipal water distribution network in order to detect possible contaminations, and selecting informative weblogs to read on the Internet. We show that both problems share essential structure: Information cascades spreading over the blogosphere can be modeled similarly as contaminations spreading through water networks. We show that many objectives, such as optimizing the detection time or likelihood, satisfy submodularity, making the problem amenable for greedy (and hence highly scalable) optimization. We participated in the Battle of the Water Sensor Networks competition, which required to optimize for sensor placements in a real metropolitan-area network with 20,000 nodes. Our approach achieved the highest number of non-dominated solutions. In the blog selection problem, our approach outperforms existing ranking criteria. Here's a link to the CASCADES project page.

Posture recognition. In [UIST'07], we apply our sensor placement methods to instrument a chair with pressure sensors, in order to enable seating posture recognition. Our approach reduces the sensor hardware cost by a factor of 30 compared to previous solutions, while achieving comparable classification accuracy. We test our approach in a user study on a real deployment.

 

Nonmyopic algorithms

Gaussian processes. The above problems address a priori (open-loop) selection problems, where observations are chosen according to a model, before any measured values are obtained. In some applications, it is feasible to implement a sequential (closed-loop) strategy, which decides on the next observation based on previously obtained values. An important question is, how much better a sequential algorithm can perform compared to the best a priori selection. In [ICML'07], we partially answer this question for the case of sequentially optimizing mutual information in Gaussian Processes. We develop a theoretical bound quantifying the sequential advantage, and use it to guide an exploration-exploitation approach. Our approach has sample complexity guarantees, and performs well on environmental monitoring problems.

Chain models. In [IJCAI'05] we prove that for chain graphical models (such as HMMs), one can efficiently compute both the best subset of observations, and even the (exponentially large) best sequential plan, maximizing arbitrary value of information objectives. We also show that even for tree graphical models (for which efficient inference is tractable), this problem is wildly intractable (NP^PP complete).

In [SenSys'05], we consider a building automation problem, where we want to select  sensors in order to intelligently manage the light controls in a building, satisfying user preferences and at the same time conserve power. We formalize and solve this problem using our approach for maximizing value of information.