Optimal and Syntactically-Informed Decoding for Monolingual Phrase-Based Alignment

Kapil Thadani and Kathleen McKeown
Columbia University


Abstract

The task of aligning corresponding phrases across two related sentences is an important component of approaches for natural language problems such as paraphrase detection, textual inference and text-to-text generation. In this work, we examine a state-of-the-art structured prediction model for this task which uses a phrase-based representation and is forced to decode alignments using approximate search. We propose instead a straightforward exact decoding solution based on integer linear programming that yields order-of-magnitude improvements in decoding speed while further improving alignment performance. This decoding strategy permits us to consider syntactic constraints which significantly increase the precision of the model.




Full paper: http://www.aclweb.org/anthology/P/P11/P11-2044.pdf