Joint Entity and Relation Extraction Using Card-Pyramid Parsing

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 203–212, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Joint Entity and Relation Extraction using Card-Pyramid Parsing Rohit J. Kate and Raymond J. Mooney Department of Computer Science The University of Texas at Austin 1 University Station C0500 Austin, TX 78712-0233, USA {rjkate,mooney}@cs.utexas.edu Abstract Both entity and relation extraction can benefit from being performed jointly, al- lowing each task to correct the errors of the other. We present a new method for joint entity and relation extraction using a graph we call a “card-pyramid.” This graph compactly encodes all possible en- tities and relations in a sentence, reducing the task of their joint extraction to jointly labeling its nodes. We give an efficient la- beling algorithm that is analogous to pars- ing using dynamic programming. Exper- imental results show improved results for our joint extraction method compared to a pipelined approach. 1 Introduction Information extraction (IE) is the task of extract- ing structured information from text. The two most common sub-tasks of IE are extracting enti- ties (like Person, Location and Organization) and extracting relations between them (like Work For which relates a Person and an Organization, Org- Based In which relates an Organization and a Lo- cation etc.). Figure 1 shows a sample sentence an- notated with entities and relations. The applica- tion domain and requirements of the downstream tasks usually dictate the type of entities and rela- tions that an IE system needs to extract. Most work in IE has concentrated on entity ex- traction alone (Tjong Kim Sang, 2002; Sang and Meulder, 2003) or on relation extraction assum- ing entities are either given or previously extracted (Bunescu et al., 2005; Zhang et al., 2006; Giuliano et al., 2007; Qian et al., 2008). However, these tasks are very closely inter-related. While iden- tifying correct entities is essential for identifying relations between them, identifying correct rela- tions can in turn improve identification of entities. For example, if the relation Work For is identified with high confidence by a relation extractor, then it can enforce identifying its arguments as Person and Organization, about which the entity extractor might not have been confident. A brute force algorithm for finding the most probable joint extraction will soon become in- tractable as the number of entities in a sentence grows. If there are n entities in a sentence, then there are O(n2) possible relations between them and if each relation can take l labels then there are O(ln2) total possibilities, which is intractable even for small l and n. Hence, an efficient inference mechanism is needed for joint entity and relation extraction. The only work we are aware of for jointly ex- tracting entities and relations is by Roth & Yih (2004; 2007). Their method first identifies the pos- sible entities and relations in a sentence using sep- arate classifiers which are applied independently and then computes a most probable consistent global set of entities and relations using linear pro- …

Content truncated to 500 words