Extrinsic Jensen-Shannon divergence and noisy Bayesian active learning

Consider the problem of noisy Bayesian active learning given a sample space, a finite label set, and a finite set of label generating functions from the sample space to the label set, also known as the function class. The objective is to identify the function in the function class that generates the labels using as few label queries as possible and with low probability of error despite possible corruption by independent noise. The key to achieving this objective relies on the selection of queries in a strategic and adaptive manner. The problem generalizes the problem of noisy generalized binary search [1]. Utilizing the connection between the above Bayesian active learning problem and the problem of active hypothesis testing, a heuristic based on Extrinsic Jensen-Shannon divergence [2] is analyzed and general upper bounds are obtained. The performance of this heuristic is compared with the state of the art strategies for noisy generalized binary search. In the case where the function class is of threshold nature, it is shown that this heuristic is better than previous results and, in particular, is order optimal.