Achievable Resolution Limits for the Noisy Adaptive 20 Questions Problem
作者：周琳 时间：2021年07月14日 21:22 点击数：
语言：English
发表会议：2021 IEEE International Symposium on Information Theory (ISIT)
发表日期：2021年7月14日
摘要：
We study the achievable performance of adaptive query procedures for the noisy 20 questions problem with measurement-dependent noise over a unit cube of finite dimension. The performance criterion that we consider is the minimal resolution, defined as the
L
∞
norm between the estimated and the true values of the random location vector of a target, given a finite number of queries constrained by an excess-resolution probability. Specifically, we derive the achievable resolution of an adaptive query procedure based on the variable length feedback code by Polyanskiy et al. (TIT 2011). Furthermore, we verify our theoretical results with numerical simulations and compare the performance of our considered adaptive query procedure with that of certain state-of-the-art algorithms, such as the sorted posterior matching algorithm by Chiu and Javadi (ITW 2016). In particular, we demonstrate that the termination strategy adopted in our adaptive query procedure can significantly enhance the asymptotic performance of adaptive query procedures, especially at moderate to large excess-resolution probability constraints.
原文链接
