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.

Making Structured Predictions with Integer Linear Programming

• Slides

Required Readings

• Section 2.2.2 of Linguistic Structure Prediction, Smith 2011 (assuming you read the rest of the chapter for Tuesday)

Optional Readings

• 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
• 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)