Exploiting Graph Structure for Information Planning and Structure Discovery
Tuesday, April 10, 2018 - 3:00pm to 4:00pm
Dr. John W. Fisher III Senior Research Scientist Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology
In this talk I consider two related problems. Firstly, I will discuss the use of information measures for controlling the measurement process where analysis is formulated as inference in a generative graphical model. In many distributed sensing systems, limited resources constrain the use of sensing assets. This leads to a fundamental trade-off between the utility in a distributed set of measurements versus the resources expended to acquire them, fuse them into a model of uncertainty, and ultimately reason over the resulting model. Information measures are appealing due to a variety of useful properties. For example, the results of [Nguyen et al, 2009], link a class of information measures to surrogate risk functions and their associated bounds on excess risk (see [Bartlett et al, 2003]). Consequently, these measures are suitable proxies for a wide variety of risk functions. The work of [Williams et al, 2007] (since extended) enables long time-horizon sensor planning in the context of state estimation formulated as inference in a probabilistic graphical model. Theoretical results provide fundamental performance bounds showing that, under mild assumptions, optimal (though intractable) planning schemes can yield no better than twice the performance of greedy methods for certain choices of information measures. In this setting, computation of the information measure is intimately related to the structure of the graph.