Distant supervision (DS) is an important paradigm for automatically extracting relations. It utilizes existing knowledge base to collect examples for the relation we intend to extract, and then uses these examples to automatically generate the training data. However, the examples collected can be very noisy, and pose significant challenge for obtaining high quality labels. Previous work has made remarkable progress in predicting the relation from distant supervision, but typically ignores the temporal relations among those supervising instances. This paper formulates the problem of relation extraction with temporal reasoning and proposes a solution to predict whether two given entities participate in a relation at a given time spot. For this purpose, we construct a dataset called WIKI-TIME 1 which additionally includes the valid period of a certain relation of two entities in the knowledge base. We propose a novel neural model to incorporate both the temporal information encoding and sequential reasoning. The experimental results show that, compared with the best of existing models, our model achieves better performance in both WIKI-TIME dataset and the well-studied NYT-10 dataset. As an important technique to automatically complete the knowledge base and reduce labeling efforts, distant supervision (DS) for relation extraction has drawn much attention. In DS, we align the entity pair ( head, tail ) from a triple (cid:104) head, rel, tail (cid:105) extracted from a huge knowledge base (e.g., Freebase, Wikidata) with sentences from free texts (e.g., Wikipedia, New York Times)  Jian Li is the corresponding author. to obtain the training examples, and the label of such an example is the corresponding relation rel Therefore, DS can automatically create a set of training data for each entity pair. However, the noisy training data problem (Riedel et al., 2010) significantly affects the performance of DS. Therefore, most of the recent approaches (Riedel et al., 2010; Hoffmann et al., 2011; Zeng et al., 2015; Lin et al., 2016) follow a common assumption called the at-least-once assumption, which treats all aligned sentences of each entity pair as one training sample. We refer to a sentence as an instance and all sentences aligned to one entity pair as a mention set in the following, respectively. The models in previous work (Zeng et al., 2015; Lin et al., 2016; Luo et al., 2017) generally include two parts, encoding and fusion . The former encodes each instance into a low-dimensional representation. The latter combines representation of each instance. Then, their combination is used to predict the relation. Although the approaches mentioned above seem promising, they have the following limitations: 1. They all use a separate but identical encoding module among instances and introduce no difference temporally. 2. They only adopt single step of fusion and introduce no sentence-level reasoning. We remark that the aforementioned approaches may be enough for the standard NYT-10 dataset (Riedel et al., 2010), because the dataset only extracts instances from New York Times corpus from the year 2005 to 2007 and consists of few mention sets with long time span. However, as one can easily imagine, ignoring temporal information may cause inaccurate predictions, especially when a mention set has a long time span and some instances express different relations. For example, suppose we want to predict the relation between Angelina Jolie and Brad Pitt (using Wiki-data). The knowledge base contains a factual relation of spouse between them with the valid period from August 2014 to September 2016. However, the extracted mention set contains instances about their marriage in 2014, as well as their divorce in 2016. Because existing models do not encode temporal information, the relation they extract is likely to be the one with highest confidence. In this example, their models may predict the relation of marriage since the instances may suggest a higher confidence for the relation of marriage. But the correct prediction should be divorce. As shown in the above example, we can see it is necessary to include temporal information in DS. On the other hand, in fusion module, most existing work focused on denoising using methods such as attention or reinforcement learning. We want to argue that a sentence-level reasoning can also be useful since there are instances which are not direct positive examples for the given relation, but can provide supporting evidence. We call them remote instances. Consider the Jolie-Pitt example again. Suppose we are to predict their relation after their divorce. The instances about their marriage also indirectly help to infer their divorce since marriage is the premise of divorce. Hence, we need an algorithm that can incorporate temporal information and perform reasoning over remote instances. In this paper, we address both limitations and extend the task to predict the relation of a particular entity pair at any specific time spot. The problem can be formulated as a sequence labeling problem (See  2). We propose a novel relation extraction architecture that can address both aforementioned limitations. Our model follows the popular encoding-fusion architecture, but makes two crucial modifications. Firstly, we introduce temporal encoding to model the temporal information among the instances in the encoding. Secondly, we use the Memory Network (Sukhbaatar et al., 2015; Miller et al., 2016) to iteratively reason over temporally augmented encodings in the fusion part. Moreover, we evaluate our model on the widely studied NYT-10 dataset (Riedel et al., 2010) and a new WIKI-TIME dataset. The construction of WIKI-TIME is similar to that of the NYT-10 dataset except for two important differences. One is that we only consider triples (cid:104) head, rel, tail (cid:105) with the valid period ( T 1 , T 2) . For example, the triple (cid:104) Jolie, married, P itt (cid:105) has a valid period of (2014 . 08 , 2016 . 09) . The other is that we extract contextual temporal information for each aligned instance. We use Wikidata (Vrandecic and Krotzsch, 2014) as knowledge base and Wikipedia as free corpus. Both automatic and manual evaluation are applied in the experiments. The experimental results show that, compared with existing models, our model can achieve compara-ble/better performance in both WIKI-TIME and standard NYT-10 datasets. We introduce a new task aiming to solve the problem of relation extraction with temporal information. We propose a novel relation extraction architecture, which encodes both the temporal and semantic information and includes remote instances for temporal reasoning. We construct a new WIKI-TIME dataset by aligning Wikidata to Wikipedia, which is specially designed for the task of relation extraction with temporal information. The experiment results show that, compared with the best of existing models, our model achieves comparable/better performance both in WIKI-TIME dataset and stan-dart NYT-10 dataset. Given two entities (cid:104) head, tail (cid:105) and their corresponding mention set S = { s 1 , s 2 ,    , s T } , where s i denotes the i th instance, the task aims to predict the probability for specific relation r of (cid:104) head, tail (cid:105) : entities at any specific time spot. Because modeling over any specific time spot is non-trivial, we relax the goal to predict the relation between two given entities at any mentioned time spots. Note that we can infer the relations at other time spots using prediction at mentioned ones. Formally, the relation r t at t  ( t 1 , t 2 ] can be infered by r t 1 . Therefore, we can model the problem as a sequence labeling problem with noisy inputs. Given two entities, we collect the chronologically sorted list of its mention instances and the time spot associated with each instance . We denote the list by S = { ( s 1 , t 1 ) ,    , ( s T , t T ) } , where ( s i , t i ) is the i th instance and the associated time spot. Our goal is to predict the probability of relation r at time spot t i : P ( r t i | S = { ( s 1 , t 1 ) ,    , ( s T , t T ) } , t i ) . Note that RNN-like models are not suitable for this sequence labeling problem, because the input sequence contains noisy sentences and lacks direct dependency between time steps. We propose a neural model called TempMEM which models the sequence labeling problem by creating query sequence based on each mentioned time spot. TempMEM also follows the encoding-fusion framework (Zeng et al., 2015; Lin et al., 2016; Luo et al., 2017). However, we make two crucial mod-ifications to the original framework. First, for the encoding part, we use time-aware encoding modules for instances instead of identical ones. Second, we use the memory network to iteratively reason over instances, which makes use of remote instances. For sentence encoding, here we apply the Convolutional Neural Network (CNN) and the Piecewise Convolutional Neural Network (PCNN) (Zeng et al., 2015). Note that, since TempMEM has no preferance over specific sentence encoding, other encoding modules like word memory (Feng et al., 2017) or self-attention can also be used here. The inputs of convolution layers are word embeddings concatenated with position features. For a detailed description of the inputs, we refer the readers to (Zeng et al., 2015). First, the convolution layer extracts local features with sliding window  w over the input representation. Formally, the convolution operates on the concatenation of the input representations X k : k +  w of instance j with the shared parameters W c  RD   w and b c  R 1 : o c,k = W c  X k : k +  w + b c , (3) where o c,k is the k th output of channel c . Then, we use the piece-wise max-pooling layer. It divides the outputs of filters into three parts { o c, 0: h , o c,h : t , o c,t : N } and performs max-pooling over each part: o c = [ max 0  k<h ( o c,k ) , max h  k<t ( o c,k ) , max t  k<N ( o c,k )] , (4) where h and t denote the indices of the head and tail entities, respectively. The concatenation of the output of all channels c is considered as the convolutional representation of instance j : O j = [ o 1 , o 2 ,    , o C ] , (5) where C denotes the number of filters. In order to introduce temporal priorities among instances, it is necessary to inject temporal information into the encoding part. We want the temporal encoding to have the following characteristics:  The temporal encodings should comply with the chronological order of instances. The difference between two time spots determines the similarity between two temporal encodings. Since directly encoding the time spot value leads to huge difference among mention sets of the dataset, we propose an approximate approach with PE encoding (Vaswani et al., 2017) based on the rank (i.e. position of an instance in a mention set with chronological order): P E ( j ) = (cid:40) sin ( j/ 10000 d/d m ) if d %2 = 0 cos ( j/ 10000 ( d  1) /d m ) if d %2 = 1 , (6) where j is the rank of instance s , d is the dimension, and d m is the dimension of temporal encoding. Obviously, the PE encoding complies with the chronological order and the similarity between Figure 1: Overall TempMEM architecture two PE encodings (by dot product) is determined by their rank difference. Then, we concatenate the corresponding temporal encoding with the convolutional features of instance j to form the final representation of each instance with a learnable scale factor  : m j = [ O j ;   P E ( j ) ] . In the fusion part, we use the Memory Network to perform temporal reasoning among different instances. Each encoded instance is considered to be a memory slot. Then, we construct a time specific query and iteratively compute the weighted attention over all instances. We detail the process in the following sections. We construct each query with the guidance of the following intuition. So, we construct our queries based on four key variables, ( relation, head, tail, t i ) . Specifically, we combine the embeddings (pre-trained by TransE (Bordes et al., 2013)) of head and tail and project the combination through an affine matrix  q  RD e  D r , where D e and D r denote the dimension of relation and entity embedding, respectively. After the projection, we add the randomly initialized relation embedding. The formal definition of a query is given below: q r = R r + ( E head + E tail )   q , (8) where R r  RD r is the embedding of specific relation r and E   RD e is the entity embedding. Finally, we also concatenate the query with the same temporal encoding defined in  3.2.2 to obtain the i th query: q r,i = [ q r ;   P E ( i ) ] . In this part, we introduce how to use the queries perform temporal reasoning. Two operations are involved, memory addressing and reading. One of our key motivations is to consider the remote instances. So, instead of using single step attention computation as in previous work (Lin et al., 2016; Luo et al., 2017; Ji et al., 2017), we perform an overall H steps of memory addressing and reading to obtain the final prediction. Within each step (also called hop), we update the query value by adding the output of the previous step, which provides a gradual shift in attention. Next, we introduce the whole process in detail. Memory Addressing In addressing, we compute the similarity between the query vector q i,r and each candidate memory slot key K j . Note that the encoding output m j is not in the same continuous space as the query vector. So, we adopt linear projections to both memory keys: K j = A Th  m j , (10) where A h  RD m  D r . Then, we compute the similarity score and importance probability using the bilinear form, s i,j = q Ti,r  W a  K j , (11) p i,j = exp ( s i,j ) (cid:80) M  j =1 exp ( s i,  j ) , (12) where W a  RD r  D m is the model parameter to be learned and i, j are the indices of queries and memory slots. As for the addressing step, it worths noting that the query and memory slots are both concatenated with temporal encodings. If we define the embedding layer A as the identity matrix, each similarity score of a query-memory pair can be divided into two parts, s i,j = q Ti  o j +  2  P E ( i ) T  P E ( j ) . Each query can automatically attend to instances with either close encoding representations or close temporal encodings. This tradeoff also accords with our intuition, since the confidence of a relational factual statement decreases when the time span increases. Memory reading The value of each memory slot, which is also projected by an affine matrix B  RD m  D r , is read by computing the weighted sum over all memory slots with the importance probability derived in the addressing step:  q i = (cid:88) j p i,j V j , (14) where V j = B Th  m j . Iterative computation Here, we combine the above two operations as a single step for reasoning. We use h  [1 , H ] to denote a particular step, where H is the total step number. To achieve a step-by-step reasoning, we update the next step query q h +1 with the summation of the current step output  q h and the current query q h : q h +1 = q h +  q h . During training, we add dropout with probability p b at the final query step. By combining the previous hop query and the output in this way, TempMEM can gain information from the last read output and shift addressing attention to remote instances. Here we introduce the learning and optimization details of TempMEM. We use query-level CrossEntropy loss as our objective function: J (  ) = N s (cid:88) s =1 T (cid:88) i =1 y t  log p ( y t | S s , , t i ) , (17) where N s is the number of sets and T is the length of query sequence. We use stochastic gradient descent (SGD) to minimize our objective function. For the exploration of optimization, we add small white noise to the gradients (Neelakantan et al., 2015). We also anneal the learning rate l by 0 <  < 1 (i.e., l    l ) for every  epochs. We evaluate our model on two datasets, the widely used NYT-10 dataset which is developed by (Riedel et al., 2010) and the WIKI-TIME dataset we created. This dataset is generated by aligning Freebase entities to New York Times corpus (NYT) of years from 2005 to 2007. There are 53 pre-defined relations including a particular relation NA which indicates no relation between head and tail . The training data contains 522,611 sentences, 281,270 entity pairs, and 18,252 of them are relational facts. The testing data contains 172,448 sentences, 96,678 entity pairs, and 1,950 of them are relational facts. Similar to NYT-10, the WIKI-TIME dataset is also generated by aligning knowledge base entities to free corpus, except that we choose Wikidata and Wikipedia instead of Freebase and NYT news. The motivation of creating WIKI-TIME is to generate a time aligned dataset that can support temporal reasoning. Hence, we filter knowledge base entities that participate in relations with informative temporal features, such as start time, end time. Besides, we tag the aligned sentences with their time expressions in contexts. Then, we align the contextual time expressions with the valid period of each relation to achieve labeling. For example, sentence like: On September 19, 2016, Jolie filed for divorce from Pitt, citing irreconcilable differences. is labeled with no relation (NA). The dataset contains 57 relations. The training set contains 97,616 sentences and 20,085 entity pairs. The test set contains 39,990 sentences and 8,641 entity pairs. 2 4.2 Experiment Details Hyper-Parameter Settings For WIKI-TIME experiments, we construct query over each appeared time spot in the mention set. On the other hand, for NYT-10 experiments, we adopt a single query without temporal encoding to compare results with other baseline methods since the dataset only contains one label for each mention set. Among all experiments, we use 230 convolution kernels with windows size 3. The dropout probability p d is set to 0.5. We try various max hops values H (from 1 to 5) to test how reasoning works in our model. We train the models with 20 epochs and 50 epochs for NYT-10 dataset and WIKI-TIME dataset and report the best performance. As for optimization step, we adopt SGD with gradient plus Gaussian noise with standard deviation of 0.01, which helps to better generalize. Also, we apply gradient decay of rate (  = 0 . 5 ) over every  = 10 epochs. The learning rates for NYT-10 and WIKI-TIME experiments are set to 0.001 and 0.01, respectively. With regard to inputs, we use 50-d Glove (Pen-nington et al., 2014) word embeddings pretri-aned on Wikipedia and Gigaword and 5-d pos-tion embedding. The temporal encodings are either initialized with random 50-d vectors, which are learned during training, or set directly with PE. For entity embeddings, we use the TransE (Bordes et al., 2013) entity vectors pretrained on Wikidata released by the OpenKE platform. descending order (without NA relation) and compute the precision with threshold for each recall value. Also, we report the P @ N values which indicate the precision over N predictions with the highest confidence scores. To test the effect of iterative reasoning over instances, we implement the neural models proposed in previous work (Zeng et al., 2015; Lin et al., 2016), from the source code released by authors. Since the previous models perform prediction in bag-level, the label is given by the latest relation appeared in KB. As for our models, we fix the number of hops H = 2 and set the encoding to CNN. 3 The notations of the experiments are shown in Table 1. As shown in Figure 2 and Table 2, we have the following observations: (1) All TempMEM models achieve better performance compared with the previous neural models (CNNONE, CNN ATT). 3 The PCNN encoding is not used in WIKI-TIME dataset. The detailed explanation is given in Appendix A . Recall that the hop number is set to 2. This can be seen as an ablation experiment. The results suggest that the remote instances can generally help relation extraction task. (2) TempMEM + P clearly outperforms TempMEM + R, which proves that the properly chosen temporal encodings help the performance. Note that, in the columns P@N 200 and P@N 300 of Table 2, we find that the pure TempMEM outperforms TempMEM + P and TempMEM + R. Based on the results in Table 3, their drop of performance comes from the noisy labeling problem of distant supervision. Also, TempMEM can catch relation changes through the timeline of two entities. We refer the readers to the case study in Appendix B . Since the WIKI-TIME is distantly collected, we want to obtain a more precise view of how the models perform. So, we apply the manual evaluation to verify our experimental results. We randomly pick 200 mention sets in the test set of WIKI-TIME and ask two annotators to label the relation for each instance. The annotation rule is to label the instance with the relation that can be inferred from the instance itself or previous instances. As shown in Table 3, the manual evaluated F1 scores are basically consistent with the PR curves in Figure 2, which indirectly proves the WIKI-TIME's quality. Also, we find that the TempMEM + P achieves the best performance and shows obvious advantages in both query-level and bag-level F1 scores over the naive TempMEM (i.e., with no temporal encodings). This proves the effectiveness of our temporal encodings. In this section, we discuss the effect of different number of hops in TempMEM. We change the hop value from 1 to 5 and evaluate the precision and recall of our models in query-level. The hyper-parameters are fixed. The temporal encoding is set to PE and each model is trained for 30 epochs. The results of the hop number experiment are depicted in Figure 3. From the results, we can observe that models show better performance with hop number 2 and 4. Most of the improvement of the model with hop number 4 resides in the recall range [0, 0.05], but the performance remains in the similar trend with other models in the recall range [0.05, 0.2]. In addition, we notice that the performance of the models fluctuates with the increase in the number of hops and the model with even hop number generally perform better than its predecessor, e.g. models with hop number 4 and 5. We believe that the reason might lie in the distribution of the hop distance between origin instance and useful remote instance. In this section, we report our results on the well-studied NYT-10 dataset. By evaluating our model in the NYT-10 dataset, our objective is to prove the power of reasoning among remote instances. Note that, in the NYT-10 dataset, there is no temporal information for each instance, so we only use one query for each mention set and there's no (a) Results with CNN encoding. (b) Results with PCNN encoding. Figure 4: Precison-Recall curve on NYT-10 . Best viewed in color. temporal encoding for each instance. Also, we do not use the entity embedding for the NYT-10 experiments. The results are shown in Figure 4. For both CNN and PCNN models, We can see that our models exceed the performance of all other models (CNN ATT, CNN ONE, CNN AVE, PCNN ATT, PCNN ONE, PCNN AVE) in the range of low recall values. In the high recall range, our models also have results about the same as the best model among others. This suggests that even without the temporal encoding, reasoning over remote instances is indeed useful in relation extraction task. Distant supervision for relation extraction is an important, automatic method of completing knowledge base. (Riedel et al., 2010) made the at-least-once assumption that led the distant supervision for relation extraction to multi-instance learning. (Hoff-mann et al., 2011) and (Surdeanu et al., 2012) tried to model the task with a multi-instance, multi-label setting using the classical graph model. Recently, some work focused on applying deep neural network to the DS task. (Zeng et al., 2014) was the first trial to apply deep learning in relation extraction by solving a classification problem with fully supervised approach. (Zeng et al., 2015) moved a step further and introduced the multi-instance learning paradigm by using only the most important instance to predict relation. (Lin et al., 2016; Liu et al., 2017; Ji et al., 2017) improved the previous work by adding attention mechanism to instances and automatically reducing the weights of noisy instances. There are other approaches that tried to reduce the impact of noise in DS by using active learning (Sterckx et al., 2014) and reinforcement learning (Feng et al., 2018). However, previous work focused on denoising but ignored the exploration of the remote instances and introduced no temporal information to support relation extraction. In this paper, we introduce temporal information into DS and combine it with the memory network to perform reasoning over instances. (Feng et al., 2017) also used the memory network in the context of distant supervision. Their work performed word-level and relation-level reasoning to model the importance of words and dependency between relations. Their motivation was to gain better sentence encoding and relation modeling, while in our model, we apply the sentence-level memory network to understand the inference process among instances. Also, this work is related to temporal relation extraction. (Dligach et al., 2017) was the first approach to use neural models for temporal relation extraction. (Tourille et al., 2017) used a Bi-LSTM to identify narrative containers between events and time expressions. (Cheng and Miyao, 2017) introduced dependency paths and used a common-root to solve the cross-sentence dependency. (Meng and Rumshisky, 2018) leveraged the Neural Turing Machine to enhance context-awareness of the temporal relation extraction model. Previous work in temporal relation extraction was dedicated to event timelining and focused on dealing with relations between event and time expression. In constrast, our model aims to solve general entity to entity relation extraction by instance-level temporal reasoning based on a coarse-grained timelining. Another related research aspect is the temporal slot filling (TSF) task introduced in knowledge base population (Surdeanu, 2013; Ji et al., 2014). Distant supervision approaches (Garrido et al., 2013; Cucerzan and Sil, 2013; Sil and Cucerzan, 2014) (from Freebase and Wikipedia infoboxes) are widely applied to address the lack of supervising data. (Reinanda and De Rijke, 2014) performed the prior-sampling on distant supervision data to correct the mismatch of distributions. The TSF task is similar to the task defined in this paper in the sense that TSF also asks the model to identify the start and end date of one knowledge triple (cid:104) head, rel, tail (cid:105) . The difference is that the TSF task's objective is to predict validity period given the head , rel and tail , while in our setting, we predict rel between two entities in different periods. In this paper, we formulate the task of distant supervision with temporal relation reasoning by modeling it as a sequence labeling problem. Following the DS paradigm, we created a new dataset called WIKI-TIME which is designed for the temporal relation extraction task. In addition, we propose an encoding-fusion model, TempMEM, which combines both encoding and reasoning temporally. At each computation step, our model can automatically attend information with either close representation or close temporal encoding. In experiments, we compare our model with the existing methods in both the well-known NYT-10 dataset and our WIKI-TIME dataset. Both automatic and manual evaluation are applied in the experiments. The experimental results show that our model not only realizes better performance in relation extraction by introducing instance-level reasoning but also improves the reasoning by bringing the temporal information in. In the future, we plan to further explore the effect of different encoding modules like Bi-LSTM or self-attention and try to model temporal information with more sophisticated choices. The research is supported in part by the National Basic Research Program of China Grant 2015CB358700, the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 61761146003, and a grant from Mi-crosoft Research Asia. Also, we want to thank the very kind comments from anonymous reviewers, which help improve this paper.
abstain method abstain abstain objective objective objective result abstain method abstain abstain abstain abstain method abstain abstain abstain abstain abstain objective method abstain method abstain abstain abstain abstain abstain result abstain method abstain abstain method abstain method objective abstain objective method abstain abstain abstain abstain method abstain method method abstain result objective objective objective result abstain abstain abstain method abstain abstain method abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain method other abstain abstain abstain abstain other abstain method method abstain method method method method method method abstain result method abstain abstain abstain method abstain method abstain method method abstain method abstain abstain abstain method method abstain method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain abstain result result abstain abstain abstain result abstain abstain abstain abstain abstain result abstain result abstain abstain abstain abstain abstain abstain abstain abstain result result abstain other other other other other other other other other method other other objective abstain other other other other other objective other other other method objective method objective objective abstain method abstain result objective other other