Hitting the Right Paraphrases in Good Time

Citation

Hitting the Right Paraphrases in Good Time, by S. Kok, C.Brockett. In Proceedings of NAACL/HLT 2010, 2010.

This Paper is available online [1].

Summary

The authors present an approach to paraphrasing based on random walks and bilingual parallel phrase corpora. They first construct a graph, where the nodes are phrases in multiple languages, and the edges are between phrases that have been aligned to each other using some sort of phrase alignment model or system. Next, for a particular sentence they break it down into phrases, and then compute the hitting time for each phrase and all of the other phrases in the graph. The hitting time is the expected time it would take for a random walk going from node i to reach node j, based on the transition probabilities of the graph (more on how this is computed in their particular case later). They sort the hitting times based on lowest first to come up with the paraphrases that are most probable as defined by random walks on the graph. The authors discuss a couple of methods to prune the graph and also to minimize spurious word alignments, as well as show how they can incorporate domain knowledge into the graph-based paraphrase model.