Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper presents a Neural Network based method for learning ordinal embeddings only from triplet comparisons. 
A nice, easy to read paper, with an original idea.

Still, there are some issues the authors should address:

- for the experiment with Imagenet images, it is not very clear how many pictures are used. Is this number 2500? 
- 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.
- 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. 
- 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.
- 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).
- 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)
- in section 4.3, there is no guarantee that the intersection between the training set and test set is empty. 
- in section 4.3 how is the reconstruction built (Figure 3b)?

A few typos found:
- In figure 3 (c) "number |T of input" should be  "number |T| of input"
- In figure 5 (a) "cencept" should be "concept"
- In figure 8 "Each column corresponds to ..." should be "Each row corresponds to ...".
- In the last paragraph of A1 "growth of the layer width respect" should be "growth of the layer width with respect"
- In the second paragraph of A2 "hypothesize the that relation" should be "hypothesize that the relation".
- In section 4.3 last paragraph, first sentence: "with the maximunm number" should be "with the maximum number"

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: Summary:

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.

The two primary contributions of the paper are given as:
- a showcase of the power of neural networks as a tool to approximately solve NP-hard optimization problems with discrete inputs
- a scalable approach for the ordinal embedding problem

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

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

Decision: Weak Reject

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

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

Additional feedback:

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

Very minor details:

In Figure 5, a legend indicating the relationship between color intensity and distance would be helpful.

In 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.
review_title: Official Blind Review #4

final_score: rating: 1: Reject
review_content: The paper presents a way to learn a vectorial representation for items which are only described by triplet similiarity expressions.

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

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

The paper also misses relevant citations of similar questions from the field of (probabilistic) matrix factorization and relational learning.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 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.

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

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

one quick question:

equations (3) and (4)
--> isn't this the same as using the hinge loss to bound the zero-one loss?

review_title: Official Blind Review #1

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