Distant supervised relation extraction via long short term memory networks with sentence embedding

Abstract

Distant supervision is a widely applied approach in field of relation extraction, which could automatically generate large amounts of labeled training corpus with minimal manual effort. However, the labeled training corpus may have many false positive instances, which would hurt the performance of relation extraction. Moreover, in traditional distant supervised approaches, extraction models adopt human-design features with complicated natural language processing (NLP) preprocessing. It may cause poor performance either. To address these two shortcomings, in this work, we propose a novel Long Short Term Memory (LSTM) network integrated with multi-instance learning. Our approach is supposed to learn and extract features automatically from the data itself and treats distant supervision as a multi-instance learning problem to settle the problem of false positive instances. Experimental results demonstrate that our proposed approach is effective and achieve better performance than traditional methods.

Keywords

Distant supervision relation extraction LSTM sentence embedding multi-instance learning

1. Introduction

Relation extraction, which is defined as a task of extracting semantic relations between a pair of entities expressed in text, has attracted increasing attention in big data era. It can play a significant role in various scenarios, e.g. information extraction [32, 10], question answering [20], knowledge base construction [9], ontology learning [41], etc. Most approaches to relation extraction use supervised learning of relation-specific instances, which would achieve high precision and recall. However, traditional fully supervised approaches are unlikely to scale to the large amount of relations found on Web and are limited by the availability of training data [34].

Due to the shortcoming of supervised approaches described above, recently, a more promising approach named distant supervision (DS) has gained much attention, which creating its own training data by heuristically aligning facts in existing knowledge bases to free text [21, 34, 36, 37]. The core of distant supervision for relation extraction is an assumption that if two entities have a relationship in a known knowledge base, then all sentences that contain this pair of entities will express the same relationship in some way [21]. Figure 1 shows a simple example for distant supervision in relation extraction domain. In the example, Barack Obama and United States are related entities in Freebase1

¹
http://www.freebase.com/.

and we use

r(e1,e2)=

EmployedBy (Barack Obama, United States) to indicate the relationship. According to assumption of distant supervision, all sentences that mention synonyms for both entities

e1=

Barack Obama and

e2=

United States, are considered to be a expression of the fact that

r(e1,e2)

holds and are selected as positive training instances.

Figure 1.

Automatic labeling by distant supervision. The first sentence is a correct labeling instance and the second sentence is an incorrect labeling instance.

The strategy of distant supervision is an effective approach of automatically labeling training data and a sound solution to solve the problem of availability of big data, which is suitable for text mining and web mining [8, 36, 37]. However, it has two major shortcomings constraining the effectiveness of relation extraction. Firstly, the original distant supervision assumption is too strong and may cause wrong label problem, i.e. false positive instances [36]. A sentence containing a pair of entities does not express the relation which is in a knowledge base. It is possible because the entities may just appear in the same sentence and share the same topic [6]. For instance, consider the relation EmployedBy between Barack Obama and United States in Fig. 1. The first sentence indeed expresses the relation EmployedBy between two entities. In distant supervision approach, EmployedBy is assigned to the sentence which becomes a useful training instances. On the other hand, the second sentence does not express the relation between two entities. However, distant supervision approach heuristically labels the second sentence as expressing the relation EmployedBy and selects the second sentence as a positive training example either. These false positive instances would hurt the performance of relation extraction model which is trained based on such noisy data [34].

Moreover, previous research has typically applied traditional machine learning models to exquisitely designed features with labeled training data obtained through distant supervision [21, 34, 36]. These features are derived from existing natural language processing (NLP) tools, such as openNLP2

²
http://sourceforge.net/projects/opennlp/.

and Stanford coreNLP,3

http://github.com/stanfordnlp/CoreNLP.

which would generate inevitable errors. Therefore utilizing these tools to obtain traditional designed features leads to error propagation or accumulation [6]. According to statistics [6], in a benchmark distant supervision dataset which was developed by Riedel et al. [36], approximately half of sentences are longer than 40 words. McDonald and Nivre found accuracy of syntactic parsing decreases significantly with increasing length of sentence [35]. Therefore, when using traditional human designed features in distant supervision for relation extraction, the problem of error propagation or accumulation would bring about much more serious effect on performance.

In this paper, we propose a novel Long Short Term Memory (LSTM) network integrated with multi-instance learning to address two shortcomings described above. We treat distant supervision for relation extraction as a multi-instance learning problem to settle the first deficiency similar to previous studies [6, 21, 23, 34, 36]. In multi-instance learning problem, the training dataset are divided into many bags which consists of many instances and each bag has a label [39]. When a bag is labeled as negative, it means that all the instances in the bag are negative. But when a bag is labeled as positive, we only know that as least one instance in the bag is positive. In distant supervision for relation extraction, a bag is considered as a pair of entities, label of a bag stands for a relation which two entities holds and instances in the bag are all sentences containing both two entities. Inspired by Zeng et al. [6], we utilize an objective function at the entity pair level and integrating the function into our novel LSTM networks. In this way, during training process, the uncertainty of label of instances could be taken into account, which mitigates the wrong label problem.

To address the error propagation or accumulation problem, we adopt LSTM architecture inspired by Xu et al. [44] to automatically extract features without artificial design or complicated NLP processing. We utilize the shortest dependency path (SDP) of sentences [16] as input of LSTM-based recurrent neural networks. Although SDP has been shown to be effective for relation extraction, it abandon parts of sentence and cannot capture complete information of the sentence containing two entities. Sentence embedding is a real-valued vector and proved to be able to capture syntactic and semantic information of whole sentence [13, 27, 28]. Thus in our extraction model we combine sentence embedding with the output of LSTM units at hidden layer to furnish supplementary information for relation extraction. To effectively train and update parameters of our model, we also customize a new dropout strategy to alleviate overfitting. Therefore, our approach is expected to exhibit superior performance compared with traditional methods.

The contributions of our work can be summarized as follows.

•

We propose a novel LSTM network combined with sentence embedding to performing distant supervision for relation extraction to avoid artificial designed features. Our model is suppose to automatically learn and extract features without complicated NLP preprocessing. To the best of our knowledge, we are the first work to use LSTM-based recurrent neural networks for distant supervision in relation extraction domain.

•

In our designed network, we introduce sentence embedding to supply complete syntactic and semantic information in whole sentence, which remedies the limitation of using SDP as our input of LSTM-based networks.

•

To figure out the problem of false positive instances in training data, we incorporate multi-instance learning into our LSTM-based network for distant supervised relation extraction.

In the rest of this paper, we review related work in Section 2. The formalizing description of distant supervision for relation extraction is introduced in Section 3. In Section 4, we describe our LSTM-based model in detail. Section 5 presents quantitative experimental results. Finally, we have our conclusion in Section 6.

2. Related work

Relation extraction is a widely studied topic in NLP community. Various supervised-learning methods to relation extraction have been proposed [2, 4, 5, 12, 16, 17, 18]. In these methods, relation extraction is deemed to be a multi-class classification problem which can achieve high precision and recall [4, 12, 26]. However, supervision learning methods may suffer from a lack of labeled training data and are unlikely to scale to thousands of relations found in text on the Web. To address this deficiency of supervised-learning methods, Mintz et al. [21] introduced distant supervision for relation extraction, which adopted Freebase to heuristically label a textual corpus. Riedel et al. [36], Hoffmann et al. [34] and Surdeanu et al. [23] relaxed the original distant supervision assumption, i.e. if two entities participate in a relation, at least one sentence that mentions these two entities might express that relation, and presented a series of models casting distant supervision. The relaxed assumption converts distant supervision into a multi-instance learning problem, which is coined by Dietterich et al. [39].

Recent work has focused on filtering noisy data in heuristically labeled training data generated by distant supervision. Takamatsu et al. [37] proposed a generative model of the labeling process to improve the quality of labels before training relation extraction model as a preprocessing step. Xu et al. [42] analyzed random samples from New York Times corpus, indicating that a large amount of entity pairs expressing a relation Freebase defined correspond to false negative instances. They adopt pseudo-relevance feedback to add missing entries in the knowledge base before training MultiR [34].

These studies have been proved to be effective for distant supervision in relation extraction. Whereas the performance of their models relies on the quality of artificial designed features heavily. Most existing approaches have concentrated on extracting features to classify semantic relations between two entities, which mainly fall into three classes: feature-based [8, 26], kernel-based [19, 29, 30] and neural network-based [5, 18, 22, 44]. In feature-based methods, different feature sets are extracted and selected, which would be fed into a classifier. Generally, three types of features are utilized, i.e. lexical features (e.g. POS, etc.), syntactic features (e.g. parsing tree, etc.) and semantic features (e.g. entity type, entity mention, etc.) [26]. Feature-based methods may suffer from the difficulty of selecting an appropriate feature set and transforming structured representations into feature vectors. Kernel-based approaches specify a measure of similarity between two instances without explicit feature representation. Several kernels have been proposed, such as convolution tree kernel [19], subsequence kernel [29] and dependency tree kernel [30]. The potential deficiency of kernel-based methods is that all data information is completely measured by the designed kernel function, and devising an effective kernel becomes crucial.

Deep neural networks have attracted growing attention in the literature, which can learn underlying features automatically. Socher et al. [38] proposed a recurrent neural network (RNN) with parsing tree of sentences to classify relations between entities. Hashimoto et al. [17] improved the performance by weighting importance of phrases in RNN. Ebrihimi and Dou [14] adopted dependency path between two indicated entities to build a RNN model. Xu et al. [44] fed the shortest dependency path instead of whole path into their LSTM-based RNN model and achieve a better result. Other neural networks are utilized to extract relation either. Zeng et al. [5] explored convolution neural networks (CNN) using sequential information about sentences and Dos Santos et al. [2] proposed a ranking loss function to train their CNN model.

Inspired by Zeng et al. [6] and Xu et al. [44], we propose a use of LSTM-based networks with multi-instance learning to learn features automatically for distant supervised relation extraction. Zhang and Zhou [25] integrated multi-instance learning with traditional back propagation (BP) and radial basis function (RBF) networks successfully by minimizing a sum-of-squares error function. Like Zeng’s work [6], we define an objection function based on cross-entropy principle.

3. Distant supervision for relation extraction

In this section, we concentrate on distant supervision for extraction of relations between two entities. A relation instance is defined as an expression $r(e1,e2)$ , where $r$ is a relation name, e.g. Employed in Fig. 1, and $e$ 1 and $e$ 2 are two entity names, e.g. Barack Obama and United States.

An entity mention as a contiguous sequence of text tokens denoting an entity name. In this paper, we assume all the entity mentions in a corpus are extracted by a different process, such as named entity recognition.

A relation mention is a sequence of text including two or more entity mentions, which indicates that a certain relation instance $r(e1,e2)$ is true. In this paper, we only focus on the extraction of binary relations expressed in a single sentence.

Distant supervision for relation extraction utilizes a knowledge base to create labeled data for relation extraction by heuristically matching entity pairs [37]. A knowledge base is a set of relation instances of predefined relation names. For each sentence in a corpus, we extract all of its entity pairs. Then for each entity pair, we try to retrieve all the relation instances about the entity pair from the knowledge base. If we found such a relation instance, i.e. a relation mention, a set of the entity pair and the sentence is stored as a positive example. If not, a set of the entity pair and the sentence is stored as a negative example. Through this procedure, training data are automatically constructed.

4. Methodology

In this section, we describe our LSTM-based network incorporating with multi-instance learning in detail to fulfill distant supervision for relation extraction, which is formulated as a multi-instance problem. Subsection 4.1 delineates the overall architecture of our model. Subsection 4.2 introduces the merit and demerit of using the shortest dependency path as input of our model. Subsection 4.3 discusses the rationale of adopting word embeddings and sentence embedding to provide supplementary semantic information. LSTM units and softmax layer are explained in Subsections 4.4 and 4.5. Subsection 4.6 customizes a dropout strategy for our model to alleviate overfitting. We finally integrate multi-instance learning with our LSTM-based model in Subsection 4.7. For convenient expression, we will abbreviate our proposed model to SE-LSTM (LSTM with Sentence Embedding).

4.1 Overall architecture

Figure 2 gives the overall architecture of our SE-LSTM network. A sentence containing two entities is given which is parsed to a dependency tree by Stanford parser and the shortest dependency path (SDP) is extracted as input of SE-LSTM. In the input layer, word tokens in each SDP are mapped to low-dimensional distributed representations, which are real-valued vectors called word embeddings [31, 40] and could capture the underlying syntactic and semantic information of the inputs. Then each SDP would be separated into left and right sub-path by the common ancestor node of two entities, and two recurrent neural networks are utilized to extract implicit feature and information of the two sub-path, respectively. In each recurrent neural networks, long short term memory (LSTM) units are adopted for effective information propagation. Next, a max pooling layer is applied to pick up the most deterministic feature of each sub-path and fixed the dimension of outputs of LSTM units. After that, the max pooling layers for two sub-path are thereafter concatenated and then are combined with the embedding of the whole sentence into a vector. Subsequently, the concatenated vector would be fed into a full-connected hidden layer which exports a confidence score vector of relation labels. In the end, a softmax output layer is used to predict relation names.

Figure 2.

The overall architecture of SE-LSTM.

Figure 3.

The dependence parse tree of the sentence ‘Barack Obama is the 44th and current President of the United States.’ The bold lines describe the shortest dependency path between entities Barack Obama and United States.

4.2 The shortest dependency path

Dependency parsing tree is proved to be suitable for relation extraction because it concentrates on the action and agents in a sentence [16]. Moreover, the shortest dependency paths are informative to determine the two entities’ relation, which focus on the most relevant information while diminishing relevant noise [29, 44]. For example, Fig. 3 demonstrates the shortest dependency path of the aforementioned example sentence. As the entities’ relation distinguishes its directionality, i.e. for a certain relation $r$ and two entities $a$ and $b,r(a,b)$ differs from $r(b,a)$ . Therefore, in this paper, it is necessary to consider the directionality of relation. Inspired by Xu et al. [44], we spilt each SDP into two sub-paths by the common ancestor node of two entities, which provide large amounts of information on relation’s directionality, as shown in Fig. 4. The Left sub-path contains information of $e$ 1, Barack Obama, whereas the right sub-path captures information of $e$ 2, United States. Through the direction of two sub-path separately, we can conclude that Barack Obama and United States are of relation EmployedBy (Barack Obama, United States) rather than EmployedBy (United States, Barack Obama). Thus we adopt two recurrent networks using LSTM units to keep our model direction-sensitive, which propagate information bottom-up from the entities to their common ancestor.

Figure 4.

The shortest dependency path is split into two sub-path by the common ancestor node of two entities, i.e. ‘is’.

4.3 Vector representation

Raw word tokens in each sub-path are mapped into low-dimensional vectors as other literature [2, 5, 31, 40] when using a neural network model. Every input word token is transformed into a real-valued vector by looking up pre-trained word embeddings which are trained on large-scale corpuses. Moreover, we introduce sentence embedding to make up for the information loss caused by SDP, which are illustrated in Subsection 4.3.2.

4.3.1 Word embeddings

Word embeddings are distributed representations of words. Through a lookup operation, every word in word sequence is mapped into a dense, low-dimensional and real-valued vectors, which is proposed in recent years [15, 40]. Each dimension of word embeddings expresses a latent feature of words. Such distributed representations of words have been verified to be able to capture the syntactic and semantic information and similarity property significantly [40, 15]. Using pre-trained word embeddings has become common practice for enhancing many NLP tasks [1, 7].

Word embeddings are encoded by column vectors in an embedding matrix $W\in R^{d\times|V|}$ , where $d$ is the dimension of the word embedding and $|V|$ is the size of vocabulary. Each column $W_{i}\in R^{d}$ corresponds to the word embedding of the $i$ -th word in the vocabulary. We transform a word $w$ into its word embedding $r^{\textit{emd}}$ by using a matrix-vector product:

$\displaystyle r^{\textit{emd}}=Wv^{w}$ (1)

where $v^{w}$ is a vector of size $|V|$ which has value 1 at index $w$ and zero in all other positions. The matrix $W$ is a parameter to be learned, and the size of word embeddings $d$ is a hyper-parameter to be chosen.

4.3.2 Sentence embedding

Although SDP can extract the most significant feature of the sentence containing two entities, adopting SDP only is insufficient for relation extraction. As mention in Section 1, approximately half of the sentences are longer than 40 words in the benchmark DS dataset [6]. However, SDP reduces the length of the sentence too rapidly and is unable to capture the whole important semantic information of the sentence for relation extraction. What’s more, word embeddings are severely limited because they cannot capture long-distance dependencies and semantic compositionality. Therefore, we introduce sentence embedding [13, 27, 28] to provide supplementary semantic information of the given sentence containing two entities.

Figure 5.

The architecture utilized for extracting sentence embedding.

Sentence embedding is obtained through a max-pooled convolution neural network proposed by Kim [45]. Figure 5 describes the model to offer sentence embeddings which can extract sentence level semantic and syntactic features automatically. Let $x_{i}\in R^{d}$ be a $d$ -dimensional word embedding corresponding to the $i$ -th word in a sentence. Then we represent the sentence of length $n$ as a matrix $S\in R^{n\times d}$ . A convolution operation utilizes a filter $F\in R^{k\times d}$ , which would be applied to a window of $k$ words to produce a new local feature. For instance, a local feature $c_{i}$ is acquired from a window of words $x_{i:i+k-1}$ through the following equation

$\displaystyle c_{i}=f(w\cdot x_{i:i+k-1}+b)$ (2)

where $b\in R$ is a bias term and $f$ is a non-linear function. Using Eq. (2) the filter $F$ convert the sentence to a feature map $C=[c_{1},c_{2},...,c_{n-k+1}]$ . It is noted that the model would adopt multiple filters to obtain multiple feature maps. Subsequently a max-pooled operation [31] is applied over the whole feature map and take the maximum value $c_{\textit{max}}=$ Max{ $C$ } as the most significant feature of the whole sentence. This max-pooled operation can also fix the length of feature despite input sentences are length-variable. After the max-pooled operation, multiple features are passed to a fully connected non-linear transformation layer to generate sentence embedding $s^{\textit{emd}}$ .

4.4 Long short term memory units in recurrent neural network

Recurrent neural network (RNN) models are promising deep learning models which can represent phrases of arbitrary length in a vector space of a fixed dimension [14, 17, 38]. It is indicated that RNNs are suitable for modeling sequential data such as text and speech, because they keep a hidden state vector $h$ , which changes with input data at each step accordingly. We utilize RNN models to extract features and information along each sub-path in our SDP. Although RNNs perform effectively in many NLP tasks, it is generally difficult to learn the long-distance dependencies within a sequence due to gradient vanishing problem. RNNs use gradient back propagation algorithm to train networks and to update parameters. If the propagation path is too long, the gradient would probably either blows up or decay exponentially. One of the effective solutions for this problem in RNNs is to adopt Long Short Term Memory (LSTM) units instead of traditional neurons.

LSTM architecture was proposed and extended by [33]. The main mechanism of LSTM is to adopt memory blocks to decide the degree of information that LSTM unit should keep and memorize. In the literature, many LSTM variants have been proposed. Inspired by Xu’s work [44], we adopt a variant version of LSTM introduced by [43]. More specifically, a LSTM unit consists of one recurrently memory cell and three multiplicative blocks, i.e. an input gate $i_{t}$ , an output gate $o_{t}$ and a forget gate $f_{t}$ , which provide continuous analogues of writing, reading and reset operations for the cell.

Figure 6.

Inner structure of a long short term memory unit.

Figure 6 depicts one LSTM unit. Concretely, the LSTM unit at $i$ -th word of the input depends on the previous state $h_{t-1}$ , the current input $x_{t}$ and the memory cell $c_{t-1}$ . New vectors are calculated using the following equations.

$\displaystyle i_{t}=\sigma(W^{(i)}\cdot x_{t}+U^{(i)}\cdot h_{t-1}+b^{(i)})$ (3) $\displaystyle f_{t}=\sigma(W^{(f)}\cdot x_{t}+U^{(f)}\cdot h_{t-1}+b^{(f)})$ (4) $\displaystyle o_{t}=\sigma(W^{(o)}\cdot x_{t}+U^{(o)}\cdot h_{t-1}+b^{(o)})$ (5) $\displaystyle u_{t}=\tanh(W^{(u)}\cdot x_{t}+U^{(u)}\cdot h_{t-1}+b^{(u)})$ (6) $\displaystyle c_{t}=i_{t}\odot u_{t}+f_{t}\odot c_{t-1}$ (7)

where $\sigma$ denotes the logistic function, $\odot$ denotes element-wise multiplication, $W$ and $U$ are weight matrices and $b$ is bias vector. The output of LSTM units is the hidden state of recurrent networks, which is computed by Eq. (8) as follows and is fed to the subsequent units.

$\displaystyle h_{t}=o_{t}\odot\tanh(c_{t})$ (8)

Then a max-pooling operator [5, 31, 44] runs over all the LSTM units to extract the global prominent feature in each dimension for two sub-path.

4.5 Output

The output layer determines the relation label of input relation mention, and consists of a full-connected layer which is called penultimate layer and a softmax layer. For each relation mention, the exports of the two max-pooling layers and sentence embedding $S$ , are concatenated directly in the follow way.

$\displaystyle H=[h_{\textit{Left}},h_{\textit{Right}},S]$ (9)

which are then fed into the penultimate layer.

$\displaystyle p=\tanh(W^{(p)}\cdot H+b^{(p)})$ (10)

To compute confidence of each relation label, the vector $p$ is connected to a softmax layer.

$\displaystyle o=W^{(s)}\cdot p+b^{(s)}$ (11)

where $W^{(p)}$ , $W^{(s)}$ are weight matrix, $b^{(p)}$ , $b^{(s)}$ are bias vectors, which would be learned via a basic optimization technique called batch gradient descent (BGD) [3]. And $o$ is the final output of the SE-LSTM model.

4.6 Dropout strategies

It is proved that deep neural networks which contain multiple hidden layers could achieve satisfactory performance for many specific tasks. However, because training data is inadequate, deep neural networks with a great amount of parameters always suffer the problem of overfitting [44]. Therefore, a suitable regularization approach is needed to alleviate this inevitable problem. Dropout, proposed by Hinton [11], has been indicated to be successful in deep learning domain. Through dropping out of neural units randomly during training phase, dropout can generate more robust network units and achieve better performance. Three dropout strategies are attempted for our SE-LSTM network.

•
Dropout word embeddings and sentence embedding.
•
Dropout the penultimate layer.
•
Dropout inner cells in LSTM units.

On the basis of comparison results of experiments in Section 5.5, the first two dropout strategies remarkably boost the performance of our model. Whereas, omitting inner cells of LSTM units is demonstrated to be harmful to SE-LSTM network.

In the first strategy, i.e. dropout word embeddings and sentence embedding, following equations are given.

$\displaystyle i_{t}=\sigma(W^{(i)}\cdot D^{p}(x_{t})+U^{(i)}\cdot h_{t-1}+b^{(% i)})$ (12) $\displaystyle f_{t}=\sigma(W^{(f)}\cdot D^{p}(x_{t})+U^{(f)}\cdot h_{t-1}+b^{(% f)})$ (13) $\displaystyle o_{t}=\sigma(W^{(o)}\cdot D^{p}(x_{t})+U^{(o)}\cdot h_{t-1}+b^{(% o)})$ (14) $\displaystyle u_{t}=\tanh(W^{(u)}\cdot D^{p}(x_{t})+U^{(u)}\cdot h_{t-1}+b^{(u% )})$ (15) $\displaystyle H=[h_{\textit{Left}},h_{\textit{Right}},D^{p}(S)]$ (16)

where $D^{p}$ denotes the dropout operator and $p$ is the probability of omitting the unit. Each dimension in word embeddings and sentence embedding is set to zero with probability $p$ .

In penultimate layer, given the input $H$ concatenated by the outputs of two max-pooling layers and sentence embedding directly, corresponding dropout strategy is implemented by utilizing the following equation.

$\displaystyle p=\tanh(W^{(p)}\cdot D^{p}(H)+b^{(p)})$ (17)

where $D^{p}$ denotes the dropout operator and $p$ is the probability of omitting the unit as mention above.
4.7 Multi-instance Learning

It is proved that there may be large amounts of false positive instances in distant supervision for relation extraction because the original assumption is too strong [21, 34, 36]. In order to alleviate the problem of wrong label, we relax the assumption and convert distant supervision for relation extraction to a multi-instance problem like many scholars. In this paper, we integrate multi-instance learning and our proposed SE-LSTM networks model inspired by Zhang and Zhou [25] and Zeng et al. [5]. In the distant supervision for relation extraction problem, supposing that $\theta$ is the collection set of all parameters of our SE-LSTM model include word embeddings, sentence embedding and all the weight matrices and bias vectors, i.e. $\theta=(W^{\textit{emd}},S^{\textit{emd}},W,b)$ . Given a input instance $r$ , SE-LSTM model with the parameter set $\theta$ would output a vector $o$ . In the output vector $o$ , the $m$ -th dimension $o_{m}$ is the confidence score of relation $m$ . In the original training phase of model, a softmax function is adopted over all relations to obtain the conditional probability $p(m|r;\theta)$ .

$\displaystyle p(m|r;\theta)=\frac{e^{o_{m}}}{\sum\limits_{k}{e^{o_{k}}}}$ (18)

Multi-instance learning introduces the concept of bag which contains multiple instances. We assume there are $N$ bags [ $B_{1}$ , $B_{2}$ , …, $B_{N}$ ] in our distant supervised relation extraction, and the $i$ -th bag consists of $k$ instances $B_{i}=$ [ $b_{i}^{1}$ , $b_{i}^{2}$ , …, $b_{i}^{k}$ ]. The target of multi-instance learning is to predict the label of bags instead of each instance. Therefore, we should define an objective function aiming at bags.

$\displaystyle J(\theta)=\sum\limits_{i=1}^{N}{\log p(y_{i}|b_{i}^{k};\theta)}$ (19)

where $k$ denotes the relation mention which can maximize $p(y_{i}|b_{i}^{k}$ ; $\theta$ ), i.e. the following equation.

$\displaystyle k^{\ast}=\arg\max p(y_{i}|m_{i}^{k};\theta)$ (20)

We adopt stochastic gradient descent over shuffled mini-batches with Adadelta [24] update rule to maximize $J$ ( $\theta$ ) through above equations. The procedure is described in Algorithm 1.

[h] Multi-instance Learning 1. Initialize the parameter set $\theta$ 2. Split each bag into mini batches of a fixed size.3. Repeat until desired convergence is satisfied or the maximum number of epochs is reached.4. For each bag $B_{i}$ 4. Choose a mini-batch randomly, and input into SE-LSTM.5. Find the instance $m_{i}^{k}$ in each bag according to Eq. (20)6. Update $\theta$ based on the gradients of the instance $m_{i}^{k}$ using Adadelta.

As described above, in the training phase, our SE-LSTM model would update parameters based on bags instead of each relation mention, which reflects the essential of distant supervised relation extraction because false positive instances are inevitable.

5. Experiments

In purpose to verify that our proposed SE-LSTM model is effective to automatically learning features and can reduce wrong label instances using multi-instance learning, extensive experiments have been carried out in this section. Section 5.1 introduces the dataset we adopted. Section 5.2 describes experimental hyper-parameter settings and evaluation metrics used. In Section 5.3, we compare SE-LSTM’s performance with several traditional methods. We also analyze the effect of sentence embedding and multi-instance learning in Section 5.4.

5.1 Experimental dataset

Following [21, 34, 36], we evaluate our method on the same dataset4

⁴
http://iesl.cs.umass.edu/riedel/ecml/.

in our experiments which was developed by [36]. This dataset was generated by aligning Freebase relations with the New York Times corpus. Freebase is an online knowledge base, which stores facts about entities and their relations. And the New York Times corpus5

⁵

http://catalog.ldc.upenn.edu/LDC2008T19.

contains over 1.8 million articles written and published by the New York Times between January 1, 1987 and June 19, 2007. In our experiments, we adopt sentences from the years 2005–2006 as our training corpus and sentences from 2007 used as the testing corpus.

5.2 Experimental settings

5.2.1 Parameter settings

This subsection describes hyper-parameter tuning for our approach. To ensure a fair comparison, we utilize a three-fold validation to tune all the hyper-parameters of our model just as Surdeanu did [23]. Table 1 demonstrates all hyper-parameters used in the experiments. We set word embeddings to be 50-dimensional and the penultimate hidden layer is 50-dimensional. While in training phase, the batch size is fixed to 50. Following Zeiler [24], two main parameters Adadelta relying on, i.e. $\varepsilon$ and $\rho$ are set to be 1 $e^{-6}$ and 0.95, respectively.

Table 1
Hyper-parameter in the experiments

Word embedding dimension	Penultimate dimension	Batch size	Adadelta parameter
			$\varepsilon$	$\rho$
50	50	50	1 $e^{-6}$	0.95

5.2.2 Pre-trained word embeddings

The word embeddings used in our experiments are 50-dimensional and initialized by unsupervised pre-training. We use the Skip-gram neural network architecture to pre-train word embeddings which is available in the word2vec tool6

⁶
http://code.google.com/p/word2vec/.

designed by Mikolov et al. [40]. To ensure our pre-trained word embeddings are large scale and effective, we adopt the December 2013 snapshot of the English Wikipedia corpus7

⁷

http://en.wikipedia.org/.

to train word embeddings with word2vec in the first place. Then we continually train our word embeddings on the New York Times corpus between 1987 and 2007. Following [2], we preprocess training corpus using the following steps:

•

Remove paragraphs that are not in English.

•

Substitute non-western characters for a special character.

•

Remove sentences that are less than 20 characters long including white spaces.

•

Lowercase all words and substitute each numerical digit for a single zero.

It is notable that we utilize the pre-trained word embeddings to obtain sentence embedding either.

5.2.3 Evaluation metrics

As same as [21], we adopt two evaluation metrics to assessment our SE-LSTM model in distant supervised relation extraction, which are the held-out evaluation and the manual evaluation specifically. In the held-out evaluation method, the extracted relation instances are only compared with Freebase facts and the precision/recall curves of the experiments are shown to indicate whether our SE-LSTM model is effective. In the manual evaluation, we check the extracted relation instances manually which are not appearing in Freebase faces [6].

5.3 Experimental results and discussions

5.3.1 Baselines

We compare our approach against three traditional methods to evaluate the performance of our proposed SE-LSTM model.

•
Mintz: This is an original model for distant supervised relation extraction proposed by [21].
•
MultiR: This is a distant supervision for relation extraction model based on multi-instance learning, which was developed by [34]. MultiR transforms relation extraction into a multi-instance problem, but adopts a Perceptron algorithm and uses a deterministic ‘at-least-one’ assumption instead of a relation classifier.
•
MIML: This is a multi-instance multi-label model for distant supervised relation extraction, which is proposed by [23]. MIML models the latent assignment of labels to instances and dependencies between labels assigned to the same entity pair.

5.3.2 Held-out evaluation

Following [21, 34, 36], we use the held-out evaluation to demonstrate whether our SE-LSTM model is effective. The held-out evaluation provides an approximate measure of precision without manual evaluating. In our experiments, half of the Freebase facts are used for testing. Relation instances discovered from the test articles are automatically compared with those in Freebase. As for training cost, our approach processes around 100 sentences per second on a single NVIDA Tesla K20 GPU.

In Fig. 7, we compare the precision and recall curve for the three baseline distant supervision model, i.e., Mintz, MultiR and MIML and our proposed SE-LSTM model with multi-instance learning (MIL). The curve is constructed by ranking the predicted relation instances using their log-linear score. From Fig. 7, we can see that our SE-LSTM with MIL is consistently outperforming the three baseline methods with achieving higher precision over the entire range of recall. It is noticed that three baseline models are utilizing artificial designed features. However, our approach learns features automatically from original word tokens in sentences. The results of experiments are indicating that SE-LSTM with MIL is effective for distant supervised relation extraction, and features obtained by SE-LSTM can degrade the influence of error propagation which occurs in traditional feature engineering. Moreover, integrating SE-LSTM and multi-instance learning is a sound and valid solution to reduce false positive instances in distant supervision for relation extraction.

Figure 7.

Comparison of precision and recall curve for the Riedel dataset of SE-LSTM with multi-instance and three baseline methods.

Figure 8.

Precision comparison of SE-LSTM with multi-instance and three baseline methods in manual evaluation.

5.3.3 Manual evaluation

For the manual evaluation we adopt all Freebase facts as training instances. As relation candidate instances we choose those entity pairs which at least one participating entity is not in Freebase. It is meaning that there is no overlap between the held-out and manual candidates. Then we apply our models to the test set, and evaluate the top- $K$ extracted relation instances artificially. Due to the unknown amount of relation instances expressed in the test data, we cannot calculate recall in this case. Instead, we adopt a Precision at top- $K$ metric following [36]. Figure 8 shows the precisions for values of $K$ between 0 and 1000 (at 100, 200, 500 and 1000).

The results of experiments show that our SE-LSTM with MIL obtains competitive or even better precision than other three baseline models. More specifically, as $K=$ 1000 we observe that a precision of 52% for SE-LSTM with MIL and 43%, 47% and 48% for Mintz, MultiR and MIML, respectively. Figure 8 demonstrates that SE-LSTM with MIL is significantly better than three baseline models in this scenario, with $p\subset$ 0.05.

In addition, it is noted that the precision in manual evaluation case is much higher than in held-out evaluation case. This is because in the held-out evaluation, false negative instances in Freebase are in the majority of incorrect instances [37]. However, many of the false negative instances are in fact true relation instances which are misclassified due to the absence in Freebase. This is the same reason that there is a sharp decline in the held-out precision-recall curves [6].

5.4 Effect of sentence embedding and multi-instance learning

In this paper, we introduce sentence embedding to provide supplementary semantic information of the given sentence containing two entities and we incorporate multi-instance learning into our SE-LSTM model. This subsection analyzes how sentence embedding and multi-instance learning affect our model. To demonstrate the effect of the above two techniques, we first adopt LSTM alone through held-out evaluation as a baseline. Then we integrate sentence embedding and multi-instance learning with LSTM, respectively. The results of comparison experiments are presented in Fig. 9.

We see from Fig. 9 that when sentence embedding is incorporating into LSTM model, SE-LSTM yield a remarkable performance compared with LSTM alone. This phenomenon is indicated that proposed SE-LSTM is beneficial and can effectively capture structural and semantic information for sentence-level relation extraction. Moreover, we notice that after integrating multi-instance learning (MIL) technique, both LSTM with MIL and SE-LSTM with MIL achieve greater performance than their counterparts, LSTM alone and SE-LSTM alone, respectively. This suggests that adding multi-instance learning into our SE-LSTM can indeed degrade the problem of false positive instances in distant supervision for relation extraction effectively. Overall, SE-LSTM with MIL achieves the best performance due to the combination of both sentence embedding and multi-instance learning.

Table 2
Top 500 precision in manual evaluation of three dropout strategies at different dropout probability

Dropout probability	Precision ( $K=$ 500)
	LSTM units (%)	Embeddings (%)	The penultimate layer (%)
0	0.64	0.64	0.64
0.2	0.62	0.64	0.65
0.5	0.62	0.65	0.65
0.8	0.61	0.63	0.66
1	0.59	0.62	0.65

Figure 9.

Effect of sentence embedding and multi-instance learning.

5.5 Effect of different strategies of dropout

It has been proved that deep neural networks such as LSTMs have complex structure and large amounts of parameters, which probably lead to a better functional fitting capability, whereas they are prone to be over-fitting [44]. Therefore techniques which can alleviate such problem would be necessary. The dropout strategy proposed by Hinton et al. [11] is adopted in our approach, which can degrade the over-fitting problem effectively. In order to observe which dropout strategy is proper for our SE-LSTM and find out which dropout rate can bring the best performance, we devise a series of experiments of distant supervised relation extraction in the manual evaluation ( $K=$ 500).

As described in Section 4.6, three dropout strategies are attempted for our SE-LSTM network, i.e. dropout word embeddings and sentence embedding, the penultimate layer and inner cells in LSTM units, respectively. From Table 2, it can be observed that the dropout of omitting inner cells of LSTM units is harmful to the performance of our SE-LSTM network. This is because LSTM has the characteristic of sharing weight, which leads to alleviating the over-fitting problem itself. Thus, the application of dropout is backfired. However, it is indicated that the other two dropout strategies can improve the performance of SE-LSTM. From Table 2, we can see that when dropout rate of word embeddings and sentence embedding is 0.5, SE-LSTM can achieve the best precision. And in terms of the penultimate layer the best precision is obtained when dropout rate is 0.8.

6. Conclusion

In this paper, we propose a novel neural network model for distant supervised relation extraction, SE-LSTM, which could be able to learn and extract features automatically almost from data itself without complicated NLP preprocessing. Meanwhile, we incorporate multi-instance learning into our SE-LSTM to tackle the problem of false positive instances in distant supervision for relation extraction. Experimental results indicate that our proposed approach outperforms traditional methods. Moreover, effect of sentence embedding and different dropout strategies are analyzed and discussed in a series of additional experiments.

The proposed approach just converts distant supervised relation extraction into a multiple instances learning problem. However, distant supervised relation extraction can be posed as a multi-instance multi-label problem [23]. Our future work is to modify our SE-LSTM model to solve the multi-instance multi-label problem.

Footnotes

Acknowledgments

We would like to thank members of Military Data & Knowledge Engineering Lab and the anonymous reviewers for their comprehensive feedback on all the research described here. This work has been supported by The National Natural Science Foundation for Young Scientists of China (Grant No. 71501186).

References

Parikh

A.P.

Cohen

S.B.

and Xing

E.P.

, Spectral unsupervised parsing with additive tree metrics, In: Proceedings of ACL, 2014, pages 1062–1072.

Dos Santos

C.N.

Xiang

and Zhou

, Classifying relations by ranking with convolutional neural networks, In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics, 2015.

Wilson

and Martinez

, The general inefficiency of batch training for gradient descent learning, Neural Networks 16(10) (2003), 1429–1451.

Zelenko

Aone

and Richardella

, Kernel methods for relation extraction, J. Mach. Learn. Res. 3 (2003), 1083–1106.

Zeng

Liu

Lai

et al., Relation Classification via Convolutional Deep Neural Network, In: COLING, 2014, pages 2335–2344.

Zeng

Liu

Chen

et al., Distant Supervision for Relation Extraction via Piecewise Convolutional Neural Networks, In: Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2015, pp. 17–21.

Huang

Ahuja

Downey

Yang

et al., Learning representations for weakly supervised natural language processing tasks, Journal of Computational Linguistics 40(1) (2014), 85–120.

Suchanek

Ifrim

and Weikum

, Combining linguistic and statistical analysis to extract relations from web documents, In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006, pp. 712–717.

Suchanek

Fan

Hoffmann

et al., Advances in automated knowledge base construction, SIGMOD Records Journal, March 2013.

10.

and Weld

, Open information extraction using Wikipedia, In: Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, 2010.

11.

Hinton

et al., Improving Neural Networks by Preventing Co-adaptation of Feature Detectors, Computer Science 3(4) (2012), 212–223.

12.

Zhou

G.D.

Zhang

D.H.

et al., Tree kernel-based relation extraction with context-sensitive structured parse tree information, In: Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 2007.

13.

Palangi

Deng

Shen

et al., Deep sentence embedding using the long short term memory network: Analysis and application to information retrieval, IEEE/ACM Transactions on Audio, Speech, and Language Processing 24(4) (2016), 694–707.

14.

Ebrahimi

and Dou

D.J.

, Chain based RNN for relation classification, In: Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2015, pp. 1244–1249.

15.

Pennington

Socher

and Manning

C.D.

, Glove: Global Vectors for Word Representation, In: EMNLP 14 (2014), 1532–1543.

16.

Fundel

Küffner

and Zimmer

, RelEx – Relation extraction using dependency parse trees, Bioinformatics 23(3) (2007), 365–371.

17.

Hashimoto

Miwa

Tsuruoka

et al., Simple Customization of Recursive Neural Networks for Semantic Relation Classification, In: EMNLP, 2013, 1372–1376.

18.

Feng

Huang

et al., Semantic relation classification via convolutional neural networks with simple negative sampling, Computer Science 71(7) (2015), 941–949.

19.

Qian

L.H.

Zhou

G.D.

Kong

et al., Exploiting constituent dependencies for tree kernel-based semantic relation extraction, In: Proceedings of COLING, 2008, pp. 697–704.

20.

Lyyer

et al., A neural network for factoid question answering over paragraphs, In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014, pp. 633–644.

21.

Mintz

Bills

Snow

et al., Distant supervision for relation extraction without labeled data, In: Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 2-Volume 2. Association for Computational Linguistics, 2009, pp. 1003–1011.

22.

Miwa

and Bansal

, End-to-end Relation Extraction using LSTMs on Sequences and Tree Structures[J], arXiv, 1601.00770, 2016.

23.

Surdeanu

Tibshirani

Nallapati

et al., Multi-instance multi-label learning for relation extraction, In: Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Association for Computational Linguistics, 2012, pp. 455–465.

24.

Zeiler

, Adadelta: An adaptive learning rate method, Computer Science, 2012.

25.

Zhang

M.L.

and Zhou

Z.H.

, Adapting RBF neural networks to multi-instance learning, Neural Processing Letters 23(1) (2006), 1–26.

26.

Kambhatla

, Combining lexical, syntactic, and semantic features with maximum entropy models for extracting relations, In: Proceedings of the ACL 2004 on Interactive Poster and Demonstration Sessions, 2004.

27.

Kalchbrenner

Grefenstette

and Blunsom

, A convolutional neural network for modelling sentences, arXiv, 1404.2188, 2014.

28.

Q.V.

and Mikolov

, Distributed representations of sentences and documents, In: ICML 14 (2014), 1188–1196.

29.

Bunescu

and Mooney

, A shortest path dependency kernel for relation extraction, In: Proceedings of HLT/EMNLP, 2005, pp. 724–731.

30.

Bunescu

and Mooney

, Subsequence kernels for relation extraction, In: Proceedings of NIPS 18 (2006), 171–178.

31.

Collobert

Weston

Bottou

et al., Natural language processing (almost) from scratch, The Journal of Machine Learning Research 12 (2011), 2493–2537.

32.

Grishman

, Information Extraction: Capabilities and Challenges, Oxford University Press, August 2011.

33.

Hochreiter

, The vanishing gradient problem during learning recurrent neural nets and problem solutions, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 6(2) (1998), 107–116.

34.

Hoffmann

Zhang

Ling

et al., Knowledge-based weak supervision for information extraction of overlapping relations, In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1. Association for Computational Linguistics, 2011, pp. 541–550.

35.

McDonald

and Nivre

, Characterizing the Errors of Data-Driven Dependency Parsing Models, In: EMNLP-CoNLL, 2007, 122–131.

36.

Riedel

Yao

and McCallum

, Modeling relations and their mentions without labeled text, Machine Learning and Knowledge Discovery in Databases, Springer Berlin Heidelberg, 2010, 148–163.

37.

Takamatsu

Sato

and Nakagawa

, Reducing wrong labels in distant supervision for relation extraction, In: Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1. Association for Computational Linguistics, 2012, pp. 721–729.

38.

Socher

Pennington

Huang

E.H.

et al., Semi-supervised recursive autoencoders for predicting sentiment distributions, In: Proceedings of the Conference on Empirical Methods in Natural Language Association for Computational Linguistics, 2011, pp. 151–161.

39.

Dietterich

Lathrop

R.H.

and Lozano-Pérez

, Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence 89(1) (1997), 31–71.

40.

Mikolov

Chen

Corrado

et al., Efficient estimation of word representations in vector space, Computer Science, 2013.

41.

Wong

Liu

and Bennamoun

, Ontology learning from text: A look back and into the future, ACM Computing Surveys (CSUR) 44(4) (2012), 20.

42.

Zhao

R.L.

and Grishman

, Filling Knowledge Base Gaps for Distant Supervision of Relation Extraction, In: Proceedings of Association for Computational Linguistics, 2013.

43.

Zaremba

and Sutskever

, Learning to execute, arXiv, 1410.4615, 2014.

44.

Mou

et al., Classifying relations via long short term memory networks along shortest dependency paths, In: Proceedings of Conference on Empirical Methods in Natural Language Processing, 2015.

45.

Kim

, Convolutional neural networks for sentence classification, arXiv, 1408.5882, 2014.

Distant supervised relation extraction via long short term memory networks with sentence embedding

Abstract

Keywords

1. Introduction

1 http://www.freebase.com/.

3. Distant supervision for relation extraction

4. Methodology

4.1 Overall architecture

4.3.1 Word embeddings

5.1 Experimental dataset

4 http://iesl.cs.umass.edu/riedel/ecml/.

5.2.1 Parameter settings

Table 1 Hyper-parameter in the experiments

6 http://code.google.com/p/word2vec/.

5.3 Experimental results and discussions

5.3.1 Baselines

5.4 Effect of sentence embedding and multi-instance learning

Table 2 Top 500 precision in manual evaluation of three dropout strategies at different dropout probability

6. Conclusion

Footnotes

Acknowledgments

References

¹
http://www.freebase.com/.

⁴
http://iesl.cs.umass.edu/riedel/ecml/.

Table 1
Hyper-parameter in the experiments

⁶
http://code.google.com/p/word2vec/.

Table 2
Top 500 precision in manual evaluation of three dropout strategies at different dropout probability