# Class Meeting for 10-710 10-06-2011

From Cohen Courses

Jump to navigationJump to searchThis is one of the class meetings on the schedule for the course Structured Prediction 10-710 in Fall 2011.

## Contents

### Making Structured Predictions with Integer Linear Programming

### 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
- 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

### Interaction between inference and learning

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

### Background Readings

- Approximate Inference in Graphical Models using LP Relaxations, David Sontag's PhD thesis (MIT, 2010)