Distant Supervision for Relation Extraction with Matrix Completion

Miao Fan

{}^{\dagger,\ddagger,*}

, Deli Zhao

{}^{\ddagger}

, Qiang Zhou

{}^{\dagger}

, Zhiyuan Liu

{}^{\diamond,\ddagger}

, Thomas Fang Zheng

{}^{\dagger}

, Edward Y. Chang

{}^{\ddagger}

{}^{\dagger}

CSLT, Division of Technical Innovation and Development,
Tsinghua National Laboratory for Information Science and Technology, Tsinghua University, China.

{}^{\diamond}

Department of Computer Science and Technology, Tsinghua University, China.

{}^{\ddagger}

HTC Beijing Advanced Technology and Research Center, China.

{}^{*}

fanmiao.cslt.thu@gmail.com

Abstract

The essence of distantly supervised relation extraction is that it is an incomplete multi-label classification problem with sparse and noisy features. To tackle the sparsity and noise challenges, we propose solving the classification problem using matrix completion on factorized matrix of minimized rank. We formulate relation classification as completing the unknown labels of testing items (entity pairs) in a sparse matrix that concatenates training and testing textual features with training labels. Our algorithmic framework is based on the assumption that the rank of item-by-feature and item-by-label joint matrix is low. We apply two optimization models to recover the underlying low-rank matrix leveraging the sparsity of feature-label matrix. The matrix completion problem is then solved by the fixed point continuation (FPC) algorithm, which can find the global optimum. Experiments on two widely used datasets with different dimensions of textual features demonstrate that our low-rank matrix completion approach significantly outperforms the baseline and the state-of-the-art methods.

1 Introduction

Relation Extraction (RE) is the process of generating structured relation knowledge from unstructured natural language texts. Traditional supervised methods [28, 1] on small hand-labeled corpora, such as MUC¹¹http://www.itl.nist.gov/iaui/894.02/related projects/muc/ and ACE²²http://www.itl.nist.gov/iad/mig/tests/ace/, can achieve high precision and recall. However, as producing hand-labeled corpora is laborius and expensive, the supervised approach can not satisfy the increasing demand of building large-scale knowledge repositories with the explosion of Web texts. To address the lacking training data issue, we consider the distant [19] or weak [13] supervision paradigm attractive, and we improve the effectiveness of the paradigm in this paper.

Figure 1: Training corpus generated by the basic alignment assumption of distantly supervised relation extraction. The relation instances are the triples related to President Barack Obama in the Freebase, and the relation mentions are some sentences describing him in the Wikipedia.

The intuition of the paradigm is that one can take advantage of several knowledge bases, such as WordNet³³http://wordnet.princeton.edu, Freebase⁴⁴http://www.freebase.com and YAGO⁵⁵http://www.mpi-inf.mpg.de/yago-naga/yago, to automatically label free texts, like Wikipedia⁶⁶http://www.wikipedia.org and New York Times corpora⁷⁷http://catalog.ldc.upenn.edu/LDC2008T19, based on some heuristic alignment assumptions. An example accounting for the basic but practical assumption is illustrated in Figure 1, in which we know that the two entities ( $<$ Barack Obama, U.S. $>$ ) are not only involved in the relation instances⁸⁸According to convention, we regard a structured triple $r(e_{i},e_{j})$ as a relation instance which is composed of a pair of entities < $e_{i},e_{j}$ >and a relation name $r$ with respect to them. coming from knowledge bases (President-of(Barack Obama, U.S.) and Born-in(Barack Obama, U.S.)), but also co-occur in several relation mentions⁹⁹The sentences that contain the given entity pair are called relation mentions. appearing in free texts (Barack Obama is the 44th and current President of the U.S. and Barack Obama was born in Honolulu, Hawaii, U.S., etc.). We extract diverse textual features from all those relation mentions and combine them into a rich feature vector labeled by the relation names (President-of and Born-in) to produce a weak training corpus for relation classification.

Figure 2: The procedure of noise-tolerant low-rank matrix completion. In this scenario, distantly supervised relation extraction task is transformed into completing the labels for testing items (entity pairs) in a sparse matrix that concatenates training and testing textual features with training labels. We seek to recover the underlying low-rank matrix and to complete the unknown testing labels simultaneously.

This paradigm is promising to generate large-scale training corpora automatically. However, it comes up against three technical challeges:

•

Sparse features. As we cannot tell what kinds of features are effective in advance, we have to use NLP toolkits, such as Stanford CoreNLP¹⁰¹⁰http://nlp.stanford.edu/downloads/corenlp.shtml, to extract a variety of textual features, e.g., named entity tags, part-of-speech tags and lexicalized dependency paths. Unfortunately, most of them appear only once in the training corpus, and hence leading to very sparse features.
•

Noisy features. Not all relation mentions express the corresponding relation instances. For example, the second relation mention in Figure 1 does not explicitly describe any relation instance, so features extracted from this sentence can be noisy. Such analogous cases commonly exist in feature extraction.
•

Incomplete labels. Similar to noisy features, the generated labels can be incomplete. For example, the fourth relation mention in Figure 1 should have been labeled by the relation Senate-of. However, the incomplete knowledge base does not contain the corresponding relation instance (Senate-of(Barack Obama, U.S.)). Therefore, the distant supervision paradigm may generate incomplete labeling corpora.

In essence, distantly supervised relation extraction is an incomplete multi-label classification task with sparse and noisy features.

In this paper, we formulate the relation-extraction task from a novel perspective of using matrix completion with low rank criterion. To the best of our knowledge, we are the first to apply this technique on relation extraction with distant supervision. More specifically, as shown in Figure 2, we model the task with a sparse matrix whose rows present items (entity pairs) and columns contain noisy textual features and incomplete relation labels. In such a way, relation classification is transformed into a problem of completing the unknown labels for testing items in the sparse matrix that concatenates training and testing textual features with training labels, based on the assumption that the item-by-feature and item-by-label joint matrix is of low rank. The rationale of this assumption is that noisy features and incomplete labels are semantically correlated. The low-rank factorization of the sparse feature-label matrix delivers the low-dimensional representation of de-correlation for features and labels.

We contribute two optimization models, DRMC¹¹¹¹It is the abbreviation for Distant supervision for Relation extraction with Matrix Completion-b and DRMC-1, aiming at exploiting the sparsity to recover the underlying low-rank matrix and to complete the unknown testing labels simultaneously. Moreover, the logistic cost function is integrated in our models to reduce the influence of noisy features and incomplete labels, due to that it is suitable for binary variables. We also modify the fixed point continuation (FPC) algorithm [16] to find the global optimum.

Experiments on two widely used datasets demonstrate that our noise-tolerant approaches outperform the baseline and the state-of-the-art methods. Furthermore, we discuss the influence of feature sparsity, and our approaches consistently achieve better performance than compared methods under different sparsity degrees.

2 Related Work

The idea of distant supervision was firstly proposed in the field of bioinformatics [8]. Snow et al. [23] used WordNet as the knowledge base to discover more hpyernym/hyponym relations between entities from news articles. However, either bioinformatic database or WordNet is maintained by a few experts, thus hardly kept up-to-date.

As we are stepping into the big data era, the explosion of unstructured Web texts simulates us to build more powerful models that can automatically extract relation instances from large-scale online natural language corpora without hand-labeled annotation. Mintz et al. [19] adopted Freebase [3, 2], a large-scale crowdsourcing knowledge base online which contains billions of relation instances and thousands of relation names, to distantly supervise Wikipedia corpus. The basic alignment assumption of this work is that if a pair of entities participate in a relation, all sentences that mention these entities are labeled by that relation name. Then we can extract a variety of textual features and learn a multi-class logistic regression classifier. Inspired by multi-instance learning [17], Riedel et al. [22] relaxed the strong assumption and replaced all sentences with at least one sentence. Hoffmann et al. [13] pointed out that many entity pairs have more than one relation. They extended the multi-instance learning framework [22] to the multi-label circumstance. Surdeanu et al. [24] proposed a novel approach to multi-instance multi-label learning for relation extraction, which jointly modeled all the sentences in texts and all labels in knowledge bases for a given entity pair. Other literatures [25, 18, 27, 26] addressed more specific issues, like how to construct the negative class in learning or how to adopt more information, such as name entity tags, to improve the performance.

Our work is more relevant to Riedel et al.’s [21] which considered the task as a matrix factorization problem. Their approach is composed of several models, such as PCA [7] and collaborative filtering [15]. However, they did not concern about the data noise brought by the basic assumption of distant supervision.

3 Model

We apply a new technique in the field of applied mathematics, i.e., low-rank matrix completion with convex optimization. The breakthrough work on this topic was made by Candès and Recht [5] who proved that most low-rank matrices can be perfectly recovered from an incomplete set of entries. This promising theory has been successfully applied on many active research areas, such as computer vision [4], recommender system [20] and system controlling [9]. Our models for relation extraction are based on the theoretic framework proposed by Goldberg et al. [10], which formulated the multi-label transductive learning as a matrix completion problem. The new framework for classification enhances the robustness to data noise by penalizing different cost functions for features and labels.

3.1 Formulation

Suppose that we have built a training corpus for relation classification with $n$ items (entity pairs), $d$ -dimensional textual features, and $t$ labels (relations), based on the basic alignment assumption proposed by Mintz et al. [19]. Let $X_{train}\in\mathbb{R}^{n\times d}$ and $Y_{train}\in\mathbb{R}^{n\times t}$ denote the feature matrix and the label matrix for training, respectively. The linear classifier we adopt aims to explicitly learn the weight matrix ${\bf W}\in\mathbb{R}^{d\times t}$ and the bias column vector ${\bf b}\in\mathbb{R}^{t\times 1}$ with the constraint of minimizing the loss function $l$ ,

\mathop{\operatorname*{arg~{}min}}_{{\bf W,b}}~{}~{}l(Y_{train},\left[{\begin{% array}[]{*{20}{c}}{\bf 1}&{{X_{train}}}\end{array}}\right]\left[{\begin{array}% []{*{20}{c}}{\bf b}^{T}\\ {\bf W}\end{array}}\right]),

(1)

where 1 is the all-one column vector. Then we can predict the label matrix $Y_{test}\in\mathbb{R}^{m\times t}$ of $m$ testing items with respect to the feature matrix $X_{test}\in\mathbb{R}^{m\times d}$ . Let

{\bf Z}=\left[\begin{array}[]{*{20}{c}}{{X_{train}}}&{{Y_{train}}}\\ {{X_{test}}}&{{Y_{test}}}\end{array}\right].

This linear classification problem can be transformed into completing the unobservable entries in $Y_{test}$ by means of the observable entries in $X_{train}$ , $Y_{train}$ and $X_{test}$ , based on the assumption that the rank of matrix ${\bf Z}\in\mathbb{R}^{(n+m)\times(d+t)}$ is low. The model can be written as,

\begin{split}&\mathop{\operatorname*{arg~{}min}}_{{\bf Z}\in\mathbb{R}^{(n+m)% \times(d+t)}}~{}~{}\text{rank}({\bf Z})\\ &\text{s.t.}~{}~{}\forall(i,j)\in\Omega_{X},~{}~{}z_{ij}=x_{ij},\\ &~{}~{}~{}~{}~{}~{}~{}~{}(1\leq i\leq n+m,~{}~{}1\leq j\leq d),\\ &~{}~{}~{}~{}~{}~{}~{}~{}\forall(i,j)\in\Omega_{Y},~{}~{}z_{i(j+d)}=y_{ij},\\ &~{}~{}~{}~{}~{}~{}~{}~{}(1\leq i\leq n,~{}~{}1\leq j\leq t),\end{split}

(2)

where we use $\Omega_{X}$ to represent the index set of observable feature entries in $X_{train}$ and $X_{test}$ , and $\Omega_{Y}$ to denote the index set of observable label entries in $Y_{train}$ .

Formula (2) is usually impractical for real problems as the entries in the matrix ${\bf Z}$ are corrupted by noise. We thus define

{\bf Z}={\bf Z^{*}}+{\bf E},

where ${\bf Z^{*}}$ as the underlying low-rank matrix

{\bf Z^{*}}=\left[{\begin{array}[]{*{20}{c}}{{X^{*}}}&{{Y^{*}}}\end{array}}% \right]=\left[{\begin{array}[]{*{20}{c}}{X_{train}^{*}}&{Y_{train}^{*}}\\ {X_{test}^{*}}&{Y_{test}^{*}}\end{array}}\right],

and E is the error matrix

{\bf E}=\left[{\begin{array}[]{*{20}{c}}{E_{X_{train}}}&{E_{Y_{train}}}\\ {E_{X_{test}}}&{0}\end{array}}\right].

The rank function in Formula (2) is a non-convex function that is difficult to be optimized. The surrogate of the function can be the convex nuclear norm ${\bf||Z||_{*}}=\sum\sigma_{k}({\bf Z})$ [5], where $\sigma_{k}$ is the $k$ - $t h$ largest singular value of ${\bf Z}$ . To tolerate the noise entries in the error matrix ${\bf E}$ , we minimize the cost functions $C_{x}$ and $C_{y}$ for features and labels respectively, rather than using the hard constraints in Formula (2).

According to Formula (1), ${\bf Z^{*}}\in\mathbb{R}^{(n+m)\times(d+t)}$ can be represented as $[X^{*},{\bf W}X^{*}]$ instead of $[X^{*},Y^{*}]$ , by explicitly modeling the bias vector ${\bf b}$ . Therefore, this convex optimization model is called DRMC-b,

\begin{split}&\mathop{\operatorname*{arg~{}min}}_{{\bf Z,b}}~{}~{}\mu||{\bf Z}% ||_{*}+\frac{1}{|{\Omega_{X}}|}\sum_{(i,j)\in{\Omega_{X}}}{C_{x}(z_{ij},x_{ij}% )}\\ &~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{\lambda}{{|{\Omega_{Y}}|}}% \sum_{(i,j)\in{\Omega_{Y}}}{C_{y}(z_{i(j+d)}+b_{j},y_{ij})},\\ \end{split}

(3)

where $\mu$ and $\lambda$ are the positive trade-off weights. More specifically, we minimize the nuclear norm $||{\bf Z}||_{*}$ via employing the regularization terms, i.e., the cost functions $C_{x}$ and $C_{y}$ for features and labels.

If we implicitly model the bias vector ${\bf b}$ , ${\bf Z^{*}}\in\mathbb{R}^{(n+m)\times(1+d+t)}$ can be denoted by $[{\bf 1},X^{*},{\bf W^{{}^{\prime}}}X^{*}]$ instead of $[X^{*},Y^{*}]$ , in which ${\bf W^{{}^{\prime}}}$ takes the role of $[{\bf b}^{T};{\bf W}]$ in DRMC-b. Then we derive another optimization model called DRMC-1,

\begin{split}&\mathop{\operatorname*{arg~{}min}}_{{\bf Z}}~{}~{}\mu||{\bf Z}||% _{*}+\frac{1}{|{\Omega_{X}}|}\sum_{(i,j)\in{\Omega_{X}}}{C_{x}(z_{i(j+1)},x_{% ij})}\\ &~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{% \lambda}{{|{\Omega_{Y}}|}}\sum_{(i,j)\in{\Omega_{Y}}}{C_{y}(z_{i(j+d+1)},y_{ij% })}\\ &~{}~{}~{}~{}~{}~{}~{}\text{s.t.}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}% ~{}~{}~{}{\bf Z}(:,1)={\bf 1},\\ \end{split}

(4)

where ${\bf Z}(:,1)$ denotes the first column of ${\bf Z}$ .

For our relation classification task, both features and labels are binary. We assume that the actual entry $u$ belonging to the underlying matrix ${\bf Z^{*}}$ is randomly generated via a sigmoid function [14]: $Pr(u|v)=1/(1+e^{-uv})$ , given the observed binary entry $v$ from the observed sparse matrix ${\bf Z}$ . Then, we can apply the log-likelihood cost function to measure the conditional probability and derive the logistic cost function for $C_{x}$ and $C_{y}$ ,

C(u,v)=-\log Pr(u|v)=\log(1+e^{-uv}),

After completing the entries in $Y_{test}$ , we adopt the sigmoid function to calculate the conditional probability of relation $r_{j}$ , given entity pair $p_{i}$ pertaining to $y_{ij}$ in $Y_{test}$ ,

Pr(r_{j}|p_{i})=\frac{1}{1+e^{-y_{ij}}},~{}~{}~{}y_{ij}\in Y_{test}.

Finally, we can achieve Top-N predicted relation instances via ranking the values of $Pr(r_{j}|p_{i})$ .

4 Algorithm

The matrix rank minimization problem is NP-hard. Therefore, Candés and Recht [5] suggested to use a convex relaxation, the nuclear norm minimization instead. Then, Ma et al. [16] proposed the fixed point continuation (FPC) algorithm which is fast and robust. Moreover, Goldfrab and Ma [11] proved the convergence of the FPC algorithm for solving the nuclear norm minimization problem. We thus adopt and modify the algorithm aiming to find the optima for our noise-tolerant models, i.e., Formulae (3) and (4).

4.1 Fixed point continuation for DRMC-b

Algorithm 1 describes the modified FPC algorithm for solving DRMC-b, which contains two steps for each iteration,

Gradient step: In this step, we infer the matrix gradient $g({\bf Z})$ and bias vector gradient $g({\bf b})$ as follows,

g(z_{ij})=\begin{cases}\frac{1}{|\Omega_{X}|}\frac{-x_{ij}}{1+e^{x_{ij}z_{ij}}% },&(i,j)\in\Omega_{X}\\ \frac{\lambda}{|\Omega_{Y}|}\frac{-y_{i(j-d)}}{1+e^{y_{i(j-d)}(z_{ij}+b_{j})}}% ,&(i,j-d)\in\Omega_{Y}\\ 0,&otherwise\end{cases}

and

g(b_{j})=\frac{\lambda}{|\Omega_{Y}|}\sum_{i:(i,j)\in\Omega_{Y}}{\frac{-y_{ij}% }{1+e^{y_{ij}(z_{i(j+d)}+b_{j})}}}.

We use the gradient descents ${\bf A}={\bf Z}-\tau_{z}g({\bf Z})$ and ${\bf b}={\bf b}-\tau_{b}g({\bf b})$ to gradually find the global minima of the cost function terms in Formula (3), where $\tau_{z}$ and $\tau_{b}$ are step sizes.

Shrinkage step: The goal of this step is to minimize the nuclear norm ${\bf||Z||_{*}}$ in Formula (3). We perform the singular value decomposition (SVD) [12] for ${\bf A}$ at first, and then cut down each singular value. During the iteration, any negative value in ${\bf\Sigma-\tau_{z}\mu}$ is assigned by zero, so that the rank of reconstructed matrix ${\bf Z}$ will be reduced, where ${\bf Z}={\bf U}max({\bf\Sigma-\tau_{z}\mu},0){\bf V^{T}}$ .

{algorithm}

FPC algorithm for solving DRMC-b {algorithmic} \REQUIRE
Initial matrix ${\bf Z_{0}}$ , bias ${\bf b_{0}}$ ; Parameters $\mu,\lambda$ ;
Step sizes $\tau_{z},\tau_{b}$ .

Set ${\bf Z}={\bf Z_{0}}$ , ${\bf b}={\bf b_{0}}.$ \FOR $\mu=\mu_{1}>\mu_{2}>...>\mu_{F}$ \WHILErelative error $>\varepsilon$ \STATEGradient step:
${\bf A}={\bf Z}-\tau_{z}g({\bf Z}),{\bf b}={\bf b}-\tau_{b}g({\bf b}).$ \STATEShrinkage step:
${\bf U}{\bf\Sigma}{\bf V^{T}}=\text{SVD}({\bf A})$ ,
${\bf Z}={\bf U}~{}max({\bf\Sigma-\tau_{z}\mu},0)~{}{\bf V^{T}}.$ \ENDWHILE

\ENDFOR

\ENSURE Completed Matrix Z, bias b. To accelerate the convergence, we use a continuation method to improve the speed. $\mu$ is initialized by a large value $\mu_{1}$ , thus resulting in the fast reduction of the rank at first. Then the convergence slows down as $\mu$ decreases while obeying $\mu_{k+1}=max(\mu_{k}\eta_{\mu},\mu_{F})$ . $\mu_{F}$ is the final value of $\mu$ , and $\eta_{\mu}$ is the decay parameter.

For the stopping criteria in inner iterations, we define the relative error to measure the residual of matrix ${\bf Z}$ between two successive iterations,

\frac{||{\bf Z}^{k+1}-{\bf Z}^{k}||_{F}}{max(1,||{\bf Z}^{k}||_{F})}\leq\varepsilon,

where $\varepsilon$ is the convergence threshold.

4.2 Fixed point continuation for DRMC-1

Algorithm 2 is similar to Algorithm 1 except for two differences. First, there is no bias vector b. Second, a projection step is added to enforce the first column of matrix Z to be 1. In addition, The matrix gradient $g({\bf Z})$ for DRMC-1 is

g(z_{ij})=\begin{cases}\frac{1}{|\Omega_{X}|}\frac{-x_{i(j-1)}}{1+e^{x_{i(j-1)% }z_{ij}}},&(i,j-1)\in\Omega_{X}\\ \frac{\lambda}{|\Omega_{Y}|}\frac{-y_{i(j-d-1)}}{1+e^{y_{i(j-d-1)}z_{ij}}},&(i% ,j-d-1)\in\Omega_{Y}\\ 0,&otherwise\end{cases}.

{algorithm}

FPC algorithm for solving DRMC-1 {algorithmic} \REQUIRE
Initial matrix ${\bf Z_{0}}$ ; Parameters $\mu,\lambda$ ;
Step sizes $\tau_{z}$ .

Set ${\bf Z}={\bf Z_{0}}.$ \FOR $\mu=\mu_{1}>\mu_{2}>...>\mu_{F}$ \WHILErelative error $>\varepsilon$ \STATEGradient step: ${\bf A}={\bf Z}-\tau_{z}g({\bf Z}).$ \STATEShrinkage step:
${\bf U}{\bf\Sigma}{\bf V^{T}}=\text{SVD}({\bf A})$ ,
${\bf Z}={\bf U}~{}max({\bf\Sigma-\tau_{z}\mu},0)~{}{\bf V^{T}}.$ \STATEProjection step: ${\bf Z}(:,1)={\bf 1}.$ \ENDWHILE

\ENDFOR

\ENSURE Completed Matrix Z.

5 Experiments

Dataset	# of training tuples	# of testing tuples	% with more than one label	# of features	# of relation labels
NYT’10	4,700	1,950	7.5%	244,903	51
NYT’13	8,077	3,716	0%	1,957	51

Table 1: Statistics about the two widely used datasets.

Model	NYT’10 ( $\theta$ =2)	NYT’10 ( $\theta$ =3)	NYT’10 ( $\theta$ =4)	NYT’10 ( $\theta$ =5)	NYT’13
DRMC-b	51.4 $\pm$ 8.7 (51)	45.6 $\pm$ 3.4 (46)	41.6 $\pm$ 2.5 (43)	36.2 $\pm$ 8.8(37)	84.6 $\pm$ 19.0 (85)
DRMC-1	16.0 $\pm$ 1.0 (16)	16.4 $\pm$ 1.1(17)	16 $\pm$ 1.4 (17)	16.8 $\pm$ 1.5(17)	15.8 $\pm$ 1.6 (16)

Table 2: The range of optimal ranks for DRMC-b and DRMC-1 through five-fold cross validation. The threshold

\theta

means filtering the features that appear less than

\theta

times. The values in brackets pertaining to DRMC-b and DRMC-1 are the exact optimal ranks that we choose for the completed matrices on testing sets.

In order to conduct reliable experiments, we adjust and estimate the parameters for our approaches, DRMC-b and DRMC-1, and compare them with other four kinds of landmark methods [19, 13, 24, 21] on two public datasets.

5.1 Dataset

The two widely used datasets that we adopt are both automatically generated by aligning Freebase to New York Times corpora. The first dataset¹²¹²http://iesl.cs.umass.edu/riedel/ecml/, NYT’10, was developed by Riedel et al. [22], and also used by Hoffmann et al. [13] and Surdeanu et al. [24]. Three kinds of features, namely, lexical, syntactic and named entity tag features, were extracted from relation mentions. The second dataset¹³¹³http://iesl.cs.umass.edu/riedel/data-univSchema/, NYT’13, was also released by Riedel et al. [21], in which they only regarded the lexicalized dependency path between two entities as features. Table 1 shows that the two datasets differ in some main attributes. More specifically, NYT’10 contains much higher dimensional features than NYT’13, whereas fewer training and testing items.

(a) DRMC-b on NYT’10 validation set (

\theta=5

(b) DRMC-1 on NYT’10 validation set (

\theta=5

(d) DRMC-1 on NYT’13 validation set.

Figure 3: Five-fold cross validation for rank estimation on two datasets.

5.2 Parameter setting

In this part, we address the issue of setting parameters: the trade-off weights $\mu$ and $\lambda$ , the step sizes $\tau_{z}$ and $\tau_{b}$ , and the decay parameter $\eta_{\mu}$ .

We set $\lambda=1$ to make the contribution of the cost function terms for feature and label matrices equal in Formulae (3) and (4). $\mu$ is assigned by a series of values obeying $\mu_{k+1}=max(\mu_{k}\eta_{\mu},\mu_{F})$ . We follow the suggestion in [10] that $\mu$ starts at $\sigma_{1}\eta_{\mu}$ , and $\sigma_{1}$ is the largest singular value of the matrix Z. We set $\eta_{\mu}=0.01$ . The final value of $\mu$ , namely $\mu_{F}$ , is equal to $0.01$ . Ma et al. [16] revealed that as long as the non-negative step sizes satisfy $\tau_{z}<min(\frac{4|\Omega_{Y}|}{\lambda},|\Omega_{X}|)$ and $\tau_{b}<\frac{4|\Omega_{Y}|}{\lambda(n+m)}$ , the FPC algorithm will guarantee to converge to a global optimum. Therefore, we set $\tau_{z}=\tau_{b}=0.5$ to satisfy the above constraints on both two datasets.

5.3 Rank estimation

Even though the FPC algorithm converges in iterative fashion, the value of $\varepsilon$ varying with different datasets is difficult to be decided. In practice, we record the rank of matrix Z at each round of iteration until it converges at a rather small threshold $\varepsilon=10^{-4}$ . The reason is that we suppose the optimal low-rank representation of the matrix Z conveys the truly effective information about underlying semantic correlation between the features and the corresponding labels.

We use the five-fold cross validation on the validation set and evaluate the performance on each fold with different ranks. At each round of iteration, we gain a recovered matrix and average the F1¹⁴¹⁴ $F1=\frac{2\times precision\times recall}{precision+recall}$ scores from Top-5 to Top-all predicted relation instances to measure the performance. Figure 3 illustrates the curves of average F1 scores. After recording the rank associated with the highest F1 score on each fold, we compute the mean and the standard deviation to estimate the range of optimal rank for testing. Table 2 lists the range of optimal ranks for DRMC-b and DRMC-1 on NYT’10 and NYT’13.

On both two datasets, we observe an identical phenomenon that the performance gradually increases as the rank of the matrix declines before reaching the optimum. However, it sharply decreases if we continue reducing the optimal rank. An intuitive explanation is that the high-rank matrix contains much noise and the model tends to be overfitting, whereas the matrix of excessively low rank is more likely to lose principal information and the model tends to be underfitting.

5.4 Method Comparison

(a) NYT’10 testing set (

\theta=5

(b) NYT’13 testing set.

Figure 4: Method comparison on two testing sets.

(a) NYT’10 testing set (

\theta=5

(b) NYT’13 testing set.

Figure 5: Precision-Recall curve for DRMC-b and DRMC-1 with different ranks on two testing sets.

Firstly, we conduct experiments to compare our approaches with Mintz-09 [19], MultiR-11 [13], MIML-12 and MIML-at-least-one-12 [24] on NYT’10 dataset. Surdeanu et al. [24] released the open source code¹⁵¹⁵http://nlp.stanford.edu/software/mimlre.shtml to reproduce the experimental results on those previous methods. Moreover, their programs can control the feature sparsity degree through a threshold $\theta$ which filters the features that appears less than $\theta$ times. They set $\theta=5$ in the original code by default. Therefore, we follow their settings and adopt the same way to filter the features. In this way, we guarantee the fair comparison for all methods. Figure 4 (a) shows that our approaches achieve the significant improvement on performance.

We also perform the experiments to compare our approaches with the state-of-the-art NFE-13¹⁶¹⁶Readers may refer to the website, http://www.riedelcastro.org/uschema for the details of those methods. We bypass the description due to the limitation of space. [21] and its sub-methods (N-13, F-13 and NF-13) on NYT’13 dataset. Figure 4 (b) illustrates that our approaches still outperform the state-of-the-art methods.

Figure 6: Feature sparsity discussion on NYT’10 testing set. Each row (from top to bottom,

\theta=4,3,2

) illustrates a suite of experimental results. They are, from left to right, five-fold cross validation for rank estimation on DRMC-b and DRMC-1, method comparison and precision-recall curve with different ranks, respectively.

Top-N	NFE-13	DRMC-b	DRMC-1
Top-100	62.9%	82.0%	80.0%
Top-200	57.1%	77.0%	80.0%
Top-500	37.2%	70.2%	77.0%
Average	52.4%	76.4%	79.0%

Table 3: Precision of NFE-13, DRMC-b and DRMC-1 on Top-100, Top-200 and Top-500 predicted relation instances.

In practical applications, we also concern about the precision on Top-N predicted relation instances. Therefore, We compare the precision of Top-100s, Top-200s and Top-500s for DRMC-1, DRMC-b and the state-of-the-art method NFE-13 [21]. Table 3 shows that DRMC-b and DRMC-1 achieve 24.0% and 26.6% precision increments on average, respectively.

6 Discussion

We have mentioned that the basic alignment assumption of distant supervision [19] tends to generate noisy (noisy features and incomplete labels) and sparse (sparse features) data. In this section, we discuss how our approaches tackle these natural flaws.

Due to the noisy features and incomplete labels, the underlying low-rank data matrix with truly effective information tends to be corrupted and the rank of observed data matrix can be extremely high. Figure 5 demonstrates that the ranks of data matrices are approximately 2,000 for the initial optimization of DRMC-b and DRMC-1. However, those high ranks result in poor performance. As the ranks decline before approaching the optimum, the performance gradually improves, implying that our approaches filter the noise in data and keep the principal information for classification via recovering the underlying low-rank data matrix.

Furthermore, we discuss the influence of the feature sparsity for our approaches and the state-of-the-art methods. We relax the feature filtering threshold ( $\theta=4,3,2$ ) in Surdeanu et al.’s [24] open source program to generate more sparse features from NYT’10 dataset. Figure 6 shows that our approaches consistently outperform the baseline and the state-of-the-art methods with diverse feature sparsity degrees. Table 2 also lists the range of optimal rank for DRMC-b and DRMC-1 with different $\theta$ . We observe that for each approach, the optimal range is relatively stable. In other words, for each approach, the amount of truly effective information about underlying semantic correlation keeps constant for the same dataset, which, to some extent, explains the reason why our approaches are robust to sparse features.

7 Conclusion and Future Work

In this paper, we contributed two noise-tolerant optimization models¹⁷¹⁷The source code can be downloaded from https://github.com/nlpgeek/DRMC/tree/master, DRMC-b and DRMC-1, for distantly supervised relation extraction task from a novel perspective. Our models are based on matrix completion with low-rank criterion. Experiments demonstrated that the low-rank representation of the feature-label matrix can exploit the underlying semantic correlated information for relation classification and is effective to overcome the difficulties incurred by sparse and noisy features and incomplete labels, so that we achieved significant improvements on performance.

Our proposed models also leave open questions for distantly supervised relation extraction task. First, they can not process new coming testing items efficiently, as we have to reconstruct the data matrix containing not only the testing items but also all the training items for relation classification, and compute in iterative fashion again. Second, the volume of the datasets we adopt are relatively small. For the future work, we plan to improve our models so that they will be capable of incremental learning on large-scale datasets [6].

Acknowledgments

This work is supported by National Program on Key Basic Research Project (973 Program) under Grant 2013CB329304, National Science Foundation of China (NSFC) under Grant No.61373075.

References

[1] N. Bach and S. Badaskar(2007) A review of relation extraction. Literature review for Language and Statistics II. Cited by: 1.
[2] K. Bollacker, R. Cook and P. Tufts(2007) Freebase: a shared database of structured general human knowledge. Vol. 22, pp. 1962. External Links: Link Cited by: 2.
[3] K. Bollacker, C. Evans, P. Paritosh, T. Sturge and J. Taylor(2008) Freebase: a collaboratively created graph database for structuring human knowledge. pp. 1247–1250. External Links: Link Cited by: 2.
[4] R. S. Cabral, F. Torre, J. P. Costeira and A. Bernardino(2011) Matrix completion for multi-label image classification. pp. 190–198. Cited by: 3.
[5] E. J. Candès and B. Recht(2009) Exact matrix completion via convex optimization. Foundations of Computational mathematics 9 (6), pp. 717–772. Cited by: 3.1, 3, 4.
[6] E. Y. Chang(2011) Foundations of large-scale multimedia information management and retrieval. Springer. Cited by: 7.
[7] M. Collins, S. Dasgupta and R. E. Schapire(2001) A generalization of principal components analysis to the exponential family. pp. 617–624. Cited by: 2.
[8] M. Craven and J. Kumlien(1999) Constructing biological knowledge bases by extracting information from text sources.. Vol. 1999, pp. 77–86. External Links: Link Cited by: 2.
[9] M. Fazel, H. Hindi and S. P. Boyd(2001) A rank minimization heuristic with application to minimum order system approximation. Vol. 6, pp. 4734–4739. External Links: Link Cited by: 3.
[10] A. Goldberg, B. Recht, J. Xu, R. Nowak and X. Zhu(2010) Transduction with matrix completion: three birds with one stone. pp. 757–765. Cited by: 3, 5.2.
[11] D. Goldfarb and S. Ma(2011) Convergence of fixed-point continuation algorithms for matrix rank minimization. Foundations of Computational Mathematics 11 (2), pp. 183–210. Cited by: 4.
[12] G. Golub and W. Kahan(1965) Calculating the singular values and pseudo-inverse of a matrix. Journal of the Society for Industrial & Applied Mathematics, Series B: Numerical Analysis 2 (2), pp. 205–224. Cited by: 4.1.
[13] R. Hoffmann, C. Zhang, X. Ling, L. Zettlemoyer and D. S. Weld(2011-06) Knowledge-based weak supervision for information extraction of overlapping relations. Portland, Oregon, USA, pp. 541–550. External Links: Link Cited by: 1, 2, 5.1, 5.4, 5.
[14] M. Jordan(1995) Why the logistic function? a tutorial discussion on probabilities and neural networks. Computational Cognitive Science Technical Report. Cited by: 3.1.
[15] Y. Koren(2008) Factorization meets the neighborhood: a multifaceted collaborative filtering model. pp. 426–434. External Links: Link Cited by: 2.
[16] S. Ma, D. Goldfarb and L. Chen(2011) Fixed point and bregman iterative methods for matrix rank minimization. Mathematical Programming 128 (1-2), pp. 321–353. External Links: Link Cited by: 1, 4, 5.2.
[17] O. Maron and T. Lozano-Pérez(1998) A framework for multiple-instance learning. Advances in neural information processing systems, pp. 570–576. Cited by: 2.
[18] B. Min, R. Grishman, L. Wan, C. Wang and D. Gondek(2013-06) Distant supervision for relation extraction with an incomplete knowledge base. Atlanta, Georgia, pp. 777–782. External Links: Link Cited by: 2.
[19] M. Mintz, S. Bills, R. Snow and D. Jurafsky(2009) Distant supervision for relation extraction without labeled data. pp. 1003–1011. Cited by: 1, 2, 3.1, 5.4, 5, 6.
[20] J. D. Rennie and N. Srebro(2005) Fast maximum margin matrix factorization for collaborative prediction. pp. 713–719. External Links: Link Cited by: 3.
[21] S. Riedel, L. Yao, A. McCallum and B. M. Marlin(2013-06) Relation extraction with matrix factorization and universal schemas. Atlanta, Georgia, pp. 74–84. External Links: Link Cited by: 2, 5.1, 5.4, 5.4, 5.
[22] S. Riedel, L. Yao and A. McCallum(2010) Modeling relations and their mentions without labeled text. Machine Learning and Knowledge Discovery in Databases, pp. 148–163. Cited by: 2, 5.1.
[23] R. Snow, D. Jurafsky and A. Y. Ng(2004) Learning syntactic patterns for automatic hypernym discovery. Advances in Neural Information Processing Systems 17. External Links: Link Cited by: 2.
[24] M. Surdeanu, J. Tibshirani, R. Nallapati and C. D. Manning(2012) Multi-instance multi-label learning for relation extraction. pp. 455–465. External Links: Link Cited by: 2, 5.1, 5.4, 5, 6.
[25] S. Takamatsu, I. Sato and H. Nakagawa(2012) Reducing wrong labels in distant supervision for relation extraction. pp. 721–729. External Links: Link Cited by: 2.
[26] W. Xu, R. Hoffmann, L. Zhao and R. Grishman(2013-08) Filling knowledge base gaps for distant supervision of relation extraction. Sofia, Bulgaria, pp. 665–670. External Links: Link Cited by: 2.
[27] X. Zhang, J. Zhang, J. Zeng, J. Yan, Z. Chen and Z. Sui(2013-08) Towards accurate distant supervision for relational facts extraction. Sofia, Bulgaria, pp. 810–815. External Links: Link Cited by: 2.
[28] G. Zhou, J. Su, J. Zhang and M. Zhang(2005) Exploring various knowledge in relation extraction. pp. 427–434. Cited by: 1.

Generated on Tue Jun 10 18:09:43 2014 by LaTeXML [LOGO]