summaries: The paper proposes a new joint learning algorithm that works for two tasks, NER and RE. The model is based on a pre-trained BERT model, which provides the word vectors of the input word sequence. Then it solves two tasks with two network branches: the first branch minimizes the loss for NER, and the second branch minimizes the loss for RE. The second branch uses entity labels predicted by the first branch, so joint learning may benefit both tasks.

summaries: The paper proposes an end-to-end joint model for named entity recognition (NER) and relation extraction (RE), using pre-trained language models. The model is very simple, with the key is to use BERT and take NER output as input to RE. The experimental results show the model, without the need for handcrafted features, get state-of-the-art results on five datasets.

abstractText: Named entity recognition (NER) and relation extraction (RE) are two important tasks in information extraction and retrieval (IE & IR). Recent work has demonstrated that it is beneficial to learn these tasks jointly, which avoids the propagation of error inherent in pipeline-based systems and improves performance. However, state-of-the-art joint models typically rely on external natural language processing (NLP) tools, such as dependency parsers, limiting their usefulness to domains (e.g. news) where those tools perform well. The few neural, end-to-end models that have been proposed are trained almost completely from scratch. In this paper, we propose a neural, end-to-end model for jointly extracting entities and their relations which does not rely on external NLP tools and which integrates a large, pre-trained language model. Because the bulk of our model’s parameters are pre-trained and we eschew recurrence for self-attention, our model is fast to train. On 5 datasets across 3 domains, our model matches or exceeds state-of-the-art performance, sometimes by a large margin.

authors:
Heike Adel
Hinrich Schütze

title: Global normalization of convolutional neural networks for joint entity and relation classification

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
Stein Aerts
Diether Lambrechts
Sunit Maity
Peter Van Loo
Bert Coessens
Frederik De Smet
Leon-Charles Tranchevent
Bart De Moor
Peter Marynen
Bassem Hassan
Peter Carmeliet
Yves Moreau

title: Gene prioritization through genomic data fusion

venue: Nature Biotechnology,

authors:
Giannis Bekoulis
Johannes Deleu
Thomas Demeester
Chris Develder

title: Joint entity recognition and relation extraction as a multi-head selection problem

venue: Expert Systems with Applications,

title: Adversarial training for multi-context joint entity and relation extraction

venue: arXiv preprint arXiv:1808.06876,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
George Doddington
Alexis Mitchell
Mark Przybocki
Lance Ramshaw
Stephanie Strassel
Ralph Weischedel

title: The automatic content extraction (ACE) program – tasks, data, and evaluation

venue: In Proceedings of the Fourth International Conference on Language Resources and Evaluation (LREC’04),

authors:
Timothy Dozat
Christopher D Manning

title: Deep biaffine attention for neural dependency parsing

venue: arXiv preprint arXiv:1611.01734,

authors:
Pankaj Gupta
Hinrich Schütze
Bernt Andrassy

title: Table filling multi-task recurrent neural network for joint entity and relation extraction

venue: In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers,

authors:
Harsha Gurulingappa
Abdul Mateen Rajput
Angus Roberts
Juliane Fluck
Martin HofmannApitius
Luca Toldo

title: Development of a benchmark corpus to support the automatic extraction of drug-related adverse effects from medical case reports

venue: Journal of Biomedical Informatics,

title: Information Extraction from Text, pp. 11–41

authors:
Jinhyuk Lee
Wonjin Yoon
Sungdong Kim
Donghyeon Kim
Sunkyu Kim
Chan Ho So
Jaewoo Kang

title: Biobert: pre-trained biomedical language representation model for biomedical text mining

authors:
Fei Li
Yue Zhang
Meishan Zhang
Donghong Ji

title: Joint models for extracting adverse drug events from biomedical text

venue: In IJCAI,

authors:
Fei Li
Meishan Zhang
Guohong Fu
Donghong Ji

title: A neural joint model for entity and relation extraction from biomedical text

venue: BMC bioinformatics,

authors:
Gang Li
Karen E. Ross
Cecilia N. Arighi
Yifan Peng
Cathy H. Wu
K. Vijay-Shanker

title: miRTex: A text mining system for miRNA-gene relation extraction

venue: PLOS Computational Biology,

authors:
Xiaoya Li
Fan Yin
Zijun Sun
Xiayu Li
Arianna Yuan
Duo Chai
Mingxin Zhou
Jiwei Li

title: Entity-relation extraction as multi-turn question answering

authors:
Ilya Loshchilov
Frank Hutter

title: Fixing weight decay regularization in adam

authors:
Riccardo Miotto
Fei Wang
Shuang Wang
Xiaoqian Jiang
Joel T Dudley

title: Deep learning for healthcare: review, opportunities and challenges

venue: Briefings in bioinformatics,

authors:
Makoto Miwa
Mohit Bansal

title: End-to-end relation extraction using lstms on sequences and tree structures

venue: arXiv preprint arXiv:1601.00770,

authors:
Makoto Miwa
Yutaka Sasaki

title: Modeling joint entity and relation extraction with table representation

venue: In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP),

authors:
Dat Quoc Nguyen
Karin Verspoor

title: End-to-end neural relation extraction using deep biaffine attention

venue: Advances in Information Retrieval,

authors:
Razvan Pascanu
Tomas Mikolov
Yoshua Bengio

title: On the difficulty of training recurrent neural networks

venue: In International Conference on Machine Learning,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in PyTorch

venue: In NIPS Autodiff Workshop,

authors:
Yifan Peng
Shankai Yan
Zhiyong Lu

title: Transfer learning in biomedical natural language processing: An evaluation of BERT and elmo on ten benchmarking

venue: URL http://arxiv.org/abs/1906.05474

authors:
Alessandro Raganato
Jörg Tiedemann

title: An analysis of encoder representations in transformerbased machine translation

venue: In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP,

authors:
Dan Roth
Wen-tau Yih

title: A linear programming formulation for global inference in natural language tasks

venue: In Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL-2004) at HLT-NAACL

authors:
Yuqi Si
Jingqi Wang
Hua Xu
Kirk Roberts

title: Enhancing clinical concept extraction with contextual embedding

authors:
Özlem Uzuner
Brett R South
Shuying Shen
Scott L DuVall

title: i2b2/va challenge on concepts, assertions, and relations in clinical text

venue: Journal of the American Medical Informatics Association,

title: A multiscale visualization of attention in the transformer model

authors:
Zhong-Yi Wang
Hong-Yu Zhang

title: Rational drug repositioning by medical genetics

authors:
Zhilin Yang
Zihang Dai
Yiming Yang
Jaime Carbonell
Ruslan Salakhutdinov
Quoc V Le

title: Xlnet: Generalized autoregressive pretraining for language understanding

authors:
Meishan Zhang
Yue Zhang
Guohong Fu

title: End-to-end neural relation extraction with global optimization

authors:
XueZhong Zhou
Jrg Menche
Albert-László Barabási
Amitabh Sharma

title: Human symptoms–disease network

venue: Nature Communications,

heading: 1 INTRODUCTION

text:
The extraction of named entities (named entity recognition, NER) and their semantic relations (relation extraction, RE) are key tasks in information extraction and retrieval (IE & IR). Given a sequence of text (usually a sentence), the objective is to identify both the named entities and the relations between them. This information is useful in a variety of NLP tasks such as question answering, knowledge base population, and semantic search (Jiang, 2012). In the biomedical domain, NER and RE facilitate large-scale biomedical data analysis, such as network biology (Zhou et al., 2014), gene prioritization (Aerts et al., 2006), drug repositioning (Wang & Zhang, 2013) and the creation of curated databases (Li et al., 2015). In the clinical domain, NER and RE can aid in disease and treatment prediction, readmission prediction, de-identification, and patient cohort identification (Miotto et al., 2017).
Most commonly, the tasks of NER and RE are approached as a pipeline, with NER preceding RE. There are two main drawbacks to this approach: (1) Pipeline systems are prone to error propagation between the NER and RE systems. (2) One task is not able to exploit useful information from the other (e.g. the type of relation identified by the RE system may be useful to the NER system for determining the type of entities involved in the relation, and vice versa). More recently, joint models that simultaneously learn to extract entities and relations have been proposed, alleviating the aforementioned issues and achieving state-of-the-art performance (Miwa & Sasaki, 2014; Miwa & Bansal, 2016; Gupta et al., 2016; Li et al., 2016; 2017; Zhang et al., 2017; Adel & Schütze, 2017; Bekoulis et al., 2018a;b; Nguyen & Verspoor, 2019; Li et al., 2019).
Many of the proposed joint models for entity and relation extraction rely heavily on external natural language processing (NLP) tools such as dependency parsers. For instance, Miwa & Bansal (2016) propose a recurrent neural network (RNN)-based joint model that uses a bidirectional long-short term memory network (BiLSTM) to model the entities and a tree-LSTM to model the relations between entities; Li et al. (2017) propose a similar model for biomedical text. The tree-LSTM uses dependency tree information extracted using an external dependency parser to model relations between entities. The use of these external NLP tools limits the effectiveness of a model to domains
(e.g. news) where those NLP tools perform well. As a remedy to this problem, Bekoulis et al. (2018a) proposes a neural, end-to-end system that jointly learns to extract entities and relations without relying on external NLP tools. In Bekoulis et al. (2018b), they augment this model with adversarial training. Nguyen & Verspoor (2019) propose a different, albeit similar end-to-end neural model which makes use of deep biaffine attention (Dozat & Manning, 2016). Li et al. (2019) approach the problem with multi-turn question answering, posing templated queries to a BERT-based QA model (Devlin et al., 2018) whose answers constitute extracted entities and their relations and achieve state-of-the-art results on three popular benchmark datasets.
While demonstrating strong performance, end-to-end systems like Bekoulis et al. (2018a;b) and Nguyen & Verspoor (2019) suffer from two main drawbacks. The first is that most of the models parameters are trained from scratch. For large datasets, this can lead to long training times. For small datasets, which are common in the biomedical and clinical domains where it is particularly challenging to acquire labelled data, this can lead to poor performance and/or overfitting. The second is that these systems typically contain RNNs, which are sequential in nature and cannot be parallelized within training examples. The multi-pass QA model proposed in Li et al. (2019) alleviates these issues by incorporating a pre-trained language model, BERT (Devlin et al., 2018), which eschews recurrence for self-attention. The main limitation of their approach is that it relies on handcrafted question templates to achieve maximum performance. This may become a limiting factor where domain expertise is required to craft such questions (e.g., for biomedical or clinical corpora). Additionally, one has to create a question template for each entity and relation type of interest.
In this study, we propose an end-to-end model for joint NER and RE which addresses all of these issues. Similar to past work, our model can be viewed as a mixture of a NER module and a RE module (Figure 1). Unlike most previous works, we include a pre-trained, transformer-based language model, specifically BERT (Devlin et al., 2018), which achieved state-of-the-art performance across many NLP tasks. The weights of the BERT model are fine-tuned during training, and the entire model is trained in an end-to-end fashion.
Our main contributions are as follows: (1) Our solution is truly end-to-end, relying on no handcrafted features (e.g. templated questions) or external NLP tools (e.g. dependency parsers). (2) Our model is fast to train (e.g. under 10 minutes on a single GPU for the CoNLL04 corpus), as most of its parameters are pre-trained and we avoid recurrence. (3) We match or exceed state-of-the-art performance for joint NER and RE on 5 datasets across 3 domains.

heading: 2 THE MODEL

text:
Figure 1 illustrates the architecture of our approach. Our model is composed of an NER module and an RE module. The NER module is identical to the one proposed by Devlin et al. (2018). For a given input sequence s of N word tokens w1, w2, . . ., wN , the pre-trained BERTBASE model first produces a sequence of vectors, x(NER)1 , x (NER) 2 , . . ., x (NER) N which are then fed to a feed-forward neural network (FFNN) for classification.
s (NER) i = FFNNNER(x (NER) i ) (1)
The output size of this layer is the number of BIOES-based NER labels in the training data, |C(NER)|. In the BIOES tag scheme, each token is assigned a label, where the B- tag indicates the beginning of an entity span, I- the inside, E- the end and S- is used for any single-token entity. All other tokens are assigned the label O.
During training, a cross-entropy loss is computed for the NER objective,
LNER = − N∑
n=1
log
( es
(NER) n∑C(NER)
c e s(NER)n,c
) (2)
where s(NER)n is the predicted score that token n ∈ N belongs to the ground-truth entity class and s (NER) n,c is the predicted score for token n belonging to the entity class c ∈ C(NER).
In the RE module, the predicted entity labels are obtained by taking the argmax of each score vector s (NER) 1 , s (NER) 2 , . . ., s (NER) N . The predicted entity labels are then embedded to produce a sequence of fixed-length, continuous vectors, e(NER)1 , e (NER) 2 , . . ., e (NER) N which are concatenated with the hidden states from the final layer in the BERT model and learned jointly with the rest of the models parameters.
x (RE) i = x (NER) i ‖ e (NER) i (3)
Following Miwa & Bansal (2016) and Nguyen & Verspoor (2019), we incrementally construct the set of relation candidates, R, using all possible combinations of the last word tokens of predicted entities, i.e. words with E- or S- labels. An entity pair is assigned to a negative relation class (NEG) when the pair has no relation or when the predicted entities are not correct. Once relation candidates are constructed, classification is performed with a deep bilinear attention mechanism (Dozat & Manning, 2016), as proposed by Nguyen & Verspoor (2019).
To encode directionality, the mechanism uses FFNNs to project each x(RE)i into head and tail vector representations, corresponding to whether the ith word serves as head or tail argument of the relation.
h (head) i = FFNNhead(x (RE) i ) (4)
h (tail) i = FFNNtail(x (RE) i ) (5)
These projections are then fed to a biaffine classifier,
s (RE) j,k = Biaffine(h (head) j ,h (tail) k ) (6)
Biaffine(x1,x2) = xT1 Ux2 + W (x1 ‖ x2) + b (7)
where U is an m×|C(RE)|×m tensor, W is a |C(RE)|× (2∗m) matrix, and b is a bias vector. Here, m is the size of the output layers of FFNNhead and FFNNtail andC(RE) is the set of all relation classes (including NEG). During training, a second cross-entropy loss is computed for the RE objective
LRE = − R∑
r=1
log
( es
(RE) r∑C(RE)
c e s(RE)r,c
) (8)
where s(RE)r is the predicted score that relation candidate r ∈ R belongs to the ground-truth relation class and s(RE)r,c is the predicted score for relation r belonging to the relation class c ∈ C(RE). The model is trained in an end-to-end fashion to minimize the sum of the NER and RE losses.
L = LNER + LRE (9)

heading: 2.1 ENTITY PRETRAINING

text:
In Miwa & Bansal (2016), entity pre-training is proposed as a solution to the problem of lowperformance entity detection in the early stages of training. It is implemented by delaying the training of the RE module by some number of epochs, before training the entire model jointly.
Our implementation of entity pretraining is slightly different. Instead of delaying training of the RE module by some number of epochs, we weight the contribution of LRE to the total loss during the first epoch of training
L = LNER + λ LRE (10)
where λ is increased linearly from 0 to 1 during the first epoch and set to 1 for the remaining epochs. We chose this scheme because the NER module quickly achieves good performance for all datasets (i.e. within one epoch). In early experiments, we found this scheme to outperform a delay of a full epoch.

heading: 2.2 IMPLEMENTATION

text: We implemented our model in PyTorch (Paszke et al., 2017) using the BERTBASE model from the PyTorch Transformers library1. Our model is available at our GitHub repository2. Furthermore, we use NVIDIAs automatic mixed precision (AMP) library Apex3 to speed up training and reduce memory usage without affecting task-specific performance.

heading: 3 EXPERIMENTAL SETUP

heading: 3.1 DATASETS AND EVALUATION

text: To demonstrate the generalizability of our model, we evaluate it on 5 commonly used benchmark corpora across 3 domains. All corpora are in English. Detailed corpus statistics are presented in Table A.1 of the appendix.

heading: 3.1.1 ACE04/05

text:
The Automatic Content Extraction (ACE04) corpus was introduced by Doddington et al. (2004), and is commonly used to benchmark NER and RE methods. There are 7 entity types and 7 relation types. ACE05 builds on ACE04, splitting the Physical relation into two classes (Physical and PartWhole), removing the Discourse relation class and merging Employment-Membership-Subsidiary and Person-Organization-Affiliation into one class (Employment-Membership-Subsidiary).
For ACE04, we follow Miwa & Bansal (2016) by removing the Discourse relation and evaluating our model using 5-fold cross-validation on the bnews and nwire subsets, where 10% of the data was held out within each fold as a validation set. For ACE05, we use the same test split as Miwa & Bansal (2016). We use 5-fold cross-validation on the remaining data to choose the hyperparameters. Once hyperparameters are chosen, we train on the combined data from all the folds and evaluate on the test set. For both corpora, we report the micro-averaged F1 score. We obtained the pre-processing scripts from Miwa & Bansal (2016)4.
1https://github.com/huggingface/pytorch-transformers 2to-add-to-camera-ready-version 3https://github.com/NVIDIA/apex 4https://github.com/tticoin/LSTM-ER/tree/master/data

heading: 3.1.2 CONLL04

text:
The CoNLL04 corpus was introduced in Roth & Yih (2004) and consists of articles from the Wall Street Journal (WSJ) and Associated Press (AP). There are 4 entity types and 5 relation types.
We use the same test set split as Miwa & Sasaki (2014)5. We use 5-fold cross-validation on the remaining data to choose hyperparameters. Once hyperparameters are chosen, we train on the combined data from all folds and evaluate on the test set, reporting the micro-averaged F1 score.

heading: 3.1.3 ADE

text:
The adverse drug event corpus was introduced by Gurulingappa et al. (2012) to serve as a benchmark for systems that aim to identify adverse drug events from free-text. It consists of the abstracts of medical case reports retrieved from PubMed6. There are two entity types, Drug and Adverse effect and one relation type, Adverse drug event.
Similar to previous work (Li et al., 2016; 2017; Bekoulis et al., 2018b), we remove ∼130 relations with overlapping entities and evaluate our model using 10-fold cross-validation, where 10% of the data within each fold was used as a validation set, 10% as a test set and the remaining data is used as a train set. We report the macro F1 score averaged across all folds.

heading: 3.1.4 I2B2

text:
The 2010 i2b2/VA dataset was introduced by Uzuner et al. (2011) for the 2010 i2b2/Va Workshop on Natural Language Processing Challenges for Clinical Records. The workshop contained an NER task focused on the extraction of 3 medical entity types (Problem, Treatment, Test) and an RE task for 8 relation types.
In the official splits, the test set contains roughly twice as many examples as the train set. To increase the number of training examples while maintaining a rigorous evaluation, we elected to perform 5- fold cross-validation on the combined data from both partitions. We used 10% of the data within each fold as a validation set, 20% as a test set and the remaining data was used as a train set. We report the micro F1 score averaged across all folds.
To the best of our knowledge, we are the first to evaluate a joint NER and RE model on the 2010 i2b2/VA dataset. Therefore, we decided to compare to scores obtained by independent NER and RE systems. We note, however, that the scores of independent RE systems are not directly comparable to the scores we report in this paper. This is because RE is traditionally framed as a sentence-level classification problem. During pre-processing, each example is permutated into processed examples containing two “blinded” entities and labelled for one relation class. E.g. the example: “His PCP had recently started ciprofloxacinTREATMENT for a UTIPROBLEM” becomes “His PCP had recently started @TREATMENT$ for a @PROBLEM$”, where the model is trained to predict the target relation type, “Treatment is administered for medical problem” (TrAP).
This task is inherently easier than the joint setup, for two reasons: relation predictions are made on ground-truth entities, as opposed to predicted entities (which are noisy) and the model is only required to make one classification decision per pre-processed sentence. In the joint setup, a model must identify any number of relations (or the lack thereof) between all unique pairs of predicted entities in a given input sentence. To control for the first of these differences, we report scores from our model in two settings, once when predicted entities are used as input to the RE module, and once when ground-truth entities are used.

heading: 3.2 HYPERPARAMETERS

text:
Besides batch size, learning rate and number of training epochs, we used the same hyperparameters across all experiments (see Table A.2). Similar to Devlin et al. (2018), learning rate and batch size were selected for each dataset using a minimal grid search (see See Table A.3).
5https://github.com/pgcool/TF-MTRNN/tree/master/data/CoNLL04 6https://www.ncbi.nlm.nih.gov/pubmed
One hyperparameter selected by hand was the choice of the pre-trained weights used to initialize the BERTBASE model. For general domain corpora, we found the cased BERTBASE weights from Devlin et al. (2018) to work well. For biomedical corpora, we used the weights from BioBERT (Lee et al., 2019), which recently demonstrated state-of-the-art performance for biomedical NER, RE and QA. Similarly, for clinical corpora we use the weights provided by Peng et al. (2019), who pre-trained BERTBASE on PubMed abstracts and clinical notes from MIMIC-III7.

heading: 4 RESULTS

heading: 4.1 JOINTLY LEARNING NER AND RE

text:
Table 1 shows our results in comparison to previously published results, grouped by the domain of the evaluated corpus. We find that on every dataset besides i2b2, our model improves NER performance, for an average improvement of ∼2%. This improvement is particularly large on the ACE04 and ACE05 corpora (3.98% and 2.41% respectively). On i2b2, our joint model performs within 0.29% of the best independent NER solution.
For relation extraction, we outperform previous methods on 2 datasets and come within ∼2% on both ACE05 and CoNLL04. In two cases, our performance improvement is substantial, with improvements of 4.59% and 10.25% on the ACE04 and ADE corpora respectively. For i2b2, our score is not directly comparable to previous systems (as discussed in section 3.1.4) but will facilitate future comparisons of joint NER and RE methods on this dataset. By comparing overall performance, we find that our approach achieves new state-of-the-art performance for 3 popular benchmark datasets (ACE04, ACE05, ADE) and comes within 0.2% for CoNLL04.

heading: 4.2 ABLATION ANALYSIS

text:
To determine which training strategies and components are responsible for our models performance, we conduct an ablation analysis on the CoNLL04 corpus (Table 2). We perform five different ablations: (a) Without entity pre-training (see section 2.1), i.e. the loss function is given by equation 9. (b) Without entity embeddings, i.e. equation 3 becomes x(RE)i = x (NER) i . (c) Replacing the two feed-forward neural networks, FFNNhead and FFNNtail with a single FFNN (see equation 4 and 5). (d) Removing FFNNhead and FFNNtail entirely. (e) Without the bilinear operation, i.e. equation 7 becomes a simple linear transformation.
Removing FFNNhead and FFNNtail has, by far, the largest negative impact on performance. Interestingly, however, replacing FFNNhead and FFNNtail with a single FFNN has only a small negative impact. This suggests that while these layers are very important for model performance, using distinct FFNNs for the projection of head and tail entities (as opposed to the same FFNN) is relatively much less important. The next most impactful ablation was entity pre-training, suggesting that low-performance entity detection during the early stages of training is detrimental to learning (see section 2.1). Finally, we note that the importance of entity embeddings is surprising, as a previous study has found that entity embeddings did not help performance on the CoNLL04 corpus (Bekoulis et al., 2018a), although their architecture was markedly different. We conclude that each of our ablated components is necessary to achieve maximum performance.

heading: 4.3 ANALYSIS OF THE WORD-LEVEL ATTENTION WEIGHTS

text:
One advantage of including a transformer-based language model is that we can easily visualize the attention weights with respect to some input. This visualization is useful, for example, in detecting model bias and locating relevant attention heads (Vig, 2019). Previous works have used such visualizations to demonstrate that specific attention heads mark syntactic dependency relations and that lower layers tend to learn more about syntax while higher layers tend to encode more semantics (Raganato & Tiedemann, 2018).
In Figure 2 we visualize the attention weights of select layers and attention heads from an instance of BERT fine-tuned within our model on the CoNLL04 corpus. We display four patterns that are easily
7https://mimic.physionet.org/
interpreted: paying attention to the next and previous words, paying attention to the word itself, and paying attention to the end of the sentence. These same patterns have been found in pre-trained BERT models that have not been fine-tuned on a specific, supervised task (Vig, 2019; Raganato & Tiedemann, 2018), and therefore, are retained after our fine-tuning procedure.
To facilitate further analysis of our learned model, we make available Jupyter and Google Colaboratory notebooks on our GitHub repository8, where users can use multiple views to explore the learned attention weights of our models. We use the BertViz library (Vig, 2019) to render the interactive, HTML-based views and to access the attention weights used to plot the heat maps.

heading: 5 DISCUSSION AND CONCLUSION

text:
In this paper, we introduced an end-to-end model for entity and relation extraction. Our key contributions are: (1) No reliance on any hand-crafted features (e.g. templated questions) or external NLP tools (e.g. dependency parsers). (2) Integration of a pre-trained, transformer-based language model. (3) State-of-the-art performance on 5 datasets across 3 domains. Furthermore, our model is inherently modular. One can easily initialize the language model with pre-trained weights better suited for a domain of interest (e.g. BioBERT for biomedical corpora) or swap BERT for a comparable language model (e.g. XLNet (Yang et al., 2019)). Finally, because of (2), our model is fast to train, converging in approximately 1 hour or less on a single GPU for all datasets used in this study.
Our model out-performed previous state-of-the-art performance on ADE by the largest margin (6.53%). While exciting, we believe this corpus was particularly easy to learn. The majority of sentences (∼68%) are annotated for two entities (drug and adverse effect, and one relation (adverse drug event). Ostensibly, a model should be able to exploit this pattern to get near-perfect performance on the majority of sentences in the corpus. As a test, we ran our model again, this time using ground-truth entities in the RE module (as opposed to predicted entities) and found that the model very quickly reached almost perfect performance for RE on the test set (∼98%). As such, high performance on the ADE corpus is not likely to transfer to real-world scenarios involving the large-scale annotation of diverse biomedical articles.
In our experiments, we consider only intra-sentence relations. However, the multiple entities within a document generally exhibit complex, inter-sentence relations. Our model is not currently capable of extracting such inter-sentence relations and therefore our restriction to intra-sentence relations will limit its usefulness for certain downstream tasks, such as knowledge base creation. We also ignore the problem of nested entities, which are common in biomedical corpora. In the future, we would like to extend our model to handle both nested entities and inter-sentence relations. Finally, given that multilingual, pre-trained weights for BERT exist, we would also expect our model’s performance to hold across multiple languages. We leave this question to future work.
8to-add-to-camera-ready-version

heading: A APPENDIX

text:
A.1 CORPUS STATISTICS
Table A.1 lists detailed statistics for each corpus used in this study.
A.2 HYPERPARAMETERS AND MODEL DETAILS
Table A.2 lists hyperparameters and model details that were held constant across all experiments. Table A.3 lists those that were specific to each evaluated corpus.


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.

summaries: 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.

authors:
S. Agarwal
J. Wills
L. Cayton
G. Lanckriet
D. Kriegman
S. Belongie

title: Generalized nonmetric multidimensional scaling

venue: In AISTATS, pp

authors:
Guillermo Aguilar
Felix A Wichmann
Marianne Maertens

title: Comparing sensitivity estimates from MLDS and forced-choice methods in a slant-from-texture experiment

venue: J. Vis.,

authors:
E. Amid
A. Ukkonen

title: Multiview triplet embedding: Learning attributes in multiple maps

venue: In ICML, pp

authors:
Jesse Anderton
Javed Aslam

title: Scaling up ordinal embedding: A landmark approach

authors:
Sanjeev Arora
Hrishikesh Khandeparkar
Mikhail Khodak
Orestis Plevrakis
Nikunj Saunshi

title: A theoretical analysis of contrastive unsupervised representation learning

authors:
M.F. Balcan
E. Vitercik
C. White

title: Learning combinatorial functions from pairwise comparisons

venue: In COLT,

title: Universal approximation bounds for superpositions of a sigmoidal function

venue: IEEE Transactions on Information theory,

authors:
Sean Bell
Kavita Bala

title: Learning visual similarity for product design with convolutional neural networks

venue: ACM Transactions on Graphics (TOG),

authors:
Yoshua Bengio
Pascal Lamblin
Dan Popovici
Hugo Larochelle

title: Greedy layer-wise training of deep networks. In Advances in neural information processing

authors:
Yoshua Bengio
Aaron Courville
Pascal Vincent

title: Representation learning: A review and new perspectives

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Amanda Bower
Lalit Jain
Laura Balzano

title: The landscape of non-convex quadratic feasibility

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
De Cheng
Yihong Gong
Sanping Zhou
Jinjun Wang
Nanning Zheng

title: Person re-identification by multi-channel parts-based cnn with improved triplet loss function

venue: In Proceedings of the iEEE conference on computer vision and pattern recognition,

authors:
Anna Choromanska
Mikael Henaff
Michael Mathieu
Gérard Ben Arous
Yann LeCun

title: The loss surfaces of multilayer networks

venue: In Artificial Intelligence and Statistics,

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: ImageNet: A Large-Scale Hierarchical Image Database

venue: In CVPR09,

title: Deep metric learning with hierarchical triplet loss

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Ross Girshick
Jeff Donahue
Trevor Darrell
Jitendra Malik

title: Rich feature hierarchies for accurate object detection and semantic segmentation

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
S. Haghiri
D. Ghoshdastidar
U. von Luxburg

title: Comparison-based nearest neighbor search

venue: In AISTATS,

authors:
Siavash Haghiri
Damien Garreau
Ulrike Luxburg

title: Comparison-based random forests

authors:
Siavash Haghiri
Felix Wichmann
Ulrike von Luxburg

title: Estimation of perceptual scales using ordinal embedding

venue: arXiv preprint arXiv:1908.07962,

authors:
Geoffrey E Hinton
Ruslan R Salakhutdinov

title: Using deep belief nets to learn covariance kernels for gaussian processes

venue: In Advances in neural information processing systems,

authors:
Geoffrey E Hinton
Simon Osindero
Yee-Whye Teh

title: A fast learning algorithm for deep belief nets

venue: Neural computation,

authors:
Elad Hoffer
Nir Ailon

title: Deep metric learning using triplet network

venue: In International Workshop on Similarity-Based Pattern Recognition,

authors:
Lalit Jain
Kevin G Jamieson
Rob Nowak

title: Finite sample prediction and recovery bounds for ordinal embedding

venue: In NIPS,

authors:
Kenji Kawaguchi
Yoshua Bengio

title: Depth with nonlinearity creates no bad local minima in resnets

venue: Neural Networks,

authors:
Kenji Kawaguchi
Jiaoyang Huang
Leslie Pack Kaelbling

title: Effect of depth and width on local minima in deep learning

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
M. Kleindessner
U. von Luxburg

title: Uniqueness of ordinal embedding

authors:
Matthias Kümmerer
Lucas Theis
Matthias Bethge

title: Deep gaze i: Boosting saliency prediction with feature maps trained on imagenet

venue: arXiv preprint arXiv:1411.1045,

authors:
Moshe Leshno
Vladimir Ya Lin
Allan Pinkus
Shimon Schocken

title: Multilayer feedforward networks with a nonpolynomial activation function can approximate any function

venue: Neural networks,

authors:
Lajanugen Logeswaran
Honglak Lee

title: An efficient framework for learning sentence representations

venue: arXiv preprint arXiv:1803.02893,

authors:
Jonathan Long
Evan Shelhamer
Trevor Darrell

title: Fully convolutional networks for semantic segmentation

authors:
Thomas Mensink
Jakob Verbeek
Florent Perronnin
Gabriela Csurka

title: Metric learning for large scale image classification: Generalizing to new classes at near-zero cost

venue: In European Conference on Computer Vision,

authors:
Tomas Mikolov
Ilya Sutskever
Kai Chen
Greg S Corrado
Jeff Dean

title: Distributed representations of words and phrases and their compositionality

authors:
Quynh Nguyen
Matthias Hein

title: The loss surface of deep and wide neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Panos M Pardalos
Stephen A Vavasis

title: Quadratic programming with one negative eigenvalue is np-hard

venue: Journal of Global Optimization,

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Marc’Aurelio Ranzato
Christopher Poultney
Sumit Chopra
Yann L Cun

title: Efficient learning of sparse representations with an energy-based model

authors:
Marc’Aurelio Ranzato
Y-Lan Boureau
Yann L Cun

title: Sparse feature learning for deep belief networks. In Advances in neural information processing

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing

authors:
Florian Schroff
Dmitry Kalenichenko
James Philbin

title: Facenet: A unified embedding for face recognition and clustering

authors:
Y. Terada
U. von Luxburg

title: Local ordinal embedding

authors:
A. Ukkonen
B. Derakhshan
H. Heikinheimo

title: Crowdsourced nonparametric density estimation using relative distances

venue: In HCOMP,

authors:
L. van der Maaten
K. Weinberger

title: Stochastic triplet embedding

venue: MLSP,

authors:
Jiang Wang
Yang Song
Thomas Leung
Chuck Rosenberg
Jingbin Wang
James Philbin
Bo Chen
Ying Wu

title: Learning fine-grained image similarity with deep ranking

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Xiaolong Wang
Abhinav Gupta

title: Unsupervised learning of visual representations using videos

venue: In Proceedings of the IEEE International Conference on Computer Vision, pp

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

venue: arXiv preprint arXiv:1611.03530,

heading: 1 INTRODUCTION

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

heading: 2 BACKGROUND ON COMPARISON-BASED MACHINE LEARNING AND ORDINAL EMBEDDING

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.

heading: 3 PROPOSED METHOD: ORDINAL EMBEDDING NEURAL NETWORK (OENN)

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.

heading: 4 SIMULATIONS

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.

heading: 4.1 CHOICE OF HYPER-PARAMETERS.

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.

heading: 4.2 CHOICE OF THE LENGTH OF INPUT ENCODING.

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.

heading: 4.3 RECONSTRUCTION AND GENERALIZATION TO UNSEEN TRIPLETS

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.

heading: 4.4 COMPARISON WITH OTHER ORDINAL EMBEDDING METHODS

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.

heading: 5 EXPERIMENTS

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.

heading: 6 DISCUSSION

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.

heading: A APPENDIX

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.