NAACL/HLT 2009 Workshop on Integer Linear Programming for Natural Language Processing

June 4, 2009, Boulder, Colorado, USA
Contact: <moc.liamg|9002plnpli#moc.liamg|9002plnpli>

Workshop Program

9:20–9:30 Opening Remarks

9:30–10:30 Invited Talk by Dan Roth

10:30–11:00 Coffee break

11:00–11:30 Summarization with a Joint Model for Sentence Extraction and Compression
Andre Martins and Noah Smith

11:30–12:00 A Scalable Global Model for Summarization
Dan Gillick and Benoit Favre

12:00–12:30 Bounding and Comparing Methods for Correlation Clustering Beyond ILP
Micha Elsner and Warren Schudy

12:30–2:00 Lunch break

2:00–2:45 Invited Talk by Andre Martins and Noah Smith

2:45–3:15 A New Objective Function for Word Alignment
Tugba Bodrumlu, Kevin Knight and Sujith Ravi

3:15–3:30 A Constraint Programming Approach to Probabilistic Syntactic Processing
Irene Langkilde-Geary

3:30–4:00 Coffee break

4:00–5:00 Discussion

Invited Talks

Constrained Conditional Models: Learning and Inference in Natural Language Understanding
Dan Roth

Making decisions in natural language understanding tasks often involves assigning values to sets of interdependent variables where an expressive dependency structure among these can influence, or even dictate, what assignments are possible.

Structured learning problems provide one such example, but we are interested in a broader setting where multiple models are involved and it may not be ideal, or possible, to learn them jointly.

I will present work on Constrained Conditional Models (CCMs), a framework that augments probabilistic models with declarative constraints as a way to support decisions in an expressive output space while maintaining modularity and tractability of training.

The focus will be on discussing training and inference paradigms for Constrained Conditional Models, with examples drawn from natural language understanding tasks such as semantic role learning, information extraction tasks, and transliteration.

ILP: Approximate Learning and Application to Parsing
Andre F. T. Martins and Noah A. Smith

Many problems in NLP can be cast as structured prediction. Efficient structured inference relies on strong independence assumptions, or using only “local” features. Yet recent research shows that significant improvements can be made by modeling global phenomena. Since exact inference with arbitrary features is generally intractable, this raises multiple questions: which approximate algorithm is the best for each task? What is the effect of approximate inference when used as a subroutine during learning?

In the first part of the talk, we focus on scenarios where inference can be cast as an integer linear program (ILP). We establish risk bounds for approximate max-margin learning via LP relaxations of the loss-augmented inference problem, and propose a new online discriminative learning algorithm that learns to penalize “time-consuming” models. Our analysis relies on a geometric characterization of the outer polyhedra associated with the LP relaxation.

We then apply these techniques to the problem of nonprojective dependency parsing, for which we present a novel ILP formulation with a polynomial number of variables and constraints in the size of the sentence. It can learn features that model correlations among neighboring arcs (siblings and grand-parents), word valency, and tendencies toward nearly-projective parses. We evaluate the performance of our parser on data in several natural languages, achieving improvements over existing state-of-the-art methods.

This is joint work with Eric Xing and portions of it will be published at ICML 2009 and ACL-IJCNLP 2009.

Call for Papers (Submission deadline: March 15, 2009)

Integer Linear Programming (ILP) has recently attracted much attention within the NLP community. Formulating problems using ILP has several advantages. It allows us to focus on the modelling of problems, rather than engineering new search algorithms; provides the opportunity to incorporate generic global constraints; and guarantees exact inference. This and the availability of off-the-shelf solvers has lead to a large variety of natural language processing tasks being formulated in the ILP framework, including semantic role labelling, syntactic parsing, summarisation and joint information extraction.

The use of ILP brings many benefits and opportunities but there are still challenges for the community; these include: formulations of new applications, dealing with large-scale problems and understanding the interaction between learning and inference at training and decision time. The purpose of this workshop is to bring together researchers interested in exploiting ILP for NLP applications and tackling the issues involved. We are interested in a broad range of topics including, but not limited to:

  • Novel ILP formulations of NLP tasks. This includes: the introduction of ILP formulations of tasks yet to be tackled within the framework; and novel formulations, such as equivalent LP relaxations, that are more efficient to process than previous formulations.
  • Learning and Inference. This includes issues relating to: decoupling of learning (e.g., learning through local classifiers) and inference, learning with exact (e.g., ILP) or approximate inference, learning of constraints, learning weights for soft constraints, and the impact of ignoring various constraints during learning.
  • The utility of global hard and soft constraints in NLP. Sometimes constraints do not increase accuracy (and can even decrease it), when and why do global constraints become useful? For example, do global constraints become more important if we have less data?
  • Formulating and solving large NLP problems. Applying ILP to hard problems (such as parsing, machine translation and joint inference for several NLP tasks at once) often results in very large formulations which can be impossible to solve directly by the ILP engine. This may require exploring different ILP solving methods (such as, approximate ILP solvers/methods) or cutting plane and pricing techniques.
  • Alternative declarative approaches. A variety of other modelling frameworks exist, of which ILP is just one instance. Using other approaches, such as weighted MAX-SAT, Constraint Satisfaction Problems (CSP) or Markov Networks, could be more suitable than ILP in some cases. It can also be helpful to model a problem in one framework (e.g., Markov Networks) and solve optimization problem within another (e.g., ILP) by using general mappings between representations.
  • First Order Modelling Languages. ILP, and other essentially propositional languages, require the creation of wrapper code to generate an ILP formulation for each problem instance. First (Higher) Order languages, such as Learning Based Java and Markov Logic, reduce this overhead and can also aid the solver to be more efficient. Moreover, with such languages the automatic exploration of the model space is easier.

Submission Information

We encourage submissions addressing the above questions and topics or other relevant issues. Authors are invited to submit a full paper of up to 8 pages (with up to 1 additional page for references), or an abstract of up to 2 pages. Appropriate topics for abstracts include preliminary results, application notes, descriptions of work in progress, etc. Previously published papers cannot be accepted.

The submissions will be reviewed by the program committee. Note that reviewing will be blind and hence no author information should be included in the papers. Self-references that reveal the author's identity, e.g., "We previously showed (Smith, 1991) …", should be avoided. Instead, use citations such as "Smith previously showed (Smith, 1991) …".

Papers will be accepted on or before 15 March 2009 in PDF format via the START system at Submissions should follow the NAACL HLT 2009 formatting requirements for full papers , found at

Workshop Organisers <moc.liamg|9002plnpli#moc.liamg|9002plnpli>

  • James Clarke (University of Illinois at Urbana-Champaign)
  • Sebastian Riedel (University of Tokyo/DBCLS)

Invited Speaker

  • Dan Roth (University of Illinois at Urbana-Champaign)

Confirmed committee members

  • Dan Roth (University of Illinois at Urbana-Champaign)
  • Mirella Lapata (University of Edinburgh)
  • Scott Yih (Microsoft Research)
  • Nick Rizzolo (University of Illinois at Urbana-Champaign)
  • Ming-Wei Chang (University of Illinois at Urbana-Champaign)
  • Ivan Meza-Ruiz (University of Edinburgh)
  • Ryan McDonald (Google Research)
  • Jenny Rose Finkel (Stanford University)
  • Pascal Denis (INRIA Paris-Rocquencourt)
  • Manfred Klenner (University of Zurich)
  • Hal Daume III (University of Utah)
  • Daniel Marcu (University of Southern California)
  • Kevin Knight (University of Southern California)
  • Katja Filippova (EML Research gGmbH)
  • Mark Dras (Macquarie University)
  • Hiroya Takamura (Tokyo Institute of Technology)

Important Dates

March 15, 2009
Deadline for paper submissions
March 31, 2009
Notification of paper acceptance
April 12, 2009
Camera-ready copies due
June 4, 2009
Workshop date
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License