Elamur Research
☰
home / papers / 2004 / A Linear Programming Formulation for Global Inference in Natural Language Tasks

A Linear Programming Formulation for Global Inference in Natural Language Tasks

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/W04-2401.pdf

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

Cited by

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

Cite

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

@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/}
}

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
  2. C. Bishop, 1995. Neural Networks for Pattern Recognition, chapter 6.4: Modelling conditional distributions, page 215. Oxford University Press. find
  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
  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
  5. CPLEX. 2003. ILOG, Inc. 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
  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
  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
  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
  10. S. Li. 2001. Markov Random Field Modeling in Image Analisys. Springer-Verlag. find
  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
  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
  13. D. Roth. 1998. Learning to resolve natural language ambiguities: A unified approach. In Proc. of AAAI, pages 806–813. find
  14. D. Roth. 2002. Reasoning with classifiers. In Proc. of the European Conference on Machine Learning, pages 506–510. find
  15. A. Schrijver. 1986. Theory of Linear and Integer Programming. Wiley Interscience series in discrete math-matics. John Wiley & Sons, December. find
  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
  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
  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
  19. L. Wolsey. 1998. Integer Programming. John Wiley & Sons, Inc. find
  20. Xpress-MP. 2003. Dash Optimization. Xpress-MP. http://www.dashoptimization.com/products.html. ↗