Integer Linear Programming Inference for Conditional Random Fields

Download paper here

Inference in Conditional Random Fields and Hidden Markov Models is done using the Viterbi algorithm, an e±cient 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 e±ciently 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.