Comparison-Based Learning with Rank Nets

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 {\em 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.

Published in:
Proceedings of the 29th International Conference on Machine Learning (ICML)
Presented at:
29th International Conference on Machine Learning (ICML), Edinburgh, Scotland, June 26- July 1

 Record created 2012-10-14, last modified 2018-09-13

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)