Dependency Tree Kernels for Relation Extraction

Dependency Tree Kernels for Relation Extraction Aron Culotta University of Massachusetts Amherst, MA 01002 USA culotta@cs.umass.edu Jeffrey Sorensen IBM T.J. Watson Research Center Yorktown Heights, NY 10598 USA sorenj@us.ibm.com Abstract We extend previous work on tree kernels to estimate the similarity between the dependency trees of sen- tences. Using this kernel within a Support Vector Machine, we detect and classify relations between entities in the Automatic Content Extraction (ACE) corpus of news articles. We examine the utility of different features such as Wordnet hypernyms, parts of speech, and entity types, and find that the depen- dency tree kernel achieves a 20% F1 improvement over a “bag-of-words” kernel. 1 Introduction The ability to detect complex patterns in data is lim- ited by the complexity of the data’s representation. In the case of text, a more structured data source (e.g. a relational database) allows richer queries than does an unstructured data source (e.g. a col- lection of news articles). For example, current web search engines would not perform well on the query, “list all California-based CEOs who have social ties with a United States Senator.” Only a structured representation of the data can effectively provide such a list. The goal of Information Extraction (IE) is to dis- cover relevant segments of information in a data stream that will be useful for structuring the data. In the case of text, this usually amounts to finding mentions of interesting entities and the relations that join them, transforming a large corpus of unstruc- tured text into a relational database with entries such as those in Table 1. IE is commonly viewed as a three stage process: first, an entity tagger detects all mentions of interest; second, coreference resolution resolves disparate mentions of the same entity; third, a relation extrac- tor finds relations between these entities. Entity tag- ging has been thoroughly addressed by many statis- tical machine learning techniques, obtaining greater than 90% F1 on many datasets (Tjong Kim Sang and De Meulder, 2003). Coreference resolution is an active area of research not investigated here (Pa- Entity Type Location Apple Organization Cupertino, CA Microsoft Organization Redmond, WA Table 1: An example of extracted fields sula et al., 2002; McCallum and Wellner, 2003). We describe a relation extraction technique based on kernel methods. Kernel methods are non- parametric density estimation techniques that com- pute a kernel function between data instances, where a kernel function can be thought of as a sim- ilarity measure. Given a set of labeled instances, kernel methods determine the label of a novel in- stance by comparing it to the labeled training in- stances using this kernel function. Nearest neighbor classification and support-vector machines (SVMs) are two popular examples of kernel methods (Fuku- naga, 1990; Cortes and Vapnik, 1995). An advantage of kernel methods is that they can search a feature space much larger than could be represented by a feature extraction-based approach. This is possible because the kernel function can ex- plore an implicit feature space when calculating the similarity between …

Content truncated to 500 words