A Hierarchical Framework for Relation Extraction with Reinforcement Learning

Ryuichi Takanobu, Tianyang Zhang, Jiexi Liu, Minlie Huang

Introduction

Extracting entities, relations, or events from unstructured texts is crucial for building large-scale, reusable knowledge which can facilitate many other tasks (?; ?), including knowledge base construction (?; ?), question answering (?), and biomedical text mining (?).

The task of relation extraction is to identify relations $(e_{s},r,e_{t})$ Throughout this paper, a relation refers to a triple $(e_{s},r,e_{t})$ , a relation type refers to $r$ ., a triple consisting of a relation type $r$ , a source entity $e_{s}$ and a target entity $e_{t}$ . In this paper, we propose a novel joint extraction paradigm in the framework of hierarchical reinforcement learning (?), where we first detect a relation and then extract the corresponding entities as the argument of a relation.

Our model detects relation indicators by a high-level reinforcement learning (RL) process and identifies the participating entities for the relation by a low-level RL process. As shown in Figure 1, the extraction process makes sequential scans from the beginning to the end of a sentence (I). The high-level process is to detect a relation indicator at some particular position. If a certain relation is identified, a low-level sequential process is triggered to identify the corresponding entities for that relation (II). When the low-level subtask for entity extraction is completed (III), the high-level RL process continues its scan to search for the next relation (IV) in the sentence.

This paradigm has strengths in dealing with two issues existing in prior studies. First, most traditional models (?; ?; ?) determine a relation type only after all the entities have been recognized, whereas the interaction between the two tasks is not fully captured. In some sense, these methods are aligning a relation to entity pairs, and therefore, they may introduce additional noise since a sentence containing an entity pair may not truly mention the relation (?), or may describe multiple relations (?).

Second, there still lacks the elegance of the joint extraction method to deal with one-to-many problems (overlapping relations): one entity may participate in multiple relations in the same sentence (see Steve Blichick in Figure 1), or even the same entity pair within a sentence is associated with different relations. To our best knowledge, CopyR (?) is the only method that discussed this issue, which views relation extraction as a triple generation process. However, this method, as our experiments reveal, strongly relies on the training data, and cannot extract multi-word entity mentions.

In our paradigm, the first issue is handled by treating entities as the arguments of a relation. The dependency between entity mentions and relation types is formulated through designing the state representations and rewards in the high-level and low-level RL processes. The interaction is well captured since the main task (high-level RL process for relation detection) passes messages when launching a subtask (low-level RL process for entity extraction), and the low-level rewards, signifying how well a subtask is completed, are passed back to the main task. In this manner, the interaction between relation types and entity mentions can be better modeled.

The second issue is addressed by our hierarchical structure. By decomposing relation extraction into a high-level task for relation detection and a low-level task for entity extraction, multiple relations in a sentence can be handled separately and sequentially. As shown in Figure 1, the first relation is extracted when the main task detects the first relation type (parent-children), and the second relation is subsequently extracted when the second relation type (place-of-death) is triggered, even though the two relations share the same entity (Steve Blichick). Experiments demonstrate the proposed paradigm achieves strong performance over the baselines in extracting overlapping relations.

In summary, our contributions are in two folds:

We design a novel end-to-end hierarchical paradigm to jointly identify entity mentions and relation types, which decomposes the task into a high-level task for relation detection and a low-level task for entity extraction.

By incorporating reinforcement learning into this paradigm, the proposed method outperforms baselines in modeling the interactions between the two tasks, and extracting overlapping relations.

Related Work

Traditional pipelined approaches treat entity extraction and relation classification as two separate tasks (?; ?; ?). They first extract the token spans in the text to detect entity mentions, and then discover the relational structures between entity mentions. Although it is flexible to build pipelined methods, these methods suffer from error propagation since downstream modules are largely affected by the errors introduced by upstream modules.

To address this problem, a variety of joint learning methods was proposed. ? (?) proposed a card-pyramid graph structure for joint extraction, and ? (?) developed graph-based multi-instance learning algorithms. However, the two methods both applied a greedy search strategy to reduce the exploration space aggressively, which limits the performance. Other studies employed a structured learning approach (?; ?). All these models depend on heavy feature engineering, which requires much manual efforts and domain expertise.

On the other hand, ? (?) proposed to first extract relation triggers, which refer to a phrase that explicitly expresses the occurrence of a relation in a sentence, and then determine their arguments to reduce the task complexity. Open IE systems ReVerb (?) identifies relational phrases using lexical constraints, which also follows a “relation”-first, “argument”-second approach. But there are many cases where no relation trigger appears in a sentence so that such relations cannot be captured in these methods.

Neural models for joint relation extraction are investigated in recent studies (?; ?). ? (?) proposed a neural model that shares parameters for entity extraction and relation classification, but the two tasks are separately handled, and the final decision is obtained via exhaustively enumerating the combinations between detected entity mentions and relation types. Unlike aforementioned methods that all the entities are recognized first, ? (?) used a tagging scheme which applies a Cartesian product of the relation type tags and the entity mention tags, and thus each word is assigned a unique tag that encodes entity mentions and relation types simultaneously. However, it is unable to deal with overlapping relations in a sentence: if an entity is the argument of multiple relations, the tag for the entity should not be unique. The recent study (?) is closely related to ours that aims to handle overlapping relations. It employs multiple decoders based on sequence-to-sequence (Seq2Seq) learning where a decoder copies an entity word from the source sentence and each triple in a sentence is generated by different decoders, but such a method strongly relies on the annotation of training data and it cannot extract an entity that has multiple words.

Reinforcement learning has been witnessed in information extraction very recently. RL was employed to acquire and incorporate external evidence in event extraction (?). ? (?) used RL to train an instance selector to denoise training data obtained via distant supervision for relation classification. Improvement was reported in distant supervision relation type extraction by exploring RL to redistribute false positives into the negative examples (?).

Hierarchical Extraction Framework

First of all, we define relation indicator as follows:

Relation indicator is the position in a sentence when sufficient information has been mentioned to identify a semantic relation. Different from relation trigger (i.e., explicit relation mention), relation indicators can be verbs (e.g. die of), nouns (e.g. his father), or even prepositions (e.g. from/by), other symbols such as comma and period (As shown in Figure 1, the relation type place-of-death can be signified till the comma position).

Relation indicator is crucial for our model to complete the extraction task, because the entire extraction task is decomposed into relation indicator detection and entity mention extraction.

The entire extraction process works as follows. An agent predicts a relation type at a particular position when it scans a sentence sequentially. Note that this process of relation detection needs no annotation of entities, thus different from relation classification which is to identify the relations between pairs of entities. When there is no sufficient evidence to indicate a semantic relation at a time step, the agent may choose NR, a special relation type that indicates no relation. Otherwise a relation indicator is triggered, the agent launches a subtask for entity extraction to identify the arguments of the relation, the two entities. When the entity mentions are identified, the subtask is completed and the agent continues to scan the rest of the sentence for other relations.

Such a process can be naturally formulated as a semi-Markov decision process (?): 1) a high-level RL process that detects a relation indicator in a sentence; 2) a low-level RL process that identifies the associated entities for the corresponding relation. By decomposing the task into a hierarchy of two RL processes, the model is advantageous at dealing with sentences which have multiple relation types for the same entity pair, or one-to-many entities in which an entity is the argument of multiple relations.

Relation Detection with High-level RL

The high-level RL policy $\mu$ aims to detect the relations in a sentence $S=w_{1}w_{2}\cdots w_{L}$ , which can be regarded as a conventional RL policy over options. An option refers to a high-level action, and a low-level RL process will be launched once an option is executed by the agent. Option: The option $o_{t}$ is selected from $\mathcal{O}=\{\texttt{NR}\}\cup\mathcal{R}$ where NR indicates no relation, and $\mathcal{R}$ is the relation type set. When a low-level RL process enters a terminal state, the control of the agent will be taken over to the high-level RL process to execute the next options. State: The state $\mathbf{s}_{t}^{h}$ $\in\mathcal{S}$ of the high level RL process at time step $t$ , is represented by: 1) the current hidden state $\mathbf{h}_{t}$ , 2) the relation type vector $\mathbf{v}_{t}^{r}$ (the embedding of the latest option $o_{t^{\prime}}$ that $o_{t^{\prime}}\not=\texttt{NR}$ , a learnable parameter), and 3) the state from the last time step $\mathbf{s}_{t-1}$ where $\mathbf{s}_{t-1}=\mathbf{s}_{t-1}^{h}$ if the agent sampled a high-level option at last time step $t-1$ , and $\mathbf{s}_{t-1}=\mathbf{s}_{t-1}^{l}$ if the agent sampled a low-level action., formally represented by

where $f^{h}(\cdot)$ is a non-linear function implemented by MLP. To obtain the hidden state $\mathbf{h}_{t}$ , we introduce a sequence Bi-LSTM over the current input word embedding $\mathbf{w}_{t}$ :

Policy: The stochastic policy for relation detection $\mu:\mathcal{S}\to\mathcal{O}$ which specifies a probability distribution over options:

Reward: Then, the environment provides intermediate reward $r_{t}^{h}$ to estimate the future return when executing $o_{t}$ . The reward is computed as below:

If $o_{t}=\texttt{NR}$ at certain time step, the agent transfers to a new high-level inter-option state at the next time step. Otherwise the low-level policy will execute the entity extraction process. The inter-option state will not transfer until the subtask over current option $o_{t}$ is done, which may take multiple time steps. Such a semi-Markov process continues until the last option about the last word $w_{L}$ of $S$ is sampled. Finally, a final reward $r_{fin}^{h}$ is obtained to measure the sentence-level extraction performance that $\mu$ detects:

where Fβ is the weighted harmonic mean of precision and recall in terms of the relations in $S$ . $Prec$ / $Rec$ indicates precision/recall respectively, computed over one sentence.

Entity Extraction with Low-level RL

Once the high-level policy has predicted a non-NR relation type, the low-level policy $\pi$ will extract the participating entities for the corresponding relation. The low-level policy over actions (primitive actions) is formulated very similarly as the high-level policy over options. To make the predicted relation type accessible in the low-level process, the option $o_{t^{\prime}}$ from the high level RL is taken as additional input throughout the low-level extraction process. Action: The action at each time step is to assign an entity tag to the current word. The action space, i.e., entity tag space $\mathcal{A}=(\{\texttt{S},\texttt{T},\texttt{O}\}\times\{\texttt{B},\texttt{I}\})\cup\{\texttt{N}\}$ , where S represents the participating source entity, T for the target one, O for the entities that are not associated with the predicted relation type $o_{t^{\prime}}$ , and N for for non-entity words. Note that, the same entity mention may be assigned with different S/T/O tags depending on different relation types concerned at the moment. In this way, the model can deal with overlapping relations. In addition, we use the B/I symbols to represent the beginning word and the inside of an entity, respectively. Refer to Figure 4 for an example. State: Similar to the policy for relation detection, the low-level intra-option state $\mathbf{s}_{t}^{l}$ is represented by 1) the hidden state $\mathbf{h}_{t}$ of current word embedding $\mathbf{w}_{t}$ , 2) the entity tag vector $\mathbf{v}_{t}^{e}$ which is a learnable embedding of $a_{t-1}$ , 3) the state from previous time step $\mathbf{s}_{t-1}$ , and 4) the context vector $\mathbf{c}_{t^{\prime}}$ using the relational state representation assigned to the latest option $\mathbf{s}_{t^{\prime}}^{h}$ in Eq. (1), as follows:

where $\mathbf{h}_{t}$ is the hidden state obtained from the Bi-LSTM module in Eq. (2), and $f^{l}(\cdot)$ , $g(\cdot)$ are non-linear functions implemented by MLP. Note that $\mathbf{s}_{t-1}$ may be a state either from the high-level RL process or the low-level one. Policy: The stochastic policy for entity extraction $\pi:\mathcal{S}\to\mathcal{A}$ outputs an action distribution given intra-option state $\mathbf{s}_{t}^{l}$ and the high-level option $o_{t^{\prime}}$ that launches the current subtask.

where $\mathbf{W}_{\pi}$ is an array of $|\mathcal{R}|$ matrices. RewardWe only discuss the situation where $o_{t^{\prime}}$ is included in $S$ , i.e. the subtask option $o_{t^{\prime}}$ is correctly predicted. Otherwise, all the low-level rewards are set to 0, which can be seen that the agent has done nothing with the low-level policy.: Given the relation type $o_{t^{\prime}}$ , the entity tag for each word can be easily obtained by sampling actions from the policy. Therefore, an immediate reward $r_{t}^{l}$ is provided when the action $a_{t}$ is sampled by simply measuring the prediction error over gold-standard annotation:

where $sgn(\cdot)$ is the sign function, and $y(o_{t^{\prime}})$ is the gold-standard entity tag conditioned on the predicted relation type $o_{t^{\prime}}$ . Here $\lambda(y)$ is a bias weight for down-weighing non-entity tag, defined as follows:

The smaller $\alpha$ leads to less reward on words that are not entities. In this manner, the model avoids to learn a trivial policy that predicts all words as N (non-entity words). When all the actions are sampled, an additional final reward $r_{fin}^{l}$ is computed. If all the entity tags are predicted correctly, then the agent receives +1 reward, otherwise -1.

Hierarchical Policy Learning

To optimize the high-level policy, we aim to maximize the expected cumulative rewards from the main task at each time step $t$ as the agent samples trajectories following the high-level policy $\mu$ , which can be computed as follows:

where $\mu$ is parameterized by $\theta_{\mu}$ , $\gamma$ is a discount factor in RL, and the whole sampling process $\mu$ takes $T$ time steps before it terminates.

Similarly, we learn the low-level policy by maximizing the expected cumulative intra-option rewards from the subtask over option $o_{t^{\prime}}$ when the agent samples along low-level policy $\pi(\cdot|o_{t^{\prime}})$ at time step $t$ :

if the subtask ends at time step $T^{\prime}$ .

By decomposing the cumulative rewards into a Bellman equation, we acquire:

where $N$ is the number of time steps that a subtask continues when the entity extraction policy runs upon option $o_{t}$ , so the agent’s next option is $o_{t+N}$ . In particular, if $o_{t}=\texttt{NR}$ , then $N=1$ .

Then, we use policy gradient methods (?) with the REINFORCE algorithm (?) to optimize both high-level and low-level policies. With the likelihood ratio trick, the gradient for the high-level policy yields:

and the gradient for the low-level policy yields:

The entire training process is described at Algorithm 1.

Experiments

We evaluated our model on the New York Times corpus which is developed by distant supervision and contains noisy relations. The corpus has two versions: 1) The original version generated by aligning the raw data with Freebase relations (?); 2) A smaller version of which the test set was manually annotated (?). We name the original version as NYT10, and the smaller version as NYT11. We split some of the training data from NYT11 to construct NYT11-plus, which will be described later.

We filtered the datasets by removing 1) the relations in the training set whose relation type does not exist in the test set; 2) the sentences that contain no relations at all. Such a preprocess is also in line with the settings in the literature (for instance, Tagging). All the baselines are evaluated in this setting for fair comparison. The statistics of the two filtered datasets are presented in Table 1.

For each dataset, we randomly chose 0.5% data from the training set for validation.

Parameter Settings

All hyper-parameters are tuned on the validation set. The dimension of all vectors in Eq. (1), (2) and (6) is $300$ . The word vectors are initialized using Glove vectors (?) and are updated during training. Both relation type vectors and entity tag vectors are initialized randomly. The learning rate is $4e-5$ , the mini-batch size is $16$ , $\alpha=0.1$ in Eq. (9), $\beta=0.9$ in Eq. (5), and the discount factor $\gamma=0.95$ .

Evaluation Metrics

We adopted standard micro- $F_{1}$ to evaluate the performance. We compared whether the extracted entity mentions can be exactly matched with those in a relation. A triplet is regarded as correct if the relation type and the two corresponding entities are all correct.

Baselines

We chose two types of baselines: one is pipelined methods (FCM), and the other is joint learning methods which include feature-based methods (MultiR and CoType) and neural methods (SPTree, Tagging and CopyR). We used open source codes and conducted the experiments by ourselves. FCM (?): a compositional model that combines lexicalized linguistic contexts and word embeddings to learn representations for the substructures of a sentence in relation extractionAs FCM cannot detect entity mentions alone, we used the NER results and related features obtained from another baseline CoType.. MultiR (?): a typical distant supervision method performing sentence-level and corpus-level extraction, which uses multi-instance weighting to deal with noisy labels in training data. CoType (?): a domain-independent framework by jointly embedding entity mentions, relation mentions, text features, and type labels into representations, which formulates extraction as a global embedding problem. SPTree (?): an end-to-end relation extraction model that represents both word sequence and dependency tree structures using bidirectional sequential and tree-structured LSTM-RNNs. Tagging (?): an approach that treats joint extraction as a sequential labeling problem using a tagging schema where each tag encodes entity mentions and relation types at the same time. CopyR (?): a Seq2Seq learning framework with a copy mechanism for joint extraction, where multiple decoders are applied to generate triples to handle overlapping relations.

Main Results

The results on relation extraction are presented in Table 2. Noticeably, there is a significant gap between the performance on noisy data (NYT10) and that on clean data (NYT11) as all the models are trained on noisy data. It can be seen that our method (HRL) outperforms the baselines on the two datasets. Significant improvements can be observed on NYT10, which indicates that our method is more robust to noisy data. Results on NYT11 show that neural models (SPTree, Tagging and CopyR) are more effective than pipelined (FCM) or feature-based (MultiR and CoType) methods. CopyR is introduced to extract overlapping relations, but it yields poor performance on the NYT11 test set where there is almost no overlapping relation in a sentence (370 relations among 369 sentences). Whereas our model is still comparable to SPTree and performs remarkably better than other baselines. Note that SPTree utilizes more linguistic resources (e.g., POS tags, chunks, syntactic parsing trees). This implies that our model is also robust to the data distribution of relations.

Overlapping Relation Extraction

We prepared another two test sets to verify the effectiveness of our model on extracting overlapping relations. Note that overlapping relations can be classified into two types.

Type I: two triples share only one entity within a sentence

Type II: two triples share two entities (both head and tail entities) within a sentence

The first set, NYT11-plus, is annotated manually and consists of 149 sentences split from the original NYT11 training data. The set contains 210/97 overlapping relations for type I/II respectively. The second set, NYT10-sub, is a subset of the test set of NYT10, and has 715 sentences, but without manual annotation. This set contains 90/2,082 overlapping relations for type I/II respectively. To summarize, most of the overlapping relations in NYT11-plus is of type I; while most in NYT10-sub is of type II. Table 3 shows the performance of extracting overlapping relations by different approaches.

Results on NYT10-sub show that the baselines are very weak to extract overlapping relations of type II on the noisy data, which is consistent with our statement that existing joint extraction approaches cannot deal with overlapping relations effectively in nature. By contrast, our method did not deteriorate too much in performance comparing to that in Table 2, and even obtained a larger gain on precision.

Results on NYT11-plus demonstrate that our method had a substantial $F_{1}$ improvement over all the baselines in extracting overlapping relations of type I on the clean data, indicating that our method can extract overlapping relations more accurately. SPTree had a high precision but low recall since it simply matches one relation type to an entity pair, suffering from ignoring the case of overlapping relations. Tagging had low performance in extracting overlapping relations because it assigns a unique tag to an entity even if that entity participates in overlapping relations. Though CopyR claimed that it can extract overlapping relations of both types, it fails to extract the relations from clean data effectively as it strongly relies on the annotation of the noisy training data.

To conclude, we can see that extracting overlapping relations is more challenging by comparing results in Table 2 and those in Table 3, and our model is better in extracting two types of overlapping relations no matter the data is noisy or clean.

Interaction between the Two Policies

To justify the effectiveness of integrating entities into a relation and how the interactions are built between the two policies, we investigated the performance on relation detection (classification). In this setting, a prediction is treated as correct as long as the relation type is correctly predicted. The prediction is derived from the high-level policy.

The results in Table 5 demonstrate that our method performs better in relation detection on both datasets. The improvements on NYT11-plus are more remarkable as our paradigm is more powerful to extract multiple relations from a sentence. The results indicate that our extraction paradigm which regards entities as arguments of a relation can better capture the relational information in the text.

When removing the low-level entity extraction policy from our model (HRL-Ent), the performance has changed slightly on NYT11 because each sentence almost contains only one relation in this test set (370 relations among 369 sentences). In this case, the interaction between the two policies has almost no influence on relation detection. However, dramatic drops are observed on NYT11-plus where we have 327 relations from 149 sentences, implying that our method (HRL) captures the dependency across multiple extraction tasks and the high-level policy benefits from such interactions. Therefore, our hierarchical extraction framework indeed enhances the interaction between relation detection and entity extraction.

Case Study

Table 4 presents some extraction examples by our model to demonstrate the ability to extract overlapping relations. The first sentence shows the case that an entity pair has multiple relations (type II). Two relations (Rupert Murdoch, person-company, News Corporation) and (News Corporation, company-founder, Rupert Murdoch) share the same entity pair but have different relation types. The model first detects the relation type person-company at “Murdoch”, and then detects the other relation type company-founder at the comma position, just next to the word “Murdoch”. This shows that relation detection is triggered when sufficient evidence has been gathered at a particular position. And the model can classify the same entities into either source or target entities (for instance, Rupert Murdoch is a source entity for person-company whereas a target entity for company-founder), demonstrating the advantage of our hierarchical framework which can assign dynamic tags to words conditioned on different relation types. In addition, Rupert Murdoch has a relation with Australia, where the two entities locate far from each other. Though this is more difficult to detect, our model can still extract the relation correctly.

The second sentence gives another example where an entity is involved in multiple relations (type I). In this sentence, (Steven A. Ballmer, person-company, Microsoft) and (Bill Gates, person-company, Microsoft) share the same relation type and target entity, but have different source entities. When the agent scans to the word “Microsoft”, the model detects the first relation. The agent then detects the second relation when it scans to the word “Gates”. This further demonstrates the benefit of our hierarchical framework which has strengths in extracting overlapping relations by firstly detecting relation and then finding the entity arguments. In addition, our model predicts another relation (Bill Gates, founder-of, Microsoft), which is wrong for this sentence because there is no explicit mention of the relation. This may result from the noise produced by distant supervision, where there are many noisy sentences that are aligned to that relation.

Conclusion and Future Work

In this paper, we present a hierarchical extraction paradigm which approaches relation extraction via hierarchical reinforcement learning. The paradigm treats entities as the arguments of a relation, and decomposes the relation extraction task into a hierarchy of two subtasks: high-level relation indicator detection and low-level entity mention extraction. The high-level policy for relation detection identifies multiple relations in a sentence, and the low-level policy for entity extraction launches a subtask to further extract the related entities for each relation. Thanks to the nature of this hierarchical approach, it is good at modeling the interactions between the two subtasks, and particularly excels at extracting overlapping relations. Experiments demonstrate that our approach outperforms state-of-the-art baselines.

As future work, this hierarchical extraction framework can be generalized to many other pairwise or triple-wise extraction tasks such as aspect-opinion mining or ontology induction.

Acknowledgements

This work was jointly supported by the National Science Foundation of China (Grant No.61876096/61332007), and the National Key R&D Program of China (Grant No. 2018YFC0830200). We would like to thank Prof. Xiaoyan Zhu for her generous support.