Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Integer Linear Programming Inference for Conditional Random Fields

D. Roth and W. Yih

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.

Details

Publication typeInproceedings
Published inProceedings of the 22nd International Conference on Machine Learning (ICML-2005)
Pages737–744
PublisherAssociation for Computing Machinery, Inc.
> Publications > Integer Linear Programming Inference for Conditional Random Fields