Difference between revisions of "Class Meeting for 10-710 10-06-2011"
From Cohen Courses
Jump to navigationJump to search| Line 17: | Line 17: | ||
* Also see this [http://ilpnlp.wikidot.com/bibliography bibliography] of uses of ILP for natural language processing through 2008 | * Also see this [http://ilpnlp.wikidot.com/bibliography bibliography] of uses of ILP for natural language processing through 2008 | ||
* [http://aclweb.org/anthology-new/D/D10/D10-1001.pdf On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing], A. Rush, D. Sontag, M. Collins, and T. Jaakola, EMNLP 2010 | * [http://aclweb.org/anthology-new/D/D10/D10-1001.pdf On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing], A. Rush, D. Sontag, M. Collins, and T. Jaakola, EMNLP 2010 | ||
| + | * [http://www.cs.cmu.edu/~nasmith/papers/martins+smith+aguiar+figueiredo.emnlp11.pdf 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 === | === Interaction between inference and learning === | ||
| Line 24: | Line 25: | ||
=== Background Readings === | === Background Readings === | ||
| + | |||
| + | *[http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf Approximate Inference in Graphical Models using LP Relaxations], David Sontag's PhD thesis (MIT, 2010) | ||
Latest revision as of 08:08, 6 October 2011
This 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)
