Unsupervised Relation Disambiguation with Order Identification Capabilities

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 568–575, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Unsupervised Relation Disambiguation with Order Identification Capabilities 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 We present an unsupervised learning ap- proach to disambiguate various relations between name entities by use of various lexical and syntactic features from the contexts. It works by calculating eigen- vectors of an adjacency graph’s Lapla- cian to recover a submanifold of data from a high dimensionality space and then performing cluster number estima- tion on the eigenvectors. This method can address two difficulties encoutered in Hasegawa et al. (2004)’s hierarchical clustering: no consideration of manifold structure in data, and requirement to pro- vide cluster number by users. Experiment results on ACE corpora show that this spectral clustering based approach outper- forms Hasegawa et al. (2004)’s hierarchi- cal clustering method and a plain k-means clustering method. 1 Introduction The task of relation extraction is to identify vari- ous semantic relations between name entities from text. Prior work on automatic relation extraction come in three kinds: supervised learning algorithms (Miller et al., 2000; Zelenko et al., 2002; Culotta and Soresen, 2004; Kambhatla, 2004; Zhou et al., 2005), semi-supervised learning algorithms (Brin, 1998; Agichtein and Gravano, 2000; Zhang, 2004), and unsupervised learning algorithm (Hasegawa et al., 2004). Among these methods, supervised learning is usu- ally more preferred when a large amount of la- beled training data is available. However, it is time-consuming and labor-intensive to manually tag a large amount of training data. Semi-supervised learning methods have been put forward to mini- mize the corpus annotation requirement. Most of semi-supervised methods employ the bootstrapping framework, which only need to pre-define some ini- tial seeds for any particular relation, and then boot- strap from the seeds to acquire the relation. How- ever, it is often quite difficult to enumerate all class labels in the initial seeds and decide an “optimal” number of them. Compared with supervised and semi-supervised methods, Hasegawa et al. (2004)’s unsupervised ap- proach for relation extraction can overcome the dif- ficulties on requirement of a large amount of labeled data and enumeration of all class labels. Hasegawa et al. (2004)’s method is to use a hierarchical cluster- ing method to cluster pairs of named entities accord- ing to the similarity of context words intervening be- tween the named entities. However, the drawback of hierarchical clustering is that it required providing cluster number by users. Furthermore, clustering is performed in original high dimensional space, which may induce non-convex clusters hard to identified. This paper presents a novel application of spec- tral clustering technique to unsupervised relation ex- traction problem. It works by calculating eigenvec- tors of an adjacency graph’s Laplacian to recover a submanifold of data from a high dimensional space, and then performing cluster number estimation …

Content truncated to 500 words