Effective Deep Memory Networks for Distant Supervised Relation Extraction

1 Introduction

Relation extraction (RE) aims at extracting semantic relations between entities. Formally, given a sentence s with the annotated head entity eh and tail entity et, the goal of RE is to predict the relations between eh and et. RE is a fundamental task in Natural Language Processing (NLP), and a crucial component for building structured Knowledge Base (KB) from free texts. Previous methods including featurebased approaches [Zhang et al., 2006; Li et al., 2012] and neural-based approaches [Nguyen and Grishman, 2015b] can extract high-quality relational facts based on human annotations. However, the heavy cost of annotation typically limits the existing labeled data of RE in both scale and domains.

A promising RE paradigm that addresses this challenge is distant supervision, which can automatically generate training data by aligning a database of relational facts with text [Mintz et al., 2009]. Figure 1 shows a simple example for a RE domain with two labels. Distant supervision will regard all sentences (S1, S2, S3) that contain these two entities as active instances. Therefore, it can be formalized as a multiinstance multi-label classification problem.

To facilitate the modeling of texts, neural networks have been widely explored in distant supervised RE and achieved state-of-the-art results [Zeng et al., 2015; Lin et al., 2016; Jiang et al., 2016]. Various neural networks such as Convolutional Neural Network (CNN) and Recurrent Neural Network (RNN) have been adopted [Zeng et al., 2014; Xu et al., 2015; Vu et al., 2016] to learn the representation of each instance (sentences), which is then used as the representation of the corresponding entity pair for relation classification.

In this paper, we investigate effective neural attention mechanisms for distant supervised RE. We base our approach on the following two observations:

• Not all context words contribute equally to the inference of relation for an entity pair. For example, in S2, "born" is an important clue for the entity pair (Barack Obama, United States) while "said" is much less important.
• There exists dependencies (e.g., entailment, conflict) between different relations, which is a crucial cue to infer some instances with implicit relation expression. For instance, if triple (A, capital, B) holds, another triple (A, contains, B) will hold as well.

Therefore, a desirable solution should not only have the capability of explicitly capturing the importance of different context words but also automatically learning the dependencies between relations.

In pursuit of these goals, we propose a neural model that includes two attention-based memory networks inspired by the recent success of computational models with explicit memory [Sukhbaatar et al., 2015; Tang et al., 2016;

Lin et al., 2016]. The first one is a a word-level memory network, which learns the importance/weight of each context word with regard to the specific entity pair. Then, the entity pair representation will be computed as the semantic composition of the soft-attended context words. Afterwards, we present a two-layer relation-level attention-based memory network. The first layer is to capture the weight of each active instance, which addresses the wrong labeling problem [Lin et al., 2016]. The second layer is to learn the dependencies between relations. The output of the second layer will be used as the representation of the bag-of-instances for multi-label relation classification. As every component is differentiable, the entire model can be efficiently trained end-to-end with gradient descent. Experimental results show that our model achieve significant and consistent improvements in relation extraction as compared with the state-of-the-art methods.

Our contributions can be summarized as follows:

• We present a novel neural architecture with two memory networks, which is capable of modeling the semantic relatedness of the entity pair with its contexts words as well as the dependencies between relations.
• Experiments on real-world datasets show that our approach significantly and consistently outperforms all baselines.

2 Background

2.1 Memory Network

Memory network is a general machine learning framework introduced by [Weston et al., 2014]. Its central idea is inference with a long-term memory component, which could be read, written to, and jointly learned with the goal of using it for prediction. Formally, a memory network consists of a memory m and four components I, G, O and R, where m is an array of objects such as an array of vectors. Let us take question answering as an example to explain the work flow of memory network. Given a list of sentences and a question, the task aims to find evidences from these sentences and generate an answer, e.g. a word. During inference, I component reads one sentence si at a time and encodes it into a vector representation. Then G component updates a piece of memory mi based on current sentence representation. After all sentences are processed, we get a memory matrix m which stores the semantics of these sentences, each row representing a sentence. Given a question q, memory network encodes it into vector representation eq, and then O component uses eq to select question related evidences from memory m and generates an output vector o. Finally, R component takes o as the input and outputs the final response. [Sukhbaatar et al., 2015; Rush et al., 2015; Tang et al., 2016] demonstrate that multiple hops could uncover more abstractive evidences than single hop, and could yield improved results on question answering , summarization and sentiment classification.

2.2 Convolutional Neural Network

In this section, we briefly introduce how to model entity pair semantic representation with CNN, as widely used in previous studies [Nguyen and Grishman, 2015a; Zeng et al.,

2014]. A CNN with three convolutional filters is illustrated in Figure 2.

Denote a sentence consisting of n words as {w1,w2, ...wi, ...wn}, and each word wi is mapped to its embedding ei ∈ Rd . An additional position feature (PF) is used to indicate the relative distance of the current word to the two entities. A convolutional filter is a list of linear layers with shared parameters. Let lcf be the width of a convolutional filter, and Wcf , bcf be the shared parameters of linear layers in the filter. The input of a linear layer is the concatenation of word embeddings in a fixed-length window size lcf . The output of a linear layer is calculated as Ocf = Wcf · lcf +bcf , where Wcf ∈ Rd×lcf and bcf ∈ Rlen . len is the output length of the linear layer. The output of each convolutional filter is fed to a MaxPooling layer, resulting in an output vector with fixed length.

3 DeepMemory Networks for Distant Supervised Relation Extraction

This section describes our deep memory network approach for distant supervised RE. We first give the task definition and notations, following with an overview of our proposed neural architecture. Then, we provide detailed formalizations of our model in distant supervised RE, with special emphasize on the two major memory components.

3.1 Task Definition and Notation

Given a set of sentences S = {s1, ..., si, ..., sn} consisting of n sentences and an entity pair {eh, et} 1 occurring in all sentences, distant supervised RE aims at predicting the relation of sentence set S towards the entity pair {eh, et}. For example, in figure 1, entity pair ("Obama", "United States") has two labels, "EmployedBy" and "BornIn".

When dealing with a text corpus, we map each word into a low dimensional, continuous and real-valued vector, which is also known as word embeddings [Mikolov et al., 2013; Pennington et al., 2014]. All the word vectors are stacked in a word embedding matrix L ∈ Rdw×|V | , where dw is the dimension of word vector and |V | is vocabulary size. The embedding of the ith word is notated as ei ∈ Rdw×1 , which is a column in the embedding matrix L. In addition, to specify the position of each entity pair, we also use position embeddings for all words in the sentence. Each content word has two relative positions to head entity eh and tail entity et, and they are mapped to two different dp dimensional vectors separately. For example in S1 from Figure 1, the relative distance from the word "President" to head entity "Obama" is -2 and tail entity 'United States' is 1. Finally, we concatenate the word embeddings and position embeddings of all words and denote it as a vector sequence s = {e1, e2, ..., ei, ..., en}, where ei ∈ Rd×1 (d = dw + 2 × dp).

1 In practice, an entity might be a multi-word expression such as "United States". For simplicity, we still consider entity as a single word in this definition. And their entity representation is an average of its constituting word vectors [Sun et al., 2015].

3.2 An Overview of the Approach

In this section, we present an overview of our model for distant supervised RE, as illustrated in Figure 3. Specifically, our model includes two major components, both of which are built with deep memory networks.

Word-Level Memory Network Given a sentence s = {w1,w2, ...,wi, ...,wl} and an entity pair, a word-level memory network is used to model a distributed representation vs of this sentence towards the entity pair. To simplify the interpretation, we consider entity pair as two single words wh and wt. Context word vectors {e1, ..., eeh-1, eeh+1, ..., eet-1, eet+1, ..., el} are stacked and regarded as the external memory l ∈ Rd×(l-2) , where l is the sentence length.

An illustration of this network is given in bottom-left dashed box of Figure 2. In the first computational layer (hop 1), we use the entity vector as input to adaptively select important evidences from memory m through an attention layer. The output of the attention layer and the linear transformation of entity pair vector are summed and fed to the next layer (hop 2). In a similar way, we stack multiple hops and run these steps multiple times, so that more abstractive evidences could be selected from the external memory m. The output vector in the last hop is concatenated with the output of CNN model (Section 2.2) and the resulting vector is considered as the representation of sentence with regard to the entity pair. 2

Relation-Level Memory Network Suppose there is a set S = {s1, ..., si, ..., sn} contains n sentences for entity pair (bag-of-instances) and each sentence si has a distributed representation xi. We further propose a relation-level memory network to generate a representation of the sentence set towards the entity pair. Specifically, for different relations, each entity pair has a different representation.

As shown in the bottom-right dashed box of Figure 2, we build a two-layer memory network for each relation. In the first layer, we follow [Lin et al., 2016] and use instance-level attention to select the sentences which really express the corresponding relation. For relation ri-related memory network , we randomly generate a vector vri which indicates the representation of relation ri and use it to calculate the relevance weight between relation ri and each sentence through a attention layer. In the second layer, we develop a relation-level attention model to learn the dependencies between relations. For instance, if a person is a founder of company (A, founder, B), we will know that A has high probability to be a major shareholder of B (A, major shareholders, B). The input of this layer is the output of the first attention layer and this input will be used to calculate the dependency weights between relation ri and other relation {r1, ..., ri-1, ri+1, ..., rk}. Finally, the resulting representation is used for multi-label relation classification.

2 It is helpful to note that the parameters of attention and linear layers are shared in different hops.

3.3 Word Attention

Here we introduce the word-attention model. The basic idea of attention mechanism is that it assigns a weight (importance) to each lower position when computing an upper level representation (Bahdanauet al., 2015). In this work, we use a word-attention model to compute the representation of a sentence with regard to an entity pair. The intuition is that context words do not contribute equally to the semantic meaning of a sentence. Furthermore, the importance of a word should be different if we focus on different entity pairs. Let us take the sentences "US President Barack Obama meets NBA player LeBron James" as an example. The context word "President" is more important than "player" for entity pair ("US", "Barack Obama"). On the contrary, "player" is more important than "President" for entity pair ("NBA", "LeBron James").

Taking an external memory m ∈ Rd×w and an entity pair vector VEP ∈ R2d×1 (concatenating two entities) as input, the attention model outputs a continuous vector x ∈ Rd×1 , which is a weighted sum of each piece of memory in m:

where w is the memory size, αi ∈ [0, 1] is the weight of mi and ∑i αi = 1. We implement a neural network based attention model. For each piece of memory mi, we use a feed forward neural network to compute its semantic relatedness with the entity pair. The scoring function is calculated as follows:

where Wword-att ∈ R1×3d and bword-att ∈ R1×1 . After obtaining g1, g2, ...gw, we feed them to a softmax function to calculate the final importance distribution α1, α2, ...αw.

One advantage of this model is that it could adaptively assign an importance score to each piece of memory mi according to its semantic relatedness with the entity pair.

3.4 Relation Attention

Next, we explore the importance of all sentences for each relation and learn the dependencies between relations. The final representation of entity pair will be the composition of the sentence representations.

Selective Attention over Instances

In this section, for relation rj-related model, we know that the final representation Rj depends on all sentences representations X = {x1, x2, ..., xn}. Each sentence representation xi contains information about whether entity pair (head,tail)

contains relation rj for input sentence si. Therefore, the vector Rj can be computed as the weighted sum of these sentence vector xi:

where βi is the weight of each sentence vector xi. Then, we use a selective attention to de-emphasize the noisy sentence. Hence, βi is further defined as:

where zi is a query-based function which scores how well the input sentence xi and the predict relation rj matches. We follow [Lin et al., 2016] and select the bilinear form which achieves the best performance in different alternatives:

where A is a weight matrix, and vrj is the relation vector.

Selective Attention over Relations

Suppose there is a set R containing k relation representations for each entity pair, i.e., R = {R1,R2, ...,Rk}. To exploit the dependencies of all relations, we use selective attention to calculate the similarity between each relation. In this section, our attention function is the same as the instance-level attention model. The input is the output of the previous layer {R1, R2, ..., Rk}. The output R∗ j is computed as:

where γi is the similarity between relation Rj and Ri.

where hi is referred as a similarity measure which scores how well the relation Rj and Ri correlates.

where B is a weight matrix.

3.5 Distant Supervised Relation Extraction

We regard the output vector {R∗ 1 , R∗ 2 , ...,R∗k } in last layer of relation-level memory network as the feature, and feed each one to a binary classifier. Therefore the confidence scores for each relation ri can be calculated as:

where matrix Wi ∈ Rd×2 is the collection of weight vectors for each label and bi ∈ R2 is a bias. Afterwards, we apply logistic function on each element of the score vector oi to calculate the probability of each relation:

where M denotes the set of aligned sentences, and i ∈ {1, 2, ..., k}, k is the number of relation labels. A binary label vector y is used to indicate the set of true relations holding between the entity pair, where 1 means a true relation in the set, and 0 otherwise. Following this setting, we design a loss function for multi-label modeling:

where yi ∈ {0, 1} is the true value on label i. We use back propagation to calculate the gradients of all the parameters, and update them with Adadelta [Zeiler, 2012]. Dropout [Srivastava et al., 2014] is also employed on formula (10) for regularization. We randomize other parameters with uniform distribution U( -0.01, 0.01 ). We clamp the word embeddings with 50-dimensional vectors, which is the same as [Jiang et al., 2016].

4 Experiment

We describe experimental settings and report empirical results in this section.

4.1 Experimental Setting

We conduct experiments on the basis of NYT10, a dataset developed by [Riedel et al., 2010] and then widely used in distant supervised relation extraction [Hoffmann et al., 2011; Surdeanu et al., 2012]. This dataset was generated by aligning Freebase relations with the New York Times (NYT) corpus, with sentences from the years of 2005 and 2006 used for training and sentences from 2007 used for testing. Statistics of the datasets are given in Table 1. It is worth noting that we follow [Jiang et al., 2016] and use a filtered version of NYT10 released by them. The new version removes some relations which have very small number of instances.

Following previous work [Lin et al., 2016], we evaluate our method in the held-out evaluation. The held-out evaluation only compares the extracted relation instances, it gives a rough measure of precision without requiring expensive human evaluation. We evaluate the performance of each model with Precision-Recall curve and P@N metric.

4.2 Comparison with ExistingMethods

We compare our approach with three traditional feature-based methods and two popular neural-based methods.

Feature-based methods

(1) Mintz: [Mintz et al., 2009] proposed distant supervision paradigm and developed a multi-class logistic regression for classification. (2) Multir is a multi-instance learning method that was proposed by [Hoffmann et al., 2011] with a deterministic "at-least-one" decision . (3) MIML [Surdeanu et al., 2012] is a multi-instance multi-label approach for distant supervision using a graph model.

Neural-based methods

(1) PCNN [Zeng et al., 2015] is a convolutional neural network based method for relation extraction. This method models overlapping relations by combining sentence-level relation extraction features into entity-pair-level results. (2) ATT: [Lin et al., 2016] pointed out that distant supervision suffers from the entity pair wrong labeling problem. They developed a sentence-level attention model which can dynamically reduce the weights of those noisy instances and achieves stateof-the-art results.

Figure 4 shows the resulting precision-recall curve in the most concerned area. Our model is abbreviated to DMN, which contains a 6-hops word-level memory network and a two layer relation-level memory network. We can find that neural-based methods are extremely strong performer and substantially outperforms feature-based methods, demonstrating that the error propagation brought by NLP tools will hurt the performance of relation extraction. Among the three neural models, DMN and ATT perform better than PCNN, which indicates that taking the sentencelevel selective attention into account is helpful. In addition, we can see that DMN provides superior performance to all other methods by a wide margin, at least between 0 and 0.1 recall.

Table 2 further presents the results using P@N metric. In accordance with our observation in precision-recall curve, DMN is still the winner at most of the entire P@N levels. Another conclusion is that neural network methods are also good at predicting top-ranked results compared with traditional feature-based methods. This is probably caused by the imbalance of corpus and the wrong labeling problem that prevent it from reaching high precision when the recall keeps increasing.

4.3 Effect of word-level and relation-level Memory Network

The most important components in our model is the wordlevel memory network and the relation-level memory network. To demonstrate the effect of these two components, we further conduct ablation experiments, as shown in Figure 5. DMN is our full model with the two memory networks. "w/o word" is the system which removes the word memory part. In this way, the sentence representation is only learned by CNN. "w/o relation" is DMN without the relation memory part, using a sentence-level attention model instead. From the P-R curves of these three models, we can see that different memory networks have diverse emphases. When we incorporate the word-level memory network, most of the improvement resides in recall range [0.0, 0.1], but remains same trend in range [0.1, 0.2]. Compared with the word-level memory network, the relation memory brings improvement almost in all positions. Therefore, both memory networks play an important role in our model.

4.4 Effect of the Number of Hops

In this section, we further investigate the effect of the number of hops in word-level memory network. Results are summarized in Table 3, which lists the performance peak (highest F1

score) for each of the models. Among all of our models from 1 hop to 8 hops, we can observe that using more computational layers could generally lead to better performance, especially when the number of hops is less than three. When the number of hops exceeds 6, the experimental results become worse. We suggest that the reason might lie in the gradient vanishing problem as the memory network going deeper.

5 Related work

Distant supervised relation extraction is a fine-grained classification task in relation extraction, which aims at identifying the semantic relation of a sentence set expressed towards an entity pair [Mintz et al., 2009]. Most of the existing works use machine learning algorithms, and build relation classifier from sentences with automatically annotated relation labels based on Knowledge Base. However, distant supervision inevitably accompanies with the wrong labeling problem. To reduce the impact of noisy data, [Riedel et al., 2010] models distant supervision for relation extraction as a multiinstance single-label problem, which allows multiple mentions for the same tuple but disallows more than one label per object. [Hoffmann et al., 2011; Surdeanu et al., 2012] adopt multi-instance multi-label learning in relation extraction.

Compared with feature-based methods, neural methods are attracting growing interest primarily due to their capacity of learning text representation from data without careful engineering of features, and capturing semantic relations between entity pair and context words in a more scalable way. [Zeng et al., 2015] combines at-least-one multi-instance learning with neural network model to extract relations on distant supervision data. Specifically, a study [Lin et al., 2016] has shown promising results on building sentence-level attention for dynamically calculate the weights of multiple instances. Despite the effectiveness of these approaches, these neural models (e.g. CNN) don't explicitly reveal the importance of context evidences with regard to an entity pair and they ignore the dependencies between relations. In this work, we develop two memory networks that explicitly encode the context importance towards a given entity pair and capture the dependencies between relation labels.

6 Conclusion

In this paper, we develop a novel neural model with two memory networks for distant supervised RE. In first word-level memory network, our model capture importances of context words and automatically model a semantic representation of sentences towards the entity pair. We also successfully devise relation-level memory network to capture the dependencies between relations and incorporating multi-instance multi-label learning. Experimental results show that the proposed approach offers significant improvements over comparable methods.

Acknowledgments

This work was supported by the National High Technology Development 863 Program of China (No. 2015AA015407), National Natural Science Foundation of China (No. 61632011 and No. 61370164).