COMPARISON-BASED ACTIVE SEARCHING/LEARNING

摘要

A method is provided for performing a content search through comparisons, where a user is presented with two candidate objects and reveals which is closer to the user's intended target object. The disclosed principles provide active strategies for finding the user's target with few comparisons. The so-called rank-net strategy for noiseless user feedback is described. For target distributions with a bounded doubling constant, rank-net finds the target in a number of steps close to the entropy of the target distribution and hence of the optimum. The case of noisy user feedback is also considered. In that context a variant of rank-nets is also described, for which performance bounds within a slowly growing function (doubly logarithmic) of the optimum are found. Numerical evaluations on movie datasets show that rank-net matches the search efficiency of generalized binary search while incurring a smaller computational cost.

主权项

1. A method for searching for a target within a data base, comprising:
constructing a net of nodes having a size that encompasses at least a target; choosing a set of nodes within the net; comparing a distance from a target to each node within the set of nodes; selecting a node, within the set of nodes, closest to the target in accordance with said comparing step; reducing the net to a size still encompassing the target in accordance with said selecting step; repeating said choosing, comparing, selecting, and reducing steps until the size of the net is small enough to encompass only the target.