BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Lagrangian relaxation for inference in natural language processing
  - Michael Collins\, Columbia University
DTSTART:20110613T120000Z
DTEND:20110613T133000Z
UID:TALK31687@talks.cam.ac.uk
CONTACT:Bill Byrne
DESCRIPTION:There has been a long history in combinatorial optimization of
  methods that exploit structure in complex problems\, using methods such a
 s dual decomposition or Lagrangian relaxation. These methods leverage the 
 observation that complex inference problems can often be decomposed into e
 fficiently solvable sub-problems. Thus far\, however\, these methods are n
 ot widely used in NLP.\n\nIn this talk I'll describe recent work on infere
 nce algorithms for NLP based on Lagrangian relaxation. In the first part o
 f the talk I'll describe work on non-projective parsing. In the second par
 t of the talk I'll describe an exact decoding algorithm for syntax-based s
 tatistical translation. If time permits\, I'll also briefly describe algor
 ithms for dynamic programming intersections (e.g.\, the intersection of a 
 PCFG and an HMM)\, and for phrase-based translation.\n\nFor all of the pro
 blems 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 fo
 r problems that are solvable in polynomial time using dynamic programming\
 , but where the traditional exact algorithms are far too expensive to be p
 ractical.\n\nWhile the focus of this talk is on NLP problems\, there are c
 lose 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 rando
 m fields.\n\nThis is joint work with Yin-Wen Chang\, Tommi Jaakkola\, Terr
 y Koo\, Sasha Rush\, and David Sontag.\n
LOCATION: Cambridge University Engineering Department\, Lecture Room 6
END:VEVENT
END:VCALENDAR