Lagrangian relaxation for inference in natural language processing

Add to your list(s) Download to your calendar using vCal

• Michael Collins, Columbia University
• Monday 13 June 2011, 13:00-14:30
• Cambridge University Engineering Department, Lecture Room 6.

If you have a question about this talk, please contact Bill Byrne.

There will be sandwiches.

There has been a long history in combinatorial optimization of methods that exploit structure in complex problems, using methods such as dual decomposition or Lagrangian relaxation. These methods leverage the observation that complex inference problems can often be decomposed into efficiently solvable sub-problems. Thus far, however, these methods are not widely used in NLP .

In this talk I’ll describe recent work on inference algorithms for NLP based on Lagrangian relaxation. In the first part of the talk I’ll describe work on non-projective parsing. In the second part of the talk I’ll describe an exact decoding algorithm for syntax-based statistical translation. If time permits, I’ll also briefly describe algorithms for dynamic programming intersections (e.g., the intersection of a PCFG and an HMM ), and for phrase-based translation.

For all of the problems that we consider, the resulting algorithms produce exact solutions, with certificates of optimality, on the vast majority of examples; the algorithms are efficient for problems that are either NP-hard (as is the case for non-projective parsing, or for phrase-based translation), or for problems that are solvable in polynomial time using dynamic programming, but where the traditional exact algorithms are far too expensive to be practical.

While the focus of this talk is on NLP problems, there are close connections to inference methods, in particular belief propagation, for graphical models. Our work was inspired by recent work that has used dual decomposition as an alternative to belief propagation in Markov random fields.

This is joint work with Yin-Wen Chang, Tommi Jaakkola, Terry Koo, Sasha Rush, and David Sontag.

This talk is part of the Speech Seminars series.

This talk is included in these lists:

• Cambridge University Engineering Department, Lecture Room 6
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Speech Seminars

Note that ex-directory lists are not shown.