Twenty questions game is the following basic problem: An oracle chooses an object from a finite set, and a player tries to guess the chosen object by posing a sequence of queries that can be answered by a simple yes or no, while the goal is to minimize the expected number of queries. By designing queries so as to extract as much information as possible at each trial, we can minimize the expected number of queries. This is a fundamental problem that arises in active learning, object identification, disease diagnosis, and other areas. In this talk, we consider a generalization of this game to estimate a continuous random variable with noisy answers. When the answers are corrupted by noise, the optimum querying strategy is not anymore the one just extracting the maximum information, since the reliability of the collected information should also be encounterd. Under this new scenario, we highlight the difference between adaptive and non-adaptive strategies and discuss many aspects in designing the optimal queries, including the proper information surrogates for the true cost function and the design of channel codes for unequal error protection.
Hye Won Chung is currently a postdoctoral research fellow at the Dept. of Electrical Engineering and Computer Science at the University of Michigan. Her research interests are at the interface of information theory, statistical estimation, and quantum information theory. She received the B.S. degree (with summa cum laude) from KAIST, Korea, and the S.M. and Ph.D. degrees from MIT, all in Electrical Engineering and Computer Science, in 2007, 2009 and 2014, respectively. She has received several fellowships and awards including the Kwanjeong Educational Foundation fellowship.