Revisiting the Negative Data of Distantly Supervised Relation Extraction

As shown in Table 1, the triples in NYT (SKE) datasets¹¹1Detailed description of datasets is in Sec. 5.1 labeled by Freebase²²2Bollacker et al. (2008) (BaiduBaike³³3https://baike.baidu.com/) is 88,253 (409,767), while the ones labeled by Wikidata⁴⁴4Vrandecic and Krötzsch (2014) (CN-DBPedia⁵⁵5 Xu et al. (2017)) are 58,135 (342,931). In other words, there exists massive FN matches if only labeled by one KB due to the incompleteness of KBs. Notably, we find that the FN rate is underestimated by previous researches Min et al. (2013); Xu et al. (2013), based on the manual evaluation of which there are 15%-35% FN matches. This discrepancy may be caused by human error. In specific, a volunteer may accidentally miss some triples. For example, as pointed out by Wei et al. (Wei et al., 2020, in Appendix C), the test set of NYT11 Hoffmann et al. (2011) missed lots of triples, especially when multiple relations occur in a same sentence, though labeled by human. That also provides an evidence that FN’s are harder to discover than FP’s.

We point out that some of the previous paradigms designed for relation extraction aggravate the imbalance and lead to inefficient supervision. The mainstream approaches for relation extraction mainly fall into three paradigms depending on what to extract first.

• P1

  The first paradigm is a pipeline that begins with named entity recognition (NER) and then classifies each entity pair into different relations, i.e., [$s,o$ then $r$]. It is adopted by many traditional approaches Mintz et al. (2009); Chan and Roth (2011); Zeng et al. (2014, 2015); Gormley et al. (2015); dos Santos et al. (2015); Lin et al. (2016).

• P2

  The second paradigm first detects all possible subjects in a sentence then identifies objects with respect to each relation, i.e., [$s$ then $r,o$]. Specific implementation includes modeling relation extraction as multi-turn question answering Li et al. (2019), span tagging Yu et al. (2020) and cascaded binary tagging Wei et al. (2020).

• P3

  The third paradigm first perform sentence-level relation detection (cf. P1, which is at entity pair level.) then extract subjects and entities, i.e., [$r$ then $s,o$]. This paradigm is largely unexplored. HRL Takanobu et al. (2019) is hitherto the only work to apply this paradigm based on our literature review.

We provide theoretical analysis of the output space and class prior with statistical support from three datasets (see Section 5.1 for description) of the three paradigms in Table 2. The second step of P1 can be compared with the first step of P3. Both of them find relation from a sentence (P1 with target entity pair given). Suppose a sentence contains $m$ entities⁶⁶6Below the same., the classifier has to decide relation from $\mathcal{O}(m^{2})$ entity pairs, while in reality, relations are often sparse, i.e., $\mathcal{O}(m)$. In other words, most entity pairs in P1 do not form valid relation, thus resulting in a low class prior. The situation is even worse when the sentence contains more entities, such as in NYT11-HRL. In addition, P1 is not sample efficient because the classifier will be trained/queried $\frac{m(m-1)}{2}$ for the same sentences. For P2, we demonstrate with the problem formulation of CasRel Wei et al. (2020). The difference of the first-step class prior between P2 and P3 depends on the result of comparison between # relations and average sentence length (i.e., $|\mathcal{R}|$ and $\bar{N}$), which varies in different scenarios/domains. However, $\pi_{2}$ of P2 is extremely low, where a classifier has to decide from a space of $|\mathcal{R}|*\bar{N}$. In contrast, P3 only has to decide from $4*\bar{N}$ based on our task formulation (Section 3.1)

Other task formulations include jointly extracting the relation and entities Yu and Lam (2010); Li and Ji (2014); Miwa and Sasaki (2014); Gupta et al. (2016); Katiyar and Cardie (2017); Ren et al. (2017) and recently in the manner of sequence tagging Zheng et al. (2017), sequence-to-sequence learning Zeng et al. (2018b). In contrast to the aforementioned three paradigms, most of these methods actually provide an incomplete decision space that cannot handle all the situation of relation extraction, for example, the overlapping one Wei et al. (2020).

Given an instance $(c_{i},T_{i})$ from $\mathcal{D}$, the goal of training is to maximize the likelihood defined in Eq. (1). It is decomposed into two components by applying the definition of conditional probability, formulated in Eq. (2).

		$\displaystyle\prod_{i=1}^{|\mathcal{D}|}\Pr(T_{i}|\mathbf{c}_{i};\theta)$		(1)
	$\displaystyle=$	$\displaystyle\prod_{i=1}^{|\mathcal{D}|}\prod_{r\in T_{i}}\Pr(r|\mathbf{c}_{i};\theta)\prod_{\langle s,o\rangle\in T_{i}|r}\Pr(s,o|r,\mathbf{c}_{i};\theta),$		(2)

where we use $r\in T_{i}$ as a shorthand for $r\in\{r\mid\langle s,r,o\rangle\in T_{i}\}$, which means that $r$ occurs in the triple set w.r.t. $\mathbf{c}_{i}$; Similarly, $s\in T_{i}$, $\langle s,o\rangle\in T_{i}|r$ stands for $s\in\{s\mid\langle s,r,o\rangle\in T_{i}|r\}$ and $\langle s,o\rangle\in\{\langle s,o\rangle\mid\langle s,r,o\rangle\in T_{i}|r\}$, respectively. $T_{i}|r$ represents a subset of $T_{i}$ with a common relation $r$. $\mathbbm{1}[\cdot]$ is an indicator function; $\mathbbm{1}[\text{condition}]=1$ when the condition happens. We denote by $\theta$ the model parameters.

Under this decomposition, relational triple extraction task is formulate into two subtasks: relation classification and entity extraction.

Our task formulation shows several advantages. By adopting P3 as paradigm, the first and foremost advantage of our solution is that it suffers less from the imbalanced classes (Section 2.2). Secondly, relation-level false negative is easy to recover. When modeled as a standard classification problem, many off-the-shelf methods on positive unlabeled learning can be leveraged. Thirdly, entity-level false negatives do not affect relation classification. Taking S5 in Figure 1 as an example, even though the Birthplace relation between William Swartz and Scranton is missing, the relation classifier can still capture the signal from the other sample with a same relation, i.e., $\langle$ Joe Biden, Birthplace, Scranton $\rangle$. Fourthly, this kind of modeling is easy to update with new relations without the need of retraining a model from bottom up. Only relation classifier needs to be redesigned, while entity extractor can be updated in an online manner without modifying the model structure. Last but not the least, relation classifier can be regarded as a pruning step when applied to practical tasks. Many existing methods treat relation extraction as question answering Li et al. (2019); Zhao et al. (2020). However, without first identifying the relation, they all need to iterate over all the possible relations and ask diverse questions. This results in extremely low efficiency where time consumed for predicting one sample may takes up to $|\mathcal{R}|$ times larger than our method.

We first detect relation at sentence level. The input is a sequence of tokens $\mathbf{c}$ and we denote by $\mathbf{\hat{y}}_{rc}=[\hat{y}_{rc}^{1},\hat{y}_{rc}^{2},...,\hat{y}_{rc}^{|\mathcal{R}|}]$ the output vector of the model, which aims to estimate $\hat{y}_{rc}^{i}$ in Eq. (3). We use BERT Devlin et al. (2019) for English and RoBERTa Liu et al. (2019) for Chinese, pre-trained language models with multi-layer bidirectional Transformer structure Vaswani et al. (2017), to encode the inputs⁸⁸8For convenience, we refer to the pre-trained Transformer as BERT hereinafter.. Specifically, the input sequence $\mathbf{x}_{rc}=[\text{\tt[CLS]},\mathbf{c}_{i},\text{\tt[SEP]}]$, which is fed into BERT for generating a token representation matrix $\mathbf{H}_{rc}\in\mathbb{R}^{N\times d}$, where $d$ is the hidden dimension defined by pre-trained Transformers. We take $\mathbf{h}_{rc}^{0}$, which is the encoded vector of the first token [CLS], as the representation of the sentence. The final output of relation classification module $\mathbf{\hat{y}}_{rc}$ is defined in Eq. (5).

$$\mathbf{\hat{y}}_{rc}=\sigma(\mathbf{W}_{rc}\mathbf{h}_{rc}^{0}+\mathbf{b}_{rc}),$$

(5)

where $\mathbf{W}_{rc}$ and $\mathbf{b}_{rc}$ are trainable model parameters, representing weights and bias, respectively; $\sigma$ denotes the sigmoid activation function.

After the relation detected at sentence-level, we extract subjects and objects for each candidate relation. We aim to estimate $\mathbf{\hat{y}}_{ee}=[0,1]^{N\times 4}$, of which each element corresponds to $\hat{y}_{ee}^{n,k}$ in Eq. (4), using a deep neural model. We take $\mathbf{\hat{y}}_{rc}$, the one-hot output vector of relation classifier, and generate query tokens $\mathbf{q}$ using each of the detected relations (i.e., the “1”s in $\mathbf{\hat{y}}_{rc}$). We are aware that many recent works Li et al. (2019); Zhao et al. (2020) have studied how to generate diverse queries for the given relation, which have the potential of achieving better performance. Nevertheless, that is beyond the scope of this paper. To keep things simple, we use the surface text of a relation as the query.

Next, the input sequence is constructed as $\mathbf{x}_{ee}=[\text{\tt[CLS]},\mathbf{q}_{i},\text{\tt[SEP]},\mathbf{c}_{i},\text{\tt[SEP]}]$. Like Section 4.1, we get the token representation matrix $\mathbf{H}_{ee}\in\mathbb{R}^{N\times d}$ from BERT. The $k$-th output pointer of entity extractor is defined by

$$\mathbf{\hat{y}}_{ee}^{k}=\sigma(\mathbf{W}_{ee}^{k}\mathbf{H}_{ee}+\mathbf{b}_{ee}^{k}),$$

(6)

where $k\in\{s_{start},s_{end},o_{start},o_{end}\}$ is in accordance to Eq. (4); $\mathbf{W}_{ee}^{k}$ and $\mathbf{b}_{ee}^{k}$ are the corresponding parameters.

The final subject/object spans are generated by pairing the nearest $s_{start}$/$o_{start}$ with $s_{end}$/$o_{end}$. Next, all subjects are paired to the nearest object. If multiple objects occur before the next subject appears, all subsequent objects will be paired with it until next subject occurs.

In normal cases, the log-likelihood is taken as the learning objective. However, as is emphasized, there exists many false negative samples in the training data. Intuitively speaking, the negative labels cannot be simply considered as negative. Instead, a small portion of the negative labels should be considered as unlabeled positives and their influence towards the penalty should be eradicated. Therefore, we adopt cPU Xie et al. (2020), a collective loss function that is designed for positive unlabeled learning (PU learning). To briefly review, cPU considers the learning objective to be the correctness under a surrogate function,

$$\ell(\hat{y},y)=\ln(c(\hat{y},y)),$$

(7)

where they redefine the correctness function for PU learning as

$$c(\hat{y},y)=\begin{cases}\mathbb{E}[\hat{y}]&\text{if }y=1,\\ 1-|\mathbb{E}[\hat{y}]-\mu|&\text{otherwise},\end{cases}$$

(8)

where $\mu$ is the ratio of false negative data (i.e., the unlabeled positive in the original paper).

We extend it to multi-label situation by embodying the original expectation at sample level. Due to the fact that class labels are highly imbalanced for our tasks, we introduce a class weight $\gamma\in(0,1)$ to downweight the positive penalty. For relation classifier,

$$\ell_{rc}(\mathbf{\hat{y}},\mathbf{y})=\begin{cases}\displaystyle-\gamma_{rc}\ln(\frac{1}{|\mathcal{R}|}\sum_{i=1}^{|\mathcal{R}|}\hat{y}_{rc}^{i}])&\text{if }y_{rc}^{i}=1\\ \displaystyle-\ln(1-|\frac{1}{|\mathcal{R}|}\sum_{i=1}^{|\mathcal{R}|}\hat{y}_{rc}^{i}-\mu_{rc}|)&\text{otherwise}.\end{cases}$$

(9)

For entity extractor,

$$\ell_{ee}(\mathbf{\hat{y}}^{k},\mathbf{y}^{k})=\begin{cases}\displaystyle-\gamma_{ee}\ln(\sum_{n=1}^{N}\hat{y}_{ee}^{n,k}])&\text{if }y_{ee}^{n,k}=1\\ \displaystyle-\ln(1-|\sum_{n=1}^{N}\hat{y}_{ee}^{n,k}-\mu_{ee}|)&\text{otherwise}.\end{cases}$$

(10)

In practice, we set $\mu=\pi(\tau+1)$, where $\tau\approx 1-\frac{\text{\# labeled positive}}{\text{\# all positive}}$ is the ratio of false negative and $\pi$ is the class prior. Note that $\mu$ is not difficult to estimate for both relation classification and entity extraction task in practice. Besides various of methods in the PU learning du Plessis et al. (2015); Bekker and Davis (2018) for estimating it, an easy approximation is $\mu\approx\pi$ when $\pi\ll\tau$, which happens to be the case for our tasks.

Our experiments are conducted on these four datasets¹⁰¹⁰10We do not use WebNLG Gardent et al. (2017) and ACE04⁹⁹9https://catalog.ldc.upenn.edu/LDC2005T09 because these datasets are not automatically labeled by distant supervision. WebNLG is constructed by natural language generation with triples. ACE04 is manually labeled.. Some statistics of the datasets are provided in Table 1 and Table 2. In relation extraction, some datasets with the same names involve different preprocessing, which leads to unfair comparison. We briefly review all the datasets below and specify the operations to perform before applying each dataset.

• •

  NYT Riedel et al. (2010). NYT is the very first version among all the NYT-related datasets. It is based on the articles in New York Times¹¹¹¹11https://www.nytimes.com/. We use the sentences from it to conduct the pilot experiment in Table 1. However, 1) it contains duplicate samples, e.g., 1504 in the training set; 2) It only labels the last word of an entity, which will mislead the evaluation results.

• •

  NYT10-HRL. & NYT11-HRL. These two datasets are based on NYT. The difference is that they both contain complete entity mentions. NYT10 Riedel et al. (2010) is the original one. and NYT11 Hoffmann et al. (2011) is a small version of NYT10 with 53,395 training samples and a manually labeled test set of 368 samples. We refer to them as NYT10-HRL and NYT11-HRL after preprocessed by HRL Takanobu et al. (2019) where they removed 1) training relation not appearing in the testing and 2) “NA” sentences. These two steps are almost adopted by all the compared methods. To compare fairly, we use this version in evaluations.

• •

  NYT21. We provide relabel version of the test set of NYT11-HRL. The test set of NYT11-HRL still have false negative problem. Most of the samples in the NYT11-HRL has only one relation. We manually added back the missing triples to the test set.

• •

  SKE2019/SKE21¹²¹²12http://ai.baidu.com/broad/download?dataset=sked. SKE2019 is a dataset in Chinese published by Baidu. The reason we also adopt this dataset is that it is currently the largest dataset available for relation extraction. There are 194,747 sentences in the train set and 21,639 in the validate set. We manually labeled 1,150 sentences from the test set with 2,765 annotated triples, which we refer to as SKE21. No preprocessing for this dataset is needed. We provide this data for future research¹³¹³13download url..

We evaluate our model by comparing with several models on the same datasets, which are SOTA graphical model MultiR Hoffmann et al. (2011), joint models SPTree Miwa and Bansal (2016) and NovelTagging Zheng et al. (2017), recent strong SOTA models CopyR Zeng et al. (2018b), HRL Takanobu et al. (2019), CasRel Wei et al. (2020), TPLinker Wang et al. (2020). We also provide the result of automatically aligning Wikidata/CN-KBpedia with the corpus, namely Match, as a baseline. To note, we only keep the intersected relations, otherwise it will result in low precision due to the false negative in the original dataset. We report standard micro Precision (Prec.), Recall (Rec.) and F1 score for all the experiments. Following the previous works Takanobu et al. (2019); Wei et al. (2020), we adopt partial match on these data sets for fair comparison. We also provide the results of exact match results of the methods we implemented, and only exact match on SKE2019.

We show the overall comparison result in Table 3. First, we observe that ReRe consistently outperforms all the compared models. We find an interesting result that by purely aligning the database with the corpus, it already achieves surprisingly good overall result (surpassing MultiR) and relatively high precision (comparable to CoType in NYT11-HRL). However, the recall is quite low, which accords with our discussion in Section  2.1 that distant supervision leads to many false negatives. We also provide an ablation result where BERT is replaced with a bidirectional LSTM encoder Graves et al. (2013) with randomly initialized weights. From the results we discover that even without BERT, our framework achieves competitive results against the previous approaches such as CoType and CopyR. This further prove the effectiveness of our ReRe framework.

To further study how our model behaves when training data includes different quantity of false negatives, we conduct experiments on synthetic datasets. We construct five new training data by randomly removing triples with probability of 0.1, 0.3 and 0.5, simulating the situation of different FN rates. We show the precision-recall curves of our method in comparison with CasRel Wei et al. (2020), the best performing competitor, in Figure 3. 1) The overall performance of ReRe is superior to competitor models even when trained on a dataset with a 0.5 FN rate. 2) We show that the intervals of ReRe between lines are smaller than CasRel, indicating that the performance decline under different FN rates of ReRe is smaller. 3) The straight line before curves of our model means that there is no data point at the places where recall is very low. This means that our model is insensitive with the decision boundary and thus more robust.