Twenty questions with noise: Bayes optimal policies for entropy loss

Jedynak, Bruno; Frazier, Peter; Sznitman, Raphael (2012). Twenty questions with noise: Bayes optimal policies for entropy loss. Journal of Applied Probability, 49(1), pp. 114-136. Applied Probability Trust

[img] Text
1331216837.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (1MB) | Request a copy

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.

Item Type:

Journal Article (Original Article)

Division/Institute:

10 Strategic Research Centers > ARTORG Center for Biomedical Engineering Research > ARTORG Center - AI in Medical Imaging Laboratory

UniBE Contributor:

Sznitman, Raphael

Subjects:

500 Science > 510 Mathematics

ISSN:

1475-6072

Publisher:

Applied Probability Trust

Language:

English

Submitter:

Raphael Sznitman

Date Deposited:

21 May 2015 13:30

Last Modified:

05 Dec 2022 14:47

BORIS DOI:

10.7892/boris.68809

URI:

https://boris.unibe.ch/id/eprint/68809

Actions (login required)

Edit item Edit item
Provide Feedback