Active Sequential Hypothesis Testing

Professor Tara Javidi
Associate Professor, UC San Diego
Given on: October 11, 2012

Abstract

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 error exponents in statistics and information theory. One of the main drawbacks of Chernoff’s asymptotic optimality notion is his neglecting the complimentary role of asymptotic analysis in the number of hypothesis. In particular, his notion of asymptotic optimality falls short in showing the tension between using (asymptotically large number of) samples to discriminate among a few hypotheses with (asymptotically) high accuracy or a (asymptotically) large number of hypotheses with a lower degree of accuracy. Connecting De Groot's information utility framework with the Shannon theoretic concept of uncertainty reduction, we strengthen Chernoff's lower bound to account for the question of non-zero and maximum information acquisition rates as well as an upper bound on the error exponent as a function of rate.

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, under a mild technical condition, it is shown that the proposed heuristic achieves a strictly positive information acquisition rate with a strictly positive error exponent. Furthermore, in the special case of variable length coding over discrete memoryless channels with perfect feedback, EJS policy is shown to be 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.

Biography

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.