Tree Kernel-Based Relation Extraction with Context-Sensitive Structured Parse Tree Information

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 728–736, Prague, June 2007. c⃝2007 Association for Computational Linguistics Tree Kernel-based Relation Extraction with Context-Sensitive Structured Parse Tree Information GuoDong ZHOU12 Min ZHANG 2 Dong Hong JI 2 QiaoMing ZHU 1 1School of Computer Science & Technology 2 Institute for Infocomm Research Soochow Univ. Heng Mui Keng Terrace Suzhou, China 215006 Singapore 119613 Email: {gdzhou,qmzhu}@suda.edu.cn Email: {zhougd, mzhang, dhji}@i2r.a-star.edu.sg Abstract This paper proposes a tree kernel with context- sensitive structured parse tree information for re- lation extraction. It resolves two critical problems in previous tree kernels for relation extraction in two ways. First, it automatically determines a dy- namic context-sensitive tree span for relation ex- traction by extending the widely-used Shortest Path-enclosed Tree (SPT) to include necessary context information outside SPT. Second, it pro- poses a context-sensitive convolution tree kernel, which enumerates both context-free and context- sensitive sub-trees by considering their ancestor node paths as their contexts. Moreover, this paper evaluates the complementary nature between our tree kernel and a state-of-the-art linear kernel. Evaluation on the ACE RDC corpora shows that our dynamic context-sensitive tree span is much more suitable for relation extraction than SPT and our tree kernel outperforms the state-of-the-art Collins and Duffy’s convolution tree kernel. It also shows that our tree kernel achieves much bet- ter performance than the state-of-the-art linear kernels. Finally, it shows that feature-based and tree kernel-based methods much complement each other and the composite kernel can well integrate both flat and structured features. 1 Introduction Relation extraction is to find various predefined se- mantic relations between pairs of entities in text. The research in relation extraction has been promoted by the Message Understanding Conferences (MUCs) (MUC, 1987-1998) and the NIST Automatic Content Extraction (ACE) program (ACE, 2002-2005). Ac- cording to the ACE Program, an entity is an object or a set of objects in the world and a relation is an ex- plicitly or implicitly stated relationship among enti- ties. For example, the sentence “Bill Gates is the chairman and chief software architect of Microsoft Corporation.” conveys the ACE-style relation “ EMPLOYMENT.exec” between the entities “Bill Gates” (person name) and “Microsoft Corporation” (organization name). Extraction of semantic relations between entities can be very useful in many applica- tions such as question answering, e.g. to answer the query “Who is the president of the United States?”, and information retrieval, e.g. to expand the query “ George W. Bush” with “the president of the United States” via his relationship with “the United States”. Many researches have been done in relation extrac- tion. Among them, feature-based methods (Kamb- hatla 2004; Zhou et al., 2005) achieve certain success by employing a large amount of diverse linguistic features, varying from lexical knowledge, entity- related information to syntactic parse trees, depend- ency trees and semantic information. However, it is difficult for them to effectively capture structured parse tree information (Zhou et al 2005), which is critical for further performance improvement …

Content truncated to 500 words