Integer linear programming inference for conditional random fields

Dan Roth, Wen Tau Yih

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Inference in Conditional Random Fields and Hidden Markov Models is done using the Viterbi algorithm, an efficient dynamic programming algorithm. In many cases, general (non-local and non-sequential) constraints may exist over the output sequence, but cannot be incorporated and exploited in a natural way by this inference procedure. This paper proposes a novel inference procedure based on integer linear programming (ILP) and extends CRF models to naturally and efficiently support general constraint structures. For sequential constraints, this procedure reduces to simple linear programming as the inference process. Experimental evidence is supplied in the context of an important NLP problem, semantic role labeling.

Original languageEnglish (US)
Title of host publicationICML 2005 - Proceedings of the 22nd International Conference on Machine Learning
EditorsL. Raedt, S. Wrobel
Pages737-744
Number of pages8
StatePublished - Dec 1 2005
EventICML 2005: 22nd International Conference on Machine Learning - Bonn, Germany
Duration: Aug 7 2005Aug 11 2005

Publication series

NameICML 2005 - Proceedings of the 22nd International Conference on Machine Learning

Other

OtherICML 2005: 22nd International Conference on Machine Learning
CountryGermany
CityBonn
Period8/7/058/11/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Integer linear programming inference for conditional random fields'. Together they form a unique fingerprint.

Cite this