LARGE SCALE REPRESENTATION LEARNING FROM TRIPLET COMPARISONS
Authors: Siavash Haghiri
Leena Chennuru Vankadara
Ulrike von Luxburg
Venue:  (2020)
Keywords: representation learning
triplet comparison
contrastive learning
ordinal embedding

Abstract: In this paper, we discuss the fundamental problem of representation learning from a new perspective. It has been observed in many supervised/unsupervised DNNs that the final layer of the network often provides an informative representation for many tasks, even though the network has been trained to perform a particular task. The common ingredient in all previous studies is a low-level feature representation for items, for example, RGB values of images in the image context. In the present work, we assume that no meaningful representation of the items is given. Instead, we are provided with the answers to some triplet comparisons of the following form: Is item A more similar to item B or item C? We provide a fast algorithm based on DNNs that constructs a Euclidean representation for the items, using solely the answers to the above-mentioned triplet comparisons. This problem has been studied in a sub-community of machine learning by the name "Ordinal Embedding". Previous approaches to the problem are painfully slow and cannot scale to larger datasets. We demonstrate that our proposed approach is significantly faster than available methods, and can scale to real-world large datasets.

Thereby, we also draw attention to the less explored idea of using neural networks to directly, approximately solve non-convex, NP-hard optimization problems that arise naturally in unsupervised learning problems.

LARGE SCALE REPRESENTATION LEARNING FROM TRIPLET COMPARISONS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, discuss the fundamental problem of representation learning from a new perspective. It has been observed in many supervised/unsuperiieed DNNs that the final layer of the network often provides an informative representation for many tasks, even though the network has been trained to perform a particular task. The common ingredient in all previous studies is a low-level feature rep- resentation for items, for example, RGB values of images in the image context. In the present work, we assume that no meaningful representation of the items is given. Instead, we are provided with the answers to some triplet comparisons of the following form: Is item A more similar to item B or item C? We provide a fast algorithm based on DNNs that constructs Euclidean representation for the items, using solely the answers to the above-mentioned triplet comparisons. This problem has been studied in sub-community of machine learning by the name "Ordinal Embedding". Previous approaches to the problem are painfully slow and cannot scale to larger datasets. We demonstrate that our proposed approach is sig- nificantly faster than available methods, and can scale to real-world large datasets. Thereby, we also draw attention to the less explored idea of using neural networks to directly. approximately solve non-come non-convex, NP-hard optimization problems that arise naturally in unsupervised learning problems.
INTRODUCTION
It has been widely recognized that deep neural networks (DNN) provide a powerful tool for represen-
tation learning (Bengio et al. 2013). Representations learned an unsupervised fashion have been demonstrated to be useful in learning tasks such as classification (Ranzato et al. [007 2008 Hinton Salakhutdinov 2008 Hinton et al., 2006)] Bengio et al.) (007)). In the context of supervised learn- ing, representations are typically learned as by-products neural networks (Radford et al. 2015). For example in image classification, low level representations
inputs (e.g., rgb values) are fed to network, together with class label information, the network is trained to perform some supervised classification. As a by-product discovers a condensed data representation in the last hidden layers of the network that turns out be surprisingly successful for other computer vision tasks such as ob- ject detection or semantic segmentation (Girshick et al. 2014) Kümmerer et al. 2014 Long et al.] 2015 Ren et al. 2015). Subsequently, more direct mechanisms have been designed to explicitly learn data representations (Mensink et al. 20122] Bell & Bala, 20155] Schroff et al. 2015). Again the raw data is fed to network, this time together with some information about the similarity of objects, and then the network is trained to generate meaningful data representation.
Particularly relevant to our work the field of contrastive representation learning (Wang et al. 2014 Hoffer & Ailon 2013: Cheng et al.) 2016 Ge 2018 Arora et 2019). where similarity information is provided in terms of contrastive triplets of points (x. x ): for a given point x, the point t and x= are specifically chosen data points that are similar dissimilar to æ. Such approaches have been extremely successful on image and text data, and they are particularly elegant the similarity information can be extracted from the raw data in some unsupervised manner. Examples are the case of word embeddings (Mikolov et al., 2013),, where words are considered similar if they occur within the same local neighborhood, or text representations (Logeswaran & Lee 2018), where two subsequent sentences are considered similar, or in computer vision (Wang & Gupta 2013) where pairs of image patches in subsequent frames of videos are considered similar.

---

BRIII
DUNRIN
HUME
(a)
(b)
Figure I: Illustration of general triplet comparisons.
There are two main ingredients that seem unavoidable in all these approaches: First, one needs an explicit low level representation of the data to feed as input to the DNN architectures. Secondly, one needs information about the similarity of different data points that can be used to train the network parameters. This information can be provided by class membership labels in supervised approaches, or it is extracted from some unsupervised meta-data - for instance the temporal information for frames of video data.
In our work, we investigate the problem of learning a data representation cases where no mean- ingful input representation explicit similarity information exists. Instead we assume that provided with the answers to a set of general triplet comparisons where, for any arbitrary triplet of items (I,, zj. Tx), know whether 2; is more similar zj I&. The problem of learning representation based on such triplet comparisons is called ordinal embedding (Agarwal et al. 2007 van der Maaten & Weinberger 2012 Kleindessner & von Luxburg. 2014 Terada & von Luxburg 2014).
This setting can be of advantage in many cases. Consider learning a representation for large set of movies. There does not exist an obvious informative low level representation that can be used in straight forward manner in a neural net, yet one can ask triplet comparisons from users of movie database. An example of triplet comparison on movies in shown in Figure [a Other use-cases also arise in more scientific contexts. For example, psychophysical scaling aims to find the functional relation of physical stimulus and human perception. For example, AAgiiar et al. (2017) conducted experiments with triplet comparisons to find out the relation between the angle a tilted plane and the perceived angle of human observer. In this study, number of triplet questions asked from human observers (see an example of triplet question in Figure lb). Later, a one-dimensional embedding (representation) is learned for the perceived value of angle. A comprehensive study the application of ordinal embedding in psychophysics is available at Haghiri et al. (2019).
We design novel neural network architecture that can learn representations when only given the answers to a set of triplet comparisons and no input representation exists. Our approach opens doors into two different worlds:
(1) We use the power of DNNs to approximately solve an NP hard optimization problem with discrete input (point identifiers and binary comparisons). Its widely believed amongst neural net- work practitioners that the non-convex landscape of deep and wide neural networks is primarily free of sub-optimal local minima. This theory is supported under simplified assumptions by vari- ous theoretical findings (Nguyen & Hein 2017 Choromanska et al. 2015 Kawaguchi & Bengio, 2019 Kawaguchi et al.) 2019). These results provide a basis for the hypothesis that deep neural network models offer a tool that can make non-convex, NP-hard optimization problems "tractable practice".
In machine learning, this line of thinking is particularly interesting for unsupervised learning prob- lems such as clustering, dimensionality reduction or representation learning, where the typical ob- jective functions are discrete, often NP hard, or non-convex. The standard approach to solve such problems are convex relaxations. Albeit the resulting relaxed problem then can be solved exactly, there often does not exist any provable guarantee that relates the solution of the relaxed problem to the solution of the original problem. We believe that the ability of DNN's to directly (approximately) solve non-convex optimization functions provides an attractive alternative and has not really been

---

explored to solve such problems in ML: very little emphasis has been placed in approaches that use neural networks not as learning machines but rather as toolboxes to solve optimization problems.
The same point of view might be valuable for general, even discrete optimization problems. In paper we demonstrate that DNNs can be successfully applied to such a problem. It will be interesting to see how more generie architectures can be designed to solve more generic discrete, non-convex, NP-Hard optimization problems.
(2) We provide the first, scalable approach for the ordinal embedding problem based on neural networks. The problem of ordinal embedding has been studied extensively in the machine learning literature (Agarwal et al. 2007| van der Maaten & Weinberger 2012 Kleindessner & von Luxburg. 2014 Terada & von Luxburg 2014;Jain et al.) 2016]. Optimizing the ordinal embedding objective by traditional means is notoriously difficult (either algorithms are very slow or lead unsatisfactory results), and for computational reasons it is close to impossible to embed more than 10000 items. Thanks to the fast parallel computations of DNN training. our approach runs significantly faster than traditional methods (see Subsection 4.4
2 BACKGROUND ON COMPARISON-BASED MACHINE LEARNING AND ORDINAL EMBEDDING
Assume we given a set of abstract items X { T2,,,., Fn). but no explicit representation is available for the items. Even though there exists a dissimilarity function 8(..-) that describes the dissimilarity of pairs of items, we also do not have direct access to this dissimilarity function. Instead, we only get to see answers to triplet questions of the form "Is item more similar to item Iy or item xg? We denote such a triplet question by t (I, TR:) (or sometimes just by t = (i, J, k)), and the answer to this triplet question by
1,
if my is more similar to 2 than to Te
R₂
-1
if x4 is more similar to 2% than to zz
Machine learning based on such qualitative comparisons has become popular (Agarwal et al. 2007 van der Maaten & Weinberger| 2012 Amid & Ukkonen 2015] Ukkonen al.] [015]] Balcan al, 2016 Haghiri et al. 2017 2018). One fundamental approach in this area is the ordinal embedding procedure. Here we assume that a set of triplet comparisons T = (41 ....... km } is given to us. We consider the passive setting where we do not have any influence the chosen comparisons (as opposed to an active setting where we could actively ask particular questions to an oracle). The binary answers, according to the above definition, are stored. Ordinal embedding aims to find d-dimensional representation f1, ...... Yn E Rd such that the Euclidean distances between these points satisfy many triplet answers possible. This can be expressed by the following optimiza- tion problem:
Σ
R sign 3ز 112 l1y: 13)
max Mh ERd
(((,AA))TT
In a real world setting it is typically impossible to satisfy all the input triplets: the dissimilarity function is not necessarily constrained to be a d-dimensional Euclidean metric, and even if so the answers might be noisy.
The above optimization problem is discrete, non-convex and NP-hard (Bower et al. 2018 Parda- los Vavasis [199].. There exit various methods that employ relaxations of the this optimization problem: Generalized non-metric multidimensional embedding (GNMDS; Agarwal et al. 2007), stochastic triplet embedding (STE: van der Maaten & Weinbergeri 2012) and local ordinal embed- ding (LOE; Terada & von Luxburg (0014) are among the methods in this category. However, all of them are computationally very demanding, and none of these methods can scale beyond few thou- sand input points at most. The only somewhat scalable approach is the one by Anderton & Aslam 2019), based on explicit geometric constructions and landmarks. However, this approach requires an active access to triplet answers: rather than just receiving bag of triplet answers, the algorithm needs to repeatedly ask very specific triplet questions to an oracle. Our approach works in the more general passive setting.

---

22 (010110)
EmbNet
11
Lit = (i,j,k), Ra)
#WW
#W
#d
Imput Ra
Output E R
1- (ij.k)
(001010)
EmbNet
FC
FC
FC
FC
(22, 10, 37)
37 (100103)
EmbNet
Uk
(b)
Figure 2: (a) The architecture of Ordinal Embedding Neural Network (OENN). As example a triplet (22, 10, 37) and its answer R2 are fed to the architecture. (b) The EmbNet neural network, which is used as building blocks of ordinal embedding architecture.
The performance of ordinal embedding methods is typically evaluated by the triplet ervor. Given an estimated representation {Ū), 52, ./...... ) error simply counts how many triplet answers are satisfied by the given representation:
of the data items and set T" of triplet answers, the triplet
triplet error (TE) = T
1
Σ
[Re sign(llo: 5 10::
iall -1].
(3)
((J,A)))
where 1(.) equals to one, the inside expression is true and it is zero otherwise. Note that Rs sign [| ūز [|: Ox (²) -1 if the estimated embedding is not consistent with the triplet Thus, we count the ratio of non-consistent triplets this way.
3 PROPOSED METHOD: ORDINAL EMBEDDING NEURAL NETWORK (OENN)
Our proposed architecture inspired by the recent line work on contrastive learning WWag et al. 2014 Schroff al. 2015 Cheng et al.) 2016 Hoffer Ailon 2015). Figure Za shows a sketch of our proposed network architecture. The central sub-module of our architecture is what we call the embedding network (EmbNet): one such network takes certain encoding of single data point x; as input (typically, an encoding of its index i, see below) and outputs dddimennsinal representation di of data point 24- The EmbNet replicated three times with shared (identical) parameters. The overall OENN network now takes the indices (i. k)) corresponding to triplet (I,, Kij xx) as an input. It routes each of the indices i, , & to one of the copies the EmbNet, which then return the d-dimensional representations yt, új. yk. respectively (cf. Figure 2ap.
The three sub-modules are trained jointly using the triplet hinge loss, as described by the following objective function:
C(t = (i.j,k), Ra)
Σ (((G))))T
max (-Ra - 55ll 11 yi II) 1,00)
[T]
Choice of input representation (encoding): Since we don't have access to any informative low- level input representations, the choice of input representations presents challenge to this approach. However, leverage the expressive power of neural networks (Leshno al. 1993] Barron 1993) and their ability to (for instance) fit random labels to random inputs (Zhang et al., 2016) to motivate choice of input encoding. Since main goal is find representations that minimize the training objective, we believe that completely arbitrary input representations are a viable choice.
One such input representation could be the one-hot encoding of the index (where point is encoded by a string i; of length n such that (!) = 1 if = and otherwise). The advantage of choosing such representation is that is memory efficient in the sense that there need to additionally

---

store the representations of the items. However, under this choice of representation the length of the input vectors grows linearly with the number n of input items. As one of the central contributions consider more efficient way: of our work is to perform ordinal embedding in large scales, represent each item by the binary code of its index, leading to a representation length of log n. Such representation retains the memory efficiency of the one-hot encoding (in the sense discussed above) but improves the length of the input representation from n to log n. As we will see below, this representation works well in practice. However, note that there is nothing peculiar about this choice of binary code. Indeed, we conducted experiments where each input point was represented by a unique, random binary string of length log (see subsection [4.]] The results are pretty similar to the ones using the binary codes. We believe that any representation that dedicates a unique code to the items and covers the R [log space will do the job.
Structure of EmbNet: Figure 2b shows the schematic of the EmbNet. We propose a simple network with three fully-connected hidden layers and ReLu activation function. The final layer is a linear layer that takes the output of third hidden layer and produces the output embedding. The input size to the network is [log n and each hidden layer contains w nodes. The output layer has d nodes to produce embeddings in Rdd The input and output size, [logn] and d, are pre-determined by the task. Thus the only independent parameter of the network is the width of hidden layers. Our experiments (see subsection [4.1) demonstrate that the hidden layer width (w) should grow logarithmically with respect to the number of items in order to produce good embedding outputs.
Difference to previous constrastive learning approaches: As described earlier, our architecture is inspired from Wang et al. (2014); Hoffer & Ailon (2015). However, there are fundamental differ- ences between the works in both the problem that we try to address and our approach to solve this problem. (i) The most stand-out aspect of our problem is that we have no access to representations for the input items En. Our network takes completely arbitrary representations for the input items. In addition, the way in which triplets are sampled is different as well. (ii) The nature of triplet comparisons is quite different in comparison with the previous studies. In the previous work, triplets are always contrastive triplets of the form (z, x )) Obtaining contrastive triplets requires extra information, either either class labels, or more explicit similarity information between objects. In our ordinal framework, we are given neither of this information, and simply gather triplets answers involving arbitrary sets of three points.
4 SIMULATIONS
We run an extensive set of simulations, on the one hand find good rules of thumb to set our hyper- parameters and input encoding, and on the other hand to evaluate the performance of the OENN in terms of triplet error and compare it alternative ordinal embedding approaches.
4.1 CHOICE OF HYPER- PARER-PAR.MMEERS.
Our neural network model consists of a single
the width of the hidden layers w. We simulations inform our choice of based the number of input items n and the embed- ding dimension d. Our simulations demonstrated that the width of the hidden layers needs to grow logarithmically with the number of items and linearly with the embedding dimension. The detailed experimental setups as well as the results from these experiments are provided in the supplementary.
4.2 CHOICE OF THE LENGTII OF INPUT ENCODING.
The input to the OENN, described earlier, can be chosen as a triplet of arbitrary encoding of the items. We ran simulations to establish the dependence of the length of such encoding with the number of items. These simulations show that the size of the input encoding needs to grow logarithmically with the number of items. For more details on the parameters of our simulations and the corresponding plots, please refer to supplementary.

---

Two
Blobs
Circles
TE 0.02
TE = 0.02
TE 0.02
TWC- mo-ommons
Blobs
Circles
0.24
6.18
0.32
6.12
4.17
0.20
0.00
0.te
0.04
0.80
20350 80002 63000 80303 # Input triplets
2000 csre 60333 86000
20060 40000 secco aooco
# Input triplets
Input triplets
(h)
Figure 3: (a) Three datasets used for the reconstruction experiment. (b) Embedding output of OENN with [T| = 80000 input triplet answers. The training triplet error (TErrain) written on top each plot (c) Training and test error of the OENN algorithm with respect to varying number ( of input triplet answers.
4.3 RECONSTRUCTION AND GENERALIZATION TO UNSEEN TRIPLETS
To demonstrate the capacity of OENNS to reconstruct the true embedding we use three 2- dimensional datasets generated with the scikit-leaze package in Python. Datasets are shown in Figure 3a 1- two-moons dataset with two labels, 2- Blobs dataset, which is mixture of three Gaussians, and 3- concentric circles with 2 labels. In all three cases 1000 items are generated. The label information added to check the reconstruction capability visually.
The number of input triplets the embedding algorithm is chosen around nd log ~ 20000, which the theoretical bound for the reconstruction of items. More precisely the following range is chosen: [T'] {10000, 20000, ... 80000}. We generate the triplet answers according to the following procedure: We first sample three data points without replacement from the given set of n = 1000 points, and then evaluate the corresponding triplet question based on the true Euclidean distances between these points. In this experiment, we report the training triplet error (TFFrrasn) ) and test triplet error (Tetest). We generate 1000 triplet answers test set, independent of the training set.
We depict the embedding output of our proposed algorithm with the maximunm number of triplets (80000) in Figure 3b) We reported TExrain on top of each plot. In case of all three datasets, observe that the output embedding matches the ground truth data closely. In addition, we report the training error and test error of the embedding with various number of input triplets Figure Be The training eтror is always about 0.03, showing that the embedding method can satisfy most of the input triplets. However, with few input triplets (10000) the test error is high as 0.12. Note that the number of constraints on the ordinal embedding problem increase with the number of triplets and with fewer triplets its easier to find many configurations of data points that satisfy the given set of triplets. The test error, on unseen triplets, however can be higher since the embedding algorithm is less likely to have converged to the true, unique solution up to isometric transformations.
4.4 COMPARISON WITH OTHER ORDINAL EMBEDDING METHODSS
Here we compare the performance of the proposed OENN method with two competitors, namely local ordinal embedding (LOE) (Terada & von Luxburg 2014) and t-distrubuted stochastic triplet embedding (TSTE) (van der Maaten & Weinberger 2012). The main advantage of proposed OENN method is its ability to scale. this section we perform a simple simulation with increasing number of items. The items are sampled from uniform distribution on the unit square in TR22. In a first simu-
It has been theoretically shown that an ordinal embedding can be uniquely determined up to an isometric transform - if the items are sampled from compact subset of the Fuclidean space and the number of items grows infinity (Kleindessner & von Luxburg 2014)

---

0.88
0.0
GENN TSTE
---
OEMN TSTE
Training time (seconds)
4000
GE TSTTE
1or
+- LCE
LCE
0.30
2000.
0.85
Train
0.06
0.08
0.02
0.00
2002 1020 mino nons 10362 fer 5M
165
0.00
2002 1020 rot 1033 fer Sed
145
2000 1020 roto msca10nt 2et Set
Number items (n)
Number of Items
Number of Items
(a)
(b)
(c)
Figure 4: (a) Training triplet error with varying number of items for three different ordinal embed- ding methods. (b) Test triplet eπror for varying number n of items. Note that we scale the number of input triplets seconds. LOE and TSTE did not scale to data sets larger than 10000 points. Note that the right part corresponds to the extended range of items. In addition, the x-axis on the right part is exponential, thus the slope of the curve is not comparable to the left part of the plot.
[7] = nd log (c) Training time (embedding time) of the three methods in
lation we compare running times for the number of items in the range n E {1000, 2000, ... 10000). Because the running time for LOE and TSTE grows very quickly with n, we could not run these two algorithms on larger datasets, while our method still tractable. Therefore, we run our method {20000, 50000, 100000}.
alone extended range of items:
For fixed set of items we generate nd log n triplet answers (d = 2) based on the Euclidean dis- tances. The answers are fed to the ordinal embedding algorithms as input. For each set of items, generate an independent set of 1000 triplet answers as test set. The methods are compared based on three evaluation criteria: training triplet error (TEgrain) test triplet error (TEtest), and embedding time in seconds.
For our method, chose fixed hidden layer width 400 for n 10000 and w 800 for larger n. The optimization parameters of LÕE and TSTE are set to the default values. The author's implementation of LOE in R, available CRAN repository!! is used perform LOE experiments. We also used the Python implementation of TSTE, available on GitHut Note that the Python implementation consistently faster than the original MATLAB implementation by the author. All experiments are performed on the same machine with Intel XEON CPU E5-2620 processor, with GeForce GTX 1080-Ti GPU and 20 GB of memory. Obviously the proposed OENN method takes advantage of fast GPU computations, while the other methods run solely on the CPU.
We depicted the training triplet error and test triplet error various method in Figure and Fig- rrspebleeppcctively LOE can perfectly fit the embedding to the input triplet answers, thus we observe almost zero training error. Our method (OENN) and TSTE both perform reasonably well, showing less than 5% error on the training set. On the test set, all three methods have a similar performance. Finally, we depicted the embedding time of the three methods in seconds on Figure 4c As the number items grows, the traditional methods (LOE and TSTE) become painfully slow. In case of n = 1000, traditional methods require about hour to obtain the embedding, while the OENN re- quires about 5 minutes. The slope of the curve already shows that, ordinal embedding in large scales in essentially impossible with the traditional methods. In contrast, the OENN method can embed 100000 items in about hour, shown on the right part of Figure [4c Note that the scale of the x-axis on the right part is exponential, thus the growth is computation time is not comparable to the left side.
EXPERIMENTS
In this section, we perform ordinal embedding on a large scale dataset of triplet answers. To obtain such a dataset, we study Amazon's 's mechanical Turk (MTurk) platform. The study aims to collect answers to triplet comparisons of natural images. As data set we used a subsample of the Imagenet (Deng al. 2009) dataset. We chose the three high-level concepts "animal", "food". and

---

Heat-map pairwise distances
Animal
Vehicle
Animal
Food
Vehicle
(a)
Figure 5: (a) The heat-map of pairwise distances between the embedding outputs. The cencept name for each chunk of 2500 items is written both axes. (b) An example of 60 images depicted on their actual embedded location in two dimensions. Four images from each category are chosen at random.
"vehicles", and in each of these concepts we picked sub-categories ("synsets"). The details of these categories and our MTurk implementation are presented the supplementary material.
We gathered 1 120000 triplet answers from the MTTurk workers, which is somewhat less than the nd log 190000 triplets that would required for high-quality recovery according to the theo- retical lower bound for embedding in d = 2 dimensions (Jain et al. 2016).
Figure 5a depicts the pairwise distances of embedding outputs with embedding dimension 2. The three clusters are clearly evident in the distance matrix. We also depict the embedding output for a subsample of 60 images in Figure 5b We randomly chose images from each category to produce sample of 60 images. Looking the embedding output, clearly that three concepts of animals, vehicles and food are located at upper right, bottom, and upper left part of the picture respectively. There
the few exceptions well. For instance the very left bottom shelf of confectionery store.
DISCUSSION
In this paper, we propose novel, scalable representation learning algorithm. unique distinguish- ing property of our method is that it does not need any feature representation for the items - we successfully apply DNNs with random input encoding to achieve meaningful representations. As input we only require binary, relative distance comparisons.
Our proposed DNN architecture exploits the ability of neural networks approximately solve non- convex, NP-hard problems to obtain near optimal solutions to ordinal embedding problems. We believe that this provides new perspective to DNNs, which opens the doors to apply DNNs on other challenging optimization problems, particularly in the context of unsupervised learning.
In its application domain, our proposed method shows an outstanding improvement in terms of the computation time of ordinal embedding problems. Over the last decade, the ordinal embedding problem has been analyzed exhaustively, and number of methods have been proposed. However, ordinal embedding for more than thousands of items has been beyond the reach of algorithms. We proposed the first method that can work with passively collected triplet answers and solves the large scale ordinal embedding problem.

---

REFERENCES
S. Agarwal, J. Wills, I.. Cayton, G. Lanckriet, D. Kriegman, and S. Belongie. Generalized non-
metric multidimensional scaling. In AISTATS, pp. 11-18, 2007.
Guillermo Aguilar, Felix A Wichmann, and Marianne Maertens. Comparing sensitivity estimates from MLDS and forced-choice methods in slant-from -room-tetture experiment. J. Vis., 17(1):37, 2017. ISSN 1534-7362. doi: 10.1167/17.1.37. URL /ttL:tt://oo....voooouu... article aswp7doi=10000.mm 1167/17..
E. Amid and A. Ukkonen. Multiview triplet embedding: Learning attributes in multiple maps. In ICML, pp. 1472-1480, 2015.
Jesse Anderton and Javed Aslam. Scaling up ordinal embedding: A landmark approach. Interna- tional Conference on Machine Learning, pp. 282-290, 2019.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: DrXivv:902.092200 09299, 2019.
M.F. Balean, E. Vitercik, and C. White. Learning combinatorial functions from pairwise compar- isons. In COLT, 2016.
Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory, 39(3):930-945, 1993.
Sean Bell and Kavita Bala. Learning visual similarity for product design with convolutional neural networks. ACM Transactions on Graphics (TOG), 34(4):98, 2015.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In Advances neural information processing systems, pp. 153-160, 2007.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence, 35(8):1798-1822 2013.
Amanda Bower, Lalit Jain, and Laura Balzano. The landscape of non-convex quadratic feasibility. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3974-3978. IEEE, 2018.
De Cheng, Yihong Gong, Sanping Zhou, Jinjum Wang, and Nanning Zheng. Person re-identification by multi-channel parts- based enn with improved triplet loss function. In Proceedings of the iEEE conference on computer vision and pattern recognition, pp. 1335-1344, 2016.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pp. 192-204, 2015.
J. Deng, W. Dong, R. Socher, L.-J. Li. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hicrarchical Image Database. In CVPR09, 2009.
Weifeng Ge. Deep metric learning with hierarchical triplet loss. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 269-285, 2018.
Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for ac- curate object detection and semantic segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 580-587, 2014.
Haghiri, D. Ghoshdastidar, and U. von Luxburg. Comparison-based nearest neighbor search. In AISTATS, pp. 851-859, 2017.
Siavash Haghiri, Damien Garreau, and Ulrike Luxburg. Comparison-based random forests. In International Conference on Machine Learning, pp. 1866-1875, 2018.
Siavash Haghiri, Felix Wichmann, and Ulrike von Luxburg. Estimation of perceptual scales using ordinal embedding. arXiv preprint (ttp::/900099622.. 2019.

---

Geoffrey E Hinton and Ruslan R Salakhutdinov. Using deep belief nets to learn covariance kernels for gaussian processes. In Advances in neural information processing systems, pp. 1249-1256, 1256, 2008.
Geoffrey E Hinton, Simon Osindero, and Yee-W Whye Teh. A fast learning algorithm for deep belief nets. Neural computation, 18(7):1527-1555 2006.
Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In International Workshop on Similarity- Based Pattern Recognition, pp. 84-92. Springer, 2015.
Lalit Jain, Kevin G Jamieson, and Rob Nowak. Finite sample prediction and recovery bounds for ordinal embedding. In NIPS, pp. 2703-2711 2016.
Kenji Kawaguchi and Yoshua Bengio. Depth with nonlinearity creates no bad local minima in resnets. Neural Networks, 118:167-174, 2019.
Kenji Kawaguchi, Jiaoyang Huang, and Leslie Pack Kaelbling. Effect of depth and width on local minima deep learning. Neural computation, 31(7):1462-1498, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
M. Kleindessner and U. von Luxburg. Uniqueness of ordinal embedding. In COLT, 2014.
Matthias Kümmerer, Lucas Theis, and Matthias Bethge. Deep gaze i: Boosting saliency prediction with feature maps trained on imagenet. arXiv preprint arXiv: arXiv:/411. I. 1045, 2014.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
Lajanugen Logeswaran and Honglak Lee, An efficient framework for learning sentence representa- tions. arXiv preprint arXiv: / 8803 303.02893, 2018.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE IEEE conference on computer vision and pattern recognition, pp. 3431-3440, 2015.
Thomas Mensink, Jakob Verbeek, Florent Perronnin, and Gabriela Csurka. Metric learning for large scale image classification: Generalizing to new classes at near-zero cost. In European Conference Computer Vision, pp. 488 488-501. Springer, 2012.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp. 3111-31 19, 2013.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Pro- ceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2603-2612. JMLR. org, 2017.
Panos M Pardalos and Stephen A Vavasis. Quadratic programming with one negative eigenvalue is np-hard. Journal of Globul Optimization, 1(1):15-22, 1991.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint urXivv1511.000 1115151114444 1.0644, 2015.
Marc'Aurelis Aurelio Ranzato, Christopher Poultney, Sumit Chopra, and Yann L Cun. Efficient learning of sparse representttnsss with an energy-baar based model. Advances in neural information processing systems, pp. 1137-1144, 2007.
Mare' Aurelio Ranzato, Y-Lan Boureau, and Yann L Cun. Sparse feature learning for deep belief networks. In Advances in neural information processing systems, pp. 1185-1192, 2008

---

Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing systems, pp. 91-99,1015,
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pp. 815-823,20 2015.
Y. Terada and von Luxburg. Local ordinal embedding. In ICML, pp. 447-855, 2014.
A. Ukkonen, B. Derakhshan, and H. Heikinheimo. Crowdsourced nonparametric density estimation using relative distances. In HCOMP, 2015.
L. van der Maaten and K. Weinberger. Stochastic triplet embedding. In MLSP, 2012. Code available on http::/t:// / http::://hhoepeee.eeeemm t httpp//aae...tee...ee..eea/eaaee
Jiang Wang, Yang Song, Thomas Leung, Chuck Rosenberg, Jingbin Wang, James Philbin, Bo Chen, and Ying Wu. Learning fine-grained image similarity with deep ranking. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1386-1393, 2014.
Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2794-22928820 2802, 2015.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.

---

A APPENDIX
A.1 DEPENDENCE BETWEEN THE LAYER WIDTH w AND THE NUMBER TI OF ITEMS
As the number n of items grows, we expect that a larger network is required to address the com- plexity of the task. We can either increase the representational power of the network by adding more layers or by increasing the width of layers. In our experience a network with three hidden layers is always sufficient to solve the ordinal embedding problems if the layer width is chosen properly. Therefore, we focus on network with three hidden layers and investigate the required number of nodes in each layer (layer width w.)
In our first simulation, we fix the space TR:2, and choose n points from its unit square according to the uniform distribution. We consider nd log n triplet answers (where d = 2 is the dimension) according to the following procedure: We first sample three data points without replacement from the given set of points, and then evaluate the corresponding triplet question based on the true Euclidean distances between these points. The number of triplets chosen based on the theoretical lower bound the required number of triplet answers for the recovery of Euclidean representation (Jain et al. 2016). ignoring constants that might have been swallowed in the big-O nig-O-notation.
{27, 22, ........ 2 Given sample of points, we generate
The embedding network constructed with 3 hidden layers, each having w fully-connected neurons with ReLu activation functions. The width of the layers number of neurons in each layer) is 170). .0.............................. For a fixed network and a fixed set of triplet answers, the ordinal embedding executed 10 times in order examine the average behaviour of the model.
chosen from w E {70,90, .....
The implementations use the "PyTorch open- source library. The initial weights of the hidden layers and the final embedding layer are chosen according a uniform distribution (default initialization of PyTorch). We used Adam(Kingn)) & Ba 2014) to optimize the weights of the network. The learning-rate and batch-size parameters of the Adam optimizer are chosen as * 10-3 and 5000, respectively.
Figure Shass the training triplet error (TErrain) of the ordinal embedding with varying number of items and width of the hidden layers. The error is reported with heat-map plot, where warmer colors denote higher triplet error. The result shows that logarithmic growth of the layer width respect to is enough to obtain desirable performance.
A.2 DEPENDENCE BETWEEN LAYER WIDTH AND EMBEDDING DIMENSION d
Besides the number of items, the embedding dimension is another factor that influences the complex- ity of ordinal embedding. We expect that the required layer width needs to grow with the embedding dimension. We perform simulation with n = 1000 items in a d-dimensional Euclidean space with varying dimension d. Similar to the previous subsection, we sample 1000 items from the unit cube in Rdd. Then, we generate triplet answers to nd n triplet questions based on the Euclidean distances of items.
As we hypothesize the that relation between required layer width and the dimension is linear, we choose the dimension range E {100, 125.....
E (5. 10,... 40). The width of the hidden layer is chosen in the linear ... 225). The number of hidden layers, the optimization algorithm and the
hyperparameters of optimization are the same as the previous subsection.
Figure(bjshoows the training triplet error (TErrain ) of the ordinal embedding with varying dimension and width of the hidden layers. In order to achieve a desirable triplet error (below 10%), the width of hidden layers need to grow with the dimension. There is again clear line of transition between low and high error regions. As both axes are chosen linear in this experiment, we can conclude that linear increase in layer width with respect the dimension is needed.

---

Triplet (training)
Tripltt error (training)
170
0.30
0.5
200
0.75
Widh hidden
130
0.20
2000 hiddte
0.150
0.125
190
125
0.050
100
0.05
(n)
(b)
Figure 6: (a) Triplet error with varying number of items and hidden layer size. The x and y axes correspond to the number of items (n) and the hidden layer size (w) respectively. Note that x-axis grows exponentially. (b) Triplet error with varying dimension and hidden layer size. The x and axes correspond to the number of dimensions (d) and the hidden layer size (w) respectively.
A.3 DEPENDENCE BETWEEN THE SIZE OF THE INPUT ENCODING d' AND THE NUMBER OF POINTS
Our simulations demonstrate that the size of the input encoding needs to grow logarithmically with number of points. On the account of space constraints, experimental details and plots from these simulations are available in the supplementary file of this article.
A.4 DEPENDENCE ON SIZE OF THE INPUT REPRESENTATION
Our Ordinal Embedding Neural Network takes random encoding of a triplets items as input and learns transformation from the input encodings to vectors in Euclidean space of dimension spec- ified by the task. We ran simulations with binary encoding of the indices as well as with input representations of fixed length (d') by choosing each component of the vector uniformly at dom from an arbitrary interval (we choose the interval [1, 100) in our experiments). Our simulations show that the size of the input encoding needs grow logarithmically with increasing number of items.
To conduct the simulations, we sampled (ranging in {27,25, 214) data points uniformly from a unit square R2. For fixed set items, we generate nd log triplet answers (where is the dimension) according to the procedure as described in the main paper (see section 4.1). Our simulations demonstrated that choosing the width the hidden layers at the order log 7 would suffice to achieve low reconstruction error. So, construct EmNet by choosing the width of the hidden layer sufficiently large (w 100) for n = 214, which is the largest number of items used in our simulation.
Figure 7 shows the training triplet error (TErrain) of the ordinal embedding with varying number of items and size of the input encoding. The result shows that logarithmic growth of the size of the input encoding with respect to n suffices to obtain desirable performance.
A.5 RECONSTRUCTION DETAILED RESULTS
Here, we report the detailed results of the reconstruction experiment, presented in Subsection Figure&sshor the true datasets and the estimated embedding with different number of imput triplets. The left column shows the true datasets. The number of input triplet chosen r nd log n. where (0.5. 1, 2, 4]. This number is written on top of each plot, increases from left to right. In case of all three datasets, we observe that the output embedding gets more similar to the ground truth increase the number of input triplet answers. However, the loss and the training triplet emrr are both almost steady. If the algorithm is provided with less triplet answers, it needs to satisfy less constraints, thus it has simpler task. In other words, there exist more than one solution to the problem. However, in all cases the algorithm can satisfy almost the whole set of input triplet answers (TF 0.03).
dataset

---

Triplet error (training)
1.0
14
12
0.8
Size of input
10
0.6
8
0.4
4
0.2
2
128
256
512
1024 2048 4096 8192
Number of items (n)
Figure 7: The horizontal axis of the heatmap represents the number of points. Note that it increases exponentially. The vertical axis represents the size of the chosen input encoding. This axis increases linearly. The color of the heat map represents the triplet error obtained in the training procedure.
[T] 0.5ndlog loss 0.1. TE 0.04
[T] eddnggg
[T] 2rding lass 0.06, TE 0.03
[T] Andlag lass - 0.07, TE 0.02
Two moons, ground Fruth
loss 0.07. 0.08
6.5-
-10
-2.0
-00
-10
-26
-20
10
-30
0.5ndlog
[T]
2ndlog
[T]
ground truth
0.09.
loss
0.04
[T] - 0.5ndlog n
(T] rdlogg
IT] 2rdlog n
[T] - 4ndlog
ground
42
-30
Figure The reconstruction three toy datasets with various number of input triplet answers. Each column corresponds to one dataset. In each row, the first plot (from left) depicts the original datasets. The four next plots show the embedding output of OENN with various triplet inputs. The number of triplet inputs ((T)). training loss, and the triplet emor (TE) have appeared top of each plot. Colors of the dots represent hypothetical labels for the items.

---

Sine wave, ground truth
Embedding, Tripet error 0.02
1.00
15.
12.5
0.50
0.2
10.0
-0.25
-0.50
0.0
0.4
0.6
0.6
1.0
-15
-10
Sine wave, ground truth
Embedding, Tripet error 0.01
0.75
050
-025
00.
-330
-5-
-30
-1.00
02
0.4
0.8
1.0
-20
-10
10
Figure 9: An example of a pathological dataset for ordinal embedding
A.6 EXTRA DATASETS, PATHOLOGICAL EXAMPLES
our three examples for the reconstruction experiment datasets exhibit some nice properties: large number points, clustered data distribution. The natural question would be: "Does the proposed method still work in absence of the nice properties? Do we still get a good reconstruction of the initial dataset?"
Here, we present two examples in which the above properties do not hold. We chose a sine wave as the data distribution. The two datasets have 25 and 100 points respectively (see Figure 9 left column). We perform the ordinal embedding in two dimensions with nd log(n) triplet answers, which are produced based on Euclidean distances in two dimensions. Figure (right column) depicts the embedding result. The training triplet error for both experiments still less than 2%, which shows that the solution is valid solution.
Regarding the quality of reconstruction, the embedding with more data points resembles sine wave better than fewer data point. This is due the fact that with less number of data points there is more room for the embedding output to wiggle and the output still satisfies all triplet answers. Here, our ordinal embedding method is able to find valid solution a solution which satisfies the input triplet answers irrespective of dataset properties. This solution may not be unique as the ordinal embedding problem does not necessarily have a unique solution. Hence, one cannot expect a perfect reconstruction in such cases.
A.7 DETAILS OF THE MTURK EXPERIMENT
We conducted the crowd-sourcing study with a web-based implementation of the triplet comparisons on our servers. The workers are redirected to our page, where they have to answer 2000 triplet questions. The chosen concepts are very diverse, thus many resulting triplet questions might be not meaningful. For instance, sports car cannot really be considered more similar a pizza or vice versa. The workers are advised to give an answer when they can see a similarity, otherwise option provided to declare that the comparison cannot be made.
dog than to

---

The triplet answers collected from workers expected to be noisy. Beside the natural sources of human error, some workers may provide random or very unreliable answers. To filter out such workers, designed sanity check system. In every set of 2000 triple questions in one session, there exist about 200 triplet questions with very obvious answers. These are the cases where the pivot item 2; is in the same category with one the choices J., while the other choice The has different category. If a worker has less than 70% accurate answers on these triplets, we rejected his/her work, and consequently did add the response to the final pool of triplet answers.
The three concepts of Animal, Food, Vehicle }, each contain 5 categories. The labels of the categories are as follows:
Dog, Cougar, Alligator, Scorpion, Cat, Pizza, Pomegranate, Ice cream, Mashed potato, Confec- tionery, Goods wagon, Tractor, Police van, Limousine, Sport car) }
The larger and detailed pairwise distance matrix of two dimensional embedding is shown in Figur I0
Heat-map pairwise distances
Dog
Cougar
Alligator
Scorpion
Cat
Pizza
Pomegranate
Ice cream
Mashed potato
Confectionary
Goods wagon
Tractor
Police van
Limousine
Sport car
Dog
Cougar
Alligator
Scorpion
Cat
Pizza
Pomegranate
Mashed potato
Confectionary
Goods wagon
Tractor
Police
Limousine
Sport car
cream
Figure 10
A.8 THE CHOICE OF THE LOSS FUNCTION
In this section, we justify the choice of the loss function used in the paper. The problem of ordinal embedding finding an embedding X = {I1, .., H. Rd that satisfies a set of given triplets,
can phrased as a quadratic feasibility problem (Bower et al. (0188) as shown in equation
find X subject to X P., > OV(,,, ET.
(5)
Each Pij.k corresponds to a triplet constraint that satisfies,
| 22 > || -x = X2

---

Every feasible solution to is valid solution to the problem of ordinal embedding.
An equivalent way to solve 5 i.c., find feasible solution of i by finding the global optima of the constrained optimization problem (Bower et al. 2018) given by 6
min X (KJAA)T
Σ
max {0, 1 x P.jAA
(6)
Meaning, every feasible solution (5) can be scaled attain global optima of (6) and every global optima of (6) is feasible solution of (5) (Bower et al. 2018). Moreover, in optimization (1), any positive scaling feasible point solution as well. Whereas in optimization (2) this effect is eliminated.
To summarize, the hinge loss satisfies some nice properties in the sense that using the hinge loss to solve the ordinal embedding problem is not a relaxation but rather an equivalent one.


Reviews:
[{"review_id": "rkxBU7f0qH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a Neural Network based method for learning ordinal embeddings only from triplet comparisons. \nA nice, easy to read paper, with an original idea.\n\nStill, there are some issues the authors should address:\n\n- for the experiment with Imagenet images, it is not very clear how many pictures are used. Is this number 2500? \n- the authors state that they use \"the power of DNNs\" while they are experimenting with a neural network with only 4 layers. While there is no clear line between shallow and deep neural networks, I would argue that a 4 layer NN is rather shallow.\n- the authors fix the number of layers of the used network based on \"our experience\". For the sake of completeness, more experiments in this area would be nice. \n- for Figure 6, there is not a clear conclusion. While, it supports that \" that logarithmic growth of the layer width respect to n is enough to obtain desirable performance.\"  I don't see a clear conclusion of how to pick the width of hidden layers, maybe a better representation could be used.\n- I don't see a discussion about the downsides of the method (for example, the large number of triplet comparison examples needed for training; and possible methods to overcome this problem).\n- in section 4.4 when comparing the proposed approach with another methods why not use more complex datasets (like those used in section 4.3)\n- in section 4.3, there is no guarantee that the intersection between the training set and test set is empty. \n- in section 4.3 how is the reconstruction built (Figure 3b)?\n\nA few typos found:\n- In figure 3 (c) \"number |T of input\" should be  \"number |T| of input\"\n- In figure 5 (a) \"cencept\" should be \"concept\"\n- In figure 8 \"Each column corresponds to ...\" should be \"Each row corresponds to ...\".\n- In the last paragraph of A1 \"growth of the layer width respect\" should be \"growth of the layer width with respect\"\n- In the second paragraph of A2 \"hypothesize the that relation\" should be \"hypothesize that the relation\".\n- In section 4.3 last paragraph, first sentence: \"with the maximunm number\" should be \"with the maximum number\"\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rkgfiCmT5r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nMany prior works have found that the features output by the final layer of neural networks can often be used as informative representations for many tasks despite being trained for one in particular. These feature representations, however, are learned transformations of low-level input representations, e.g. RGB values of an image. In this paper, they aim to learn useful feature representations without meaningful low-level input representations, e.g. just an instance ID. Instead, meaningful representations are learned through gathered triplet comparisons of these IDs, e.g. is instance A more similar to instance B or instance C? Similar existing techniques fall in the realm of learning ordinal embeddings, but this technique demonstrates speed-ups that allow it to scale to large real world datasets.\n\nThe two primary contributions of the paper are given as:\n- a showcase of the power of neural networks as a tool to approximately solve NP-hard optimization problems with discrete inputs\n- a scalable approach for the ordinal embedding problem\n\nAfter experimentation on synthetic data, they compare the effectiveness of their proposed method Ordinal Embedding Neural Network (OENN) against the baseline techniques of Local Ordinal Embedding (LOE) and t-distributed Stochastic Triplet Embedding (TSTE). The test error given by the systems is comparable, but there are clear speed benefits to the proposed method OENN as the other techniques could not be run for a dataset size of 20k, 50k, or 100k.\n\nThen, they gathered real-world data using MTurk applied to a subset of ImageNet and applied OENN to learning embeddings of different image instances using only the MTurk triplet information rather than the input RGB input features.\n\nDecision: Weak Reject\n\n1. Interesting technique to take advantage of neural networks to efficiently learn ordinal embeddings from a set of relationships without a low-level feature representation, but I believe the experiments could be improved. One of the main advantages of this approach is efficiency, which allows it to be used on large real-world datasets. The MTurk experiment gives a qualitative picture, but it could be improved with comparisons to pairwise distances learned through alternative means using the RGB image itself (given that images would permit such a comparison). By this I mean, that you may be able to use relationships learned using conventional triplet methods which use input RGB features as ground truth, and test your learned relationships against those. However, since quantitative exploration of large real-world datasets may be challenging and expensive to collect, the synthetic experiments could have been more detailed. The message of synthetic experiments would be stronger if more of them were available and if the comparison between LOE, TSTE, and OENN was made on more of them.\n\n2. I think that the claim that the use of neural networks with discrete inputs can approximately solve NP-hard optimization problems is an exciting one, which likely necessitates more experiments (or theoretical results), but as it stands I don't think it is a fundamentally different conclusion from the fact that this method provides a great scalable solution for the ordinal embedding problem. This claim can be made secondarily or as motivation for continued exploration along this direction, but I think listing them as two distinct contributions is necessary.\n\nAdditional feedback:\n\nSince quantitative real-world results are challenging to obtain, improved presentation of the qualitative results would be helpful as well. You may be able to show more plots which help display the quality of the embedding space varying with the number of triplets used. For example, an additional plot after Figure 5 (b) which shows a few scatter plots of points (color coded by class) for training with different numbers of collected triplets. Also, since it should be fairly easy to distinguish between cars and animals or cars and food, it may be more interesting to focus on the heat-maps from along the block diagonal of Figure 5 (a) and talk about what relationships may have been uncovered within the animal or food subsets.\n\nVery minor details:\n\nIn Figure 5, a legend indicating the relationship between color intensity and distance would be helpful.\n\nIn Figure 6 there seem to be unnecessary discrepancies between the y-axis and colorbar of subplots (a) and (b), and keeping those more consistent would improve readability.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HygLj-cG9B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a way to learn a vectorial representation for items which are only described by triplet similiarity expressions.\n\nThe paper not only claims 'large scale representation learning' but also utilizing the described idea to use neural networks to \"directly, approximately solve non-convex NP-hard optimization problems that arise naturally in unsupervised learning problems.\" Both claims are not really shown in the paper: (i) The experiments are not large scale and (ii)  it becomes not clear how any substantiate insight with respect to NP-hard problems can be gained here apart from the fact that it tackles a ML problem, which many seem to be computationally hard problems.\n\nAs such the paper is not convincing. On a more detailed level it is not clear why the log n representation for items is choosen -- why not just map to embeddings directly? The more interesting question of how to generalize to unseen items (how would that be possible given that items have no representation at all) is not discussed at all and seems not to be realizable, which makes the starting point of such methods (items have no representation) questionable.\n\nThe paper also misses relevant citations of similar questions from the field of (probabilistic) matrix factorization and relational learning.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxl4O3AYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to use the triplet loss as a convex relaxation of the ordinal embedding problem. The loss is solved using feed-forward neural network with the input to the network being the ids of the items encoded in binary codes. The benefit of using a deep network is to exploit its optimization capability and the parallelism on GPUs. The experiments presented in the paper include a set of simulation experiments and a real-world task.\n\nI am giving a score of 3. This work is an interesting application of deep learning, but it gives little insight as to why deep networks are able to solve the problem and how to solve ordinal embedding itself.\n\nTo elaborate, the problem is known to be NP-hard in the worst case, while the data sets used in the paper seem to have certain nice properties. It would be interesting to see how deep networks do for the hard cases. It would also be interesting to see if additional assumptions, such as the existence of clusters or separation between clusters, make ordinal embedding simpler and thus tractable. Another approach is to assume the solution to have low surrogate loss (4), and any convex solver with sufficiently large number of points is able to find such a solution. Then the question becomes how deep networks solve the particular convex optimization problem. Thinking along these directions would bring more insight and impact to both the ordinal embedding problem and optimization in deep networks.\n\none quick question:\n\nequations (3) and (4)\n--> isn't this the same as using the hinge loss to bound the zero-one loss?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors demonstrate how neural networks can be used to learn vectorial representations of a set of items given only triplet comparisons among those items.  The reviewers had some concerns regarding the scale of the experiments and strength of the conclusions:  empirically, it seemed like there should be more truly large-scale experiments considering that this is a selling point; there should have been more analysis and/or discussion of why/how the neural networks help; and the claim that deep networks are approximately solving an NP-hard problem seemed unimportant as they are routinely used for this purpose in ML problems.  With a combination of improved experiments and revised discussion/analysis, I believe a revised version of this paper could make a good submission to a future conference.
Decision: Reject