{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T04:11:06Z","timestamp":1682568666222},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Appl. Probab."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p>We consider the problem of twenty questions with noisy answers, in which we seek to find a target by repeatedly choosing a set, asking an oracle whether the target lies in this set, and obtaining an answer corrupted by noise. Starting with a prior distribution on the target's location, we seek to minimize the expected entropy of the posterior distribution. We formulate this problem as a dynamic program and show that any policy optimizing the one-step expected reduction in entropy is also optimal over the full horizon. Two such Bayes optimal policies are presented: one generalizes the probabilistic bisection policy due to Horstein and the other asks a deterministic set of questions. We study the structural properties of the latter, and illustrate its use in a computer vision application.<\/jats:p>","DOI":"10.1017\/s0021900200008895","type":"journal-article","created":{"date-parts":[[2016,3,29]],"date-time":"2016-03-29T14:50:28Z","timestamp":1459263028000},"page":"114-136","source":"Crossref","is-referenced-by-count":1,"title":["Twenty Questions with Noise: Bayes Optimal Policies for Entropy Loss"],"prefix":"10.1017","volume":"49","author":[{"given":"Bruno","family":"Jedynak","sequence":"first","affiliation":[]},{"given":"Peter I.","family":"Frazier","sequence":"additional","affiliation":[]},{"given":"Raphael","family":"Sznitman","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,2,4]]},"reference":[{"key":"S0021900200008895_ref33","first-page":"287","volume-title":"A Celebration of Applied Probability","volume":"25A","year":"1988"},{"key":"S0021900200008895_ref20","first-page":"1366","volume":"22","year":"2009","journal-title":"Adv. Neural Inf. Processing Systems"},{"key":"S0021900200008895_ref31","volume-title":"Proc. 2011 Winter Simulation Conference","year":"2011"},{"key":"S0021900200008895_ref30","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000013087.49260.fb"},{"key":"S0021900200008895_ref18","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000029664.99615.94"},{"key":"S0021900200008895_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.144"},{"key":"S0021900200008895_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"S0021900200008895_ref15","volume-title":"Stochastic Approximation and Recursive Algorithms and Applications","year":"2003"},{"key":"S0021900200008895_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/070693424"},{"key":"S0021900200008895_ref14","first-page":"881","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms","year":"2007"},{"key":"S0021900200008895_ref8","volume-title":"Controlled Markov Processes","year":"1979"},{"key":"S0021900200008895_ref13","first-page":"136","volume":"9","year":"2002","journal-title":"IEEE Trans. Inf. Theory"},{"key":"S0021900200008895_ref7","volume-title":"Optimal Statistical Decisions","year":"1970"},{"key":"S0021900200008895_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1963.1057832"},{"key":"S0021900200008895_ref6","volume-title":"Elements of Information Theory","year":"1991"},{"key":"S0021900200008895_ref11","volume-title":"Multi-Armed Bandit Allocation Indices","year":"1989"},{"key":"S0021900200008895_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49819-5_8"},{"key":"S0021900200008895_ref10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/34.476006","volume":"18","year":"1996","journal-title":"IEEE Trans. Pattern Anal. Machine Intelligence"},{"key":"S0021900200008895_ref4","first-page":"51","volume":"10","year":"1974","journal-title":"Problemy Peredachi Informatsii"},{"key":"S0021900200008895_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728659"},{"key":"S0021900200008895_ref2","volume-title":"Bandit Problems","year":"1985"},{"key":"S0021900200008895_ref1","first-page":"221","volume-title":"2008 49th Ann. IEEE Symp. Foundations of Computer Science","year":"2008"},{"key":"S0021900200008895_ref28","volume-title":"The Nature of Statistical Learning Theory","year":"1995"},{"key":"S0021900200008895_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.106"},{"key":"S0021900200008895_ref26","first-page":"197","volume":"5","year":"1990","journal-title":"Machine Learning"},{"key":"S0021900200008895_ref24","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"S0021900200008895_ref23","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1952-09620-8"},{"key":"S0021900200008895_ref22","first-page":"937","volume":"51","year":"1990","journal-title":"Automat. Remote Control"},{"key":"S0021900200008895_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00303-6"},{"key":"S0021900200008895_ref32","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994469"}],"container-title":["Journal of Applied Probability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0021900200008895","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T06:37:16Z","timestamp":1682491036000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0021900200008895\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":30,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["S0021900200008895"],"URL":"https:\/\/doi.org\/10.1017\/s0021900200008895","relation":{},"ISSN":["0021-9002","1475-6072"],"issn-type":[{"value":"0021-9002","type":"print"},{"value":"1475-6072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}