Graph-Based Seed Set Expansion for Relation Extraction Using Random Walk Hitting Times

Proceedings of NAACL-HLT 2013, pages 772–776, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Graph-Based Seed Set Expansion for Relation Extraction Using Random Walk Hitting Times Joel Lang University of Geneva 7 Route de Drize 1227 Carouge, Switzerland joel.lang@unige.ch James Henderson Xerox Research Centre Europe 6 Chemin de Maupertuis 38240 Meylan, France james.henderson@xrce.xerox.com Abstract Iterative bootstrapping methods are widely employed for relation extraction, especially because they require only a small amount of human supervision. Unfortunately, a phenomenon known as semantic drift can affect the accuracy of iterative bootstrapping and lead to poor extractions. This paper proposes an alternative bootstrapping method, which ranks relation tuples by measuring their distance to the seed tuples in a bipartite tuple-pattern graph. In contrast to previous bootstrapping methods, our method is not susceptible to semantic drift, and it empirically results in better extractions than iterative methods. 1 Introduction The goal of relation extraction is to extract tu- ples of a particular relation from a corpus of natural language text. A widely employed ap- proach to relation extraction is based on iter- ative bootstrapping (Brin, 1998; Agichtein and Gravano, 2000; Pasca et al., 2006; Pantel and Pennacchiotti, 2006), which can be applied with only small amounts of supervision and which scales well to very large datasets. A well-known problem with iterative boot- strapping is a phenomenon known as seman- tic drift (Curran et al., 2007): as bootstrap- ping proceeds it is likely that unreliable pat- terns will lead to false extractions. These extrac- tion errors are amplified in the following itera- tions and the extracted relation will drift away from the intended target. Semantic drift often results in low precision extractions and there- fore poses a major limitation of iterative boot- strapping algorithms. Previous work on itera- tive bootstrapping has addressed the issue of re- ducing semantic drift for example by bagging the results of various runs employing differing seed tuples, constructing filters which identify false tuples or patterns and adding further con- straints to the bootstrapping process (T. McIn- tosh, 2010; McIntosh and Curran, 2009; Curran et al., 2007). However, the analysis of Komachi et al. (2008) has shown that semantic drift is an in- herent property of iterative bootstrapping algo- rithms and therefore poses a fundamental prob- lem. They have shown that iterative bootstrap- ping without pruning corresponds to an eigen- vector computation and thus as the number of iterations increases the resulting ranking will al- ways converge towards the same static ranking of tuples, regardless of the particular choice of seed instances. In this paper, we describe an alternative method, that is not susceptible to semantic drift. We represent our data as a bipartite graph, whose vertices correspond to patterns and tu- ples respectively and whose edges capture cooc- currences and then measure the distance of a tuple to the seed set in terms of random walk hitting times. Experimental results confirm that semantic drift is avoided by our method and show that substantial improvements over iter- ative forms of bootstrapping …

Content truncated to 500 words