Class Meeting for 10-710 10-06-2011

This is one of the class meetings on the schedule for the course Structured Prediction 10-710 in Fall 2011.

A Linear Programming Formulation for Global Inference in Natural Language Tasks, D. Roth and W.-T. Yih, CoNLL 2004
Integer Linear Programming Inference for Conditional Random Fields, D. Roth and W.-T. Yih, ICML 2005
A Fast Finite-State Relaxation Method for Enforcing Global Constraints on Sequence Decoding, R. W. Tromble and J. Eisner, NAACL 2006 (this paper is not about using ILP; it shows that the ILP of the paper above can be better represented using finite-state machines and a blend of dynamic programming and cutting planes-style relaxation)
Word Alignment via Quadratic Assignment, S. Lacoste-Julien, B. Taskar, D. Klein, and M. I. Jordan, NAACL 2006
Also see this bibliography of uses of ILP for natural language processing through 2008
On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing, A. Rush, D. Sontag, M. Collins, and T. Jaakola, EMNLP 2010
Dual Decomposition with Many Overlapping Components, A. F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and M. A. T. Figuereida, EMNLP 2011

When decoding/inference can be cast as an LP, there are some interesting approaches to learning in the max-margin framework: Structured Prediction, Dual Extragradient and Bregman Projections, B. Taskar, S. Lacoste-Julien, and M. I. Jordan, JMLR 7:1627-1653
Embedding LP relaxed inference inside learning, and encouraging your model to avoid fractional vertices: Polyhedral Outer Approximations with Application to Natural Language Parsing, A. F. T. Martins, N. A. Smith, E. P. Xing, ICML 2009; see also important earlier papers by Kulesza and Pereira (2007) and Finley and Joachims (2008)

Contents