Unsupervised Information Extraction Approach Using Graph Mutual Reinforcement

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 501–508, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Unsupervised Information Extraction Approach Using Graph Mutual Reinforcement Hany Hassan Ahmed Hassan Ossama Emam IBM Cairo Technology Development Center Giza, Egypt P.O. Box 166 Al-Ahram hanyh@eg.ibm.com hasanah@eg.ibm.com emam@eg.ibm.com Abstract Information Extraction (IE) is the task of extracting knowledge from unstructured text. We present a novel unsupervised approach for information extraction based on graph mutual reinforcement. The proposed approach does not require any seed patterns or examples. Instead, it depends on redundancy in large data sets and graph based mutual reinforcement to induce generalized “extraction patterns”. The proposed approach has been used to acquire extraction patterns for the ACE (Automatic Content Extraction) Relation Detection and Characterization (RDC) task. ACE RDC is considered a hard task in information extraction due to the ab- sence of large amounts of training data and inconsistencies in the available data. The proposed approach achieves superior performance which could be compared to supervised techniques with reasonable training data. 1 Introduction In this paper we propose a novel, and completely unsupervised approach for information extrac- tion. We present a general technique; however we focus on relation extraction as an important task of Information Extraction. The approach depends on constructing generalized extraction patterns, which could match many instances, and deploys graph based mutual reinforcement to weight the importance of these patterns. The mu- tual reinforcement is used to automatically iden- tify the most informative patterns, where patterns that match many instances tend to be correct. Similarly, instances matched by many patterns tend to be correct. The intuition is that large un- supervised data is redundant, i.e. different in- stances of information could be found many times in different contexts and by different repre- sentation. The problem can therefore be seen as hubs (instances) and authorities (patterns) prob- lem which can be solved using the Hypertext Induced Topic Selection (HITS) algorithm (Kleinberg, 1998). HITS is an algorithmic formulation of the no- tion of authority in web pages link analysis, based on a relationship between a set of relevant “authoritative pages” and a set of “hub pages”. The HITS algorithm benefits from the following observation: when a page (hub) links to another page (authority), the former confers authority over the latter. By analogy to the authoritative web pages problem, we could represent the patterns as au- thorities and instances as hubs, and use mutual reinforcement between patterns and instances to weight the most authoritative patterns. Highly weighted patterns are then used in extracting in- formation. The proposed approach does not need any seeds or examples. Human involvement is only needed in determining the entities of interest; the entities among which we are seeking relations. The paper proceeds as follows: in Section 2 we discuss previous work followed by a brief definition of our general notation in Section 3. A detailed description of the proposed approach then follows in Section 4. Section 5 discusses the application of the …

Content truncated to 500 words