---
title: "A Linear Programming Formulation for Global — Roth 2004"
description: "NLP systems often combine several separately trained classifiers whose outputs depend on one another, such as named entity labels and the relations…"
authors: ["Dan Roth", "Wen-tau Yih"]
year: 2004
venue: "Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL-2004) at HLT-NAACL 2004"
source: "https://aclanthology.org/W04-2401/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/roth-2004-linear-programming-formulation-global-inference/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/roth-2004-linear-programming-formulation-global-inference/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2004](https://md.research.elamur.ai/free/en/papers/2004/) / A Linear Programming Formulation for Global Inference in Natural Language Tasks

# A Linear Programming Formulation for Global Inference in Natural Language Tasks

**Authors:** [Dan Roth](https://md.research.elamur.ai/free/en/authors/dan-roth/), [Wen-tau Yih](https://md.research.elamur.ai/free/en/authors/wen-tau-yih/) · **Year:** 2004 · **Venue:** Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL-2004) at HLT-NAACL 2004 · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/W04-2401/) · [PDF](https://aclanthology.org/W04-2401.pdf) · [OpenAlex](https://openalex.org/W1566346388)

**Citations:** 423 citations (openalex-snapshot · 2026-10-14) · [213](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
NLP systems often combine several separately trained classifiers whose outputs depend on one another, such as named entity labels and the relations between those entities. Dynamic programming methods like Viterbi handle sequential dependencies, but general (non-sequential) constraints make exact inference intractable. Roth and Yih address this within an "inference with classifiers" setting. Local entity and relation predictors are trained independently. At decision time, a global labeling is chosen to minimize two costs: the negative log of the classifiers' probabilities, and a penalty (effectively infinite) for violating constraints, such as which entity types a relation may take as arguments. Following Chekuri et al. (2001), they encode this objective with binary indicator variables and solve it as an integer linear program. On joint entity and relation recognition, global inference raised accuracy over a basic and a pipeline baseline, most visibly for relations. It also removed the inconsistent predictions those baselines produce. The main appeal is flexibility: new constraints can be added at decision time without retraining the classifiers.

## Key points
- The objective sums per-variable assignment costs (−log of the marginal probability) and pairwise constraint costs between a relation and its two arguments. In practice, a violated constraint is penalized with a huge constant. The problem is then cast as an ILP using an LP formulation based on Chekuri et al. (2001).
- LP is compared against Basic, Pipeline and an "Omniscient" setup, in which the relation classifier is given the gold entity labels as features.
  - Entity F1 improves under LP: person 89.3→90.2, organization 89.1→90.1, location 77.9→80.1.
  - Relation F1 also improves, for example located in 48.2 (Basic) →56.2 (LP) and kill 77.6→81.7.
- Basic and Pipeline produce 5–25% incoherent predictions, where a relation's label disagrees with its arguments' entity types. LP produces none by construction.
- In a "forced decision" test, the authors add a linear equality requiring a kill relation to be present. This lifts kill F1 to 86.2%, exceeding the Omniscient setup.
- Efficiency rests on off-the-shelf solvers. CPLEX is cited as handling an LP with 13 million variables in about 5 minutes.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Linguistics & languages](https://md.research.elamur.ai/free/en/shelves/linguistics/)

## Cited by

Cited by

213 papers of our library cite it (of the 140673 whose bibliographies we read); 24 of them have a page here, 189 not yet.

- [Modeling Biological Processes for Reading Comprehension](https://md.research.elamur.ai/free/en/papers/berant-2014-modeling-biological-processes-reading-comprehension/)
- [A Shortest Path Dependency Kernel for Relation Extraction](https://md.research.elamur.ai/free/en/papers/bunescu-2005-shortest-path-dependency-kernel-relation/)
- [A Constrained Latent Variable Model for Coreference Resolution](https://md.research.elamur.ai/free/en/papers/chang-2013-constrained-latent-variable-model-coreference/)
- [First-Order Probabilistic Models for Coreference Resolution](https://md.research.elamur.ai/free/en/papers/culotta-2007-first-order-probabilistic-models-coreference/)
- [Frame-Semantic Parsing](https://md.research.elamur.ai/free/en/papers/das-2014-frame-semantic-parsing/)
- [Joint Inference and Disambiguation of Implicit Sentiments via Implicature Constraints](https://md.research.elamur.ai/free/en/papers/deng-2014-joint-inference-disambiguation-implicit-sentiments/)
- [Joint Determination of Anaphoricity and Coreference Resolution using Integer Programming](https://md.research.elamur.ai/free/en/papers/denis-2007-joint-determination-anaphoricity-coreference-resolution/)
- [A Distributional and Orthographic Aggregation Model for English Derivational Morphology](https://md.research.elamur.ai/free/en/papers/deutsch-2018-distributional-orthographic-aggregation-model-english/)
- [Why are You Taking this Stance? Identifying and Classifying Reasons in Ideological Debates](https://md.research.elamur.ai/free/en/papers/hasan-2014-why-are-you-taking-this/)
- [A Cross-Lingual ILP Solution to Zero Anaphora Resolution](https://md.research.elamur.ai/free/en/papers/iida-2011-cross-lingual-ilp-solution-zero/)
- [Incremental Joint Extraction of Entity Mentions and Relations](https://md.research.elamur.ai/free/en/papers/li-2014-incremental-joint-extraction-entity-mentions/)
- [A Joint Neural Model for Information Extraction with Global Features](https://md.research.elamur.ai/free/en/papers/lin-2020-joint-neural-model-information-extraction/)
- [Modeling Joint Entity and Relation Extraction with Table Representation](https://md.research.elamur.ai/free/en/papers/miwa-2014-modeling-joint-entity-relation-extraction/)
- [A Joint Framework for Coreference Resolution and Mention Head Detection](https://md.research.elamur.ai/free/en/papers/peng-2015-joint-framework-coreference-resolution-mention/)
- [Solving Hard Coreference Problems](https://md.research.elamur.ai/free/en/papers/peng-2015-solving-hard-coreference-problems/)
- [RelEx-PT: A Portuguese Sentence-Level Relation Extraction Dataset](https://md.research.elamur.ai/free/en/papers/pinto-2026-relex-pt-portuguese-sentence-level/)
- [The Importance of Syntactic Parsing and Inference in Semantic Role Labeling](https://md.research.elamur.ai/free/en/papers/punyakanok-2008-importance-syntactic-parsing-inference-semantic/)
- [Solving General Arithmetic Word Problems](https://md.research.elamur.ai/free/en/papers/roy-2015-solving-general-arithmetic-word-problems/)
- [Mapping to Declarative Knowledge for Word Problem Solving](https://md.research.elamur.ai/free/en/papers/roy-2018-mapping-declarative-knowledge-word-problem/)
- [Supervised and Unsupervised Methods in Employing Discourse Relations for Improving Opinion Polarity Classification](https://md.research.elamur.ai/free/en/papers/somasundaran-2009-supervised-unsupervised-methods-employing-discourse/)
- [Mitigating Gender Bias in Natural Language Processing: Literature Review](https://md.research.elamur.ai/free/en/papers/sun-2019-mitigating-gender-bias-natural-language/)
- [Two are Better than One: Joint Entity and Relation Extraction with Table-Sequence Encoders](https://md.research.elamur.ai/free/en/papers/wang-2020-two-are-better-than-one/)
- [InstructUIE: Multi-task Instruction Tuning for Unified Information Extraction](https://md.research.elamur.ai/free/en/papers/wang-2023-instructuie-multi-task-instruction-tuning/)
- [GLM-130B: An Open Bilingual Pre-trained Model](https://md.research.elamur.ai/free/en/papers/zeng-2022-glm-130b-open-bilingual-pre/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{roth2004linear,
  title = {{A Linear Programming Formulation for Global Inference in Natural Language Tasks}},
  author = {Roth, Dan and Yih, Wen-tau},
  booktitle = {Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL-2004) at HLT-NAACL 2004},
  year = {2004},
  url = {https://aclanthology.org/W04-2401/}
}
```

- [← previous A Labelled Corpus for Prepositional Phrase Attachment](https://md.research.elamur.ai/free/en/papers/lingbulk-2004-mitchell-labelled-corpus-prepositional-phrase-attachment/)
- [next → A Mention-Synchronous Coreference Resolution Algorithm Based On the Bell Tree](https://md.research.elamur.ai/free/en/papers/luo-2004-mention-synchronous-coreference-resolution-algorithm/)
- [↑ back to papers of 2004](https://md.research.elamur.ai/free/en/papers/2004/)

## References

20 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. S. Abney. 1991. Parsing by chunks. In S. Abney R. Berwick and C. Tenny, editors, Principle-based parsing: Computation and Psycholinguistics, pages 257–278. Kluwer, Dordrecht. [find](https://scholar.google.com/scholar?q=S%2E+Abney%2E+1991%2E+Parsing+by+chunks%2E+In+S%2E+Abney+R%2E+Berwick+and+C%2E+Tenny%2C+editors%2C+Principle%2Dbased+parsing%3A+Computation+and+Psycholinguistics%2C+pages+257%E2%80%93278%2E+Kluwer%2C+Dordrecht%2E)
2. C. Bishop, 1995. Neural Networks for Pattern Recognition, chapter 6.4: Modelling conditional distributions, page 215. Oxford University Press. [find](https://scholar.google.com/scholar?q=C%2E+Bishop%2C+1995%2E+Neural+Networks+for+Pattern+Recognition%2C+chapter+6%2E4%3A+Modelling+conditional+distributions%2C+page+215%2E+Oxford+University+Press%2E)
3. Y. Boykov, O. Veksler, and R. Zabih. 2001. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11):1222–1239, November. [find](https://scholar.google.com/scholar?q=Y%2E+Boykov%2C+O%2E+Veksler%2C+and+R%2E+Zabih%2E+2001%2E+Fast+approximate+energy+minimization+via+graph+cuts%2E+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+23%2811%29%3A1222%E2%80%931239%2C+November%2E)
4. C. Chekuri, S. Khanna, J. Naor, and L. Zosin. 2001. Approximation algorithms for the metric labeling problem via a new linear programming formulation. In Symposium on Discrete Algorithms, pages 109–118. [find](https://scholar.google.com/scholar?q=C%2E+Chekuri%2C+S%2E+Khanna%2C+J%2E+Naor%2C+and+L%2E+Zosin%2E+2001%2E+Approximation+algorithms+for+the+metric+labeling+problem+via+a+new+linear+programming+formulation%2E+In+Symposium+on+Discrete+Algorithms%2C+pages+109%E2%80%9311)
5. CPLEX. 2003. ILOG, Inc. [http://www.ilog.com/products/cplex/](http://www.ilog.com/products/cplex/). [↗](http://www.ilog.com/products/cplex/)
6. T. Dietterich. 2002. Machine learning for sequential data: A review. In Structural, Syntactic, and Statistical Pattern Recognition, pages 15–30. Springer-Verlag. [find](https://scholar.google.com/scholar?q=T%2E+Dietterich%2E+2002%2E+Machine+learning+for+sequential+data%3A+A+review%2E+In+Structural%2C+Syntactic%2C+and+Statistical+Pattern+Recognition%2C+pages+15%E2%80%9330%2E+Springer%2DVerlag%2E)
7. J. Kleinberg and E. Tardos. 1999. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. In IEEE Symposium on Foundations of Computer Science, pages 14–23. [find](https://scholar.google.com/scholar?q=J%2E+Kleinberg+and+E%2E+Tardos%2E+1999%2E+Approximation+algorithms+for+classification+problems+with+pairwise+relationships%3A+Metric+labeling+and+markov+random+fields%2E+In+IEEE+Symposium+on+Foundations+of+Comput)
8. J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. 18th International Conf. on Machine Learning, pages 282– 289. Morgan Kaufmann, San Francisco, CA. [find](https://scholar.google.com/scholar?q=J%2E+Lafferty%2C+A%2E+McCallum%2C+and+F%2E+Pereira%2E+2001%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+In+Proc%2E+18th+International+Conf%2E+on+Machine+Learning%2C+pages+)
9. A. Levin, A. Zomet, and Yair Weiss. 2002. Learning to perceive transparency from the statistics of natural scenes. In NIPS-15; The 2002 Conference on Advances in Neural Information Processing Systems. [find](https://scholar.google.com/scholar?q=A%2E+Levin%2C+A%2E+Zomet%2C+and+Yair+Weiss%2E+2002%2E+Learning+to+perceive+transparency+from+the+statistics+of+natural+scenes%2E+In+NIPS%2D15%3B+The+2002+Conference+on+Advances+in+Neural+Information+Processing+Systems%2E)
10. S. Li. 2001. Markov Random Field Modeling in Image Analisys. Springer-Verlag. [find](https://scholar.google.com/scholar?q=S%2E+Li%2E+2001%2E+Markov+Random+Field+Modeling+in+Image+Analisys%2E+Springer%2DVerlag%2E)
11. V. Punyakanok and D. Roth. 2001. The use of classifiers in sequential inference. In NIPS-13; The 2000 Conference on Advances in Neural Information Processing Systems, pages 995–1001. MIT Press. [find](https://scholar.google.com/scholar?q=V%2E+Punyakanok+and+D%2E+Roth%2E+2001%2E+The+use+of+classifiers+in+sequential+inference%2E+In+NIPS%2D13%3B+The+2000+Conference+on+Advances+in+Neural+Information+Processing+Systems%2C+pages+995%E2%80%931001%2E+MIT+Press%2E)
12. D. Roth and W. Yih. 2002. Probabilistic reasoning for entity & relation recognition. In COLING 2002, The 19th International Conference on Computational Linguistics, pages 835–841. [find](https://scholar.google.com/scholar?q=D%2E+Roth+and+W%2E+Yih%2E+2002%2E+Probabilistic+reasoning+for+entity+%26+relation+recognition%2E+In+COLING+2002%2C+The+19th+International+Conference+on+Computational+Linguistics%2C+pages+835%E2%80%93841%2E)
13. D. Roth. 1998. Learning to resolve natural language ambiguities: A unified approach. In Proc. of AAAI, pages 806–813. [find](https://scholar.google.com/scholar?q=D%2E+Roth%2E+1998%2E+Learning+to+resolve+natural+language+ambiguities%3A+A+unified+approach%2E+In+Proc%2E+of+AAAI%2C+pages+806%E2%80%93813%2E)
14. D. Roth. 2002. Reasoning with classifiers. In Proc. of the European Conference on Machine Learning, pages 506–510. [find](https://scholar.google.com/scholar?q=D%2E+Roth%2E+2002%2E+Reasoning+with+classifiers%2E+In+Proc%2E+of+the+European+Conference+on+Machine+Learning%2C+pages+506%E2%80%93510%2E)
15. A. Schrijver. 1986. Theory of Linear and Integer Programming. Wiley Interscience series in discrete math-matics. John Wiley & Sons, December. [find](https://scholar.google.com/scholar?q=A%2E+Schrijver%2E+1986%2E+Theory+of+Linear+and+Integer+Programming%2E+Wiley+Interscience+series+in+discrete+math%2Dmatics%2E+John+Wiley+%26+Sons%2C+December%2E)
16. B. Taskar, A. Pieter, and D. Koller. 2002. Discriminative probabilistic models for relational data. In Proc. of Uncertainty in Artificial Intelligence, pages 485–492. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+A%2E+Pieter%2C+and+D%2E+Koller%2E+2002%2E+Discriminative+probabilistic+models+for+relational+data%2E+In+Proc%2E+of+Uncertainty+in+Artificial+Intelligence%2C+pages+485%E2%80%93492%2E)
17. E. Tjong Kim Sang and F. De Meulder. 2003. Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition. In Proc. of CoNLL-2003, pages 142–147. Edmonton, Canada. [find](https://scholar.google.com/scholar?q=E%2E+Tjong+Kim+Sang+and+F%2E+De+Meulder%2E+2003%2E+Introduction+to+the+CoNLL%2D2003+shared+task%3A+Language%2Dindependent+named+entity+recognition%2E+In+Proc%2E+of+CoNLL%2D2003%2C+pages+142%E2%80%93147%2E+Edmonton%2C+Canada%2E)
18. X. Wang and A. Regan. 2000. A cutting plane method for integer programming problems with binary variables. Technical Report UCI-ITS-WP-00-12, University of California, Irvine. [find](https://scholar.google.com/scholar?q=X%2E+Wang+and+A%2E+Regan%2E+2000%2E+A+cutting+plane+method+for+integer+programming+problems+with+binary+variables%2E+Technical+Report+UCI%2DITS%2DWP%2D00%2D12%2C+University+of+California%2C+Irvine%2E)
19. L. Wolsey. 1998. Integer Programming. John Wiley & Sons, Inc. [find](https://scholar.google.com/scholar?q=L%2E+Wolsey%2E+1998%2E+Integer+Programming%2E+John+Wiley+%26+Sons%2C+Inc%2E)
20. Xpress-MP. 2003. Dash Optimization. Xpress-MP. [http://www.dashoptimization.com/products.html](http://www.dashoptimization.com/products.html). [↗](http://www.dashoptimization.com/products.html)