TY - GEN

T1 - Integer linear programming inference for conditional random fields

AU - Roth, Dan

AU - Yih, Wen Tau

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=31844450331&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=31844450331&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:31844450331

SN - 1595931805

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

SP - 737

EP - 744

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

A2 - Raedt, L.

A2 - Wrobel, S.

T2 - ICML 2005: 22nd International Conference on Machine Learning

Y2 - 7 August 2005 through 11 August 2005

ER -