[Colloquium] TTIC Colloquium: Michael Collins, Columbia University

[Liv Leader]

When:     Thursday, July 21 @ 11:00 a.m.

Where:   TTIC Conference Room #526, 6045 S. Kenwood Avenue, 5th Floor

Who:      Michael Collins, Columbia University


Title:      Lagrangian relaxation for inference in natural language
processing



Abstract: 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.



Host: David McAllester, mcallester at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute
6045 S Kenwood Ave, #504
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
 <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110718/76f7fea0/attachment.htm