Joint entity recognition and relation extraction as a multi-head selection problem
作为多头选择问题的联合实体识别和关系提取

In our work, NER is the first task which we solve in order to address the end-to-end relation extraction problem. A number of different methods for the NER task that are based on hand-crafted features have been proposed, such as CRFs [Lafferty et al., 2001], Maximum Margin Markov Networks [Taskar et al., 2003] and support vector machines (SVMs) for structured output [Tsochantaridis et al., 2004], to name just a few. Recently, deep learning methods such as CNN- and RNN-based models have been combined with CRF loss functions [Collobert et al., 2011, Huang et al., 2015, Lample et al., 2016, Ma & Hovy, 2016] for NER. These methods achieve state-of-the-art performance on publicly available NER datasets without relying on hand-crafted features.

We consider relation extraction as the second task of our joint model. The main approaches for relation extraction rely either on hand-crafted features [Zelenko et al., 2003, Kambhatla, 2004] or neural networks [Socher et al., 2012, Zeng et al., 2014]. Feature-based methods focus on obtaining effective hand-crafted features, for instance defining kernel functions [Zelenko et al., 2003, Culotta & Sorensen, 2004] and designing lexical, syntactic, semantic features, etc. [Kambhatla, 2004, Rink & Harabagiu, 2010]. Neural network models have been proposed to overcome the issue of manually designing hand-crafted features leading to improved performance. CNN- [Zeng et al., 2014, Xu et al., 2015a, dos Santos et al., 2015] and RNN-based [Socher et al., 2013, Zhang & Wang, 2015, Xu et al., 2015b] models have been introduced to automatically extract lexical and sentence level features leading to a deeper language understanding. Vu et al. [2016] combine CNNs and RNNs using an ensemble scheme to achieve state-of-the-art results.

Entity and relation extraction includes the task of (i) identifying the entities (described in Section 2.1) and (ii) extracting the relations among them (described in Section 2.2). Feature-based joint models [Kate & Mooney, 2010, Yang & Cardie, 2013, Li & Ji, 2014, Miwa & Sasaki, 2014] have been proposed to simultaneously solve the entity recognition and relation extraction (RE) subtasks. These methods rely on the availability of NLP tools (e.g., POS taggers) or manually designed features and thus (i) require additional effort for the data preprocessing, (ii) perform poorly in different application and language settings where the NLP tools are not reliable, and (iii) increase the computational complexity. In this paper, we introduce a joint neural network model to overcome the aforementioned issues and to automatically perform end-to-end relation extraction without the need of any manual feature engineering or the use of additional NLP components.

Given a sentence $w={w_{1},...,w_{n}}$ as a sequence of tokens, the word embedding layer is responsible to map each token to a word vector ($w_{\textit{word2vec}}$). We use pre-trained word embeddings using the Skip-Gram word2vec model [Mikolov et al., 2013].

RNNs are commonly used in modeling sequential data and have been successfully applied in various NLP tasks [Sutskever et al., 2014, Lample et al., 2016, Miwa & Bansal, 2016]. In this work, we use multi-layer LSTMs, a specific kind of RNNs which are able to capture long term dependencies well [Bengio et al., 1994, Pascanu et al., 2013]. We employ a BiLSTM which is able to encode information from left to right (past to future) and right to left (future to past). This way, we can combine bidirectional information for each word by concatenating the forward ($\vec{h_{i}}$) and the backward ( $\vec{\reflectbox{$h_{i}$}}$ ) output at timestep $i$. The BiLSTM output at timestep $i$ can be written as:

We formulate the entity identification task as a sequence labeling problem, similar to previous work on joint learning models [Miwa & Bansal, 2016, Li et al., 2017, Katiyar & Cardie, 2017] and named entity recognition [Lample et al., 2016, Ma & Hovy, 2016] using the BIO (Beginning, Inside, Outside) encoding scheme. Each entity consists of multiple sequential tokens within the sentence and we should assign a tag for every token in the sentence. That way we are able to identify the entity arguments (start and end position) and its type (e.g., ORG). To do so, we assign the B-type (beginning) to the first token of the entity, the I-type (inside) to every other token within the entity and the O tag (outside) if a token is not part of an entity. Fig. 1 shows an example of the BIO encoding tags assigned to the tokens of the sentence. In the CRF layer, one can observe that we assign the B-ORG and I-ORG tags to indicate the beginning and the inside tokens of the entity “Disease Control Center”, respectively. On top of the BiLSTM layer, we employ either a softmax or a CRF layer to calculate the most probable entity tag for each token. We calculate the score of each token $w_{i}$ for each entity tag:

where the superscript $(e)$ is used for the notation of the NER task, $f(\cdot)$ is an element-wise activation function (i.e., relu, tanh), $V^{(e)}\in\mathbb{R}^{p\times l}$, $U^{(e)}\in\mathbb{R}^{l\times 2d}$, $b^{(e)}\in\mathbb{R}^{l}$, with $d$ as the hidden size of the LSTM, $p$ the number of NER tags (e.g., B-ORG) and $l$ the layer width. We calculate the probabilities of all the candidate tags for a given token $w_{i}$ as $\operatorname{Pr}(tag\nonscript\;|\nonscript\;w_{i})=\text{softmax}(s(h_{i}))$ where $\operatorname{Pr}(tag\nonscript\;|\nonscript\;w_{i})\in\mathbb{R}^{p}$. In this work, we employ the softmax approach only for the entity classification (EC) task (which is similar to NER) where we need to predict only the entity types (e.g., PER) for each token assuming boundaries are given. The CRF approach is used for the NER task which includes both entity type and boundaries recognition.

where $S\in\mathbb{R}$, $s_{i,y_{i}^{(e)}}^{(e)}$ is the score of the predicted tag for token $w_{i}$, $T$ is a square transition matrix in which each entry represents transition scores from one tag to another. $T\in\mathbb{R}^{(p+2)\times(p+2)}$ because $y_{0}^{(e)}$ and $y_{n}^{(e)}$ are two auxiliary tags that represent the starting and the ending tags of the sentence, respectively. Then, the probability of a given sequence of tags over all possible tag sequences for the input sentence $w$ is defined as:

We apply Viterbi to obtain the tag sequence $\hat{y}^{(e)}$ with the highest score. We train both the softmax (for the EC task) and the CRF layer (for NER) by minimizing the cross-entropy loss $\mathcal{L}_{\textsc{ner}}$. We also use the entity tags as input to our relation extraction layer by learning label embeddings, motivated by Miwa & Bansal [2016] where an improvement of$~{}2$% F₁ is reported (with the use of label embeddings). In our case, label embeddings lead to an increase of $~{}1$% F₁ score as reported in Table 2 (see Section 5.2). The input to the next layer is twofold: the output states of the LSTM and the learned label embedding representation, encoding the intuition that knowledge of named entities can be useful for relation extraction. During training, we use the gold entity tags, while at prediction time we use the predicted entity tags as input to the next layer. The input to the next layer is the concatenation of the hidden LSTM state $h_{i}$ with the label embedding $g_{i}$ for token $w_{i}$:

In this subsection, we describe the relation extraction task, formulated as a multi-head selection problem [Zhang et al., 2017, Bekoulis et al., 2018]. In the general formulation of our method, each token $w_{i}$ can have multiple heads (i.e., multiple relations with other tokens). We predict the tuple ($\hat{y}_{i}$, $\hat{c}_{i}$) where $\hat{y}_{i}$ is the vector of heads and $\hat{c}_{i}$ is the vector of the corresponding relations for each token $w_{i}$. This is different for the previous standard head selection for dependency parsing method [Zhang et al., 2017] since (i) it is extended to predict multiple heads and (ii) the decisions for the heads and the relations are jointly taken (i.e., instead of first predicting the heads and then in a next step the relations by using an additional classifier). Given as input a token sequence $w$ and a set of relation labels $\mathcal{R}$, our goal is to identify for each token $w_{i},\;i\in\{0,...,n\}$ the vector of the most probable heads $\hat{y}_{i}\subseteq w$ and the vector of the most probable corresponding relation labels $\hat{r}_{i}\subseteq\mathcal{R}$. We calculate the score between tokens $w_{i}$ and $w_{j}$ given a label $r_{k}$ as follows:

where the superscript $(r)$ is used for the notation of the relation task, $f(\cdot)$ is an element-wise activation function (i.e., relu, tanh), $V^{(r)}\in\mathbb{R}^{l}$, $U^{(r)}\in\mathbb{R}^{l\times(2d+b)}$, $W^{(r)}\in\mathbb{R}^{l\times(2d+b)}$, $b^{(r)}\in\mathbb{R}^{l}$, $d$ is the hidden size of the LSTM, $b$ is the size of the label embeddings and $l$ the layer width. We define

to be the probability of token $w_{j}$ to be selected as the head of token $w_{i}$ with the relation label $r_{k}$ between them, where $\sigma(.)$ stands for the sigmoid function. We minimize the cross-entropy loss $\mathcal{L}_{\textrm{rel}}$ during training:

where $y_{i}\subseteq w$ and $r_{i}\subseteq{\mathcal{R}}$ are the ground truth vectors of heads and associated relation labels of $w_{i}$ and $m$ is the number of relations (heads) for $w_{i}$. After training, we keep the combination of heads $\hat{y}_{i}$ and relation labels $\hat{r}_{i}$ exceeding a threshold based on the estimated joint probability as defined in Eq. (7). Unlike previous work on joint models [Katiyar & Cardie, 2017], we are able to predict multiple relations considering the classes as independent and not mutually exclusive (the probabilities do not necessarily sum to 1 for different classes). For the joint entity and relation extraction task, we calculate the final objective as $\mathcal{L}_{\textsc{ner}}+\mathcal{L}_{\textrm{rel}}$.

Our model is able to simultaneously extract entity mentions and the relations between them. To demonstrate the effectiveness and the general purpose nature of our model, we also test it on the recently introduced Dutch real estate classifieds (DREC) dataset [Bekoulis et al., 2017] where the entities need to form a tree structure. By using thresholded inference, a tree structure of relations is not guaranteed. Thus we should enforce tree structure constraints to our model. To this end, we post-process the output of our system with Edmonds’ maximum spanning tree algorithm for directed graphs [Chu & Liu, 1965, Edmonds, 1967]. A fully connected directed graph $G=(V,E)$ is constructed, where the vertices $V$ represent the last tokens of the identified entities (as predicted by NER) and the edges $E$ represent the highest scoring relations with their scores as weights. Edmonds’ algorithm is applied in cases a tree is not already formed by thresholded inference.

We conduct experiments on four datasets: (i) Automatic Content Extraction, ACE04 [Doddington et al., 2004], (ii) Adverse Drug Events, ADE [Gurulingappa et al., 2012b], (iii) Dutch Real Estate Classifieds, DREC [Bekoulis et al., 2017] and (iv) the CoNLL’04 dataset with entity and relation recognition corpora [Roth & Yih, 2004]. Our code is available in our github codebase.²²2https://github.com/bekou/multihead_joint_entity_relation_extraction

ACE04: There are seven main entity types namely Person (PER), Organization (ORG), Geographical Entities (GPE), Location (LOC), Facility (FAC), Weapon (WEA) and Vehicle (VEH). Also, the dataset defines seven relation types: Physical (PHYS), Person-Social (PER-SOC), Employment-Membership-Subsidiary (EMP-ORG), Agent-Artifact (ART), PER-ORG affiliation (Other-AFF), GPE affiliation (GPE-AFF), and Discourse (DISC). We follow the cross-validation setting of Li & Ji [2014] and Miwa & Bansal [2016]. We removed DISC and did 5-fold cross-validation on the bnews and nwire subsets (348 documents). We obtained the preprocessing script from Miwa’s github codebase.³³3https://github.com/tticoin/LSTM-ER/tree/master/data/ace2004 We measure the performance of our system using micro F₁ scores, Precision and Recall on both entities and relations. We treat an entity as correct when the entity type and the region of its head are correct. We treat a relation as correct when its type and argument entities are correct, similar to Miwa & Bansal [2016] and Katiyar & Cardie [2017]. We refer to this type of evaluation as strict.⁴⁴4For the CoNLL04, DREC and ADE datasets, the head region covers the whole entity (start and end boundaries). The ACE04 already defines the head region of an entity. We select the best hyperparameter values on a randomly selected validation set for each fold, selected from the training set (15% of the data) since there are no official train and validation splits in the work of Miwa & Bansal [2016].

CoNLL04: There are four entity types in the dataset (Location, Organization, Person, and Other) and five relation types (Kill, Live in, Located in, OrgBased in and Work for). We use the splits defined by Gupta et al. [2016] and Adel & Schütze [2017]. The dataset consists of 910 training instances, 243 for validation and 288 for testing.⁵⁵5http://cistern.cis.lmu.de/globalNormalization/globalNormalization_all.zip We measure the performance by computing the F₁ score on the test set. We adopt two evaluation settings to compare to previous work. Specifically, we perform an EC task assuming the entity boundaries are given similar to Gupta et al. [2016] and Adel & Schütze [2017]. To obtain comparable results, we omit the entity class “Other” when computing the EC score. We score a multi-token entity as correct if at least one of its comprising token types is correct assuming that the boundaries are given; a relation is correct when the type of the relation and the argument entities are both correct. We report macro-average F₁ scores for EC and RE to obtain comparable results to previous studies. Moreover, we perform actual NER evaluation instead of just EC, reporting results using the strict evaluation metric.

DREC: The dataset consists of 2,318 classifieds as described in the work of Bekoulis et al. [2018]. There are 9 entity types: Neighborhood, Floor, Extra building, Subspace, Invalid, Field, Other, Space and Property. Also, there are two relation classes Part-of and Equivalent. The goal is to identify important entities of a property (e.g., floors, spaces) from classifieds and structuring them into a tree format to get the structured description of the property. For the evaluation, we use 70% for training, 15% for validation and 15% as test set in the same splits as defined in Bekoulis et al. [2018]. We measure the performance by computing the F₁ score on the test set. To compare our results with previous work [Bekoulis et al., 2018], we use the boundaries evaluation setting. In this setting, we count an entity as correct if the boundaries of the entity are correct. A relation is correct when the relation is correct and the argument entities are both correct. Also, we report results using the strict evaluation for future reference.

ADE: There are two types of entities (drugs and diseases) in this dataset and the aim of the task is to identify the types of entities and relate each drug with a disease (adverse drug events). There are 6,821 sentences in total and similar to previous work [Li et al., 2016, 2017], we remove $\sim$130 relations with overlapping entities (e.g., “lithium” is a drug which is related to “lithium intoxication”). Since there are no official sets, we evaluate our model using 10-fold cross-validation where 10% of the data was used as validation and 10% for test set similar to Li et al. [2017]. The final results are displayed in F₁ metric as a macro-average across the folds. The dataset consists of 10,652 entities and 6,682 relations. We report results similar to previous work on this dataset using the strict evaluation metric.

We use pre-trained word2vec embeddings used in previous work, so as to retain the same inputs for our model and to obtain comparable results that are not affected by the input embeddings. Specifically, we use the 200-dimensional word embeddings used in the work of Miwa & Bansal [2016] for the ACE04 dataset⁶⁶6http://tti-coin.jp/data/wikipedia200.bin trained on Wikipedia. We obtained the 50-dimensional word embeddings used by Adel & Schütze [2017]⁵ trained also on Wikipedia for the CoNLL04 corpus. We use the 128-dimensional word2vec embeddings used by Bekoulis et al. [2018] trained on a large collection of 887k Dutch property advertisements⁷⁷7https://drive.google.com/uc?id=1Dvibr-Ps4G_GI6eDx9bMXnJphGhH_M1z&export=download for the DREC dataset. Finally, for the ADE dataset, we used 200-dimensional embeddings used by Li et al. [2017] and trained on a combination of PubMed and PMC texts with texts extracted from English Wikipedia [Moen & Ananiadou, 2013]⁸⁸8http://evexdb.org/pmresources/vec-space-models/wikipedia-pubmed-and-PMC-w2v.bin.

We have developed our joint model by using Python with the TensorFlow machine learning library [Abadi et al., 2016]. Training is performed using the Adam optimizer [Kingma & Ba, 2015] with a learning rate of $10^{-3}$. We fix the size of the LSTM to $d=64$ and the layer width of the neural network to $l=64$ (both for the entity and the relation scoring layers). We use dropout [Srivastava et al., 2014] to regularize our network. Dropout is applied in the input embeddings and in between the hidden layers for both tasks. Different dropout rates have been applied but the best dropout values (0.2 to 0.4) for each dataset have been used. The hidden dimension for the character-based LSTMs is 25 (for each direction). We also fixed our label embeddings to be of size $b=25$ for all the datasets except for CoNLL04 where the label embeddings were not beneficial and thus were not used. We experimented with tanh and relu activation functions (recall that this is the function $f(\cdot)$ from the model description). We use the relu activation only in the ACE04 and tanh in all other datasets. We employ the technique of early stopping based on the validation set. In all the datasets examined in this study, we obtain the best hyperparameters after 60 to 200 epochs depending on the size of the dataset. We select the best epoch according to the results in the validation set. For more details about the effect of each hyperparameter to the model performance see the Appendix.

In Table 1, we present the results of our analysis. The first column indicates the considered dataset. In the second column, we denote the model which is applied (i.e., previous work and the proposed models). The proposed models are the following: (i) multi-headis the proposed model with the CRF layer for NER and the sigmoid loss for multiple head prediction, (ii) multi-head+Eis the proposed model with addition of Edmonds’ algorithm to guarantee a tree-structured output for the DREC dataset, (iii) single-headis the proposed method but it predicts only one head per token using a softmax loss instead of a sigmoid, and (iv) multi-head ECis the proposed method with a softmax to predict the entity classes assuming that the boundaries are given, and the sigmoid loss for multiple head selection. Table 1 also indicates whether the different settings include hand-crafted features or features derived from NLP tools (e.g., POS taggers, dependency parsers). We use the ✓ symbol to denote that the model includes this kind of additional features and the ✗ symbol to denote that the model is only based on automatically extracted features. Note that all the variations of our model do not rely on any additional features. In the next column, we declare the type of evaluation conducted for each experiment. We include here different evaluation types to be able to compare our results against previous studies. Specifically, we use three evaluation types, namely:

1. (i)

   Strict: an entity is considered correct if the boundaries and the type of the entity are both correct; a relation is correct when the type of the relation and the argument entities are both correct,

2. (ii)

   Boundaries: an entity is considered correct if only the boundaries of the entity are correct (entity type is not considered); a relation is correct when the type of the relation and the argument entities are both correct and

3. (iii)

   Relaxed: we score a multi-token entity as correct if at least one of its comprising token types is correct assuming that the boundaries are given; a relation is correct when the type of the relation and the argument entities are both correct.

In the next three columns, we present the results for the entity identification task (Precision, Recall, F₁) and then (in the subsequent three columns) the results of the relation extraction task (Precision, Recall, F₁). Finally, in the last column, we report an additional F₁ measure which is the average F₁ performance of the two subtasks. We mark with bold font in Table 1, the best result for each dataset among those models that use only automatically extracted features.

We conduct ablation tests on the ACE04 dataset reported in Table 2 to analyze the effectiveness of the various parts of our joint model. The performance of the RE task decreases ($\sim$1% in terms of F₁ score) when we remove the label embeddings layer and only use the LSTM hidden states as inputs for the RE task. This shows that the NER labels, as expected, provide meaningful information for the RE component.