Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem.

Hye Won Chung, Brian M. Sadler, Lizhong Zheng, Alfred O. Hero IiiIEEE Trans. Information Theory 2016 · DOI · OpenReview

TL;DR

This paper introduces a novel non-adaptive querying strategy for the "noisy 20 questions" problem, where the goal is to estimate a continuous variable by asking binary questions with noisy answers. Their method, based on superposition coding, achieves a significantly faster convergence rate for estimation error compared to previous non-adaptive approaches, matching the performance of adaptive strategies.

What Problem Does This Paper Address?

The "noisy 20 questions" problem involves a player trying to pinpoint a continuous target variable (like a number between 0 and 1) by asking a series of binary questions. The catch is that the answers received from an "oracle" are not perfect; they are transmitted through a noisy channel (a Binary Symmetric Channel, or BSC). The challenge is to design a sequence of questions that minimizes the error in estimating the target variable, especially when some parts of the variable's representation (like the most significant bits) are more critical than others. Traditional approaches either use adaptive strategies (where each question depends on previous answers, offering good performance but high complexity) or non-adaptive strategies (where all questions are pre-determined, simpler but often less efficient). This paper focuses on improving non-adaptive strategies by introducing "unequal error protection" (UEP), recognizing that errors in estimating certain bits of the target variable have a much larger impact on the overall estimation error.

Methods

The core of the paper's contribution lies in developing a new non-adaptive querying policy that leverages superposition coding. This technique, borrowed from information theory, allows for encoding multiple messages with different levels of error protection. In this context, the target variable's binary representation is split into "most significant bits" (MSBs) and "least significant bits" (LSBs). The superposition coding approach is designed to provide stronger error protection for the MSBs, which are more critical for accurate estimation. This is achieved by constructing codewords that have a specific geometric structure, effectively clustering codewords that share the same MSBs. The paper then analyzes the performance of this strategy by deriving bounds on the estimation error, specifically focusing on the quantized mean squared error (MSE) exponent. They compare their proposed method against existing non-adaptive strategies like UEP repetition coding and random block coding, as well as the adaptive bisection policy.

Datasets

Not discussed in the paper. The problem is theoretical and focuses on deriving performance bounds and exponents rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • UEP is Crucial for Estimation: Unlike traditional communication problems where equal error protection is often sufficient, estimating a continuous variable requires prioritizing certain bits (MSBs) over others. Errors in MSBs have a disproportionately larger impact on the final estimate.
  • Superposition Coding for UEP: Superposition coding provides a powerful framework to achieve UEP by creating a geometric structure in the codeword space that inherently protects certain parts of the message more than others.
  • Matching Adaptive Performance with Non-Adaptive Simplicity: The proposed non-adaptive superposition coding strategy achieves an exponential convergence rate for estimation error that matches that of adaptive policies, offering a compelling trade-off between performance and complexity.
  • Beyond Equal Error Protection: Random block coding, while providing a coding gain, treats all information bits equally. The paper demonstrates that this "equal protection" is suboptimal for estimation tasks where bit importance varies.

Key Results

The paper demonstrates that their proposed non-adaptive UEP querying policy based on superposition coding achieves a significantly better exponential rate of convergence for the estimation error compared to previous non-adaptive methods like UEP repetition coding. Crucially, this new policy matches the linear in N exponential rate of decrease in estimation error achieved by adaptive strategies, where N is the number of queries. This is a major improvement over UEP repetition coding, which only achieves a $\sqrt{N}$ rate. The paper also shows that their method provides a better scale factor in the MSE exponent than random block codes.

Limitations and Future Work

The paper acknowledges that while their proposed policy matches the order of convergence of adaptive strategies, the exact constants in the error exponents might differ. Future work suggested includes:

  • Generalizing UEP: Extending the UEP querying policy to provide more than two levels of error protection, allowing for finer-grained prioritization of information bits based on their significance.
  • Diverse Channel Models and Distributions: Applying the UEP querying concept to more general channel models beyond the BSC and to target variable distributions that are not uniform.
  • Developing More Efficient Decoding: Investigating more advanced decoding algorithms for superposition codes, especially as the number of error protection levels increases, to overcome potential performance degradation from error propagation.

Summary updated

Abstract

In this paper, we propose an open-loop unequal-error-protection querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the output of a binary symmetric channel the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (UEP). A new non-adaptive querying strategy based on UEP superposition coding is introduced whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). With the proposed querying strategy, the rate of exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme where queries are sequentially designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block codes employing equal error protection.
BibTeX
@article{chung2016unequal,
  author = {Hye Won Chung and Brian M. Sadler and Lizhong Zheng and Alfred O. Hero III},
  title = {{Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem.}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  doi = {10.1109/tit.2017.2760634},
}
Figure