Seeded Discovery of Base Relations in Large Corpora

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 591–599, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Seeded Discovery of Base Relations in Large Corpora Nicholas Andrews BBN Technologies∗ noa@bbn.com Naren Ramakrishnan Virginia Tech naren@cs.vt.edu Abstract Relationship discovery is the task of iden- tifying salient relationships between named entities in text. We propose novel approaches for two sub-tasks of the problem: identifying the entities of interest, and partitioning and describing the relations based on their semantics. In particular, we show that term frequency patterns can be used effectively instead of supervised NER, and that the p- median clustering objective function naturally uncovers relation exemplars appropriate for describing the partitioning. Furthermore, we introduce a novel application of relationship discovery: the unsupervised identification of protein-protein interaction phrases. 1 Introduction Relationship extraction (RE) is the task of extracting named relationships between entities in text given some information about the relationships of interest. Relationship discovery (RD), on the other hand, is the task of finding which relations exist in a corpus without any prior knowledge. The discovered rela- tionships can then be used to bootstrap RE, which is why RD has also been called unsupervised relation extraction (Rosenfeld and Feldman, 2006). RD gen- erally involves three sub-tasks: entities of interest are either supplied or recognized in the corpus; sec- ond, of all phrases in which entities co-occur, those which express a relation are picked out; finally, these relationship phrases are partitioned based on their semantics and described. This work considers only binary relations (those between exactly two entities). Finding entities of interest has involved either named entity recognition (NER) or general noun ∗This work was conducted while author was at Virginia Tech. phrase (NP) chunking, to create the initial pool of candidate entities. In Section 2, we describe a corpus statistics approach, previously applied for web mining (Davidov and Rappoport, 2006), which we extend for relation discovery. Unlike supervised machine learning methods, this algorithm does not need training, is computationally efficient, and requires as input only the raw corpus and a small set of seed entities (as few as two). The result is a set of entities likely to be related to the seeds. An assumption commonly held in RD work is that frequently co-occurring entity tuples are likely to stand in some fixed relation (Hasegawa et al., 2004; Shinyama and Sekine, 2006; Rosenfeld and Feldman, 2006; Rosenfeld and Feldman, 2007). Tuples which share similar contexts (the exact definition of context varies) are then grouped together in clusters of relations using variants of hi- erarchical agglomerate clustering (HAC). However, to our knowledge, no prior work has satisfactorily addressed the problem of describing the resulting clusters. In Section 3, we propose an approach which incorporates this requirement directly into the clustering objective: to find relation clusters which are well-described by a single exemplar. In Section 4, we apply RD to recognize protein- protein interaction (PPI) sentences, using proteins as seeds for the entity discovery phase. We compare our results against …

Content truncated to 500 words