summaries: 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. Many 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.
abstractText: 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.
references.authors: S. Agarwal J. Wills L. Cayton G. Lanckriet D. Kriegman S. Belongie
references.title: Generalized nonmetric multidimensional scaling
references.venue: In AISTATS, pp
references.authors: Guillermo Aguilar Felix A Wichmann Marianne Maertens
references.title: Comparing sensitivity estimates from MLDS and forced-choice methods in a slant-from-texture experiment
references.venue: J. Vis.,
references.authors: E. Amid A. Ukkonen
references.title: Multiview triplet embedding: Learning attributes in multiple maps
references.venue: In ICML, pp
references.authors: Jesse Anderton Javed Aslam
references.title: Scaling up ordinal embedding: A landmark approach
references.venue: In International Conference on Machine Learning,
references.authors: Sanjeev Arora Hrishikesh Khandeparkar Mikhail Khodak Orestis Plevrakis Nikunj Saunshi
references.title: A theoretical analysis of contrastive unsupervised representation learning
references.authors: M.F. Balcan E. Vitercik C. White
references.title: Learning combinatorial functions from pairwise comparisons
references.venue: In COLT,
references.authors: Andrew R Barron
references.title: Universal approximation bounds for superpositions of a sigmoidal function
references.venue: IEEE Transactions on Information theory,
references.authors: Sean Bell Kavita Bala
references.title: Learning visual similarity for product design with convolutional neural networks
references.venue: ACM Transactions on Graphics (TOG),
references.authors: Yoshua Bengio Pascal Lamblin Dan Popovici Hugo Larochelle
references.title: Greedy layer-wise training of deep networks. In Advances in neural information processing
references.authors: Yoshua Bengio Aaron Courville Pascal Vincent
references.title: Representation learning: A review and new perspectives
references.venue: IEEE transactions on pattern analysis and machine intelligence,
references.authors: Amanda Bower Lalit Jain Laura Balzano
references.title: The landscape of non-convex quadratic feasibility
references.venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),
references.authors: De Cheng Yihong Gong Sanping Zhou Jinjun Wang Nanning Zheng
references.title: Person re-identification by multi-channel parts-based cnn with improved triplet loss function
references.venue: In Proceedings of the iEEE conference on computer vision and pattern recognition,
references.authors: Anna Choromanska Mikael Henaff Michael Mathieu Gérard Ben Arous Yann LeCun
references.title: The loss surfaces of multilayer networks
references.venue: In Artificial Intelligence and Statistics,
references.authors: J. Deng W. Dong R. Socher L.-J. Li K. Li L. Fei-Fei
references.title: ImageNet: A Large-Scale Hierarchical Image Database
references.venue: In CVPR09,
references.authors: Weifeng Ge
references.title: Deep metric learning with hierarchical triplet loss
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV),
references.authors: Ross Girshick Jeff Donahue Trevor Darrell Jitendra Malik
references.title: Rich feature hierarchies for accurate object detection and semantic segmentation
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: S. Haghiri D. Ghoshdastidar U. von Luxburg
references.title: Comparison-based nearest neighbor search
references.venue: In AISTATS,
references.authors: Siavash Haghiri Damien Garreau Ulrike Luxburg
references.title: Comparison-based random forests
references.venue: In International Conference on Machine Learning,
references.authors: Siavash Haghiri Felix Wichmann Ulrike von Luxburg
references.title: Estimation of perceptual scales using ordinal embedding
references.venue: arXiv preprint arXiv:1908.07962,
references.authors: Geoffrey E Hinton Ruslan R Salakhutdinov
references.title: Using deep belief nets to learn covariance kernels for gaussian processes
references.venue: In Advances in neural information processing systems,
references.authors: Geoffrey E Hinton Simon Osindero Yee-Whye Teh
references.title: A fast learning algorithm for deep belief nets
references.venue: Neural computation,
references.authors: Elad Hoffer Nir Ailon
references.title: Deep metric learning using triplet network
references.venue: In International Workshop on Similarity-Based Pattern Recognition,
references.authors: Lalit Jain Kevin G Jamieson Rob Nowak
references.title: Finite sample prediction and recovery bounds for ordinal embedding
references.venue: In NIPS,
references.authors: Kenji Kawaguchi Yoshua Bengio
references.title: Depth with nonlinearity creates no bad local minima in resnets
references.venue: Neural Networks,
references.authors: Kenji Kawaguchi Jiaoyang Huang Leslie Pack Kaelbling
references.title: Effect of depth and width on local minima in deep learning
references.venue: Neural computation,
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: arXiv preprint arXiv:1412.6980,
references.authors: M. Kleindessner U. von Luxburg
references.title: Uniqueness of ordinal embedding
references.venue: In COLT,
references.authors: Matthias Kümmerer Lucas Theis Matthias Bethge
references.title: Deep gaze i: Boosting saliency prediction with feature maps trained on imagenet
references.venue: arXiv preprint arXiv:1411.1045,
references.authors: Moshe Leshno Vladimir Ya Lin Allan Pinkus Shimon Schocken
references.title: Multilayer feedforward networks with a nonpolynomial activation function can approximate any function
references.venue: Neural networks,
references.authors: Lajanugen Logeswaran Honglak Lee
references.title: An efficient framework for learning sentence representations
references.venue: arXiv preprint arXiv:1803.02893,
references.authors: Jonathan Long Evan Shelhamer Trevor Darrell
references.title: Fully convolutional networks for semantic segmentation
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Thomas Mensink Jakob Verbeek Florent Perronnin Gabriela Csurka
references.title: Metric learning for large scale image classification: Generalizing to new classes at near-zero cost
references.venue: In European Conference on Computer Vision,
references.authors: Tomas Mikolov Ilya Sutskever Kai Chen Greg S Corrado Jeff Dean
references.title: Distributed representations of words and phrases and their compositionality
references.venue: In Advances in neural information processing systems,
references.authors: Quynh Nguyen Matthias Hein
references.title: The loss surface of deep and wide neural networks
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Panos M Pardalos Stephen A Vavasis
references.title: Quadratic programming with one negative eigenvalue is np-hard
references.venue: Journal of Global Optimization,
references.authors: Alec Radford Luke Metz Soumith Chintala
references.title: Unsupervised representation learning with deep convolutional generative adversarial networks
references.venue: arXiv preprint arXiv:1511.06434,
references.authors: Marc’Aurelio Ranzato Christopher Poultney Sumit Chopra Yann L Cun
references.title: Efficient learning of sparse representations with an energy-based model
references.venue: In Advances in neural information processing systems,
references.authors: Marc’Aurelio Ranzato Y-Lan Boureau Yann L Cun
references.title: Sparse feature learning for deep belief networks. In Advances in neural information processing
references.authors: Shaoqing Ren Kaiming He Ross Girshick Jian Sun
references.title: Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing
references.authors: Florian Schroff Dmitry Kalenichenko James Philbin
references.title: Facenet: A unified embedding for face recognition and clustering
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Y. Terada U. von Luxburg
references.title: Local ordinal embedding
references.venue: In ICML, pp
references.authors: A. Ukkonen B. Derakhshan H. Heikinheimo
references.title: Crowdsourced nonparametric density estimation using relative distances
references.venue: In HCOMP,
references.authors: L. van der Maaten K. Weinberger
references.title: Stochastic triplet embedding
references.venue: MLSP,
references.authors: Jiang Wang Yang Song Thomas Leung Chuck Rosenberg Jingbin Wang James Philbin Bo Chen Ying Wu
references.title: Learning fine-grained image similarity with deep ranking
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Xiaolong Wang Abhinav Gupta
references.title: Unsupervised learning of visual representations using videos
references.venue: In Proceedings of the IEEE International Conference on Computer Vision, pp
references.authors: Chiyuan Zhang Samy Bengio Moritz Hardt Benjamin Recht Oriol Vinyals
references.title: Understanding deep learning requires rethinking generalization
references.venue: arXiv preprint arXiv:1611.03530,
sections.heading: 1 INTRODUCTION
sections.text: It has been widely recognized that deep neural networks (DNN) provide a powerful tool for representation learning (Bengio et al., 2013). Representations learned in an unsupervised fashion have been demonstrated to be useful in learning tasks such as classification (Ranzato et al., 2007; 2008; Hinton & Salakhutdinov, 2008; Hinton et al., 2006; Bengio et al., 2007). In the context of supervised learning, representations are typically learned as by-products in neural networks (Radford et al., 2015). For example in image classification, low level representations of inputs (e.g., rgb values) are fed to a network, together with class label information, the network is trained to perform some supervised classification. As a by-product it discovers a condensed data representation in the last hidden layers of the network that turns out to be surprisingly successful for other computer vision tasks such as object detection or semantic segmentation (Girshick et al., 2014; Kü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., 2012; Bell & Bala, 2015; Schroff et al., 2015). Again the raw data is fed to a network, this time together with some information about the similarity of objects, and then the network is trained to generate a meaningful data representation.
  Particularly relevant to our work is the field of contrastive representation learning (Wang et al., 2014; Hoffer & Ailon, 2015; Cheng et al., 2016; Ge, 2018; Arora et al., 2019), where similarity information is provided in terms of contrastive triplets of points (x, x+, x−): for a given point x, the point x+ and x− are specifically chosen data points that are similar / dissimilar to x. Such approaches have been extremely successful on image and text data, and they are particularly elegant if 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, 2015) where pairs of image patches in subsequent frames of videos are considered similar.
  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 in cases where no meaningful input representation or explicit similarity information exists. Instead we assume that we are provided with the answers to a set of general triplet comparisons where, for any arbitrary triplet of items (xi, xj , xk), we know whether xi is more similar to xj or xk. The problem of learning a 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 a large set of movies. There does not exist an obvious informative low level representation that can be used in a straight forward manner in a neural net, yet one can ask triplet comparisons from users of a movie database. An example of a triplet comparison on movies in shown in Figure 1a. Other use-cases also arise in more scientific contexts. For example, psychophysical scaling aims to find the functional relation of a physical stimulus and human perception. For example, Aguilar et al. (2017) conducted experiments with triplet comparisons to find out the relation between the angle of a tilted plane and the perceived angle of a human observer. In this study, a number of triplet questions are asked from human observers (see an example of triplet question in Figure 1b). Later, a one-dimensional embedding (representation) is learned for the perceived value of angle. A comprehensive study on the application of ordinal embedding in psychophysics is available at Haghiri et al. (2019).
  We design a novel neural network architecture that can learn representations when we are 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 network 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 various 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 in practice”.
  In machine learning, this line of thinking is particularly interesting for unsupervised learning problems such as clustering, dimensionality reduction or representation learning, where the typical objective 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 our paper we demonstrate that DNNs can be successfully applied to such a problem. It will be interesting to see how more generic 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 to 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).
sections.heading: 2 BACKGROUND ON COMPARISON-BASED MACHINE LEARNING AND ORDINAL EMBEDDING
sections.text: Assume we are given a set of abstract items X = {x1, x2, . . . , xn}, but no explicit representation is available for the items. Even though there exists a dissimilarity function δ(., .) 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 xi more similar to item xj or item xk? We denote such a triplet question by t = (xi, xj , xk) (or sometimes just by t = (i, j, k)), and the answer to this triplet question by
  Rt = { 1, if xi is more similar to xj than to xk −1, if xi is more similar to xk than to xj
  (1)
  Machine learning based on such qualitative comparisons has become popular (Agarwal et al., 2007; van der Maaten & Weinberger, 2012; Amid & Ukkonen, 2015; Ukkonen et al., 2015; Balcan et 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 = {t1, t2, . . . tm} is given to us. We consider the passive setting where we do not have any influence on 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 a d-dimensional representation y1, y2, . . . yn ∈ Rd such that the Euclidean distances between these points satisfy as many triplet answers as possible. This can be expressed by the following optimization problem:
  max y1,...,yn∈Rd ∑ t=(i,j,k)∈T Rt · sign(‖yi − yj‖2 − ‖yi − yk‖2). (2)
  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; Pardalos & Vavasis, 1991). 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 & Weinberger, 2012) and local ordinal embedding (LOE; Terada & von Luxburg, 2014) are among the methods in this category. However, all of them are computationally very demanding, and none of these methods can scale beyond a few thousand 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 a 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.
  The performance of ordinal embedding methods is typically evaluated by the triplet error. Given an estimated representation {ŷ1, ŷ2, . . . , ŷn} of the data items and a set T ′ of triplet answers, the triplet error simply counts how many triplet answers are satisfied by the given representation:
  triplet error (TE) = 1 |T ′| ∑ t=(i,j,k)∈T ′ 1 [ Rt · sign(‖ŷi − ŷj‖2 > ‖ŷi − ŷk‖2) = −1 ] , (3)
  where 1(·) equals to one, if the inside expression is true and it is zero otherwise. Note that Rt · sign(‖ŷi − ŷj‖2 > ‖ŷi − ŷk‖2) = −1 if the estimated embedding is not consistent with the triplet t. Thus, we count the ratio of non-consistent triplets in this way.
sections.heading: 3 PROPOSED METHOD: ORDINAL EMBEDDING NEURAL NETWORK (OENN)
sections.text: Our proposed architecture is inspired by the recent line of work on contrastive learning (Wang et al., 2014; Schroff et al., 2015; Cheng et al., 2016; Hoffer & Ailon, 2015). Figure 2a 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 a certain encoding of a single data point xi as input (typically, an encoding of its index i, see below) and outputs a d-dimensional representation ŷi of data point xi. The EmbNet is replicated three times with shared (identical) parameters. The overall OENN network now takes the indices (i, j, k) corresponding to a triplet (xi, xj , xk) as an input. It routes each of the indices i, j, k to one of the copies of the EmbNet, which then return the d-dimensional representations ŷi, ŷj , ŷk, respectively (cf. Figure 2a).
  The three sub-modules are trained jointly using the triplet hinge loss, as described by the following objective function:
  L(t = (i, j, k), Rt) = 1 |T | ∑
  t=(i,j,k)∈T
  max (−Rt(‖ŷi − ŷj‖ − ‖ŷi − ŷk‖) + 1, 0) (4)
  Choice of input representation (encoding): Since we don’t have access to any informative lowlevel input representations, the choice of input representations presents a challenge to this approach. However, we leverage the expressive power of neural networks (Leshno et al., 1993; Barron, 1993) and their ability to (for instance) fit random labels to random inputs (Zhang et al., 2016) to motivate our choice of input encoding. Since our main goal is to 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 i is encoded by a string x̂i of length n such that x̂i(l) = 1 if l = i and 0 otherwise). The advantage of choosing such a representation is that it is memory efficient in the sense that there is no 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 of our work is to perform ordinal embedding in large scales, we consider a more efficient way: we represent each item by the binary code of its index, leading to a representation length of log n. Such a representation retains the memory efficiency of the one-hot encoding (in the sense as 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 n (see subsection 4.1). 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 Rdlogne 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 dlog ne and each hidden layer contains w nodes. The output layer has d nodes to produce embeddings in Rd. The input and output size, dlog ne and d, are pre-determined by the task. Thus the only independent parameter of the network is the width w 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 n 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 differences 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 x1, .., xn. 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 (x, x+, 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.
sections.heading: 4 SIMULATIONS
sections.text: We run an extensive set of simulations, on the one hand to find good rules of thumb to set our hyperparameters and input encoding, and on the other hand to evaluate the performance of the OENN in terms of triplet error and compare it to alternative ordinal embedding approaches.
sections.heading: 4.1 CHOICE OF HYPER-PARAMETERS.
sections.text: Our neural network model consists of a single hyper-parameter, the width of the hidden layers w. We ran simulations to inform our choice of w based on the number of input items n and the embedding 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.
sections.heading: 4.2 CHOICE OF THE LENGTH OF INPUT ENCODING.
sections.text: The input to the OENN, as 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 our supplementary.
sections.heading: 4.3 RECONSTRUCTION AND GENERALIZATION TO UNSEEN TRIPLETS
sections.text: To demonstrate the capacity of OENNs to reconstruct the true embedding1, we use three 2- dimensional datasets generated with the scikit-learn package in Python. Datasets are shown in Figure 3a: 1- two-moons dataset with two labels, 2- Blobs dataset, which is a mixture of three Gaussians, and 3- concentric circles with 2 labels. In all three cases 1000 items are generated. The label information is added to check the reconstruction capability visually.
  The number of input triplets to the embedding algorithm is chosen around nd log n ≈ 20000, which is 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 (TEtrain) and test triplet error (TEtest). We generate 1000 triplet answers as 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 TEtrain on top of each plot. In case of all three datasets, we 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 in Figure 3c. The training error 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 as 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.
sections.heading: 4.4 COMPARISON WITH OTHER ORDINAL EMBEDDING METHODS
sections.text: 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. In this section we perform a simple simulation with increasing number of items. The items are sampled from a uniform distribution on the unit square in R2. In a first simu-
  1It has been theoretically shown that an ordinal embedding can be uniquely determined up to an isometric transform — if the items are sampled from a compact subset of the Euclidean space and the number of items grows to infinity (Kleindessner & von Luxburg, 2014)
  2000 4000 6000 800010000 Number of items (n)
  0.00
  0.01
  0.02
  0.03
  0.04
  0.05
  0.06
  0.07
  0.08
  Tr ai ni ng
  e rro
  r
  OENN TSTE LOE
  2e4 5e4 1e5
  (a)
  2000 4000 6000 800010000 Number of items (n)
  0.00
  0.02
  0.04
  0.06
  0.08
  0.10
  0.12
  0.14
  Te st e rro
  r
  OENN TSTE LOE
  2e4 5e4 1e5
  (b)
  2000 4000 6000 800010000 Number of items (n)
  0
  1000
  2000
  3000
  4000
  Tr ai ni ng
  ti m e (s ec on
  ds ) OENN
  TSTE LOE
  2e4 5e4 1e5
  (c)
  Figure 4: (a) Training triplet error with varying number of items for three different ordinal embedding methods. (b) Test triplet error for varying number n of items. Note that we scale the number of input triplets as |T | = nd log n. (c) Training time (embedding time) of the three methods in 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.
  lation we compare running times for the number of items in the range n ∈ {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 is still tractable. Therefore, we run our method alone on an extended range of items: n ∈ {20000, 50000, 100000}. For a fixed set of items we generate nd log n triplet answers (d = 2) based on the Euclidean distances. The answers are fed to the ordinal embedding algorithms as input. For each set of items, we generate an independent set of 1000 triplet answers as test set. The methods are compared based on three evaluation criteria: training triplet error (TEtrain), test triplet error (TEtest), and embedding time in seconds.
  For our method, we chose a fixed hidden layer width w = 400 for n <= 10000 and w = 800 for larger n. The optimization parameters of LOE and TSTE are set to the default values. The author’s implementation of LOE in R, available at CRAN repository2, is used to perform LOE experiments. We also used the Python implementation of TSTE, available on GitHub3. Note that the Python implementation is 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 1 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 of various method in Figure 4a and Figure 4b respectively. 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 1 hour to obtain the embedding, while the OENN requires 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 1 hour, as 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.
sections.heading: 5 EXPERIMENTS
sections.text: In this section, we perform ordinal embedding on a large scale dataset of triplet answers. To obtain such a dataset, we ran a study on Amazon’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 et al., 2009) dataset. We chose the three high-level concepts ”animal”, ”food”, and
  2https://cran.r-project.org/web/packages/loe/index.html 3https://github.com/gcr/tste-theano
  ”vehicles”, and in each of these concepts we picked 5 sub-categories (”synsets”). The details of these 15 categories and of our MTurk implementation are presented in the supplementary material.
  We gathered 120000 triplet answers from the MTurk workers, which is somewhat less than the nd log n ≈ 190000 triplets that would be required for high-quality recovery according to the theoretical lower bound for an embedding in d = 2 dimensions (Jain et al., 2016).
  Figure 5a depicts the pairwise distances of embedding outputs with embedding dimension d = 2. The three clusters are clearly evident in the distance matrix. We also depict a the embedding output for a subsample of 60 images in Figure 5b. We randomly chose 4 images from each category to produce a sample of 60 images. Looking at the embedding output, we clearly see that three concepts of animals, vehicles and food are located at upper right, bottom, and upper left part of the picture respectively. There are a few exceptions as well. For instance on the very left bottom we see the shelf of a confectionery store.
sections.heading: 6 DISCUSSION
sections.text: In this paper, we propose a novel, scalable representation learning algorithm. A unique distinguishing property of our method is that it does not need any feature representation for the items — we successfully apply DNNs with a 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 to approximately solve nonconvex, NP-hard problems to obtain near optimal solutions to ordinal embedding problems. We believe that this provides a 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 a 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.
sections.heading: A APPENDIX
sections.text: A.1 DEPENDENCE BETWEEN THE LAYER WIDTH w AND THE NUMBER n OF ITEMS
  As the number n of items grows, we expect that a larger network is required to address the complexity 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 a 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 R2, and choose n points from its unit square according to the uniform distribution. We consider n ∈ {27, 28, . . . , 214}. Given a sample of n points, we generate 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 n points, and then evaluate the corresponding triplet question based on the true Euclidean distances between these points. The number of triplets is chosen based on the theoretical lower bound on 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-notation.
  The embedding network is constructed with 3 hidden layers, each having w fully-connected neurons with ReLu activation functions. The width w of the layers (= number of neurons in each layer) is chosen from w ∈ {70, 90, . . . , 170}. For a fixed network and a fixed set of triplet answers, the ordinal embedding is executed 10 times in order to examine the average behaviour of the model.
  The implementations use the ”PyTorch” open-source library. The initial weights of the hidden layers and the final embedding layer are chosen according to a uniform distribution (default initialization of PyTorch). We used Adam(Kingma & Ba, 2014) to optimize the weights of the network. The learning-rate and batch-size parameters of the Adam optimizer are chosen as 5 ∗ 10−3 and 5000, respectively.
  Figure 6a shows the training triplet error (TEtrain) of the ordinal embedding with varying number of items and width of the hidden layers. The error is reported with a heat-map plot, where warmer colors denote higher triplet error. The result shows that logarithmic growth of the layer width respect to n is enough to obtain desirable performance.
  A.2 DEPENDENCE BETWEEN LAYER WIDTH w AND EMBEDDING DIMENSION d
  Besides the number of items, the embedding dimension is another factor that influences the complexity of ordinal embedding. We expect that the required layer width needs to grow with the embedding dimension. We perform a 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 Rd. Then, we generate triplet answers to nd log 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 in d ∈ {5, 10, . . . , 40}. The width of the hidden layer is chosen in the linear range w ∈ {100, 125, . . . , 225}. The number of hidden layers, the optimization algorithm and the hyperparameters of optimization are the same as the previous subsection.
  Figure 6b shows the training triplet error (TEtrain) 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 a clear line of transition between low and high error regions. As both axes are chosen linear in this experiment, we can conclude that a linear increase in layer width with respect to the dimension is needed.
  A.3 DEPENDENCE BETWEEN THE SIZE OF THE INPUT ENCODING d′ AND THE NUMBER OF POINTS n
  Our simulations demonstrate that the size of the input encoding needs to grow logarithmically with the 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 of items as input and learns a transformation from the input encodings to vectors in Euclidean space of a dimension specified by the task. We ran simulations with binary encoding of the indices as well as with input representations of a fixed length (d′) by choosing each component of the vector uniformly at random from an arbitrary interval (we choose the interval [1, 100] in our experiments). Our simulations show that the size of the input encoding needs to grow logarithmically with increasing number of items.
  To conduct the simulations, we sampled n (ranging in { 27, 28, ..., 214 } ) data points uniformly from
  a unit square in R2. For a fixed set of n items, we generate nd log n triplet answers (where d = 2 is the dimension) according to the procedure as described in the main paper (see section 4.1). Our simulations demonstrated that choosing the width of the hidden layers at the order of log n would suffice to achieve low reconstruction error. So, we construct our 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.
  Figure7 shows the training triplet error (TEtrain) 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 8 shows the true datasets and the estimated embedding with different number of input triplets. The left column shows the true datasets. The number of input triplet is chosen in r · nd log n, where r ∈ {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 dataset as we increase the number of input triplet answers. However, the loss and the training triplet error are both almost steady. If the algorithm is provided with less triplet answers, it needs to satisfy less constraints, thus it has a 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 (TEtrain ≈ 0.03).
  A.6 EXTRA DATASETS, PATHOLOGICAL EXAMPLES
  In our three examples for the reconstruction experiment the 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 9 (right column) depicts the embedding result. The training triplet error for both experiments is still less than 2%, which shows that the solution is a valid solution.
  Regarding the quality of reconstruction, the embedding with more data points resembles a sine wave better than fewer data point. This is due to 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 a 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, a sports car cannot really be considered more similar to a dog than to a pizza or vice versa. The workers are advised to give an answer when they can see a similarity, otherwise an option was provided to declare that the comparison cannot be made.
  The triplet answers collected from workers can 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, we designed a 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 xi is in the same category with one the choices xj , while the other choice xk has a different category. If a worker has less than 70% accurate answers on these triplets, we rejected his/her work, and consequently did not 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, Confectionery, Goods wagon, Tractor, Police van, Limousine, Sport car } The larger and detailed pairwise distance matrix of two dimensional embedding is shown in Figure10
  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 = {x1, x2, .., xn} ∈ Rd that satisfies a set of given triplets, T - can be phrased as a quadratic feasibility problem (Bower et al., 2018) as shown in equation 5.
  find X subject to XTPi,j,kX > 0 ∀(i, j, k) ∈ T . (5)
  Each Pi,j,k corresponds to a triplet constraint that satisfies,
  ||xi − xj ||2 > ||xi − xk||2 ⇐⇒ XTPi,j,kX > 0
  Every feasible solution to 5 is a valid solution to the problem of ordinal embedding.
  An equivalent way to solve 5, i.e., find a feasible solution of 5 is by finding the global optima of the constrained optimization problem (Bower et al., 2018) given by 6.
  min X∈Rnd ∑ (i,j,k)∈T max { 0, 1−XTPi,j,kX } (6)
  Meaning, every feasible solution to (5) can be scaled to attain global optima of (6) and every global optima of (6) is a feasible solution of (5) (Bower et al., 2018). Moreover, in optimization (1), any positive scaling of a feasible point X is a 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.