Boosting for Comparison-Based Learning
This addresses the challenge of learning from comparison-based data, which is useful for domains where direct feature access is limited, but it appears incremental as it builds on existing boosting and triplet-based methods.
The paper tackles the problem of classification using only triplet comparisons (e.g., 'object x_i is closer to x_j than to x_k') by introducing TripletBoost, a method that aggregates triplets into weak classifiers and boosts them to a strong classifier, achieving competitive performance with state-of-the-art approaches and resistance to noise.
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.