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 |
| Summary: | 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. |
|---|