Syntax-based Alignment of Multiple Translations: Extracting Paraphrases and Generating New Sentences

Syntax-based Alignment of Multiple Translations: Extracting Paraphrases and Generating New Sentences Bo Pang Department of Computer Science Cornell University Ithaca, NY 14853 USA pabo@cs.cornell.edu Kevin Knight and Daniel Marcu Information Sciences Institute University of Southern California Marina Del Rey, CA 90292 USA {knight,marcu}@isi.edu Abstract We describe a syntax-based algorithm that au- tomatically builds Finite State Automata (word lattices) from semantically equivalent transla- tion sets. These FSAs are good representa- tions of paraphrases. They can be used to ex- tract lexical and syntactic paraphrase pairs and to generate new, unseen sentences that express the same meaning as the sentences in the input sets. Our FSAs can also predict the correctness of alternative semantic renderings, which may be used to evaluate the quality of translations. 1 Introduction In the past, paraphrases have come under the scrutiny of many research communities. Information retrieval re- searchers have used paraphrasing techniques for query re- formulation in order to increase the recall of information retrieval engines (Sparck Jones and Tait, 1984). Natural language generation researchers have used paraphrasing to increase the expressive power of generation systems (Iordanskaja et al., 1991; Lenke, 1994; Stede, 1999). And researchers in multi-document text summarization (Barzilay et al., 1999), information extraction (Shinyama et al., 2002), and question answering (Lin and Pantel, 2001; Hermjakob et al., 2002) have focused on identi- fying and exploiting paraphrases in the context of recog- nizing redundancies, alternative formulations of the same meaning, and improving the performance of question an- swering systems. In previous work (Barzilay and McKeown, 2001; Lin and Pantel, 2001; Shinyama et al., 2002), paraphrases are represented as sets or pairs of semantically equiva- lent words, phrases, and patterns. Although this is ade- quate in the context of some applications, it is clearly too weak from a generative perspective. Assume, for exam- ple, that we know that text pairs (stock market rose, stock market gained) and (stock market rose, stock prices rose) have the same meaning. If we memorized only these two pairs, it would be impossible to infer that, in fact, con- sistent with our intuition, any of the following sets of phrases are also semantically equivalent: {stock market rose, stock market gained, stock prices rose, stock prices gained } and {stock market, stock prices } in the con- text of rose or gained; {market rose }, {market gained }, {prices rose } and {prices gained } in the context of stock; and so on. In this paper, we propose solutions for two problems: the problem of paraphrase representation and the problem of paraphrase induction. We propose a new, finite-state- based representation of paraphrases that enables one to encode compactly large numbers of paraphrases. We also propose algorithms that automatically derive such repre- sentations from inputs that are now routinely released in conjunction with large scale machine translation evalu- ations (DARPA, 2002): multiple English translations of many foreign language texts. For instance, when given as input the 11 semantically equivalent English transla- tions in Figure 1, our algorithm automatically induces the FSA in …

Content truncated to 500 words