Abstract
We consider the problem of classification in a
comparison-based setting: given a set of objects,
we only have access to triplet comparisons of the
form “object A is closer to object B than to object
C.” In this paper we introduce TripletBoost, a new
method that can learn a classifier just from such
triplet comparisons. The main idea is to aggregate
the triplets information into weak classifiers, which
can subsequently be boosted to a strong classifier.
Our method has two main advantages: (i) it is applicable to data from any metric space, and (ii) it
can deal with large scale problems using only passively obtained and noisy triplets. We derive theoretical generalization guarantees and a lower bound
on the number of necessary triplets, and we empirically show that our method is both competitive with
state of the art approaches and resistant to noise