Comparison-Based Learning with Rank Nets
This addresses efficient target search in comparison-based systems, which is incremental over prior work.
The paper tackles the problem of search through comparisons where users select which of two objects is closer to their target, proposing a rank nets strategy that finds targets in comparisons close to the entropy of the target distribution for distributions with bounded doubling constants, achieving near-optimal performance.
We consider the problem of search through comparisons, where a user is presented with two candidate objects and reveals which is closer to her intended target. We study adaptive strategies for finding the target, that require knowledge of rank relationships but not actual distances between objects. We propose a new strategy based on rank nets, and show that for target distributions with a bounded doubling constant, it finds the target in a number of comparisons close to the entropy of the target distribution and, hence, of the optimum. We extend these results to the case of noisy oracles, and compare this strategy to prior art over multiple datasets.