TITLE: Size-dependent Noisy Search as a Problem of Information Acquisition

ABSTRACT:

Information acquisition problems form a class of stochastic decision problems in which a decision maker, by carefully controlling a sequence of actions with uncertain outcomes, dynamically refines the belief about a time-varying (Markov) parameter of interest. Examples arise in patient care, computer vision, spectrum utilization, and joint source--channel coding. In the first part of the talk, we consider this generalization of hidden Markov models (HMMs), the corresponding dynamic program, and provide some structural results. 

 In the second part of the talk, as a special case of information acquisition, we consider the problem of noisy search with size-dependent noise. We connect De Groot's "information utility" framework with the Shannon theoretic concept of "uncertainty reduction" to introduce a symmetrized divergence measure: Extrinsic Jensen-Shannon (EJS) divergence.  We use this divergence to provide (tight) lower and upper bounds on the optimal performance and  strengthen Chernoff's analysis to account for the resolution of the search. These bounds, as a corollary, provide the (asymptotic) performance gain of adaptive search strategies over the non-adaptive (open loop) and non-sequential ones.  This is joint work with Anusha Lalitha, Mohammad Naghshvar, Yonatan Kaspi, and Ofer Shayevitz. Bio: Tara Javidi studied electrical engineering at Sharif University of Technology, Tehran, Iran from 1992 to 1996. She received her 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.