Article | Proceedings of the 20th Nordic Conference of Computational Linguistics, NODALIDA 2015, May 11-13, 2015, Vilnius, Lithuania | An Optimal Quadratic Approach to Monolingual Paraphrase Alignment
Göm menyn

Title:
An Optimal Quadratic Approach to Monolingual Paraphrase Alignment
Author:
Mihai Lintean: Department of Computer Science, The University of Memphis, Memphis, USA Vasile Rus: Department of Computer Science, The University of Memphis, Memphis, USA
Download:
Full text (pdf)
Year:
2015
Conference:
Proceedings of the 20th Nordic Conference of Computational Linguistics, NODALIDA 2015, May 11-13, 2015, Vilnius, Lithuania
Issue:
109
Article no.:
017
Pages:
127-134
No. of pages:
8
Publication type:
Abstract and Fulltext
Published:
2015-05-06
ISBN:
978-91-7519-098-3
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Series:
NEALT Proceedings Series
Publisher:
Linköping University Electronic Press, Linköpings universitet


Export in BibTex, RIS or text

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.

Proceedings of the 20th Nordic Conference of Computational Linguistics, NODALIDA 2015, May 11-13, 2015, Vilnius, Lithuania

Author:
Mihai Lintean, Vasile Rus
Title:
An Optimal Quadratic Approach to Monolingual Paraphrase Alignment
References:

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.

Proceedings of the 20th Nordic Conference of Computational Linguistics, NODALIDA 2015, May 11-13, 2015, Vilnius, Lithuania

Author:
Mihai Lintean, Vasile Rus
Title:
An Optimal Quadratic Approach to Monolingual Paraphrase Alignment
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment


Responsible for this page: Peter Berkesand
Last updated: 2017-02-21