Comparison Based Learning from Weak Oracles.

There is increasing interest in learning algorithms that involve interactionbetween human and machine. Comparison-based queries are among the most naturalways to get feedback from humans. A challenge in designing comparison-basedinteractive learning algorithms is coping with noisy answers. The most commonfix is to submit a query several times, but this is not applicable in manysituations due to its prohibitive cost and due to the unrealistic assumption ofindependent noise in different repetitions of the same query.

In this paper, we introduce a new weak oracle model, where a non-malicioususer responds to a pairwise comparison query only when she is quite sure aboutthe answer. This model is able to mimic the behavior of a human in noise-proneregions. We also consider the application of this weak oracle model to theproblem of content search (a variant of the nearest neighbor search problem)through comparisons. More specifically, we aim at devising efficient algorithmsto locate a target object in a database equipped with a dissimilarity metricvia invocation of the weak comparison oracle. We propose two algorithms termedWORCS-I and WORCS-II (Weak-Oracle Comparison-based Search), which provablylocate the target object in a number of comparisons close to the entropy of thetarget distribution. While WORCS-I provides better theoretical guarantees,WORCS-II is applicable to more technically challenging scenarios where thealgorithm has limited access to the ranking dissimilarity between objects. Aseries of experiments validate the performance of our proposed algorithms.