A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing

Abstract

Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in natural language processing (NLP). This tutorial gives an overview of the technique. We describe example algorithms, describe formal guarantees for the method, and describe practical issues in implementing the algorithms. While our examples are predominantly drawn from the NLP literature, the material should be of general relevance to inference problems in machine learning. A central theme of this tutorial is that Lagrangian relaxation is naturally applied in conjunction with a broad class of combinatorial algorithms, allowing inference in models that go significantly beyond previous work on Lagrangian relaxation for inference in graphical models.

References in corpus (2)

• Tightening LP Relaxations for MAP using Message Passing
• Lagrangian Relaxation for MAP Estimation in Graphical Models

Cited by in corpus (8)

• Men Also Like Shopping: Reducing Gender Bias Amplification using Corpus-level Constraints
• Mitigating Gender Bias in Natural Language Processing: Literature Review
• Domain Knowledge Empowered Structured Neural Net for End-to-End Event Temporal Relation Extraction
• Echocardiography Segmentation with Enforced Temporal Consistency
• Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs
• Learning Soft Linear Constraints with Application to Citation Field Extraction
• Combining Generative and Discriminative Approaches to Unsupervised Dependency Parsing via Dual Decomposition
• Prior-aware Dual Decomposition: Document-specific Topic Inference for Spectral Topic Models