TDRE: A Tensor Decomposition Based Approach for Relation Extraction

In order to map each word into a word vector, we use pre-trained word embeddings with the skip-gram word2vec model [12]. And we combine character embeddings with convolutional neural networks (CNN) since they are able to capture morphological features such as prefixes and suffixes. Bidirectional Long Short-Term Memory Networks (BiLSTM) is utilized to encode bidirectional contextual information [13],

where $h_{i}$ represents the hidden states with BiLSTM networks concatenating the forward and backward hidden states at position $i$ in the given sequence, and $x_{i}$ represents the $i$th word embedding representation. Here, we formally express $x_{i}$ as $[\text{word\_emb}(w_{i});\text{CNN}(\text{char\_emb}(w_{i}))]$ by pre-trained word vector embeddings and CNN based character embeddings. For this layer, we will get a final representation matrix $A$ for the given sentence:

where $n$ is the sequence length and $d_{h}$ is the final concatenated bidirectional hidden dimension of BiLSTM networks.

To identify the entities in a given sentence, we regard entity recognition task as a sequence labeling problem as what is done in [14]. A Conditional Random Fields (CRF) layer is employed here. The designed state transition matrix makes full use of neighbor tag information, which helps both entity type identification and boundary recognition. With the sentence representation $A$ after embedding layer and BiLSTM layer, the given entity tag set $\{y_{1},y_{2},...,y_{m}\}$ and the defined feature score functions ${F_{1},F_{2},...,F_{J}}$, the probabilistic model is formulated as:

where $i=1,2,...,n;k=1,2,...,m$ and $\lambda_{j}$ shows each feature function may have different weight to decide the final probabilistic score. Each feature function $F_{j}$ may include several sub-feature functions $f$ which can be formalized as $F_{j}=\sum_{i}f_{j}(y_{i-1},y_{i},A,i)$ where $i$ represents the position of current word in the given sentence, $y_{i}$ denotes the entity tag of current word and $y_{i-1}$ denotes the entity tag of the previous word. With these definitions, the loss function is formally given as:

where $y$ is the ground truth word label and $Z(\lambda,A)=\sum_{y^{{}^{\prime}}}\exp(\sum_{j=1}^{J}\lambda_{j}F_{j}(y^{{}^{\prime}},A))$. Our optimization goal is to minimize the loss function and finally decode entity tags with Viterbi algorithm.

As we all know, simple classification problem is much easier than simultaneous classification for both relations and its related entity pairs. In this module, we consider the relation classification problem as an independent multi-label classification problem, because each sentence may contain more than one relation type [15, 16, 17, 18]. In order to share the word representation, we use the outputs of BiLSTM networks as the inputs of our classification model which could help find the interactions between entity recognition and relation classification. It is worth noting that we are categorizing for the entire sentence here instead of categorizing every word in the sentence.

A linear network is utilized in our relation classification model and it can be denoted as $f(A)=WA+b$, where $A$ is the sentence representation, $W$ and $b$ are the training parameters. As for the multi-label problems, we focus on the final expression of the classification results $P=(P_{1},P_{2},...P_{K})$ and each element is calculated as follows:

where $\sigma$ is the sigmoid activation function and $\gamma_{1}$ is the threshold for predicting the sentence contained relation types.

If the real relation types are denoted by $y$, then the goal of this classification module is to minimize the loss function:

where $y_{k}$ is the ground truth relation type and $p_{k}$ is the probability for predicting the current sentence into the $k$th relation type. And in the training process, sigmoid cross-entropy loss function is used since there exists a multi-label problem.

According to the above defined sentence with $n$ words, the target of relation extraction is to extract the existing triple tuples with the predefined relation type set $\mathcal{R}$ from the unstructured text. And the extracted triplet $(e_{s},r,e_{t})$ corresponds to specified entity spans $e_{s},e_{t}$ and the relation $r$ between $e_{s}$ and $e_{t}$. For a specific relation type $k$, we focus on mapping each word with the others in the sentence with an indication function. The word-to-word pair mapping can be modeled as a matrix $X\in{\mathbb{R}^{n\times n}}$, where the element $x_{ij}$ in the matrix $X$ indicates whether the $i$th word and the $j$th word can form a triplet related word pair. And $i$ and $j$ represent the last word of source entity and target entity respectively. Hence, the indication function is expressed as $x_{ij}=1$ when the $i$th word can map with $j$th word in the specific relation type $k$. Extending matrix $X$ with relation type component, we have a tensor extraction representation $\mathcal{X}$. It can be defined as following:

Note that in this mathematical formula, $i$ and $j$ are the tail words of two entity spans.

In order to extract useful information from the tensor, we employ a tensor decomposition algorithm named decomposition into directional component (DEDICOM) strategy introduced by Harshman et al. [5]. As for a sequence with $n$ words, the defined mapping matrix $X\in{\mathbb{R}^{n\times n}}$ needs to describe the asymmetric relationships between each word and the other words. This idea is suitable for that each extracted triplet is directional since source entity and target entity are ordered. Triplet extraction process can be modeled as a three-order DEDICOM model, where the target constructed tensor is $\mathcal{X}\in{\mathbb{R}^{n\times n\times K}}$, where $K$ denotes the number of relation types. The decomposition is:

where $A\in\mathbb{R}^{n\times d_{h}}$ is the sequence representation after BiLSTM networks, $\mathcal{D}\in\mathbb{R}^{d_{h}\times d_{h}\times K}$ and $H\in\mathbb{R}^{d_{h}\times d_{h}}$ are parameters. The matrices $\mathcal{D}_{k}\in\mathbb{R}^{d_{h}\times d_{h}}$ are diagonal, and the diagonal entry $(\mathcal{D}_{k})_{ii}$ indicates the participation of $i$th latent component at relation $k$ and $i=1,2,...,d_{h}$.

From the above mentioned module, it is necessary to predict all relation types for each word pair while the sentence may contain only few relation types. To address this problem and to further utilize the predicted relation types with relation classification model, we need to make specific settings for the factor of $\mathcal{D}$ in the structure of the tensor decomposition. Actually, it is not necessary to calculate the mapping matrix $\mathcal{X}_{r}$ when there is no prediction for the $r$th relation type. We set $\mathcal{D}_{r}^{{}^{\prime}}$ as a zero matrix, thus $\mathcal{X}_{r}$ turns into a zero matrix after calculation, which means no triplet in $r$th relation component. Thus, it is theoretically observable that the decomposition strategy avoids predicting unnecessary triplets and simultaneously reduces the predicting time. Therefore, a custom operation $\circ$ can be represented as follows:

And then, the final decomposition algorithm can be formalized as:

where $P\in\mathbb{R}^{K}$ denotes the prediction result of relation classification module.

From the perspective of probability distribution, we do not directly model the joint probability like what is done in [4] and [3] but decompose joint probability into relation component as conditional probability:

$i,j=1,2,...,n;k=1,2,...,K$, where $p$ represents probability distribution, $x_{i},x_{j}$ respectively denotes the $i$-th and $j$-th word representation in the sentence $S$ and $r_{k}$ denotes the $k$-th relation type. Owing to that each word may be mapped with more than one word and relation types, we employ sigmoid function here to amplify the difference. And the final triplet decode procession can be denoted as:

where $\mathcal{X}_{ijk}^{{}^{\prime}}$ is the calculated tensor and $\gamma_{2}$ represents the threshold for judging whether a triplet is true.

The goal of this decomposed relation extraction module is to minimize the cross-entropy loss $L_{extract}$ during training:

where $\mathcal{X}_{ijk}$ is the ground truth label and $\mathcal{X}_{ijk}^{{}^{\prime}}$ is the predicted triplet tensor.

In order to jointly train the proposed model, we combine all of the three objective loss functions and optimize parameters together. The final loss function is computed as follows:

where $L_{ner}$ is the loss function in name entity recognition module, $L_{rel}$ is the loss function in relation classification module and $L_{extract}$ is the loss function of final triplet extraction module which is calculated by DEDICOM algorithm. In order to update parameters, we optimize our model with Adam optimization approach and train the proposed joint model like multi-tasks learning paradigm.

Finally, our TDRE algorithm is summarized in Algorithm 1.

We conduct experiments on three benchmark datasets for relation extraction: (i) NYT10, the originally New York Times corpus [19] which is developed by distant supervised and published by Takanobu et al. [11] who filtered dataset by removing the relations in training set but not in testing set and sentences containing no relations. (ii) CoNLL04 dataset [20] and it is split by Gupta et al. [21] and Adel et al. [22]. The official given entity type set is {Location, Organization, Person, Other} where we omit the beginning, inside and the outside tags of entity types here. And the official defined relation type set is {Kill, Live in, Located in, OrgBased in, Work for}. (iii) Adverse Drug Events dataset (ADE) [23], where we use 80% for training and 20% as test set. Entity type set {Beginning, Inside, Outside} is applied here since there is no official entity types. And the relation type set is {Adverse-Effect, Drug-Disease Treatment}.

The details of the public datasets are reported in Table 1. The approximate statistical number of triplets on ADE dataset is shown since we conduct cross-validation on ADE dataset.

Similar to previous works, we obtain the 50-dimensional word embeddings which is used by [22] trained on Wikipedia. Character embeddings are initialized randomly and the kernel size is set to 3 for convolution neural network while parameters update with training process. And then we concatenate the word embeddings and character embeddings as the final input embeddings. For the representation of the learning layers, we use three-layer BiLSTM networks with 64 hidden units. Comparing to most existing models, we randomly initialize entity label embeddings for all conducted datasets with embedding size 128, and update parameters by optimization. Training is performed by using the Adam optimizer with learning rate $10^{-3}$, and dropout technique is used in input embeddings and BiLSTM hidden layers, where the dropout rate is set to 0.1. Early stopping is also used on the validation set for avoiding overfitting.