On dual decomposition and linear programming relaxations for natural language processing
This paper introduces dual decomposition as a framework for deriving inference algorithms for NLP problems. The approach relies on standard dynamic-programming algorithms as oracle solvers for sub-problems, together with a simple method for forcing agreement between the different oracles. The...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computational Linguistics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62836 https://orcid.org/0000-0002-2199-0379 |
| _version_ | 1826208850260262912 |
|---|---|
| author | Rush, Alexander Matthew Sontag, David Alexander Collins, Michael Jaakkola, Tommi S. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Rush, Alexander Matthew Sontag, David Alexander Collins, Michael Jaakkola, Tommi S. |
| author_sort | Rush, Alexander Matthew |
| collection | MIT |
| description | This paper introduces dual decomposition as a
framework for deriving inference algorithms
for NLP problems. The approach relies on
standard dynamic-programming algorithms as
oracle solvers for sub-problems, together with
a simple method for forcing agreement between
the different oracles. The approach
provably solves a linear programming (LP) relaxation
of the global inference problem. It
leads to algorithms that are simple, in that they
use existing decoding algorithms; efficient, in
that they avoid exact algorithms for the full
model; and often exact, in that empirically
they often recover the correct solution in spite
of using an LP relaxation. We give experimental
results on two problems: 1) the combination
of two lexicalized parsing models; and
2) the combination of a lexicalized parsing
model and a trigram part-of-speech tagger. |
| first_indexed | 2024-09-23T14:13:19Z |
| format | Article |
| id | mit-1721.1/62836 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:13:19Z |
| publishDate | 2011 |
| publisher | Association for Computational Linguistics |
| record_format | dspace |
| spelling | mit-1721.1/628362022-10-01T19:52:00Z On dual decomposition and linear programming relaxations for natural language processing Rush, Alexander Matthew Sontag, David Alexander Collins, Michael Jaakkola, Tommi S. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jaakkola, Tommi S. Rush, Alexander Matthew Sontag, David Alexander Collins, Michael Jaakkola, Tommi S. This paper introduces dual decomposition as a framework for deriving inference algorithms for NLP problems. The approach relies on standard dynamic-programming algorithms as oracle solvers for sub-problems, together with a simple method for forcing agreement between the different oracles. The approach provably solves a linear programming (LP) relaxation of the global inference problem. It leads to algorithms that are simple, in that they use existing decoding algorithms; efficient, in that they avoid exact algorithms for the full model; and often exact, in that empirically they often recover the correct solution in spite of using an LP relaxation. We give experimental results on two problems: 1) the combination of two lexicalized parsing models; and 2) the combination of a lexicalized parsing model and a trigram part-of-speech tagger. United States. Defense Advanced Research Projects Agency. Machine Reading Program United States. Air Force Research Laboratory (Prime contract no. FA8750-09-C-0181) United States. Defense Advanced Research Projects Agency. GALE Program (Contract No. HR0011-06-C-0022) Google (Firm) 2011-05-18T20:44:45Z 2011-05-18T20:44:45Z 2010-10 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/62836 Rush, Alexander M. et al. “On dual decomposition and linear programming relaxations for natural language processing.” Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing. Cambridge, Massachusetts: Association for Computational Linguistics, 2010. 1-11. c2010 Association for Computational Linguistics. https://orcid.org/0000-0002-2199-0379 en_US http://portal.acm.org/citation.cfm?id=1870659 Conference on Empirical Methods in Natural Language Processing 2010, Proceedings Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computational Linguistics MIT web domain |
| spellingShingle | Rush, Alexander Matthew Sontag, David Alexander Collins, Michael Jaakkola, Tommi S. On dual decomposition and linear programming relaxations for natural language processing |
| title | On dual decomposition and linear programming relaxations for natural language processing |
| title_full | On dual decomposition and linear programming relaxations for natural language processing |
| title_fullStr | On dual decomposition and linear programming relaxations for natural language processing |
| title_full_unstemmed | On dual decomposition and linear programming relaxations for natural language processing |
| title_short | On dual decomposition and linear programming relaxations for natural language processing |
| title_sort | on dual decomposition and linear programming relaxations for natural language processing |
| url | http://hdl.handle.net/1721.1/62836 https://orcid.org/0000-0002-2199-0379 |
| work_keys_str_mv | AT rushalexandermatthew ondualdecompositionandlinearprogrammingrelaxationsfornaturallanguageprocessing AT sontagdavidalexander ondualdecompositionandlinearprogrammingrelaxationsfornaturallanguageprocessing AT collinsmichael ondualdecompositionandlinearprogrammingrelaxationsfornaturallanguageprocessing AT jaakkolatommis ondualdecompositionandlinearprogrammingrelaxationsfornaturallanguageprocessing |