TUTORIAL - Track 2

Information Acquisition, Congtrolled Sensing and Active Hypothesis Testing

Tara Javidi

Sunday June 29, 2014
09:00 - 12:00
Room: 316B


(For a detailed abstract click here. A shorter summary follows.)

Information acquisition problems form a class of stochastic decision problems in which a decision maker is faced with utilizing a stochastically varying environment. However, the state of the environment, due to the limited nature of the measurements in terms of dimension/ complexity/cost/accuracy, is only partially known to the decision maker. The decision maker, by carefully controlling the sequence of actions with uncertain outcomes and noisy measurements, dynamically refines the belief about the stochastically varying parameters of interest. A generalization of hidden Markov models and a special case of partially observable Markov models, information acquisition is both an informational problem as well as a control one.

We start the tutorial with active hypothesis testing as a special case of information acquisition. This problem has been studied in various areas of applied mathematics, statistics, and engineering. The first part of the tutorial discusses the historical developments from Wald's original sequential binary hypothesis testing to Blackwell's (and DeGroot's) comparison of experiments to Chernoff's hypothesis testing with unbounded number of samples. We then catalogue recent improvements, analysis, and newly proposed (asymptotically) optimal solutions. We will see that the performance of any information acquisition policy is closely related to the Rényi divergence of the (noisy) collected samples/measurements under various hypothesis. We also discuss the analytical tools such as method of types, large deviation analysis, and measure concentration for martingales. Throughout the first part of the talk, we illustrate the findings and analysis in the context of (visual) noisy search.

The second part of the tutorial will return to the problem of information acquisition where the hidden state of the environment or the parameter of interest evolves according to a Markov chain. Here we bring to the forefront two aspects of the information acquisition process. The first aspect of the problem deals with the dimensionality of collected data/measurements, while the second aspect of information acquisition has to address the problem of non-persistent noise in the observation sequence and the decision makers' ability to discriminate among states in a speedy manner and with high statistical reliability. We illustrate the findings in two important application areas: 1) the problem of enhanced spectrum access where the secondary network manager seeks to track the (in)activity of the primary network users over time, frequency, and space and 2) real-time joint source-channel coding with feedback and generalized transmission cost (surprisingly, this class includes the problem of tracking as a special case).


Tara Javidi studied electrical engineering at Sharif University of Technology, Tehran, Iran from 1992 to 1996. She received the MS degrees in electrical engineering (systems), and in applied mathematics (stochastics) from the University of Michigan, Ann Arbor, in 1998 and 1999, respectively. She received her Ph.D. in electrical engineering and computer science from the University of Michigan, Ann Arbor, in 2002. From 2002 to 2004, she was an assistant professor at the Electrical Engineering Department, University of Washington, Seattle. She joined University of California, San Diego, in 2005, where she is currently an associate professor of electrical and computer engineering.

Dr. Javidi was a recipient of the National Science Foundation early career award (CAREER) in 2004, Barbour Graduate Scholarship, University of Michigan, in 1999, and the Presidential and Ministerial Recognitions for Excellence in the National Entrance Exam, in 1992. She is an Associate Editor for ACM/IEEE Transactions on Networking and for IEEE Transactions on Network Science and Engineering. She was also the lead guest editor for IEEE JSAC special issue on control and communications. Her research interests include stochastic control, feedback information theory, and wireless networking.