What are the main advantages and disadvantages of dual decomposition versus A* (and search-based methods) for NLP applications?

In EMNLP 2010 there were two papers advocating dual decomposition methods for some nlp problems. They are Koo et al Dual Decomposition for Parsing with Non-Projective Head Automata and Rush et al On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing. Some of the problems they attack are similar to problems attacked by Klein and Manning Fast exact inference with a factored model for natural language parsing, among other papers, that use a generic search-based approach.

When is one better than the other? What are the main advantages? When can one be considered a generalization of the other?

a-star nlp search dual-decomposition

asked Oct 12 '10 at 19:19

Alexandre Passos ♦
18952●44●214●333

One Answer:

oldest newest most voted

There are some obvious differences:

A* is an exact search algorithm, while dual decomposition solves a relaxation of the original problem, and this relaxation might not find the optimal solution (although it will tell you if it didn't). For this reason dual decomposition has a faster worst-case running time, but some variants of A* can be tried that will be able to finish faster (with an arbitrary budget that, when extended enough, provably leads to the optimal solution) and also guarantee optimality if it's the case.
Dual decomposition can use preexisting algorithms (almost) as a black box, while A* and other search-based methods might require substantially changing the structure of the search algorithm.

answered Oct 12 '10 at 19:20

Alexandre Passos ♦
18952●44●214●333

Your answer

toggle preview

community wiki

Once you sign in you will be able to subscribe for any updates here

Tags:

Asked: Oct 12 '10 at 19:19

Seen: 2,012 times

Last updated: Oct 12 '10 at 19:21