Integer Linear Programming Inference for Conditional Random Fields
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.
Cite
Text
Roth and Yih. "Integer Linear Programming Inference for Conditional Random Fields." International Conference on Machine Learning, 2005. doi:10.1145/1102351.1102444Markdown
[Roth and Yih. "Integer Linear Programming Inference for Conditional Random Fields." International Conference on Machine Learning, 2005.](https://mlanthology.org/icml/2005/roth2005icml-integer/) doi:10.1145/1102351.1102444BibTeX
@inproceedings{roth2005icml-integer,
title = {{Integer Linear Programming Inference for Conditional Random Fields}},
author = {Roth, Dan and Yih, Wen-tau},
booktitle = {International Conference on Machine Learning},
year = {2005},
pages = {736-743},
doi = {10.1145/1102351.1102444},
url = {https://mlanthology.org/icml/2005/roth2005icml-integer/}
}