Boosting for Comparison-Based Learning

2018/10/31 by Perrot, Michaël, von Luxburg, Ulrike
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1810.13333

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 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.

Related

• Classification from Triplet Comparison Data
• A theory of multiclass boosting
• A Direct Approach to Multi-class Boosting and Extensions
• Active Metric Learning from Relative Comparisons
• Batch Decorrelation for Active Metric Learning