Comparison Based Learning from Weak Oracles
  There is increasing interest in learning algorithms that involve interaction
between human and machine. Comparison-based queries are among the most natural
ways to get feedback from humans. A challenge in designing comparison-based
interactive learning algorithms is coping with noisy answers. The most common
fix is to submit a query several times, but this is not applicable in many
situations due to its prohibitive cost and due to the unrealistic assumption of
independent noise in different repetitions of the same query.
  In this paper, we introduce a new weak oracle model, where a non-malicious
user responds to a pairwise comparison query only when she is quite sure about
the answer. This model is able to mimic the behavior of a human in noise-prone
regions. We also consider the application of this weak oracle model to the
problem of content search (a variant of the nearest neighbor search problem)
through comparisons. More specifically, we aim at devising efficient algorithms
to locate a target object in a database equipped with a dissimilarity metric
via invocation of the weak comparison oracle. We propose two algorithms termed
WORCS-I and WORCS-II (Weak-Oracle Comparison-based Search), which provably
locate the target object in a number of comparisons close to the entropy of the
target distribution. While WORCS-I provides better theoretical guarantees,
WORCS-II is applicable to more technically challenging scenarios where the
algorithm has limited access to the ranking dissimilarity between objects. A
series of experiments validate the performance of our proposed algorithms.
