Learning Graph Walk Based Similarity Measures for Parsed Text

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 907–916, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Learning Graph Walk Based Similarity Measures for Parsed Text Einat Minkov∗ Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA einat@cs.cmu.edu William W. Cohen Machine Learning Department Carnegie Mellon University Pittsburgh, PA 15213, USA wcohen@cs.cmu.edu Abstract We consider a parsed text corpus as an in- stance of a labelled directed graph, where nodes represent words and weighted directed edges represent the syntactic relations be- tween them. We show that graph walks, com- bined with existing techniques of supervised learning, can be used to derive a task-specific word similarity measure in this graph. We also propose a new path-constrained graph walk method, in which the graph walk process is guided by high-level knowledge about mean- ingful edge sequences (paths). Empirical eval- uation on the task of named entity coordinate term extraction shows that this framework is preferable to vector-based models for small- sized corpora. It is also shown that the path- constrained graph walk algorithm yields both performance and scalability gains. 1 Introduction Graph-based similarity measures have been used for a variety of language processing applications. In this paper we assume directed graphs, where typed nodes denote entities and labelled directed and weighted edges denote the relations between them. In this framework, graph walks can be ap- plied to draw a measure of similarity between the graph nodes. Previous works have applied graph walks to draw a notion of semantic similarity over such graphs that were carefully designed and man- ually tuned, based on WordNet reations (Toutanova ∗Current address: Nokia Research Center Cambridge, Cam- bridge, MA 02142, USA. et al., 2004; Collins-Thompson and Callan, 2005; Hughes and Ramage, 2007). While these and other researchers have used WordNet to evaluate similarity between words, there has been much interest in extracting such a measure from text corpora (e.g., (Snow et al., 2005; Pad´o and Lapata, 2007)). In this paper, we suggest pro- cessing dependency parse trees within the general framework of directed labelled graphs. We construct a graph that directly represents a corpus of struc- tured (parsed) text. In the suggested graph scheme, nodes denote words and weighted edges represent the dependency relations between them. We apply graph walks to derive an inter-word similarity mea- sure. We further apply learning techniques, adapted to this framework, to improve the derived corpus- based similarity measure. The learning methods applied include existing learning techniques, namely edge weight tuning, where weights are associated with the edge types, and discriminative reranking of graph nodes, using features that describe the possible paths between a graph node and the initial “query nodes” (Minkov and Cohen, 2007). In addition, we outline in this paper a novel method for learning path-constrained graph walks. While reranking allows use of high-level features that describe properties of the traversed paths, the suggested algorithm incorporates this information in the graph walk process. More specifically, we allow the probability flow in the graph to …

Content truncated to 500 words