Dual Decomposition for Natural Language Processing
PRESENTERS: Michael Collins and Alexander M Rush

ABSTRACT:

For many tasks in natural language processing, finding the best
solution requires a search over a large set of possible choices.
Solving this decoding problem exactly can be complex and inefficient,
and so researchers often use approximate techniques at the cost
of model accuracy. In this tutorial, we present dual decomposition
as an alternative method for decoding in natural language problems.
Dual decomposition produces exact algorithms that rely only on basic
combinatorial algorithms, like shortest path or minimum spanning tree,
as building blocks. Since these subcomponents are straightforward to
implement and are well-understood, the resulting decoding algorithms
are often simpler and significantly faster than exhaustive search,
while still producing certified optimal solutions in practice.

This tutorial presents dual decomposition as a general inference
technique, while utilizing examples and applications from natural
language processing. The goal is for attendees to learn to derive
algorithms for problems in their domain and understand the formal
guarantees and practical considerations in using these algorithms.

We begin the tutorial with a step-by-step construction of an
algorithm for combined CFG parsing and trigram tagging. To analyze
this algorithm, we derive formal properties for the techniques
used in the construction. We then give further examples for how
to derive similar algorithms for other difficult tasks in NLP and
discuss some of the practical considerations for using these
algorithms on real-world problems. In the last section of the
tutorial, we explore the relationship between these algorithms
and the theory of linear programming, focusing particularly on
the connection between linear programming and dynamic programming
algorithms. We conclude by using this connection to linear
programming to develop practical tightening techniques that help
obtain exact solutions.



OUTLINE:

  1. Step-By-Step Example Derivation
  2. Formal Properties
  3. Further Examples
    a. Dependency Parsing
    b. Translation Decoding
    c. Document-level Tagging
  4. Practical Considerations
  5. Linear Programming Interpretation
  6. Connections between DP and LP
  7. Tightening Methods for Exact Solutions


BIO:

Michael Collins
	Columbia University
	mcollins@cs.columbia.edu

Michael Collins is the Vikram S. Pandit Professor of computer
science at Columbia University. His research is focused on topics
including statistical parsing, structured prediction problems in
machine learning, and applications including machine translation,
dialog systems, and speech recognition. His awards include a Sloan
fellowship, an NSF career award, and best paper awards at
EMNLP (2002, 2004, and 2010), UAI (2004 and 2005), and CoNLL 2008.


Alexander M Rush
	MIT CSAIL
	srush@csail.mit.edu

Alexander M Rush is a Ph.D. candidate in computer science at MIT.
His research explores novel decoding methods for problems in
natural language processing with applications to parsing and machine
translation. His paper "Dual Decomposition for Parsing with
Non-Projective Head Automata received the best paper award at
EMNLP 2010.