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

By Alexander M. Rush, Michael Collins. 2012

124 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Natural Language Processing, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Natural Language Processing

In Mathematical Optimization

Citations in the corpus

Men Also Like Shopping: Reducing Gender Bias Amplification using Corpus-level Constraints (2017, methodology): “(3) using a Lagrangian relaxation technique (Rush and Collins, 2012).”
Mitigating Gender Bias in Natural Language Processing: Literature Review (2019, background): “The approximate inference can be efficient solved by Lagrangian relaxation (Rush and Collins, 2012).”
A Discriminative Graph-Based Parser for the Abstract Meaning Representation (2014, methodology): “To do this, we built an automatic aligner and tested its performance on a small set of alignments we annotated by hand.”
A Primal Dual Formulation For Deep Learning With Constraints (2019, methodology): “Other approaches have used dual decomposition to solve locally decomposable constraints (Rush and Collins [2012]).”
A Machine Learning Framework for Programming by Example (2013, background): “Unfortunately, dynamic programming common in structured learning approaches with PCFGs (Rush et al., 2011) does not apply here – it would be relevant if we were given a program and wanted to parse it.”
Statistical Relational Artificial Intelligence: Logic, Probability, and Computation (2016, background): “is is an instance of the declarative “Model + Solver” paradigm that was and is prevalent in AI [Geffner, 2014], natural language processing [Rush and Collins, 2012], machine learning [Sra et al.”
Dual Decomposition Inference for Graphical Models over Strings (2015, methodology): “It has been widely used for MAP inference in graphical models (Komodakis et al., 2007; Komodakis and Paragios, 2009; Koo et al., 2010; Martins et al., 2011; Sontag et al., 2011; Rush and Collins, 2014).”
Domain Knowledge Empowered Structured Neural Net for End-to-End Event Temporal Relation Extraction (2020, unknown): “Lagrangian Relaxation has been applied in a variety NLP tasks, as described by Rush and Collins (2011, 2012) and Zhao et al. (2017).”