Near-Optimal Target Learning With Stochastic Binary Signals

Details Near-Optimal Target Learning With Stochastic Binary Signals Near-Optimal Target Learning With Stochastic Binary Signals

2012-02-14

arxiv.org/abs/1202.3704v1

Computer Science

Learning

Scientific paper

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 eta-tolerance 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 pseudo-Bayesian algorithm which provably converges to V. When the true prior matches our algorithm's Gaussian prior, we show near-optimal expected performance. Our methods extend to the general multiple-threshold setting where the observation noisily indicates which of k >= 2 regions V belongs to.

Affiliated with

Also associated with

No associations

Rating

Near-Optimal Target Learning With Stochastic Binary Signals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Near-Optimal Target Learning With Stochastic Binary Signals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Near-Optimal Target Learning With Stochastic Binary Signals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-90348