Relative distance comparisons with confidence judgements

Relative distance comparisons, or ”triplets”, are statements of the form ”item a is closer to item b than c”. When eliciting such comparisons from human annotators, it is often the case that some comparisons are easy, while others are more ambiguous. However, also for the latter cases annotators are forced to choose one of the alternatives, despite possibly having a low confidence with their selection. To alleviate this problem, we discuss a variant of the distance comparison query where annotators are allowed to explicitly state their degree of confidence for each triplet. We propose algorithms both for learning the underlying pairwise distances, as well as computing an embedding of the items from such triplets. For the distance learning problem we devise an approach based on solving a system of linear equations, while for the embedding task we modify the t-STE algorithm to handle the confidence statements. We report experiments with synthetic and real data, including a novel study in which we collected the proposed type of triplets from 80 volunteers. keywords: human computation, distance estimation,