James Clarke & Research

Incremental Integer Linear Programming for Non-projective Dependency Parsing

Sebastian Riedel and James Clarke. 2006. Incremental Integer Linear Programming for Non-projective Dependency Parsing. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 129–137. Sydney, Australia.

Download talk slides.

Abstract

Integer Linear Programming has recently been used for decoding in a number of probabilistic models in order to enforce global constraints. However, in certain applications, such as non-projective dependency parsing and machine translation, the complete formulation of the decoding problem as an integer linear program renders solving intractable. We present an approach which solves the problem incrementally, thus we avoid creating intractable integer linear programs. This approach is applied to Dutch dependency parsing and we show how the addition of linguistically motivated constraints can yield a significant improvement over state-of-the-art.

Bibtex

@inproceedings{Riedel:Clarke:06,
  author =       {Sebastian Riedel and James Clarke},
  title =        {Incremental Integer Linear Programming for
                  Non-projective Dependency Parsing},
  booktitle =    {Proceedings of the 2006 Conference on Empirical
                  Methods in Natural Language Processing (EMNLP-2006)},
  pages =        {129--137},
  year =         {2006},
  address =      {Sydney, Australia},
  URL =          {http://jamesclarke.net/media/papers/riedel-clarke-emnlp06.pdf},
}