Bayesian Multiple Target Localization

Purnima Rajan, Weidong Han, Raphael Sznitman, Peter Frazier, Bruno Jedynak
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1945-1953, 2015.

Abstract

We consider the problem of quickly localizing multiple targets by asking questions of the form “How many targets are within this set" while obtaining noisy answers. This setting is a generalization to multiple targets of the game of 20 questions in which only a single target is queried. We assume that the targets are points on the real line, or in a two dimensional plane for the experiments, drawn independently from a known distribution. We evaluate the performance of a policy using the expected entropy of the posterior distribution after a fixed number of questions with noisy answers. We derive a lower bound for the value of this problem and study a specific policy, named the dyadic policy. We show that this policy achieves a value which is no more than twice this lower bound when answers are noise-free, and show a more general constant factor approximation guarantee for the noisy setting. We present an empirical evaluation of this policy on simulated data for the problem of detecting multiple instances of the same object in an image. Finally, we present experiments on localizing multiple faces simultaneously on real images.

Cite this Paper


BibTeX
@InProceedings{pmlr-v37-rajan15, title = {Bayesian Multiple Target Localization}, author = {Rajan, Purnima and Han, Weidong and Sznitman, Raphael and Frazier, Peter and Jedynak, Bruno}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1945--1953}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/rajan15.pdf}, url = {https://proceedings.mlr.press/v37/rajan15.html}, abstract = {We consider the problem of quickly localizing multiple targets by asking questions of the form “How many targets are within this set" while obtaining noisy answers. This setting is a generalization to multiple targets of the game of 20 questions in which only a single target is queried. We assume that the targets are points on the real line, or in a two dimensional plane for the experiments, drawn independently from a known distribution. We evaluate the performance of a policy using the expected entropy of the posterior distribution after a fixed number of questions with noisy answers. We derive a lower bound for the value of this problem and study a specific policy, named the dyadic policy. We show that this policy achieves a value which is no more than twice this lower bound when answers are noise-free, and show a more general constant factor approximation guarantee for the noisy setting. We present an empirical evaluation of this policy on simulated data for the problem of detecting multiple instances of the same object in an image. Finally, we present experiments on localizing multiple faces simultaneously on real images.} }
Endnote
%0 Conference Paper %T Bayesian Multiple Target Localization %A Purnima Rajan %A Weidong Han %A Raphael Sznitman %A Peter Frazier %A Bruno Jedynak %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-rajan15 %I PMLR %P 1945--1953 %U https://proceedings.mlr.press/v37/rajan15.html %V 37 %X We consider the problem of quickly localizing multiple targets by asking questions of the form “How many targets are within this set" while obtaining noisy answers. This setting is a generalization to multiple targets of the game of 20 questions in which only a single target is queried. We assume that the targets are points on the real line, or in a two dimensional plane for the experiments, drawn independently from a known distribution. We evaluate the performance of a policy using the expected entropy of the posterior distribution after a fixed number of questions with noisy answers. We derive a lower bound for the value of this problem and study a specific policy, named the dyadic policy. We show that this policy achieves a value which is no more than twice this lower bound when answers are noise-free, and show a more general constant factor approximation guarantee for the noisy setting. We present an empirical evaluation of this policy on simulated data for the problem of detecting multiple instances of the same object in an image. Finally, we present experiments on localizing multiple faces simultaneously on real images.
RIS
TY - CPAPER TI - Bayesian Multiple Target Localization AU - Purnima Rajan AU - Weidong Han AU - Raphael Sznitman AU - Peter Frazier AU - Bruno Jedynak BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-rajan15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1945 EP - 1953 L1 - http://proceedings.mlr.press/v37/rajan15.pdf UR - https://proceedings.mlr.press/v37/rajan15.html AB - We consider the problem of quickly localizing multiple targets by asking questions of the form “How many targets are within this set" while obtaining noisy answers. This setting is a generalization to multiple targets of the game of 20 questions in which only a single target is queried. We assume that the targets are points on the real line, or in a two dimensional plane for the experiments, drawn independently from a known distribution. We evaluate the performance of a policy using the expected entropy of the posterior distribution after a fixed number of questions with noisy answers. We derive a lower bound for the value of this problem and study a specific policy, named the dyadic policy. We show that this policy achieves a value which is no more than twice this lower bound when answers are noise-free, and show a more general constant factor approximation guarantee for the noisy setting. We present an empirical evaluation of this policy on simulated data for the problem of detecting multiple instances of the same object in an image. Finally, we present experiments on localizing multiple faces simultaneously on real images. ER -
APA
Rajan, P., Han, W., Sznitman, R., Frazier, P. & Jedynak, B.. (2015). Bayesian Multiple Target Localization. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1945-1953 Available from https://proceedings.mlr.press/v37/rajan15.html.

Related Material