In general, entity extraction is performed before relation extraction, and its results can also be taken as the input of relation extraction. Relation extraction is fundamentally divided into two stages: judge if a sentence that includes target entity pair is a relation mention; classify the relation mention into a targeted type. According to the thoughts, we model the joint extraction task as a two-step decision process by reinforcement learning. The two steps correspond to entity extraction and relation extraction roughly, and the specific flow is shown in Figure 1.

Reinforcement Learning (RL). It [4] is a commonly used framework for learning control policies by the agent, through interacting with its environment.

State. The internal state S in the environment consists of the initial state s₁, the transition state s₂, and the end state s_e. Because it is difficult to find some appropriate measures to directly represent the state from unstructured texts, we use some deep learning methods to automatically extract features of texts, which can represent the state in the decision process. To be specific, we use bidirectional LSTM (Section 3.2) to realize preliminary entity extraction and use attention based method (Section 3.3) to generate the initial state s₁ = Att(X; θ₁). In addition, we use Tree-LSTM (Section 3.4) to generate the transition state s₂ = Tree(X; θ₂). The action taken at s₂ realizes preliminary relation extraction. X is the features of the input sentence; θ₁ and θ₂ are parameters in the above models.

Action. There are a set of predefined actions A in the environment: Action 1 a₁, Action 2 a₂, Action 3 a₃, Action 4 a₄, and so forth. The first decision judges to take a₁ or a₂. a₁ is to judge that a sentence that includes target entity pair is not a relation mention, and a₂ is to judge that a sentence that includes target entity pair is a relation mention. The second decision judges to take a₃ or a₄…. a₃ is to classify the relation mention into a targeted type, and a₄ is to classify the relation mention into another targeted type. R = r₁, r₂, r₃, r₄,… denotes the reward obtained for each action. The agent takes an action a in state s and receives a reward r from the environment. (s₁, a₁, r₁, s_e), (s₁, a₂, r₂, s₂), (s₂, a₃, r₃, s_e), and (s₂, a₄, r₄, s_e) denote the transitions of the decision process.

Transition and Reward Function. A state transition tuple (s₁, a₁, r₁, s_e) means that the agent takes a₁ at s₁ and then transits to s_e. If the judgement of a₁ is right, then the agent receives a reward r₁ = 10; if the judgement of a₁ is wrong, then set r₁ = −20 to punish the wrong judgement of the first decision. A state transition tuple (s₁, a₂, r₂, s₂) means that the agent takes a₂ at s₁, then transits to s₂, and receives a reward r₂ = 5. A state transition tuple (s₂, a₃, r₃, s_e) means that the agent takes a₃ at s₂ and then transits to s_e. If the judgement of a₃ is right, then the agent receives a reward r₃ = 10; if the judgement on type is wrong, then set r₃ = −10 to punish the wrong judgement of the second decision; if it is not a relation mention, then set r₃ = −20. The meaning of other state transition tuple (s₂, a₄, r₄, s_e) and the definition of its reward function are similar to those of (s₂, a₃, r₃, s_e).

Long Short-Term Memory (LSTM) [5] is a variant of recurrent neural networks (RNN) designed to cope with the gradient vanishing problem, and LSTM is very useful to find and exploit long range dependencies in the data. Now lots of LSTM variants have been proposed and applied to natural language processing tasks, such as sentiment analysis, relation classification, and question answering system. We use bidirectional LSTM (BILSTM) to model word sequence, which can efficiently make use of past features and future features. BILSTM finds the right representation of each word and assigns a tag of entity state to each word in the input sequence to realize preliminary entity extraction. BILSTM mainly consists of three representation layers: embedding layer, BILSTM layer, and output layer. Figure 2 gives the basic structure of the BILSTM.

Recently, attention mechanisms have successfully been applied to machine translation [7], text summarization [8], text comprehension [9], syntactic constituency parsing [10], relation classification [11], and text classification [12]. Inspired by those studies, we introduce attention based method to compute the hidden state vectors h_t and h_t′ in the BILSTM layer and generate the initial state s₁ in the decision process. The method can obtain the information of entity extraction and represent the sentences that include target entity pair. After the first decision on s₁, we realize preliminary entity extraction and get ready to perform relation extraction. In essence, attention based method can pass entity information to relation extraction and obtain feedback information of relation extraction by jointly updating all the parameters. Attention based method better integrates entity extraction and relation extraction.

After realizing preliminary entity extraction, we choose two entities as target entity pair in the sentence W = [w₁, w₂,…, w_n]. The attention layer is depicted in Figure 3. Let H be a matrix consisting of the hidden state vectors [h₁, h₁′, h₂, h₂′,…, h_n, h_n′] in the BILSTM layer, and H is the input of the attention layer. Then attention based method represents the sentence that includes target entity pair as a weighted sum of these hidden state vectors.(6)A=tanh⁡H,α=softmaxωTA,s1=tanh⁡HαT.

Here, α is the normalized weight vector and ω is a parameter vector. s₁ is the initial state, in which we denote by s₁ = Att(X; θ₁), and θ₁ represents all the parameters in this method.

After generating the initial state s₁, the first decision will be made to judge if a sentence that includes target entity pair is a relation mention. We pass s₁ to a softmax output layer to get y_a, which is the probability of relation mention and nonrelation for a sentence. Finally, we can determine to take a₁ or a₂.(7)ya=softmaxWsys1+by.

Here, W is weight matric and b is bias vector.

The objective function for m training instances is the negative log-likelihood:(8)Jθ1=−12m∑i=1mt0ilog⁡yai0+t1ilog⁡yai1+λ2θ122

Here, t₀⁽ⁱ⁾ and t₁⁽ⁱ⁾ are the one-hot represented ground truth. y_a⁽ⁱ⁾(0) and y_a⁽ⁱ⁾(1) are the estimated probability for relation mention and nonrelation, respectively. λ is an L2 regularization hyperparameter.

To minimize J(θ₁), we use a simple optimization technique called stochastic gradient descent (SGD).

Unlike traditional sequence LSTM, Tree-LSTM [13] is constructed over a tree structure. As is known to all, the dependency tree is very useful for analyzing the relations between words. Two words may be far apart in the linear structure and separated by many unrelated words or preposition structure, but they are in hyponymy for the dependency tree. Therefore, we construct the Tree-LSTM over the dependency tree to represent relation mentions in a bottom-up way. Tree-LSTM can extract the core dependency relation between target entity pair and generate the transition state s₂ in the decision process. The second decision on s₂ performs preliminary relation extraction.

We take the relation mention “AFP_ENG_20030319.0879-R2” in Table 1 as an example to illustrate, and the two entity arguments are “third parties” and “Entertainment.” Firstly, we perform dependency parsing on the relation mention and generate the dependency tree, as shown in Figure 4. Instead of using the full mention boundary, we use head spans for entities directly. The entity head of “third parties” is “parties,” and the entity head of “Entertainment” is “Entertainment.” The core dependency relation between target entity pair is shown by red lines in Figure 4. So we use dependency tree as a backbone to construct Tree-LSTM. Moreover, for the convenience of implementation, we prune or pad dependency trees to keep the same depth and width.

Like BILSTM, each LSTM unit of Tree-LSTM takes continuous feature vector of a word as input. In addition to word embedding e_t and part-of-speech embedding d_t, we use entity type embedding t_t and entity position embedding l_t, to which entity type feature and entity position feature are mapped. We can get the entity type features from the preliminary results of entity extraction and get the entity position features by computing the relative distances of the current word to the two entity arguments. Unlike BILSTM, the LSTM unit does not accept hidden state vectors of the adjacent words and accept the hidden state vectors of all children nodes h_tk as input. The Tree-LSTM is developed from its leaf node in a recursive way up to the root, which is the common ancestor (“divesting” in Figure 4) of all the words. Then we carry out nonlinear transformation on the hidden state vector of the ancestor to generate s₂, which is the final representation of relation mentions and serves as the transition state in the decision process. We denote s₂ by s₂ = Tree(X; θ₂), and θ₂ represents all the parameters in the Tree-LSTM.

After generating the transition state s₂, the second decision will be made to classify the relation mention into a targeted type. Then s₂ is passed to a softmax output layer to get y_r, which is the probability of different types for a relation mention. Finally, we choose a type with the maximum probability, which determines to take a₃ or a₄….(9)yr=softmaxWsys2+by.

Here, W is weight matric and b is bias vector. At each dependency tree, we use a softmax layer to predict the type for the root node given the inputs X observed at its children nodes.

The objective function for m training instances is the negative log-likelihood:(10)Jθ2=−1m∑i=1mlog⁡yri+λ2θ222.

Here, y_r⁽ⁱ⁾ is the estimated probability for the true type at each root node. The root node of Tree-LSTM is able to selectively incorporate information from each child. λ is an L2 regularization hyperparameter.

To minimize J(θ₂), we use AdaGrad [14].

Q-Learning algorithm [15] is a popular form of reinforcement learning and can be used to learn an optimal state-action value function Q(s, a) for the agent. The agent takes an action a in state s by consulting Q(s, a), which is a measure of the action's expected long-term reward. The aim is to maximize some cumulative rewards through a sequence of actions. As the state space is infinite in the decision process, it is impractical to obtain Q(s, a) for all possible state-action pairs.

For the above challenge, we approximate Q(s, a) using a neural network, which can represent Q(s, a) as a parameterized function Q_η(s, a) = MLP(ϕ(X; θ), a; η). ϕ(X; θ) refers to s₁ = Att(X; θ₁) and s₂ = Tree(X; θ₂) above, where θ can be obtained by pretraining the deep learning models above and η represents the parameters in the neural network, which are learnt by performing stochastic gradient descent step with RMSprop [16].

To approximate the real value function Q^π as closely as possible, we measure the degree of approximation with the least squares error:(11)Eη=EQπs,a−Qηs,a2.

In Q-Learning, we use the estimated value function Q_η(s, a) instead of the real value function Q^π(s, a). During each epoch, the updates of parameters aim to reduce the discrepancy between the estimation Q_η(s, a) and the expectation Q^π(s, a). The agent starts from a random Q_η(s, a) and continuously updates its values by making the decisions and obtaining rewards. Then the agent can maximize its expected future rewards by choosing the action with the highest Q_η(s, a′′). Finally, Q-Learning algorithm gets control policy π in the two-step decision process. Algorithm 1 details the Q-Learning training procedure.

During the training procedure we pretrain BILSTM, the attention layer, and Tree-LSTM, respectively. The training parameters mainly include all the parameters θ₀ in BLSTM, all the parameters θ₁ in the attention layer, and all the parameters θ₂ in Tree-LSTM.

The functionality of the attention model in our RL method is very similar to that of a separate relation mention classification part in a pipeline. We use deep learning methods to represent words and sentences in the text and use RL to combine three tasks in the decision process, that are entity extraction, relation mention classification, and relation classification. The pipeline architecture just passes the information of entity extraction to relation extraction and does not enable information to flow in the global architecture. However, our RL method not only combines the above tasks sequentially but also globally makes decisions. At the beginning, the decisions have close to a random chance. After several epochs, they will be stabilizing. Meanwhile, the parameters in our architecture are globally updated and eventually converge. Therefore, our RL method can obtain feedback from decision-making and state changes and enable information to flow in the global architecture. The attention model connects entity extraction task with relation extraction task, thus helping us to realize the joint extraction of entities and relations. Experimental results demonstrate that our RL method performs slightly better than the pipeline method for both entity extraction and relation extraction, which shows that we are on the right track.

Most previous work has reported results on ACE2005 data set, so we evaluate our method on ACE2005 for joint extraction of entities and relations. We use three common metrics to evaluate the performance: microprecision (P), recall (R), and primary micro F1-scores (F1). An entity mention is correct when its entity type and the region of its head are correct, and a relation mention is correct when its relation type and both entity arguments are correct.

Data source for English in ACE2005 is as follows: 20% Newswire (NW), 20% Broadcast News (BN), 15% Broadcast Conversation (BC), 15% Weblog (WL), 15% Usenet Newsgroups/Discussion Forum (UN), and 15% Conversational Telephone Speech (CTS). The two small subsets UN and CTS are informal, so we remove them. In addition, in order to compare with state of the art, we employ the same method as previous work [17] to split and preprocess the data. Training set contains 351 documents, development set contains 80 documents, and testing set contains 80 documents.

We set up Python2.7 + Theano + Cuda7.5 environments to implement our method. We use the publicly available word embedding Glove [18] to initialize the word embedding table, and its dimension n_e is 300. We fix the dimension of part-of-speech embedding n_d and the dimension of entity type embedding n_t to 50 and fix the dimension of entity position embedding n_l to 5. Those feature embeddings are randomly initialized and allowed to be modified during training. In addition, we fix the state size of all the LSTM units to 200 and fix the dimensions of other hidden layers to 100. We use tanh for the nonlinear function.

We tune hyperparameters using development set to achieve high F1. The best hyperparameters are as follows. Dropout rate [19] is 0.5, minibatch size is 30, the constraint of max-norm regularization is equal to 3, and initial learning rate is 0.0005. The reward after each action is described in the Section 3.1. Therefore, for all the experiments below, we will directly employ the best hyperparameters.

We run experiments to analyze the effectiveness of the various components of our joint extraction method.

Firstly, we compare the performance of BILSTM with a baseline system, LSTM for entity extraction task. We train models using training set and report models' performance on development set in Table 2. The result shows that BILSTM obtains better performance than LSTM on all evaluation metrics. Bidirectional model can actually improve the performance of sequence tagging task. Therefore, throughout the experiment, we will use BILSTM to extract entities.

Then, to demonstrate the effectiveness of the relation extraction component of our method, we carry out experiments on relation extraction when entities are known. We build a baseline system, CNN. In addition, we parse relation mentions using the Stanford neural dependency parser [20] and directly use Tree-LSTM extract relations. On the basis of Tree-LSTM, we use reinforcement learning method to control the process of relation extraction. We compare the performance of the above three methods on development set in Table 3. The result demonstrates that Tree-LSTM is better suited to extract relations than CNN, and reinforcement learning method obtains a substantial gain in recall-score over Tree-LSTM with 3.7%. Therefore, in the rest of the experiment, we will use reinforcement learning method based on Tree-LSTM to extract relations.

Finally, we demonstrate the effectiveness of our joint extraction method. We build a pipelined system, which directly connects the entity extraction component and the relation extraction component above. To be specific, the pipelined system first trains the entity extraction model and then builds a separate relation extraction model using the detected entities. Our joint system is based on the pipelined system. The joint system uses attention based method to pass entity information to relation extraction and updates the parameters in all the components simultaneously during the training procedure for Q-Learning, which realizes the joint extraction of entities and relations. We compare the performance of the two systems on development set in Table 4. The result demonstrates that our joint system slightly improves the performance of entity extraction and significantly improves the performance of relation extraction. Therefore, the experiments show that our method is effective and practical.

We will clearly show the process of the above experiments. Figure 5 shows the average reward after each training epoch. At the beginning of training, the reward is negative, because the agent takes actions randomly. But with the increase of epoch number, the reward improves gradually. Figure 6 shows the learning curves of the performance for entity extraction and relation extraction. The F1-score in both (a) and (b) increases simultaneously. From the two figures, we can clearly see that all the metrics significantly improve and then stabilize after 13 epochs of training. So we set the number of training epochs as 13.

Now deep learning methods achieve state-of-the-art performance in end-to-end relation extraction task. Miwa and Bansal [21] stacked bidirectional tree-structured LSTM-RNNs on bidirectional sequential LSTM-RNNs to extract entities and relations between them, which could capture both word sequence and dependency tree substructure information. The method is denoted by SPTree. Table 5 compares our joint extraction method with SPTree on the testing set and shows that our method performs slightly better than SPTree for both entity mentions and relation mentions. Although our method is not comparable with SPTree in precision-score, our method outperforms the best results of SPTree in recall-score. The main reason is that the reward after each action in reinforcement learning may play an important role.

We pretrain the attention model which is used for relation mention classification. Relation mention classification is always processed in a very unbalanced corpus, where most sentences are not a relation mention. From Figure 7, we see that the SGD algorithm gets to the minimum objective fast, but the objective function's value is a bit high. That means that during the pretraining of the attention model there would be a huge loss. The parameters in the attention layer are updated to accepted values, which are prepared for Q-Learning. When we do Q-Learning, we learn a stacked MLP on top of the attention model (without softmax output layer). From Figure 7, we see that Q-Learning takes more epochs to converge but reduces the value of the objective function in the first stage of the MDP. That means that our reinforcement learning method is effective despite the huge loss and poor initialization in the pretraining of the attention model. Moreover, Figure 8 shows the learning curves of the performance for relation mention classification. We can see that our reinforcement learning method gets good performance in the F1-score, which is also a proof of our effectiveness.