Uncertainty Estimates for Ordinal Embeddings
Michael Lohaus Philipp Hennig Ulrike von Luxburg




=1




abstractAbstract
1ex 








 
    
       
            
       
       
       
      




 

















./Images/













Uncertainty Estimates for Ordinal Embeddings
    
	Michael Lohaus^1
	Philipp Hennig^1,2
	Ulrike von Luxburg^1,2
	^1University of Tübingen, Germany

	^2Max-Planck-Institute for Intelligent Systems, Tübingen, Germany
	{michael.lohaus, philipp.hennig, ulrike.luxburg}@uni-tuebingen.de

    Received: date / Revised version: date
=============================================================================================================================================================================================================================================




To investigate objects without a describable notion of distance, one can gather ordinal information by asking triplet comparisons of the form “Is object x closer to y or is x closer to z?” In order to learn from such data, the objects are typically embedded in a Euclidean space while satisfying as many triplet comparisons as possible. 
In this paper, we introduce empirical uncertainty estimates for standard embedding algorithms when few noisy triplets are available, using a bootstrap and a Bayesian approach. In particular, simulations show that these estimates are well calibrated and can serve to select embedding parameters or to quantify uncertainty in scientific applications. 




§ INTRODUCTION

In a typical machine learning problem, we are given a data set of examples 𝒟 and a (dis)similarity function δ that quantifies the distance between the objects in 𝒟. The inductive bias assumption of machine learning is then that similar objects should lead to a similar output. However, in poorly specified tasks such as clustering the biographies of celebrities, an obvious computable dissimilarity function does not exist. Nonetheless, humans often possess intuitive information about which objects should be dissimilar. While it might be difficult to access this information by quantitative questions (“On a scale from 1 to 10, how similar are celebrities x and y?”), it might be revealed using comparison-based questions of the type “Is object x closer to y or closer to z?” The answer to this distance comparison is called a triplet. The clear advantage of such an approach is that it removes the issues of a subjective scale across different participants. A common application for such ordinal data is crowd sourcing, where many untrained workers complete given tasks <cit.>. Ordinal information emerges for example as real data in search-engine query logs  <cit.>. Given a list of search results, a document x, on which a user clicked, is closer to a second clicked document y than to a document z, on which the user did not click. 

The standard approach to deal with ordinal data in machine learning is to create Euclidean representations of all data points using ordinal embedding.  In the classic literature, this approach is called non-metric multidimensional scaling (NMDS) <cit.> and has its origins in the analysis of psychometric data by <cit.> and <cit.>. In NMDS the objects are embedded into a low-dimensional Euclidean space while fulfilling as many triplet answers as possible. In recent years, such embedding methods have been extensively studied, and various optimization problems were proposed <cit.>, also including probabilistic models <cit.>.

Theoretical aspects of ordinal embeddings have been studied for the scenario where the original data comes from a Euclidean space of dimension d. The consistency of ordinal embeddings in the large-sample limit n →∞ as well as the consistency for the finite sample case up to a similarity transformation have been established <cit.>. It is also known that Ω( dn n) actively chosen triplets are necessary to learn an embedding of n points in ^d <cit.> .  As of now, there has been no theoretical analysis on the distortion of embeddings that are constructed from a set of much fewer than Ω( dn n) triplets. In this paper, we develop empirical methods that provide uncertainty estimates to characterize how certain a given embedding method is about its result when only few and possibly noisy training triplets are available.

We present two methods to obtain uncertainty estimates: one is based on a bootstrap approach, the other on a Bayesian approach. In both cases, we generate a distribution over embeddings which can then be used to compute the uncertainty about the answer of a triplet comparison or the point location. These uncertainty estimates improve upon ordinal embedding and address its limitations. In particular, we apply our uncertainty estimates to estimate the embedding dimension or to quantify uncertainty in psychophysics applications. In the experiments we examine whether the triplet uncertainty estimates are well calibrated. Lastly, we use the estimates to improve active selection of triplets. We find that our uncertainty estimates provide a valuable add-on to judge the quality of ordinal embeddings. 



§ SETUP AND BACKGROUND ON ORDINAL EMBEDDING




 §.§ Setup

Let (𝒳,δ) be a metric space and 𝒟 = {ξ_1,...ξ_n }⊂𝒳 a finite data set. We consider a latent dissimilarity function δ: 𝒳×𝒳→_0^+ on 𝒟 and abbreviate δ( ξ_i, ξ_j) =: δ_ij. In the following, we assume that no explicit dissimilarity values δ_ij nor any other representations of the objects in 𝒟 are given to us. Instead, for three distinct points ξ_i, ξ_j and ξ_l, we can observe the (possibly noisy) answer to the comparison: “Is δ_ij < δ_il or is δ_ij > δ_il?” We call the answer to this question a triplet. Formally, a triplet is an ordered set of three points (i,j,l), encoding that the answer is “δ_ij < δ_il”. Similarly, (i,l,j) denotes that the answer is “δ_il< δ_ij”. This answer can be noisy in the sense that it might be wrong compared to the ground truth dissimilarity. However, this ground truth is considered unknown and we only observe a set 𝒮 of noisy triplets, which we refer to as the training set.

A Euclidean embedding of the data set 𝒟 = {ξ_1, ..., ξ_n} consists of n points x⃗_1, ..., x⃗_n ∈^d, written more compactly as X⃗∈^n × d. The parameter d is called the embedding dimension. 
The function ρ: ^d ×^d →_0^+ denotes the Euclidean distance function, abbreviated as ρ_ij := ρ( x⃗_i, x⃗_j) := x⃗_i - x⃗_j_2. Let D⃗ := D⃗(X⃗) be the Euclidean distance matrix corresponding to the embedding X⃗. 

Given a (noisy) triplet set 𝒮, the goal of ordinal embedding is to find a representation of the data set 𝒟 in a low-dimensional space ^d that recovers as many triplets as possible, that is we want to construct points x⃗_1, ..., x⃗_n ∈^d such that 

    δ(ξ_i,ξ_j) < δ(ξ_i,ξ_l) ⇒ρ(x⃗_i,x⃗_j) < ρ(x⃗_i,x⃗_l).






 §.§ Ordinal embedding methods

The goal of this paper is to provide uncertainty estimates for ordinal embeddings and improve upon existing embedding methods. In the following, we briefly recall two popular embedding methods.



  
Crowd Kernel.
<cit.> assume an explicit noise model by which the observed triplets have been generated. Given three points x⃗_i, x⃗_j, x⃗_l, the likelihood to obtain the triplet answer (i,j,l) is given by 

    p_ijl = ρ_il^2 + μ/ρ_ij^2+ρ_il^2+ 2μ,

where μ is a parameter for regularization and numerical stability. 
A high value of p_ijl indicates that a triplet (i,j,l) is well modeled by the current embedding. 
Given a noisy set of triplets 𝒮, the final embedding X⃗ is obtained by minimizing the negative log-likelihood ∑_( i,j,l ) ∈𝒮-p_ijl.

Stochastic Triplet Embedding (STE,  ) suggests a more local variant where large violations receive nearly constant penalties and clearly satisfied triplets induce a nearly constant reward. Their Gaussian noise model leads to the triplet likelihood 

    p_ijl = -ρ_ij^2/-ρ_ij^2+-ρ_il^2.

In the same paper, the authors also suggest a more robust version of STE that replaces the Gaussian distribution by the more heavy-tailed t-distribution, leading to what is called t-STE (see supplement). The final embedding is constructed by minimizing the negative log-likelihood. 






§ COMPUTING UNCERTAINTY ESTIMATES OF PAIRWISE COMPARISONS


Assume we are given a data set 𝒟 of n abstract points, a noisy triplet set 𝒮 and an embedding algorithm. The goal is to generate a set of embedding samples and use the variance of such samples to capture uncertainty over point locations or triplet answers. We consider two approaches to generate embeddings in order to compute uncertainty estimates for ordinal embedding algorithms.


In a Bayesian approach, we use a prior distribution, either over embeddings or over distance matrices. As the second ingredient we use a likelihood function, encoding the probability of observing a certain triplet given an embedding or distances. Sampling from the corresponding posterior leads to a set of embeddings, or a set of distance matrices, respectively. 

Our bootstrap approach proceeds like the following: we first subsample triplets (not points!) and secondly, we embed the points based on these triplets by the given embedding algorithm. Each repetition leads to a new embedding of the n data points. As in the Bayesian approach, we can use this set of embeddings to evaluate uncertainties. 
	
These uncertainty estimates capture uncertainties caused by the limited number of observed triplets and their possibly noisy nature. By construction, they cannot account for systematic model bias, which could be introduced by an inapt choice of embedding algorithm in the bootstrap, or a bad choice of likelihood in the Bayesian approach. 
	


 §.§ Bayesian approach for sampling embeddings

A Bayesian model is defined by a generative model that specifies prior and likelihood. We consider two variants. Our first attempt is to consider a prior over distance matrices. In order to calculate an uncertainty estimate for triplets, it is preferable to know directly the uncertainty of the two distances involved. However, this turns out to be challenging due to the specific properties of Euclidean distance matrices that would need to be modeled. Our second approach specifies a prior over embeddings. This turns out to be much more manageable despite the “detour” via embeddings to distances. In both cases, we use Gaussian distributions for the prior. Gaussians are a frequent choice of prior in the Bayesian literature. They are closely related to ℓ_2-norm regularizers in the statistical literature <cit.> and amount to a similar set of assumptions and restrictions. 

A prior over the distance matrix D⃗ is supposed to incorporate as much prior knowledge about Euclidean distance matrices as possible, yet it should be easy to handle.  Simple prior knowledge about Euclidean distance matrices is that they are symmetric, all entries are non-negative, diagonal entries are zero, and the entries fulfill the triangle inequality. These properties alone are not sufficient to characterize Euclidean distance matrices. We would need to incorporate even more complicated conditions <cit.>. However, it is hard to find a distribution of matrices that has its support exactly on Euclidean distance matrices. See the supplementary material for a first approach that employs a multivariate Gaussian prior over distance matrices to encode symmetry. It is non-trivial to encode more specific properties of distance matrices in an expressible prior. Because Bayesian models based on this simplistic but tractable prior did not behave satisfactorily in initial experiments we turn to a different approach.


A prior over embeddings is more manageable. We regard an embedding X⃗ as a vector X⃗ in ^nd. We assume the prior  X⃗∼𝒩(0⃗,Λ⃗) with Λ⃗∈^nd × nd. Furthermore, we assume that the embedded points are independently and identically distributed, that is Λ⃗ is a block diagonal matrix. Overall, the Gaussian prior over embeddings is more restrictive than a prior over distance matrices since a distance matrix can originate from any point configuration. Yet, a prior over embeddings is a reasonable assumption because triplets put strong constraints on the embedding. Hence, the prior mainly provides a scale for the embeddings.


For a likelihood, we can use any function ℓ(D⃗) that appropriately describes how well a triplet is modeled, for example the STE likelihood (<ref>) or other likelihood functions used by other embedding algorithms.

Combining either of the two priors with the chosen likelihood function yields two posterior distributions. When using the prior over embeddings we obtain

    p(X⃗ | 𝒮) ∝𝒩( 0⃗,Λ⃗) ℓ(D⃗(X⃗)).

Both posterior distributions are not analytically tractable. However, it is possible to sample from them using a Markov Chain Monte Carlo algorithm or by applying variational methods. In this paper, we use the MCMC framework of elliptical slice sampling (ESS) by <cit.>. It is applicable for multivariate Gaussian priors and any likelihood function and can therefore be used for both posteriors.  
Elliptical slice sampling requires an initial sample X⃗_0. We use the fact that some embedding methods maximize a likelihood; for example we use STE to generate  X⃗_0 when sampling from a posterior that relies on the STE likelihood. As a result, the MCMC random walk begins at a maximum likelihood estimate and discovers the posterior distribution from there. Once we can sample from the posterior, we obtain distance matrices D⃗^(1), …, D⃗^(b), either directly from p(D⃗ | 𝒮), or via embeddings X⃗^(1), …, X⃗^(b) from p(X⃗ | 𝒮).



 §.§ Bootstrap approach for generating embeddings
 

In this section we propose a bootstrap 
approach to generate a set of embeddings. Given a training set 𝒮 of triplets and a sampling parameter r ∈(0,1), we uniformly draw ⌊ r · |𝒮| ⌋ many triplets out of 𝒮 without replacement to obtain a subset 𝒮_1⊂𝒮. After that, the given embedding method uses 𝒮_1 to embed the n points into ^d. Subsampling and embedding are repeated b times, which results in b embeddings. Note that we draw triplets without replacement for a single subset, but we do not divide 𝒮 into b subsets. Therefore, we can choose b arbitrarily high. The resulting embeddings can widely differ in scale and orientation. To make the embeddings comparable, we randomly select one of them as a reference embedding and use a Procrustes analysis to rotate and scale all the other embeddings to match the reference embedding as well as possible <cit.>. This procedure results in embeddings  X⃗^(1), …, X⃗^(b), which give rise to distance matrices  D⃗^(1), …, D⃗^(b). 
		


 §.§ Computing uncertainty estimates



Given a set of distance matrices D⃗^(1), …, D⃗^(b) computed with either the Bayesian approach or the bootstrap, we can now compute uncertainties for all triplet answers. A naive approach is to compute the uncertainty of a triplet (i,j,l)  by evaluating in how many of the b embeddings this triplet is true. However, this majority vote leads to bad results because it does not take the corresponding distances of a triplet into account. We propose the following model-based approach. From the set of b distance matrices we first compute the entry-wise means ρ_ij and standard deviations σ_ij: 

    ρ_ij = 1/b∑_k = 1^b D⃗^(k)_ij,   σ_ij^2= 1/b-1∑_k = 1^b ( D⃗^(k)_ij- ρ_ij)^2.

We now assume that the distances ρ_ij are distributed as 𝒩(ρ_ij,σ_ij^2) (an assumption that approximately holds in many applications).
With these ingredients, a natural uncertainty estimate can be assigned to any triplet answer: 
the likelihood to observe the triplet answer (i,j,l) is 
    π_ijl := Φ(ρ_il -ρ_ij/σ_il + σ_ij),

where Φ denotes the cdf of the standard normal distribution. If π_ijl is close to 0.5, it signifies high uncertainty about (i,j,l). If π_ijl is close to 1 (or 0), then the triplet (i,j,l) is likely to be true (or the opposite (i,l,j) is true). 

Rather than computing the uncertainty of triplets, we can also evaluate uncertainties for each point position. Among embeddings X⃗^(1), …, X⃗^(b) we consider the mean x⃗_i = 1/b∑_k = 1^b x⃗^(k)_i and sample covariance of a single point:

    C_i   = 1/b-1∑_k = 1^b ( x⃗^(k)_i- x⃗_i) ( x⃗^(k)_i- x⃗_i)^T,

where x⃗^(k)_i∈^d is the embedding of ξ_i in the k-th embedding X⃗^(k). 
Note that these estimates make sense because in both our approaches, the embeddings are well-aligned  and the distance matrices “comparable”: due to Procrustes analysis in the bootstrap approach, and due to the model-based approach in the Bayesian setting. 
	


§ USING UNCERTAINTY ESTIMATES


In this section, we discuss four applications for our uncertainty estimates. First, we use our triplet uncertainty estimates to predict the true answers of triplet comparisons. Secondly, we estimate an appropriate embedding dimension for ordinal training data. Thirdly, we quantify the uncertainty of a psychophysics experiment by applying the point uncertainties. Finally, we query the most uncertain triplets in an active triplet selection setting.
	


 §.§ Triplet prediction



Given a set 𝒮 of noisy triplets, the aim of triplet prediction is to predict the true answers both for unobserved triplet comparisons and noisy observed triplets. To use our uncertainty estimates for the triplet prediction problem, we introduce the possibility to abstain from a prediction. To this end, we introduce an “uncertainty threshold” t > 0.5. We predict δ_ij < δ_il  if π_ijl > t and  δ_il < δ_ij if π_ijl < 1-t. If π_ijl∈ [1-t,t] there is no prediction and we “abstain”.
Note that by construction of the values π_ijl we have that  π_ijl>t ⇔π_ilj < 1-t and thus, the above construction cannot lead to any inconsistencies. 

The threshold t can be used for a trade-off between the triplet prediction error and the abstention rate: when the threshold t increases, we abstain more often, but the prediction error on the remaining predicted triplets decreases. It can also be observed that for a fixed threshold t, the abstention rate decreases when we increase the number of training triplets because we are more and more certain about our predictions. See Section <ref> for results. 



 §.§ Estimating the embedding dimension

When we employ an ordinal embedding approach and we are given real world ordinal information, it is often not clear how to choose the embedding dimension d because the true dimension of the data is unknown. The naive approach is to use some measure to quantify the error of the embedding, and choose the dimension which leads to the best result. However, many such measures improve trivially with increasing dimension. This is analogous to overfitting – we achieve a low error for training triplets, but suffer a high error for unobserved triplets.

Instead, we now use uncertainty estimates to find a good embedding dimension. Given an embedding dimension d we sample many embeddings as described above and compute the average uncertainty over all triplet answers. In regions of overfitting the uncertainty estimates reveal a higher variance due to many degrees of freedom, and in regions of underfitting the estimates reveal uncertainty due to contradicting triplets. As we can see in the experiments in Section <ref>, the average uncertainty is typically minimized for the correct dimension when using the bootstrap method. In other cases it can give an indication for a good embedding dimension depending on the intrinsic dimension of the data set. Additionally, the uncertainty estimates do not trivially decrease by increasing the embedding dimension.

 



 §.§ Application in psychophysics


When ordinal embedding is used in a context of scientific data analysis, an analysis of uncertainties is often a crucial step. We want to illustrate this with an application in psychophysics. A standard task in this field is to estimate how physical stimuli are perceived by human observers. For example, the input might consist of images of increasing contrast, or of sounds of increasing frequency. The outcome of an experiment is supposed to show how this translates to the perceived increase of contrast, or sounds. See Figure <ref> for an illustration where we plot a non-linear relation between an exemplary stimulus and its perception. While traditional methods such as the Steven's Magnitude estimation <cit.> try to quantitatively measure aspects of this relationship, a different approach is to use ordinal embeddings.
Here, the idea is to ask participants to compare triplets of stimuli, and generate a one-dimensional embedding based on their triplet answers. This embedding corresponds to the projection of the curve in Figure <ref> on the y-axis. We can now use our uncertainty estimates to additionally evaluate the uncertainties along the estimated perception curve. 



To simulate a psychophysics experiment with a couple of human observers we assume that each observer perceives a stimulus following a fixed perception function (similar to Figure <ref>). The triplets that the human observer provides are created based on her corresponding perception function. Since every human observer perceives the stimuli differently, each observer has a different perception function and hence, gives different triplet answers. Finally, the set of all observed triplets contains contradictions depending on how different the perception functions of the observers are. In Section <ref> we show that the uncertainties over point positions reveal how much the perception curves differ. 





 §.§ Active learning


For human observers providing triplets can be monotonous and boring after a while <cit.>, and crowd sourcing experiments are time consuming. Therefore, instead of asking all triplet comparisons, it can be advantageous to collect a small amount of the most informative triplets by an active approach. We propose our uncertainty estimates as a means to obtain a practical procedure for active triplet selection. 

In this section we assume that there is a limited budget of triplets that can be collected. Before we query, the crowd provides a small set of random “seed triplets”. These triplets are answers to comparisons that have been drawn randomly with replacement from the set of all possible comparisons. Our estimates derived in (<ref>) capture the uncertainty, which was introduced by the given seed set, for all triplets and determine which comparisons we should query next. The intuition is that the seed triplets determine the location of some points, while other points still have a lot of freedom. Therefore, we ask comparisons for which the answers are considered uncertain. 






Given a seed training set 𝒮, we augment 𝒮 in the following way. First, we detect the triplets with highest uncertainty:

    (i,j,l) = 	_i,j,l = 1,...,n (π_ijl - 0.5)^2.

Triplets are binary answers, and our estimates assess the uncertainty about them: if  (i,j,l) is uncertain, then (i,l,j) is uncertain to the same degree, since π_ilj = 1 - π_ijl. Therefore, two complementary triplets will minimize (<ref>). Then, we query the corresponding comparison from the crowd in order to observe the triplet answer, and add it to the training set 𝒮. When collecting more triplets, we can query one by one, each time updating the uncertainty estimates, or we query bigger batches. Also note that a comparison might be queried several times.


In Section <ref>, we perform classification, clustering, and triplet prediction using actively queried triplet comparisons. Unfortunately, the results are disappointing: triplet prediction improves only by a small amount, which does not translate to an improvement for classification and clustering. This finding is in accord with our own experience in many simulations with a large variety of triplet selection mechanisms (landmark settings, geometry-based sampling): often, none of the intricate triplet sampling schemes significantly beat the naive strategy of random selection <cit.>. However, it is in fact good news for practitioners. The advice based on the experiments in our paper is to simply query as many random comparisons as possible. 




  
Related work on active triplet selection.
Some active approaches have already been reported in the literature on ordinal embeddings, however they are not practical for various reasons. <cit.> consider an active triplet selection mechanism that is motivated from a theoretical point of view. It relies on a subroutine that outputs a consistent embedding if one exists (that is, an embedding that satisfies all true triplet answers). However, in a setting of noisy triplets, no algorithm can solve this problem. 

<cit.> propose an adaptive selection algorithm, which is similar to our Bayesian perspective. In order to collect a triplet for any point a, they consider the posterior distribution over the location of a in  ^d, involving all those triplets that have a as the anchor. Then a pair of points b, c ≠ a is selected by a procedure that maximizes an information gain criterion, and the corresponding comparison is queried. Unfortunately, no code for this method is made available, but a data-driven approximation of the information gain can be used from <cit.>. However, it was not possible to produce competitive results within our framework. For the sake of completeness see the supplementary material for results comparing to the information gain criterion.



	


§ EXPERIMENTS


In this section, we first examine the behavior of our uncertainty estimates when the number of training triplets or the noise level changes. Secondly, we consider the task of triplet prediction. Thirdly, we use our estimates to find an appropriate embedding dimension. Additionally, we simulate a psychophysics experiment and estimate point uncertainties. Lastly, we employ our estimates for an active learning approach and examine the performance with respect to triplet prediction, classification and clustering. 



  
Method setup.
With STE Bootstrap we denote our bootstrap approach based on the STE embedding method. We use the code by <cit.> for the embedding algorithms. With random subsamples of 40 percent of the training triplets (without replacement), we generate b=20 bootstrap embeddings. 

By Bayesian STE we denote our Bayesian approach (<ref>) using the STE likelihood (<ref>). Here we use the MCMC method as described above to sample 500 embeddings. Since we start with a maximum likelihood solution as described above, no burn-in phase is necessary. For the prior covariance matrix Λ⃗ in (<ref>), we simply use 15·I⃗.

All experiments except for triplet prediction and the application in psychophysics have been repeated 5 times, using the same set of Euclidean points, but independent training triplets. The figures always display means and standard deviations. Given a fixed number of points from the data sets in question, we use the Euclidean distance for the underlying distance δ. The training set 𝒮 of noisy triplets is generated as follows: we model two random variables z_ij via z_ij∼𝒩( δ_ij, σ^2) and z_il via z_il∼𝒩( δ_il, σ^2). The two positive random variables  z_ij and z_il take the role of distances between points; if z_ij < z_il, then the triplet (i,j,l) is added to 𝒮, or vice versa. This ensures that the z_ij are positive, and two similar distances can cause a wrong triplet independent of their magnitude. 

The number of triplets that we use in these experiments is in the range of 0.1 up to 10 times dnn. If the number of triplets grows much further, there is no uncertainty for the estimates to reveal except for high noise levels. Besides, the goal of active learning is to query as few triplets as possible. Moreover, computing uncertainty estimates requires repeated embedding or sampling, and hence, running time profits from a low number of triplets. 



 §.§ Are the uncertainty estimates well calibrated?

We first need to verify that our estimates are well calibrated, in the sense that they react “correctly” under the influence of noise and the amount of training triplets. To this end, we compare the changes of both the embedding error and the average uncertainty over triplets when increasing the noise or the amount of training triplets. 

In the following, we use a two-dimensional mixture of three Gaussians. The means of the three components are μ_1 = [2,2] , μ_2 = [-2,-1], μ_3 = [4,-2] and the covariance matrices are Σ_1 = [2,0; 0,1], Σ_2 = [1,0; 0,1] and  Σ_3 = [1, 0.7; 0.7,2]. We randomly draw 50 points, generate triplets as described above, and embed again in ^2.  We compute the error of an embedding X⃗∈^2 in relation to the ground truth X⃗^∗∈^2 by performing a Procrustes analysis. We then report the procrustes distance min_U⃗X⃗U⃗ - X⃗^∗^2_F, which uses the Frobenius norm and minimizes over orthogonal U⃗. For the overall uncertainty, we compute the average over the uncertainties of all true triplets. The values displayed in the figures are the averages of the overall uncertainties over the 5 independent runs of the experiments. 




  
Increasing noise.
Given a fixed fraction of true triplets, we generate noisy training sets by the mentioned noise model for a range of values for σ. We expect that increasing the noise level leads to an increase in the embedding errors. Simultaneously, we expect that the uncertainty increases, as the data contains more contradicting triplets. In Figure <ref> we can see both effects for the example of the STE embedding algorithm: both the Bayesian and the bootstrap uncertainty increases with increasing noise and converge to 0.5 (completely uncertain). Both our uncertainty measures qualitatively behave similarly, but the bootstrap approach seems to be more conservative in the sense that it produces higher values of uncertainty. Experiments with other embedding algorithms yield similar results, see the supplementary for details. 




  
Increasing the number of triplets.
In this case, we have σ = 0, but we increase the number of all true triplets in 𝒮 from 0.5 % to 15 %. In Figure <ref>, we can see that the procrustes distance decreases as rapidly as the average uncertainty when the size of the noise-free training set 𝒮 increases. When the number of triplets is roughly 10 dnn, the uncertainty estimates identify that sufficiently many triplets are used. 





 §.§ Triplet prediction.

On the same mixture of Gaussians, we perform the task of triplet prediction as described in Section <ref>. We consider noise-free training sets 𝒮 with varying size, and we consider different choices for the abstention threshold t. For all combinations of parameters we then report the trade-off between abstention rate and triplet prediction error (the proportion of wrongly predicted triplets). 

First, we expect that the prediction error decreases with an increasing threshold t, because we predict triplets with low uncertainty. Surely, the abstention rate increases with increasing threshold t and if we abstained on every prediction, the triplet prediction error would be zero. Therefore, we expect, secondly, the abstention rate to decrease, when the number of training triplets increases. In Figure <ref> we show that both effects take place. 



 §.§ Estimating the embedding dimension



To test whether our uncertainty estimates are a good tool to estimate the embedding dimension, we first generate a data set with known ground truth. To this end, we use the digits 6 and 8 of MNIST <cit.> and project the data set on its first principal components using d_true = 3 components. Then we sample 50 points from this low-dimensional data set, evaluate 20% of all corresponding triplets, and add noise with the described noise model (σ = 0.1). Then we use ordinal embedding to embed into various dimensions, and we report the cost function of STE and evaluate the average triplet uncertainty with our bootstrap and Bayesian approach.

In Figure <ref> we can see the results for the case of d_true = 3 (other results look similar, see the supplement for different d_true). The cost function of the STE algorithm decreases with an increasing embedding dimension, but in case of the Bayesian approach, the average uncertainty drops and stays constant at d_true. Furthermore, we find that the bootstrap method picks up the true dimension because the average triplet uncertainty is low or minimal for the correct dimension. 









 §.§ Application in psychophysics


In order to simulate a psychophysics experiment as described in Section <ref> we discretize the stimulus in 20 steps in [0,1] and represent every human observer with her individual perception function.  The triplet answers of each observer are created based on their perception function. The overall training data is the collection of all triplet answers and is used to construct the one-dimensional ordinal embedding, which estimates the relative positions of the perceived stimuli on the y-axis. Due to different perception functions the training data contains inconsistent triplet answers and hence, there is uncertainty about these locations. We use our Bootstrap approach and the STE embedding method to estimate the point uncertainties. 

We control how different each observers perception function is by drawing them from a Gaussian Process 𝒢𝒫(m,k) <cit.> and changing the covariance function k.  The mean function for the Gaussian Process 𝒢𝒫(m,k) is given by a logistic function m(x) = (1+-25(x-0.5))^-1. For the covariance function k we choose the squared exponential kernel k(x_i,x_j) = (-2l^2)^-1x_i-x_j^2 where l>0 denotes the lengthscale, which we use to control the covariances. Additionally, we fix all functions to be the identity at stimulus 0 and at stimulus 1. See the supplementary material for the exact posterior Gaussian Process and an illustration for a fixed lengthscale. 


For 50 observers we draw perception functions on n = 20 stimuli and create 100 triplet answers from each function. On a total of 5000 triplets we perform a bootstrap (with b = 50 and r = 0.1) and obtain several embeddings. Since ordinal embeddings are invariant to scale and rotation, we normalize each embedding such that the stimulus 0 is perceived as 0 and the stimulus 1 is perceived as 1. Lastly, we compute the mean position x_i and standard deviation s_i := √(C_i) for each embedded stimulus i = 1,...,20. We repeat this procedure for three different lengthscales l_1 = 2,l_2 = 0.88 and l_3 = 0.54. When we decrease the lengthscale l, the perception functions differ more from the mean and we obtain more contradicting triplet answers. Correspondingly, the uncertainty of each point position increases (see Figure <ref>).
 





 §.§ Active learning


We now evaluate our active learning approach using three different learning tasks on different data sets. The tasks are (i) triplet prediction, evaluated by the triplet prediction error, which in this context is the ratio of true triplets that are not satisfied in an embedding; (ii) classification on the embedded data points using a simple kNN classifier, evaluated by classification error; (iii) clustering using the normalized spectral clustering algorithm, evaluated with the Adjusted Rand Index (ARI) against the clusters provided by the true labels.


The active learning approach is realized as follows. As described in Section <ref>, we start with a random seed of 2,000 triplets and the noise level
σ = 0.1. We then use our uncertainty estimates to identify the 1,000 most uncertain triplet comparisons, query them, and add the noisy triplet answers to the training set. We then evaluate the resulting embedding corresponding to the respective task. Subsequently, we compute new uncertainty estimates and, based on them, query more triplet comparisons. We repeat this procedure of adding batches of 1,000 uncertain triplets until 10,000 triplets are in the training set. For the passive experiments, 1,000 random triplets are added each step. For both the active and passive approach, we embed the current triplet set with the respective embedding method into d = 5 dimensions. Note that in these experiments we compute the uncertainty estimates for all possible triplets. Therefore, the framework allows for repeatedly querying the same triplet comparison. 

 In Figure <ref> we examine the results of our two active strategies with the STE embedding method on the Landsat Satellite data set <cit.>. Results with t-STE and other data sets like MNIST <cit.>, and Breast Cancer <cit.> are reported in the supplementary. In terms of triplet prediction error the active approaches improve the embeddings by a noticeable margin, although not overwhelmingly. For the other tasks the active methods do not show an effect on classification error and ARI.



§ DISCUSSION

We presented both a bootstrap and a Bayesian approach that compute uncertainty estimates for a given embedding model when few and noisy triplets are available. They are well calibrated, and they can be used for the triplet prediction problem. In a negative result, we found that the uncertainty estimates are not overly helpful for active learning. This agrees with our experience that random triplet selection often outperforms elaborate ideas. In an application in psychophysics the estimates quantified the uncertainty about the outcome of the experiment. Additionally, the uncertainty estimates are helpful for embedding parameters: when using the bootstrap they can give an indication about an appropriate embedding dimension. 


    




  §.§.§ Acknowledgments


This work has been supported by the International Max Planck Research School for Intelligent Systems (IMPRS-IS), the Institutional Strategy of the University of Tübingen (DFG, ZUK 63) and the DFG Cluster of Excellence “Machine Learning – New Perspectives for Science”, EXC 2064/1, project number 390727645. Philipp Hennig gratefully acknowledges financial support by the European Research Council through ERC StG Action 757275-PANAMA.


plainnat


28
	
	
	urlstyle[Agarwal et al.(2007)Agarwal, Wills, Cayton, Lanckriet, Kriegman, and
	Belongie]agarwal07
	S. Agarwal, J. Wills, L. Cayton, G. Lanckriet, D. Kriegman, and S. Belongie.
	Generalized non-metric multidimensional scaling.
	In Artificial Intelligence and Statistics, 2007.
	
	[Amid and Ukkonen(2015)]amid15
	E. Amid and A. Ukkonen.
	Multiview triplet embedding: Learning attributes in multiple maps.
	In International Conference on Machine Learning, 2015.
	
	[Anderton et al.(2018)Anderton, Pavlu, and Aslam]anderton18
	J. Anderton, V. Pavlu, and J. Aslam.
	Revealing the Basis: Ordinal Embedding Through Geometry.
	arXiv e-prints, art. arXiv:1805.07589, 2018.
	
	[Arias-Castro(2017)]arias-castro17
	E. Arias-Castro.
	Some theory for ordinal embedding.
	Bernoulli, 2017.
	
	[Bartels and Hennig(2016)]bartels16
	S. Bartels and P. Hennig.
	Probabilistic approximate least-squares.
	In Artificial Intelligence and Statistics, 2016.
	
	[Bijmolt and Wedel(1995)]bijmolt95
	T. H.A. Bijmolt and M. Wedel.
	The effects of alternative methods of collecting similarity data for
	multidimensional scaling.
	International Journal of Research in Marketing, 1995.
	
	[Borg and Groenen(2005)]borgGroenen05
	I. Borg and P.J.F. Groenen.
	Modern Multidimensional Scaling: Theory and Applications.
	Springer, 2005.
	
	[Dattorro(2005)]dattorro05
	J. Dattorro.
	Convex Optimization & Euclidean Distance Geometry.
	2005.
	
	[Dheeru and Karra Taniskidou(2017)]UCI17
	D. Dheeru and E. Karra Taniskidou.
	UCI machine learning repository, 2017.
	
	[Gescheider(1997)]gescheider97
	G. A. Gescheider.
	Psychophysics: The Fundamentals.
	Lawrence Erlbaum Associates, 1997.
	
	[Heikinheimo and Ukkonen(2013)]heikinheimo13
	H. Heikinheimo and A. Ukkonen.
	The crowd-median algorithm.
	In HCOMP, 2013.
	
	[Jain et al.(2016)Jain, Jamieson, and Nowak]jain16
	L. Jain, K. G. Jamieson, and R. D. Nowak.
	Finite sample prediction and recovery bounds for ordinal embedding.
	In Advances in Neural Information Processing Systems. 2016.
	
	[Jamieson and Nowak(2011)]jamieson11
	K. G. Jamieson and R. D. Nowak.
	Low-dimensional embedding using adaptively selected ordinal data.
	In 49th Annual Allerton Conference on Communication, Control,
		and Computing, 2011.
	
	[Jamieson et al.(2015)Jamieson, Jain, Fernandez, Glattard, and
	Nowak]jamieson15
	K. G. Jamieson, L. Jain, C. Fernandez, N. J. Glattard, and R. D. Nowak.
	Next: A system for real-world development, evaluation, and
	application of active learning.
	In Advances in Neural Information Processing Systems. 2015.
	
	[Kanagawa et al.(2018)Kanagawa, Hennig, Sejdinovic, and
	Sriperumbudur]2018arXiv180702582K
	M. Kanagawa, P. Hennig, D. Sejdinovic, and B.K. Sriperumbudur.
	Gaussian Processes and Kernel Methods: A Review on Connections and
		Equivalences.
	arXiv e-prints, art. arXiv:1807.02582, 2018.
	
	[Karaletsos et al.(2016)Karaletsos, Belongie, and
	Rätsch]karaletsos16
	T. Karaletsos, S. Belongie, and G. Rätsch.
	Bayesian representation learning with oracle constraints.
	In International Conference on Learning Representations, 2016.
	
	[Kleindessner and von Luxburg(2014)]kleindessner14
	M. Kleindessner and U. von Luxburg.
	Uniqueness of ordinal embedding.
	In Conference on Learning Theory, 2014.
	
	[Kruskal(1964)]kruskal64
	J. B. Kruskal.
	Nonmetric multidimensional scaling: A numerical method.
	Psychometrika, 1964.
	
	[LeCun et al.(1998)LeCun, Bottou, Bengio, and Haffner]lecun98
	Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.
	Gradient-based learning applied to document recognition.
	Proceedings of the IEEE, 1998.
	
	[Murray et al.(2010)Murray, Adams, and MacKay]murray10
	I. Murray, R. P. Adams, and D. J. C. MacKay.
	Elliptical slice sampling.
	In Artificial Intelligence and Statistics, 2010.
	
	[Rasmussen and Williams(2006)]rasmussen06
	C. E. Rasmussen and C. K. I. Williams.
	Gaussian Processes for Machine Learning.
	MIT Press, 2006.
	
	[Schultz and Joachims(2004)]schultz04
	M. Schultz and T. Joachims.
	Learning a distance metric from relative comparisons.
	In Advances in Neural Information Processing Systems. 2004.
	
	[Shepard(1962)]shepard62
	R. N. Shepard.
	The analysis of proximities: Multidimensional scaling with an unknown
	distance function.
	Psychometrika, 1962.
	
	[Tamuz et al.(2011)Tamuz, Liu, Belongie, Shamir, and Kalai]tamuz11
	O. Tamuz, C. Liu, S. Belongie, O. Shamir, and A. T. Kalai.
	Adaptively learning the crowd kernel.
	In International Conference on Machine Learning, 2011.
	
	[Terada and von Luxburg(2014)]terada14
	Y. Terada and U. von Luxburg.
	Local ordinal embedding.
	In International Conference on Machine Learning, 2014.
	
	[Ukkonen et al.(2015)Ukkonen, Derakhshan, and Heikinheimo]ukkonen15
	A. Ukkonen, B. Derakhshan, and H. Heikinheimo.
	Crowdsourced nonparametric density estimation using relative
	distances.
	In HCOMP, 2015.
	
	[van der Maaten and Weinberger(2012)]maaten12
	L. van der Maaten and K. Q. Weinberger.
	Stochastic triplet embedding.
	In IEEE International Workshop on Machine Learning for Signal
		Processing, 2012.
	
	[Wolberg and Mangasarian(1990)]wolberg90
	W. H. Wolberg and O. L. Mangasarian.
	Multisurface method of pattern separation for medical diagnosis
	applied to breast cytology.
	Proceedings of the National Academy of Sciences, 1990.
	










In the following, we shortly recap the GNMDS and t-STE embedding methods.



§ EMBEDDING ALGORITHMS



Generalized Non-Metric Multidimensional Scaling (GNMDS) by <cit.>
aims to find a kernel matrix K⃗ = X⃗X⃗^T that satisfies the given triplet constraints in 𝒮 with a large margin. It minimizes the trace norm of the corresponding kernel matrix to obtain a low dimensional embedding, which leads to the following semidefinite program:

    [          min_K⃗∈S⃗^+K⃗ + C ·∑_( ijl ) ∈𝒮ξ_ijl                                              ; k_jj - 2 · k_ij + k_ll + 2 · k_il≤ 1 +  ξ_ijl                                 ∀( i,j,l ) ∈𝒮;                                      ξ_ijl≥ 0                                ∀( i,j,l ) ∈𝒮. ]

The final embedding X⃗ can be computed by an SVD of the kernel matrix K⃗ = X⃗X⃗^T. Replacing rank by trace, this program solves a relaxed version of the ordinal embedding problem, and hence one may not always find the correct embedding. 

t-Distributed Stochastic Triplet Embedding (t-STE,  ) is a more robust version of STE that replaces the Gaussian distribution by the more heavy-tailed t-distribution with α degrees of freedom. As the authors suggested, we use α = d-1. The final embedding is constructed by minimizing the negative log-likelihood with

    p_ijl = (1+x⃗_⃗i⃗-x⃗_⃗j⃗^2/α)^-α +1 /2/(1+x⃗_⃗i⃗-x⃗_⃗j⃗^2/α)^-α +1 /2 + (1+x⃗_⃗i⃗-x⃗_⃗l⃗^2/α)^-α +1 /2.







§ BAYESIAN APPROACH FOR SAMPLING EMBEDDINGS


For a prior over the distance matrix D⃗ we take a simple approach. We employ a multivariate Gaussian prior over the distance matrix and encode symmetry. For a matrix D⃗∈^n × n, we stack the rows into a vector and denote it with D⃗∈^n^2. The function 1_ik is the indicator function where 1_ik equals 1 when i=k and 0 otherwise. The operator ⊗ denotes the usual Kronecker product. Following the definition of <cit.>, symmetry is encoded in the covariance matrix of the Gaussian prior via the symmetric Kronecker product. It uses a matrix Γ⃗∈^n^2 × n^2 with [Γ⃗]_(i,j)(k,l) = 0.5 ( 1_ik1_jl + 1_il1_kj). The symmetric Kronecker product is defined as A⃗⊛C⃗ := Γ⃗ (A⃗⊗C⃗) Γ⃗. Any positive semi-definite matrix W⃗∈^n × n, leads to a prior distribution that encodes symmetry of the resulting matrix D⃗∼𝒩(D⃗_0, W⃗⊛W⃗) with mean D⃗_0. However, as described in the main paper, this approach fails to incorporate more specific properties of distance matrices.

Combining this prior with a triplet likelihood function yields the posterior distribution

    p(D⃗ | 𝒮) ∝𝒩(D⃗_0,W⃗⊛W⃗) ℓ(D⃗).

This posterior distribution is not analytically tractable. However, we can also use the MCMC framework of elliptical slice sampling (ESS) by <cit.> since it is applicable for multivariate Gaussian priors and any likelihood function.


	 

	
	

§ ARE THE UNCERTAINTY ESTIMATES WELL CALIBRATED?

	As reported in the experiments of Section 5.1, other embedding methods were used to examine if the uncertainty estimates are well calibrated.  As in the main paper, we use a two-dimensional mixture of three Gaussians (see Figure <ref>). The means of the three components are μ_1 = [2,2] , μ_2 = [-2,-1], μ_3 = [4,-2] and the covariance matrices are Σ_1 = [2,0; 0,1], Σ_2 = [1,0; 0,1] and  Σ_3 = [1, 0.7; 0.7,2]. We randomly draw 50 points, generate triplets, and embed again in ^2. We use t-STE and GNMDS to see how our uncertainty estimates behave under more noise (see Figure <ref>) or an increasing number of training triplets (see Figure <ref>). Note, that GNMDS does not use a probabilistic model, and therefore, we just perform a bootstrap for GNMDS. For the overall uncertainty, we compute the average over the uncertainties of all true triplets, and, for visualization purposes, flip the average on 0.5 such that the uncertainty decreases to 0 rather than increases to 1. 

	Additionally, we performed the task of triplet prediction, as described in Section <ref>, on the same data set. Here, we report the results for our Bayesian STE method in Figure <ref>. The abstention rate decreases faster than for the STE Bootstrap with an increasing number of triplets. On the other hand, the prediction error for Bayesian STE is quite high when only very few triplets are available, whereas the STE Bootstrap abstains more in this regime, which leads to a low triplet prediction error. 
	
	
	
	
	 

§ ESTIMATING THE EMBEDDING DIMENSION

	 
    In order to evaluate how well our uncertainty estimates are calibrated, we report the overall uncertainty which is the average over the uncertainties of all true triplets. When estimating the embedding dimension, we often have not access to all ground-truth triplets. Here, we proceed slightly differently when computing the average uncertainty: first, we compute the triplet uncertainty of every possible triplet (i,j,l). If π_ijl>0.5, we include 1-π_ijl into the average, otherwise we include π_ijl. Since uncertainty is expressed only by the distance of π_ijl to 0.5, the average uncertainty computed this way is meaningful.         
	
	
	
	

§ APPLICATION IN PSYCHOPHYSICS

	
	We model the perception functions with a Gaussian Process as described in Section <ref>. We fix all functions to be the identity function to map 0 on 0 and 1 on 1. We summarize our training points in x⃗ := (0,1)^T with the outcome y⃗ := (0,1)^T. When we use the kernel function on two vectors, we evaluate covariances of all pairs of entries, hence, k(x⃗,x⃗^⃗'⃗) denotes the matrix of pairwise covariances. Then, our posterior kernel is given by k_post(x_i,x_j) = k(x_i,x_j) - k(x_i,x⃗) ( K⃗(x⃗,x⃗))^-1  k(x⃗,x_j). The posterior mean function is given by  m_post= m(x).


	
	

§ ACTIVE LEARNING

	
    
	<cit.> suggest an adaptive approach to select the next query using the triplet probabilities (<ref>) developed for the Crowd Kernel embedding algorithm. This sampling strategy can also be used with the STE or t-STE triplet probabilities. By STE–IG (or t-STE–IG) we denote that we use the information gain (IG) sampling scheme with the STE (or t-STE) likelihood.  
	
	For the active learning experiment described in Section <ref>, we use three data sets — MNIST, Breast Cancer, and Landsat Satellite (see Table <ref>). Here, we report all results for all three data sets. For Breast Cancer see Figure <ref>, for MNIST see Figure <ref>, and for Landsat Satellite see Figure <ref>. 
	
	Recall, that we use n = 200 points and the noise level is σ = 0.1. We start with a random seed of 2,000 triplets and repeatedly add 1,000 triplets to the training set by determining the 1,000 most uncertain triplet comparisons. In the case of the information gain criterion, we add those 1,000 triplets that have the highest information gain. We measure the embeddings after each step by performing the three tasks: triplet prediction, classification and clustering. 
	
	For the following results we denote our bootstrap approach based on the t-STE embedding method with t-STE Bootstrap and our bootstrap approach based on the GNMDS embedding method with GNMDS Bootstrap. By Bayesian t-STE we denote our Bayesian approach using the t-STE likelihood (<ref>).
	


 


	
	 
 
 
  


