Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem
© 2017 IEEE. 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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134668 |
| _version_ | 1826188227522854912 |
|---|---|
| author | Chung, Hye Won Sadler, Brian M Zheng, Lizhong Hero, Alfred O |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Chung, Hye Won Sadler, Brian M Zheng, Lizhong Hero, Alfred O |
| author_sort | Chung, Hye Won |
| collection | MIT |
| description | © 2017 IEEE. 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. |
| first_indexed | 2024-09-23T07:56:29Z |
| format | Article |
| id | mit-1721.1/134668 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T07:56:29Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1346682023-12-22T21:14:41Z Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem Chung, Hye Won Sadler, Brian M Zheng, Lizhong Hero, Alfred O Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2017 IEEE. 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. 2021-10-27T20:06:06Z 2021-10-27T20:06:06Z 2018 2019-07-08T18:20:10Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134668 Hye Won, Chung, et al. "Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem [Arxiv]." arXiv (2016): 43 pp. en 10.1109/TIT.2017.2760634 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Chung, Hye Won Sadler, Brian M Zheng, Lizhong Hero, Alfred O Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem |
| title | Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem |
| title_full | Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem |
| title_fullStr | Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem |
| title_full_unstemmed | Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem |
| title_short | Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem |
| title_sort | unequal error protection querying policies for the noisy 20 questions problem |
| url | https://hdl.handle.net/1721.1/134668 |
| work_keys_str_mv | AT chunghyewon unequalerrorprotectionqueryingpoliciesforthenoisy20questionsproblem AT sadlerbrianm unequalerrorprotectionqueryingpoliciesforthenoisy20questionsproblem AT zhenglizhong unequalerrorprotectionqueryingpoliciesforthenoisy20questionsproblem AT heroalfredo unequalerrorprotectionqueryingpoliciesforthenoisy20questionsproblem |