Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Noisy Search with Comparative Feedback
Shiau Lim, Peter Auer
We present theoretical results in terms of lower and upper bounds on the query complexity of noisy search with comparative feedback. In this search model, the noise in the feedback depends on the distance between query points and the search target. Consequently, the error probability in the feedback is not fixed but varies for the queries posed by the search algorithm. Our results show that a target out of n items can be found in O(log n) queries. We also show the surprising result that for k possible answers per query, the speedup is not log k (as for k-ary search) but only log log k in some cases.
Pages: 445-452
PS Link:
PDF Link: /papers/11/p445-lim.pdf
AUTHOR = "Shiau Lim and Peter Auer",
TITLE = "Noisy Search with Comparative Feedback",
BOOKTITLE = "Proceedings of the Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "445--452"

hosted by DSL   •   site info   •   help