Relation Extraction Using Label Propagation Based Semi-Supervised Learning

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 129–136, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Relation Extraction Using Label Propagation Based Semi-supervised Learning Jinxiu Chen1 Donghong Ji1 Chew Lim Tan2 Zhengyu Niu1 1Institute for Infocomm Research 2Department of Computer Science 21 Heng Mui Keng Terrace National University of Singapore 119613 Singapore 117543 Singapore {jinxiu,dhji,zniu}@i2r.a-star.edu.sg tancl@comp.nus.edu.sg Abstract Shortage of manually labeled data is an obstacle to supervised relation extraction methods. In this paper we investigate a graph based semi-supervised learning al- gorithm, a label propagation (LP) algo- rithm, for relation extraction. It represents labeled and unlabeled examples and their distances as the nodes and the weights of edges of a graph, and tries to obtain a la- beling function to satisfy two constraints: 1) it should be fixed on the labeled nodes, 2) it should be smooth on the whole graph. Experiment results on the ACE corpus showed that this LP algorithm achieves better performance than SVM when only very few labeled examples are available, and it also performs better than bootstrap- ping for the relation extraction task. 1 Introduction Relation extraction is the task of detecting and classifying relationships between two entities from text. Many machine learning methods have been proposed to address this problem, e.g., supervised learning algorithms (Miller et al., 2000; Zelenko et al., 2002; Culotta and Soresen, 2004; Kambhatla, 2004; Zhou et al., 2005), semi-supervised learn- ing algorithms (Brin, 1998; Agichtein and Gravano, 2000; Zhang, 2004), and unsupervised learning al- gorithms (Hasegawa et al., 2004). Supervised methods for relation extraction per- form well on the ACE Data, but they require a large amount of manually labeled relation instances. Un- supervised methods do not need the definition of relation types and manually labeled data, but they cannot detect relations between entity pairs and its result cannot be directly used in many NLP tasks since there is no relation type label attached to each instance in clustering result. Considering both the availability of a large amount of untagged cor- pora and direct usage of extracted relations, semi- supervised learning methods has received great at- tention. DIPRE (Dual Iterative Pattern Relation Expan- sion) (Brin, 1998) is a bootstrapping-based sys- tem that used a pattern matching system as clas- sifier to exploit the duality between sets of pat- terns and relations. Snowball (Agichtein and Gra- vano, 2000) is another system that used bootstrap- ping techniques for extracting relations from un- structured text. Snowball shares much in common with DIPRE, including the employment of the boot- strapping framework as well as the use of pattern matching to extract new candidate relations. The third system approaches relation classification prob- lem with bootstrapping on top of SVM, proposed by Zhang (2004). This system focuses on the ACE sub- problem, RDC, and extracts various lexical and syn- tactic features for the classification task. However, Zhang (2004)’s method doesn’t actually “detect” re- laitons but only performs relation classification be- tween two entities given that they …

Content truncated to 500 words