Hitting the Right Paraphrases in Good Time

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 145–153, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Hitting the Right Paraphrases in Good Time Stanley Kok Department of Computer Science & Engineering University of Washington Seattle, WA 98195, USA koks@cs.washington.edu Chris Brockett Microsoft Research One Microsoft Way Redmond, WA 98052, USA chrisbkt@microsoft.com Abstract We present a random-walk-based approach to learning paraphrases from bilingual parallel corpora. The corpora are represented as a graph in which a node corresponds to a phrase, and an edge exists between two nodes if their corresponding phrases are aligned in a phrase table. We sample random walks to compute the average number of steps it takes to reach a ranking of paraphrases with better ones be- ing “closer” to a phrase of interest. This ap- proach allows “feature” nodes that represent domain knowledge to be built into the graph, and incorporates truncation techniques to pre- vent the graph from growing too large for ef- ficiency. Current approaches, by contrast, im- plicitly presuppose the graph to be bipartite, are limited to finding paraphrases that are of length two away from a phrase, and do not generally permit easy incorporation of domain knowledge. Manual evaluation of generated output shows that our approach outperforms the state-of-the-art system of Callison-Burch (2008). 1 Introduction Automatically learning paraphrases, or alternative ways of expressing the same meaning, is an ac- tive area of NLP research because of its useful- ness in a variety of applications, e.g., question an- swering (Lin and Pantel, 2001; Ravichandran and Hovy, 2002; Reizler et al., 2007), document sum- marization (Barzilay et al., 1999; McKeown et al., 2002), natural language generation (Iordanskaja et al., 1991; Lenke, 1994; Stede, 1999), machine trans- lation (Kauchak and Barzilay, 2006; Callison-Burch et al., 2006; Madnani et al., 2007). Early work on paraphrase acquisition has focused on using monolingual parallel corpora (Barzilay and McKeown, 2001; Barzilay and Lee, 2003; Pang et al., 2003; Quirk et al., 2004). While effective, such methods are hampered by the scarcity of monolin- gual parallel corpora, an obstacle that limits both the quantity and quality of the paraphrases learned. To address this limitation, Bannard and Callison- Burch (2005) focused their attention on the abun- dance of bilingual parallel corpora. The crux of this system (referred to below as ”BCB”) is to align phrases in a bilingual parallel corpus and hypothe- size English phrases as potential paraphrases if they are aligned to the same phrase in another language (the “pivot”). Callison-Burch (2008) further refines BCB with a system that constrains paraphrases to have the same syntactic structure (Syntactic Bilin- gual Phrases: SBP). We take a graphical view of the state-of-the-art BCB and SBP approaches by representing the bilin- gual parallel corpora as a graph. A node corresponds to a phrase, and an edge exists between two nodes if their corresponding phrases are aligned. This graph- ical form makes the limitations of the BCB/SBP ap- proaches more evident. The BCB/SBP graph …

Content truncated to 500 words