Boosting for Comparison-Based Learning

1 Introduction

In the past few years the problem of comparison-based learning has attracted growing interest in the machine learning community [Agarwal et al., 2007, Jamieson and Nowak, 2011, Tamuz et al., 2011, Tschopp et al., 2011, Van Der Maaten and Weinberger, 2012, Heikinheimo and Ukkonen, 2013, Amid and Ukkonen, 2015, Kleindessner and Luxburg, 2015, Jain et al., 2016, Haghiri et al., 2017, Kazemi et al., 2018]. The motivation is to relax the assumption that an explicit representation of the objects or a distance metric between pairs of examples are available. Instead one only has access to a set of ordinal distance comparisons that can take several forms depending on the problem at hand. In this paper we focus on triplet comparisons of the form object xi is closer to object xj than to object xk, that is on relations of the form d(xi, xj ) < d(xi, xk) where d is an unknown metric 1 .

We address the problem of classification with noisy triplets that have been obtained in a passive manner: the examples lie in an unknown metric space, not necessarily Euclidean, and we are only given a small set of triplet comparisons - there is no way in which we could actively ask for more triplets. Furthermore we assume that the answers to the triplet comparisons can be noisy. To deal with this problem one can try to first recover an explicit representation of the examples, a task that can be solved by ordinal embedding approaches [Agarwal et al., 2007, Van Der Maaten and Weinberger, 2012, Terada and von Luxburg, 2014, Jain et al., 2016], and then apply standard machine learning approaches. However, such embedding methods assume that the examples lie in a Euclidean space and do not scale well with the number of examples: typically they are too slow for datasets with more than 103 examples. As an alternative, it would be desirable to have a classification algorithm that can work with triplets directly, without taking a detour via ordinal embedding. To the best of our knowledge, for the case of passively obtained triplets, this problem has not yet been solved in the literature.

1 Note that this kind of ordinal information is sometimes just used as side information [Bellet et al., 2015, Kane et al., 2017], but, as the references in the main text, we focus on the setting where ordinal comparisons are the sole information available.

Another interesting question in this context is that of the minimal number of triplets required to successfully learn a classifier. It is known that to exactly recover an ordinal embedding one needs of the order Ω(n3 ) passively queried triplets in the worst case (essentially all of them), unless we make stronger assumptions on the underlying metric space [Jamieson and Nowak, 2011]. However, classification is a problem which seems simpler than ordinal embedding, and thus it might be possible to obtain better lower bounds.

In this paper we propose TripletBoost, a method for classification that is able to learn using only passively obtained triplets while not making any assumptions on the underlying metric space. To the best of our knowledge this is the first approach that is able to solve this problem. Our method is based on the idea that the triplets can be aggregated into simple triplet classifiers, which behave like decision stumps and are well-suited for boosting approaches [Schapire and Freund, 2012]. From a theoretical point of view we prove that our approach learns a classifier with low training error, and we derive generalization guarantees that ensure that its error on new examples is bounded. Furthermore we derive a new lower bound on the number of triplets that are necessary to ensure useful predictions. From an empirical point of view we demonstrate that our approach can be applied to datasets that are several order of magnitudes larger than the ones that can currently be handled by ordinal embedding methods. Furthermore we show that our method is quite resistant to noise.

2 The TripletBoost Algorithm

In this paper we are interested in multi-class classification problems. Let (X, d) be an unknown and general metric space, typically not Euclidean. Let Y be a finite label space. Let S = {(xi, yi)}ni=1 be a set of n examples drawn i.i.d. from an unknown distribution DS defined over X × Y. Note that we use the notation xi as a convenient way to identify an object; it does not correspond to any explicit representation that could be used by an algorithm (such as coordinates in a vector space). Let T = {(xi, xj, xk) : (xi, yi), (xj, yj), (xk, yk) ∈ S, xj ̸= xk} be a set of m triplets. Each ordered tuple (xi, xj , xk) ∈ T encodes the following relation between the three examples:

Given the triplets in T and the label information of all points, our goal is to learn a classifier. We make two main assumptions about the data. First, we assume that the triplets are uniformly and independently sampled from the set of all possible triplets. Second, we assume that the triplets in T can be noisy (that is the inequality has been swapped, for example (xi, xk, xj) ∈ T while the true relation is d(xi, xj) < d(xi, xk)), but the noise is uniform and independent from one triplet to another. In the following Ia denotes the indicator function returning 1 when a property a is verified and 0 otherwise, Wc is an empirical distribution over S × Y, and wc,xi,y is the weight associated to object xi and label y.

2.1 Weak Triplet Classifiers

Rather than considering triplets as individual pieces of information we propose to aggregate them into decision stumps that we call triplet classifiers. The underlying idea is to select two reference examples, xj and xk, and to divide the space into two half-spaces: examples that are closer to xj and examples that are closer to xk. This is illustrated in Figure 1. In principle, this can be achieved with triplets only. However, a major difficulty in our setting is that our triplets are passively obtained: for most training points xi we do not know whether they are closer to xj or xk. In particular, it is impossible to evaluate the classification accuracy of such a simple classifier on the whole training set. To deal with this problem we propose to use an abstention scheme where a triplet classifier Algorithm 1 TripletBoost: boosting with triplet classifiers

Input: S = {(xi, yi)}ni=1 a set of n examples,

T = {(xi, xj , xk) : xj ̸= xk} a set of m triplets.

Output: H(·) a strong classifier.

• 1: Let W1 be the empirical uniform distribution: ∀(xi, yi) ∈ S, ∀y ∈ Y,w1,xi,y = 1 n|Y| .
• 2: for c = 1, . . . ,C do
• 3: Choose a triplet classifier hc according to Wc (Equation (2)).
• 4: Compute the weight αc of hc according to its performance onWc (Equation (3)).
• 5: Update the weights of the examples to obtain a new distributionWc+1 (Equation (4)).
• 6: end for

abstains if it does not know on which side of the hyperplane the considered point lies. Given a set T of triplets and two reference points xj and xk, we define a triplet classifier as:

In our multi-class setting, oj and ok will be sets of labels, that is oj , ok ⊆ Y. In Section 2.2 we describe how we choose them in a data dependent fashion to obtain classifiers with minimal error on the training set. The prediction ϑ simply means that the triplet classifier abstains on the example. Let H denote the set of all possible triplet classifiers.

The triplet classifiers are very simple and, in practice, we do not expect them to perform well at all. But we prove in Section 3.1 that, for appropriate choices of oj and ok, they are at least as good as random predictors. This is all we need to ensure that they can be used successfully in a boosting framework. The next section describes how this works.

2.2 TripletBoost

Boosting is based on the insight that weak classifiers (that is classifiers marginally better than random predictors) are usually easy to obtain and can be combined in a weighted linear combination to obtain a strong classifier. This weighted combination can be obtained in an iterative fashion where, at each iteration, a weak-classifier is chosen and weighted so as to minimize the error on the training examples. The weights of the points are then updated to put more focus on hard-to-classify examples [Schapire and Freund, 2012]. In this paper we use a well-known boosting algorithm called AdaBoost.MO [Schapire and Singer, 1999, Schapire and Freund, 2012]. This method can handle multi-class problems with a one-against-all approach, works with abstaining classifiers and is theoretically well founded. Algorithm 1 summarizes the main steps of our approach that we detail below.

Choosing a triplet classifier. To choose a triplet classifier we proceed in two steps. In the first step, we select two reference points xj and xk such that yj ̸= yk. This is done by randomly sampling from an empirical distribution Wc,X on the examples. Here Wc,X denotes the marginal distribution of Wc with respect to the examples. This distribution is updated at each iteration to put more focus on those parts of the space that are hard to classify while promoting triplet classifiers that are able to separate different classes (see Equation 4).

Choosing the predicted labels. In the second step, we choose oj and ok, the sets of labels that should be predicted for each half space of the triplet classifier. Given one of the half spaces, we propose to add a label to the set of predicted labels if the weight of examples of this class is greater than the weight of examples of different classes. Formally, with wc,xi,y defined as in Algorithm 1, we construct oj as follows:

We construct ok in a similar way. The underlying idea is that adding hc to the current combination of triplet classifiers should improve the predictions on the training set as much as possible. In Section 3.1 we show that this strategy is optimal and that it ensures that the selected triplet classifier is either a weak classifier or has a weight αc of 0.

Computing the weight of the triplet classifier. To choose the weight of the triplet classifier hc we start by computing Wc,+ and Wc,-, the weights of correctly and incorrectly classified examples:

We then set αc = log ( Wc,++ 1n Wc,-+ 1n )/2. The term 1n is a smoothing constant [Schapire and Singer, 2000]: in our setting with few, passively queried triplets it helps to avoid numerical problems that might arise when Wc,+ or Wc,- = 0. In Theorem 2 we show that this choice of αc leads to a decrease in training error as the number of iterations increases.

Updating the weights of the examples. In each iteration of our algorithm, a new triplet classifier hc is added to the weighted combination of classifiers, and we need to update the empirical distribution Wc over the examples for the next iteration. The idea is (i) to reduce the weights of correctly classified examples, (ii) to keep constant the weights of the examples for which the current triplet classifier abstains, and (iii) to increase the weights of incorrectly classified examples. The weights are then normalized by a factor Zc so that Wc+1 remains an empirical distribution over the examples. Formally, ∀(xi, yi) ∈ S, ∀y ∈ Y, if hc(xi) = ϑ then wc+1,xi,y = wc,xi,y Zc and if hc(xi) ̸= ϑ then

Using H for prediction. Given a new example x, TripletBoost predicts its label as

that is the label with the highest weight as predicted by the weighted combination of selected triplet classifiers. However, recall that we are in a passive setting, and thus we assume that we are given a set of triplets Tx = {(x, xj, xk) : (xj, yj), (xk, yk) ∈ S, xj ̸= xk} associated with the example x (but there is no way to choose them). Hence, some of the triplets in Tx correspond to triplet classifiers in H (that is (x, xj, xk) ∈ Tx and the reference points for hc were xj and xk) and some do not. In particular, it might happen that none of the triplets in Tx corresponds to a triplet classifier in H and, in this case, H can only randomly predict a label. In Section 3.3 we provide a lower bound on the number of triplets necessary to avoid this behaviour. The main computational bottleneck when predicting the label of a new example x is to check whether the triplets in Tx match a triplet classifier in H. A naive implementation would compare each triplet in Tx to each triplet classifier, which can be as expensive as O(|Tx|C). Fortunately, by first sorting the triplets and the triplet classifiers, a far more reasonable complexity of O(|Tx| log(|Tx|) + C log(C)) can be achieved.

3 Theoretical Analysis

In this section we show that our approach is theoretically well founded. First we prove that the triplet classifiers with nonzero weights are weak learners: they are slightly better than random predictors (Theorem 1). Building upon this result we show that, as the number of iterations increases, the training error of the strong classifier learned by TripletBoost is decreased (Theorem 2). Then, to ensure that TripletBoost does not over-fit, we derive a generalization bound showing that, given a sufficient amount of training examples, the test error is bounded (Theorem 3). Finally, we derive a lower bound on the number of triplets necessary to ensure that TripletBoost does not learn a random predictor (Theorem 4).

3.1 Triplet Classifiers andWeak Learners

We start this theoretical analysis by showing that the strategy to choose the predicted labels of triplet classifiers described in Equation (2) is optimal: it ensures that their error is minimal on the training set (compared to any other labelling strategy). We also show that the triplet classifiers are never worse than random predictors and in fact, that only those triplets classifiers that are weak classifiers (strictly better than random classifiers) are affected a non-zero weight. This is summarized in the next theorem.

Theorem 1 (Triplet classifiers and weak learners). Let Wc be an empirical distribution over S × Y and hc be the corresponding triplet classifier chosen as described in Section 2.2. It holds that:

1. the error of hc on Wc is at most the error of a random predictor and is minimal compared to other labelling strategies,

1. the weight αc of the classifier is non-zero if and only if, hc is a weak classifier, that is is strictly better than a random predictor.

Proof. Given in Perrot and von Luxburg [2018].

3.2 Boosting Guarantees

From a theoretical point of view the boosting framework has been extensively investigated and it has been shown that most AdaBoost-based methods decrease the training error at each iteration [Freund and Schapire, 1997]. Another question that has attracted a lot of attention is the problem of generalization. It is known that when the training error has been minimized, AdaBoost-based methods often do not over-fit and it might even be beneficial to further increase the number of weak learners. A popular explanation is the margin theory which says that as the number of iterations increases, the confidence of the algorithm in its predictions increases and thus, the test accuracy is improved [Schapire et al., 1998, Breiman, 1999, Wang et al., 2011, Gao and Zhou, 2013]. TripletBoost is based on AdaBoost.MO [Schapire and Freund, 2012], and thus it inherits the theoretical guarantees presented above. In this section, we provide two theorems which show that (i) TripletBoost reduces the training error as the number of iterations increases, and (ii) it generalizes well to new examples.

The following theorem shows that, as the number of iterations increases, TripletBoost decreases the training error.

Theorem 2 (Reduction of the training error). Let S be a set of n examples and T be a set of m triplets (obtained as described in Section 2). Let H(·) be the classifier obtained after C iterations of TripletBoost (Algorithm 1) using S and T as input. It holds that:

Proof. This result, inherited from AdaBoost.MO, is proven in Perrot and von Luxburg [2018].

The next theorem shows that the true error of a classifier learned by TripletBoost can be bounded by a quantity related to the confidence of the classifier on the training examples, with respect to a margin, plus a term which decreases as the number of examples increases. The confidence of the classifier on the training examples is also bounded and decreases for sufficiently small margins.

Theorem 3 (Generalization guarantees). Let DS be a distribution over X × Y, let S be a set of n examples drawn i.i.d. from DS, and let T be a set of m triplets (obtained as described in Section 2). Let H(·) be the classifier obtained after C iterations of TripletBoost (Algorithm 1) using S and T as input. Let H be a set of triplet classifiers as defined in Section 2.1. Then, given a margin parameter θ > √ log |H| 16|Y|2 n and a measure of the confidence of H(·) in its predictions θH(x, y), with probability at least 1 - δ, we have that

Furthermore we have that

Proof. This result, inherited from AdaBoost.MO, is proven in Perrot and von Luxburg [2018].

At a first glance it seems that this bound does not depend on m, the number of available triplets. However, this dependency is implicit: m impacts the probability that the training examples are well classified with a large margin θ. If the number of triplets is small, the probability that the training examples are well classified with a given margin is small. This probability increases when the number of triplets increases (as illustrated in Perrot and von Luxburg [2018]).

To prove a bound that explicitly depends on m would be of significant interest. However this is a difficult problem, as it requires to use an explicit measure of complexity for general metric spaces, which is beyond the scope of this paper.

3.3 Lower Bound on the Number of Triplets

In this section we investigate the minimum number of triplets that are necessary to ensure that our algorithm performs well. Ideally, we would like to obtain a lower bound on the number of triplets that are necessary to achieve a given accuracy. In this paper we take a first step in this direction by deriving a bound on the number of triplets that are necessary to ensure that the learned classifier does not abstain on any unseen example. Theorems 4 and 5 show that it abstains with high probability if it is learned using too few triplets or if it combines too few triplet classifiers.

Theorem 4 (Lower bound on the probability that a strong classifier abstains). Let n ≥ 2 be the number of training examples, p = 2nk n3 with k ∈ [0, 3- log(2) log(n) ) be the probability that a triplet is available in the triplet set T and C = nβ 2 with β ∈ [0, 1 + log (n-1) log (n) ] be the number of classifiers combined in the learned classifier. Let A be any algorithm learning a classifier H(·) = arg maxy∈Y (∑Cc=1 αcIy∈hc(·)) that combines several triplet classifiers using some weights αc ∈ R. Assume that triplet classifiers that abstain on all the training examples have a weight of 0 (that is if hc(xi) = ϑ for all the examples (xi, yi) ∈ S then αc = 0). Then the probability that H abstains on a test example is bounded as follows:

Proof. Given in Perrot and von Luxburg [2018].

• (a) Moons, Metric: Euclidean, Noise Level: 0%

(b) Moons, Metric: Euclidean, Proportion of Triplets: 10%

(c) Iris, Proportion of Triplets: 10%, Noise Level: 0%

Figure 2: Moons is a small scale dataset with 500 examples and 2 dimensions. We fix the triplets metric to the Euclidean distance. In Figure 2a we consider the noise free setting and we vary the proportion of available triplets from 1 to 10% of all the triplets. In Figure 2b we fix this proportion to 10% and we vary the noise level from 0 to 20%. Iris is a small scale dataset with 150 examples and 4 dimensions. In Figure 2c we fix the proportion of available triplets to 10%, the noise level to 0% and we vary the metric considered to generate the triplets.

To understand the implications of this theorem we consider a concrete example.

Example 1. Assume that we build a linear combination of all possible triplet classifiers, that is C = n(n-1) 2 . Then we have

where k is the parameter that controls the probability p that a particular triplet is available in the triplets set T . The bottom line is that when k < 3 2 , that is when we do not have at least Ω(n√n) random triplets, the learned classifier abstains on all the examples.

Theorem 4 shows that when p and C are too small, then the strong classifier abstains with high probability. However, the theorem does not guarantee that the strong classifier does not abstain when p and C are large. The next theorem takes care of this other direction under slightly stronger assumptions on the weights learned by the algorithm.

Theorem 5 (Exact bound on the probability that a strong classifier abstains). In Theorem 4, further assume that each triplet classifier that does not abstain on at least one training example has a weight different from 0 (if for at least one example (xi, yi) ∈ S we have that hc(xi) ̸= ϑ then αc ̸= 0). Then equality holds in Equation (6).

Theorem 5 implies that equality holds in Example 1, thus when C = n(n-1) 2 we need at least k > 32 , that is at least Ω(n√n) random triplets, to obtain a classifier that never abstains. In Perrot and von Luxburg [2018] we extend Example 1 and we study the limit as n → ∞ for general values of C and p. We also provide a graphical illustration of the bound and a discussion on how this lower bound compares to existing results [Ailon, 2012, Jamieson and Nowak, 2011, Jain et al., 2016].

4 Experiments

We propose an empirical evaluation of TripletBoost. We consider six datasets of varying scales and four baselines.

Baselines. First, we consider an embedding approach. We use tSTE [Van Der Maaten and Weinberger, 2012] to embed the triplets in a Euclidean space and we use the 1-nearest neighbour algorithm for classification. We also would like to compare to alternative approaches able to learn directly from triplets (without embedding as a first step). However, to the best of our knowledge, TripletBoost is the only method able to do classification using only passively obtained triplets. The only option is to choose competing methods that have access to more information (providing them an unfair advantage). We settled for a method that uses actively chosen triplets to build a comparison-tree to retrieve nearest neighbours (CompTree) [Haghiri et al., 2017]. Finally, to put the results obtained in the triplet setting in perspective, we consider two methods that use the original Euclidean representations of the data, the 1-nearest neighbour algorithm (1NN) and AdaBoost.SAMME (SAMME) [Hastie et al., 2009].

Implementation details. For tSTE we used the implementation distributed on the authors' website and we set the embedding dimension to the original dimension of the data. This method was only considered for small datasets with less than 103 examples as it does not scale well to bigger datasets (Figure 3c). For CompTree we used our own implementation and the leaf size of the comparison tree is set to 1 as this is the only value for which this method can handle noise. For 1NN and SAMME we used sk-learn [Pedregosa et al., 2011]. The number of boosting iterations for SAMME is set to 103 . Finally for TripletBoost we set the number of iterations to 106 .

Datasets and performance measure. We consider six datasets: Iris, Moons, Gisette, Cod-rna, MNIST, and kMNIST. For each dataset we generate some triplets as in Equation (1) using three metrics: the Euclidean, Cosine, and Cityblock distances (See Perrot and von Luxburg [2018] for details). Given a set of n examples there are n2 (n-1)/2 possible triplets. We consider three different regimes where 1%, 5% or 10% of them are available, and we consider three noise levels

(a) Gisette, Metric: Euclidean, Noise

Level: 0%

(c) Moons, Metric: Euclidean, Propor-

tion of Triplets: 10%, Noise Level: 10%

Figure 3: The Gisette dataset has 7000 examples and 5000 dimensions. In Figure 3a we consider the noise free setting and we vary the proportion of triplets available from 1 to 10% of all the triplets. In Figure 3b we fix the proportion of available triplets to 5% and we vary the noise level from 0 to 20%. Figure 3c presents the training time of the triplet-based methods with training samples of increasing sizes on the Moons dataset. The proportion of triplets and the noise level were both set to 10%. The results were obtained on a single core @3.40GHz.

where 0%, 10% or 20% of them are incorrect. We measure performances in terms of test accuracy (higher is better). For all the experiments we report the mean and standard deviation of 10 repetitions. Since the results are mostly consistent across the datasets we present some representative ones here and defer the others to Perrot and von Luxburg [2018].

Small scale regime. We first consider the datasets with less than 103 training examples (Figure 2). In this setting our method does not perform well when the number of triplets is too small, but gets closer to the baselines when the number of triplets increases (Figure 2a). This behaviour can be easily explained: when only 1% of the triplets are available, the triplet classifiers abstain on all but 3 or 4 examples on average and thus their performance evaluations are not reliable. Consequently their weights cannot be chosen in a satisfactory manner. This problem vanishes when the number of triplets increases. With increasing noise levels (Figure 2b) one can notice that TripletBoost is more robust than CompTree. Indeed, CompTree generates a comparison-tree based on individual triplet queries, and the greedy decisions in the tree building procedure can easily be misleading in the presence of noise. Finally, our approach is less sensitive than tSTE to changes in the metric that generated the triplets (Figure 2c). Indeed, tSTE assumes that this metric is the Euclidean distance while our approach does not make any assumptions.

Large scale regime. On larger datasets (Figure 3), our method does not reach the accuracy of 1NN and SAMME, who exploit a significant amount of extra information. Still, it performs quite well and is competitive with CompTree, the method that uses active rather than passive queries. The ordinal embedding methods cannot compete in this regime, as they are too slow to even finish (Figure 3c). Once again TripletBoost is quite resistant to noise (Figure 3b).

5 Conclusion

In this paper we proposed TripletBoost to address the problem of comparison-based classification. It is particularly designed for situations where triplets cannot be queried actively, and we have to live with whatever set of triplets we get. We do not make any geometric assumptions on the underlying space. From a theoretical point of view we have shown that TripletBoost is well founded and we proved guarantees on both the training error and the generalization error of the learned classifier. Furthermore we derived a new lower bound showing that to avoid learning a random predictor, at least Ω(n√n) triplets are needed. In practice we have shown that, given a sufficient amount of triplets, our method is competitive with state of the art methods and that it is quite resistant to noise.

To the best of our knowledge, TripletBoost is the first algorithm that is able to handle large scale datasets using only passively obtained triplets. This means that the comparisonbased setting could be considered for problems which were, until now, out of reach. As an illustration, consider a platform where users can watch, comment and rate movies. It is reasonable to assume that triplets of the formmovie mi is closer to mj than to mk can be automatically obtained using the ratings of the users, their comments, or their interactions. In this scenario, active learning methods are not applicable since the users might be reluctant to answer solicitations. Similarly, embedding methods are too slow to handle large numbers of movies or users. However, we can use TripletBoost to solve problems such as predicting the genres of the movies. As a proof of concept we considered the 1m movielens dataset [Harper and Konstan, 2016]. It contains 1 million ratings from 6040 users on 3706 movies. We used the users' ratings to obtain some triplets about the movies and TripletBoost to learn a classifier able to predict the genres of a new movie (details are given in Perrot and von Luxburg [2018]). Given a new movie, in ∼83% of the cases the genre predicted as the most likely one is correct and, on average, the 5 genres predicted as the most likely ones cover ∼92% of the true genres.

Acknowledgments

Ulrike von Luxburg acknowledges funding by the DFG through the Institutional Strategy of the University of T¨ubingen (DFG, ZUK 63) and the Cluster of Excellence EXC 2064/1, project number 390727645.