Paper: A Linear Programming Formulation For Global Inference In Natural Language Tasks

ACL ID W04-2401
Title A Linear Programming Formulation For Global Inference In Natural Language Tasks
Venue International Conference on Computational Natural Language Learning
Session Main Conference
Year 2004
Authors

Given a collection of discrete random variables representing outcomes of learned local predic- tors in natural language, e.g., named entities and relations, we seek an optimal global as- signment to the variables in the presence of general (non-sequential) constraints. Examples of these constraints include the type of argu- ments a relation can take, and the mutual activ- ity of different relations, etc. We develop a lin- ear programming formulation for this problem and evaluate it in the context of simultaneously learning named entities and relations. Our ap- proach allows us to efficiently incorporate do- main and task specific constraints at decision time, resulting in significant improvements in the accuracy and the “human-like” quality of the inferences.