Systems Science Seminar|
Active Sequential Hypothesis Testing
Tara J avidi
University of California - San Diego, Department of Electrical and Computer Engineering
Tuesday, October 09, 2012|
3:00pm - 4:00pm
About the Event
Active sequential hypothesis testing problem arises in a broad spectrum of applications in cognition, communications, design of experiments, and sensor management. In all of these applications, a decision maker is responsible to take actions dynamically so as to enhance information about an underlying phenomena of interest in a speedy manner while accounting for the cost of communication, sensing, or data collection. In particular, due to the sequential nature of the problem, the decision maker relies on his current information state to constantly (re-)evaluate the trade-off between the precision and cost as well as the influence that every action has over the entire decision making horizon. In this talk, we first discuss active sequential hypothesis testing as a partially observable Markov decision problem. In particular, we provide a brief survey of the design of experiment literature and the dynamic programming interpretation of information utility introduced by De Groot: To achieve the best performance, it is essential that the decision maker, in each step, selects the most “informative” action among the available ones where the critical question is what the proper measure of information should be. Using the notion of asymptotic optimality due to Chernoff, we connect this stochastic control theoretic notion of information utility to the concept of uncertainty reduction and error exponents in information theory. Using the insights obtained, and to address the shortcomings of the proposed solutions, we introduce Extrinsic Jensen–Shannon (EJS) divergence as a measure of information based on which a heuristic policy for selecting actions is proposed. Via numerical and asymptotic analysis, the performance of the proposed policy, hence the utility of the EJS divergence in the context of the active hypothesis testing is investigated. In particular, it is shown that the proposed heuristic achieves asymptotic optimality in many practically relevant problems including that of variable length coding over discrete memoryless channels with perfect feedback. As a special case, this results in the first sequential, deterministic and one phase coding scheme, to the best of our knowledge, which achieves Burnashev's optimal error exponent.
This is joint work with Mohammad Naghshvar, Ofer Shayevitz, and Michele Wigger.
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. Tara Javidi was a Barbour Scholar during 1999-2000 academic year and received an NSF CAREER Award in 2004. Her research interests are in communication networks, stochastic resource allocation, stochastic control theory, and wireless communications.
Contact: Ann Pace
Sponsor: University of Michigan
Open to: Public