Boosting for Comparison-Based Learning
  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 $x_i$ is closer to object $x_j$ than to object $x_k$." 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.
