NearOptimal Target Learning With Stochastic Binary Signals
Mithun Chakraborty, Sanmay Das, Malik MagdonIsmail
Abstract:
We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or greater than a threshold theta. At step t = 0, 1, 2, ..., the learner sets threshold theta t and observes a noisy realization of sign(V  theta t). After T steps, the goal is to output an estimate V^ which is within an etatolerance of V . This problem has been studied, predominantly in environments with a fixed error probability q < 1/2 for the noisy realization of sign(V  theta t). In practice, it is often the case that q can approach 1/2, especially as theta > V , and there is little known when this happens. We give a pseudoBayesian algorithm which provably converges to V. When the true prior matches our algorithm's Gaussian prior, we show nearoptimal expected performance. Our methods extend to the general multiplethreshold setting where the observation noisily indicates which of k >= 2 regions V belongs to.
Keywords:
Pages: 6976
PS Link:
PDF Link: /papers/11/p69chakraborty.pdf
BibTex:
@INPROCEEDINGS{Chakraborty11,
AUTHOR = "Mithun Chakraborty
and Sanmay Das and Malik MagdonIsmail",
TITLE = "NearOptimal Target Learning With Stochastic Binary Signals",
BOOKTITLE = "Proceedings of the TwentySeventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI11)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "6976"
}

