Distant Supervision for Relation Extraction with Matrix Completion

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 839–849, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Distant Supervision for Relation Extraction with Matrix Completion Miao Fan†,‡,∗, Deli Zhao‡, Qiang Zhou†, Zhiyuan Liu⋄,‡, Thomas Fang Zheng†, Edward Y. Chang‡ † CSLT, Division of Technical Innovation and Development, Tsinghua National Laboratory for Information Science and Technology, Tsinghua University, China. ⋄ Department of Computer Science and Technology, Tsinghua University, China. ‡ HTC Beijing Advanced Technology and Research Center, China. ∗fanmiao.cslt.thu@gmail.com Abstract The essence of distantly supervised rela- tion extraction is that it is an incomplete multi-label classification problem with s- parse and noisy features. To tackle the s- parsity 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 s- parse matrix that concatenates training and testing textual features with training label- s. 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 model- s to recover the underlying low-rank ma- trix 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 glob- al optimum. Experiments on two wide- ly used datasets with different dimension- s of textual features demonstrate that our low-rank matrix completion approach sig- nificantly outperforms the baseline and the state-of-the-art methods. 1 Introduction Relation Extraction (RE) is the process of gen- erating structured relation knowledge from un- structured natural language texts. Traditional su- pervised methods (Zhou et al., 2005; Bach and Badaskar, 2007) on small hand-labeled corpora, such as MUC1 and ACE2, can achieve high pre- cision and recall. However, as producing hand- labeled corpora is laborius and expensive, the su- pervised approach can not satisfy the increasing 1http://www.itl.nist.gov/iaui/894.02/related projects/muc/ 2http://www.itl.nist.gov/iad/mig/tests/ace/ Figure 1: Training corpus generated by the basic alignment assumption of distantly supervised re- lation extraction. The relation instances are the triples related to President Barack Obama in the Freebase, and the relation mentions are some sen- tences describing him in the Wikipedia. demand of building large-scale knowledge reposi- tories with the explosion of Web texts. To address the lacking training data issue, we consider the dis- tant (Mintz et al., 2009) or weak (Hoffmann et al., 2011) supervision paradigm attractive, and we im- prove the effectiveness of the paradigm in this pa- per. The intuition of the paradigm is that one can take advantage of several knowledge bases, such as WordNet3, Freebase4 and YAGO5, to automatically label free texts, like Wikipedia6 and New York Times corpora7, 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 rela- tion instances8 coming from knowledge bases (President-of(Barack Obama, U.S.) and Born-in(Barack Obama, …

Content truncated to 500 words