(September 2) Designing Twenty Questions Querying for Estimation : Information Surrogates, Unequal Error Protection

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.