On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing.
Alexander M. RushDavid A. SontagMichael CollinsTommi S. JaakkolaPublished in: EMNLP (2010)
Keyphrases
- dual decomposition
- linear programming relaxation
- natural language processing
- lagrangian relaxation
- feasible solution
- integer programming
- linear programming
- map inference
- column generation
- lower bound
- cutting plane
- energy minimization
- valid inequalities
- mixed integer programming
- knapsack problem
- information extraction
- machine learning
- natural language
- branch and bound
- integer program
- markov random field
- markov logic
- knowledge representation
- max margin
- structured prediction
- dynamic programming
- mixed integer
- upper bound
- search algorithm
- branch and bound algorithm
- traveling salesman problem
- graph cuts
- optimal solution
- co occurrence
- objective function