We model the problem of monolingual textual alignment as a Quadratic Assignment Problem (QAP) which simultaneously maximizes the global lexicosemantic (at word level) and syntactic similarity of two sentence-level texts. Because QAP is an NP-complete problem, we propose a branch-and-bound approach to efficiently find an optimal solution. When compared with other methods and studies, our results are competitive.
Eneko Agirre, Daniel Cel, Mona Diab, and Aitor Gonzalez-Agirre. 2012. SemEval-2012 Task 6: A Pilot on Semantic Textual Similarity. Proceedings of SemEval 2012, in conjunction with *SEM 2012.
Montreal, Canada, June 7-8, 2012.
Kurt M. Anstreicher. 2003. Recent advances in the solution of quadratic assignment problems. Mathematical Programming, volume 97(1-2):27–42. Springer.
James Brunning. 2010. Alignment Models and Algorithms for Statistical Machine Translation. Ph.D. Thesis, Cambridge University Engineering Department.
Rainer E. Burkard, Eranda C¸ ela, Panos M. Pardalos, and Leonidas S. Pitsoulis. 1998. The Quadratic Assignment Problem. In P.M. Pardalos and D.Z. Zu, editors, Handbook of Combinatorial Optimization, volume 3:241–337. Kluwer Academic Publishers.
Nathanael Chambers, Daniel Cer, Trond Grenager, David Hall, Chloe Kiddon, Bill MacCartney, Marie-Catherine De Marneffe, Daniel Ramage, Eric Yeh, and Christopher D. Manning. 2007. Learning Alignments and Leveragning Natural Logic. In Proceedings of the ACL-07 Workshop on Textual Entailment and Paraphrasing.
Yee S. Chan and Hwee T. Ng. 2008. MAXSIM: A maximum similarity metric for machine translation evaluation. In Proceedings of ACL-08: HLT, pages 55–62.
Nicos Christofides and Enrique Benavent. 1989. An exact algorithm for the quadratic assignment problem. Operations Research, volume 37(5):760–768.
Trevor Cohn, Chris Callison-Burch, and Mirella Lapata. 2008. Constructing corpora for the development and evaluation of paraphrase systems. Computational
Linguistics, volume 34(4):597–614.
Michael Denkowski and Alon Lavie. 2011. Meteor 1.3 Automatic Metric for Reliable Optimization and Evaluation of Machine Translation Systems. In EMNLP 2011 - Workshop on Statistical Machine Translation.
Bill Dolan, Chris Quirk, and Chris Brockett. 2004. Unsupervised construction of large paraphrase corpora: Exploiting massively parallel news sources. In Proceedings of the 20th International Conference on Computational Linguistics. Geneva, Switzerland.
Tjalling C. Koopmans and Martin Beckmann. 1957. Assignment Problems and the Location of Economic Activities. Econometrica, volume 25(1):53–76.
Harold W. Kuhn. 1955. The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, volume 2:83–97.
Simon Lacoste-Julien, Ben Taskbar, Dan Klein, and Michael I. Jordan. 2006. Word Alignment via Quadratic Assignment. In Proceedings of HLTNAACL ’06, pages 112–119. New York, June 2006.
Eugene L. Lawler. 1963. The quadratic assignment problem. Management Science, volume 9:586–599.
Bill MacCartney, Michel Galley, and Christopher D. Manning. 2008. A Phrase-Based Alignment Model for Natural Language Inference. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing. Honolulu. October, 2008.
Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating Typed Dependency Parses from Phrase Structure Parses. In LREC 2006.
James Munkres. 1957. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38.
Society for Industrial and Applied Mathematics. Franz J. Och and Hermann Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, volume 29:19–51.
Ted Pedersen, Siddharth Patwardhan, and Jason Michelizzi. 2004. WordNet::Similarity - Measuring the Relatedness of Concepts. In NAACL-2004.
Vasile Rus, Mihai Lintean, Rajendra Banjade, Nobal Niraula, and Dan Stefanescu. 2013. SEMILAR: The Semantic Similarity Toolkit. In Proceedings of ACL 2013. Sofia, Bulgaria. August 4-9, 2013.
Sartaj Sahni and Teofilo Gonzalez. 1976. P-complete approximation problems. Journal of the Association for Computing Machinery, volume 23:555–565.
Arafat Md Sultan, Steven Bethard, and Tamara Summer 2014. Back to Basics for Monolingual Alignment: Exploiting Word Similarity and Contextual Evidence. Transactions of the Association of Computational Linguistics, volume 2(1):219–230.
Kapil Thadani, Scott Martin, and Michael White. 2012. A Join Phrasal and Dependency Model for Paraphrase Alignment. In Proceedings of COLING-2012
Kapil Thadani and Kathleen McKeown. 2011. Optimal and syntactically-informed decoding for monolingual phrase-based alignment. In Proceedings of ACL-HLT, HLT ’11, pages 254–259.
Xuchen Yao, Benjamin Van Durme, Chris Callison-Burch and Peter Clark 2013. A Lightweight and High Performance Monolingual Word Aligner. In ACL (2). The Association for Computer Linguistics, pages 702–707.
