Elamur Research⌕
☰
home / papers / 2009 / Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints

Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints

Summary

The paper tackles a practical obstacle to using Zero-One Integer Linear Programming (ILP) for coreference resolution. Global constraints such as transitivity, together with exclusivity rules derived from binding, are needed to make the decisions of a pairwise classifier consistent. However, standard ILP requires every instance of these constraints to be written out in advance, which quickly becomes intractable. The authors adapt the Balas (1965) algorithm so that constraints are handled intensionally, meaning instances are generated only when the search actually needs them. Weights come from a TiMBL memory-based pairwise classifier, converted into classification costs. Experiments on German use the TüBa-D/Z coreference corpus with five-fold cross-validation. The central finding is that the first consistent solution found by the search (Balas-First) is as good as the fully optimized one in F-measure, and even marginally better. This matters because exhaustive NP-complete optimization can be skipped, which often cuts runtime substantially. Global consistency still significantly improves on the raw classifier output, and the Balas weight ordering beats a linear ordering.

Key points

  • Data. TüBa-D/Z is a treebank of 1,100 German newspaper texts and about 25,000 sentences. It contains 13,818 anaphoric, 1,031 cataphoric and 12,752 coreferential relations.
  • Candidate pairs and features. The TiMBL classifier uses features such as distance, POS, grammatical function, head match, salience and semantic class. Candidate pairs are generated only within a 3-sentence sliding window.
  • Why intensional constraints are needed. Writing out transitivity for about 150 noun phrases (roughly 30 sentences) already yields around 1,500,000 equations.
  • Approximating c-command. Exclusivity relies on simple predicates (clause bound, np bound) instead of full syntactic c-command.
  • Ordering results.
    • With all mentions, F rises from 62.83 to 64.27 (+1.44) when Balas ordering replaces linear ordering.
    • With true mentions, F rises from 76.08 to 78.90 (+2.82).
    • Without boundness enforcement constraints, solving takes quadratic time.

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

Topics: Coreference resolution

Cited by

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

Cite

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

@inproceedings{klenner2009optimization,
  title = {{Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints}},
  author = {Klenner, Manfred and Ailloud, Étienne},
  booktitle = {Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009)},
  year = {2009},
  url = {https://aclanthology.org/E09-1051/}
}

References

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

  1. E. Althaus, N. Karamanis, and A. Koller. 2004. Computing locally coherent discourses. In Proc. of the ACL. find
  2. A. Bagga and B. Baldwin. 1998. Algorithms for scoring coreference chains. In Proceedings of the Linguistic Coreference Workshop at The First International Conference on Language Resources and Evaluation (LREC98), pages 563–566. find our card
  3. E. Balas. 1965. An additive algorithm for solving linear programs with zero-one variables. Operations Research, 13(4):517–546. find
  4. J.W. Chinneck. 2004. Practical optimization: a gentle introduction. Electronic document: http://www.sce.carleton.ca/faculty/chinneck/po.html. ↗
  5. W. Daelemans, J. Zavrel, K. van der Sloot, and A. van den Bosch. 2004. TiMBL: Tilburg Memory-Based Learner. find
  6. P. Denis and J. Baldridge. 2007. Joint determination of anaphoricity and coreference resolution using integer programming. Proceedings of NAACL HLT, pages 236–243. find our card
  7. P. Denis and J. Baldridge. 2008. Specialized models and ranking for coreference resolution. In Proceedings of the Empirical Methods in Natural Language Processing (EMNLP 2008), Hawaii, USA. To appear. find our card
  8. J.R. Finkel and C.D. Manning. 2008. Enforcing transitivity in coreference resolution. Association for Computational Linguistics. find our card
  9. E. Hinrichs, K. Filippova, and H. Wunsch. 2005. A data-driven approach to pronominal anaphora resolution in German. In Proc. of RANLP ’05. find
  10. M. Klenner and É. Ailloud. 2008. Enhancing coreference clustering. In C. Johansson, editor, Proc. of the Second Workshop on Anaphora Resolution (WAR II), volume 2 of NEALT Proceedings Series, pages 31–40, Bergen, Norway. find
  11. M. Klenner. 2007. Enforcing consistency on coreference sets. In Recent Advances in Natural Language Processing (RANLP), pages 323–328, September. find
  12. X. Luo, A. Ittycheriah, H. Jing, N. Kambhatla, and S. Roukos. 2004. A mention-synchronous coreference resolution algorithm based on the Bell tree. Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics. find our card
  13. X. Luo. 2005. On coreference resolution performance metrics. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 25–32. Association for Computational Linguistics Morristown, NJ, USA. find our card
  14. T. Marciniak and M. Strube. 2005. Beyond the pipeline: Discrete optimization in NLP. In Proc. of the CoNLL. find
  15. K. Naumann. 2006. Manual for the annotation of indocument referential relations. Electronic document: http://www.sfs.uni-tuebingen.de/de_tuebadz.shtml. ↗
  16. V. Ng and C. Cardie. 2002. Improving machine learning approaches to coreference resolution. In Proc. of the ACL. find our card
  17. C. Nicolae and G. Nicolae. 2006. Best Cut: A graph algorithm for coreference resolution. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 275–283. Association for Computational Linguistics. find
  18. C.H. Papadimitriou and K. Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover Publications. find
  19. S.P. Ponzetto and M. Strube. 2006. Exploiting semantic role labeling, WordNet and Wikipedia for coreference resolution. In Proc. of HLT-NAACL, volume 6, pages 192–199. find our card
  20. V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2004. Semantic role labeling via integer linear programming inference. In Proc. of the COLING. find
  21. S. Riedel and J. Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. of the EMNLP. find
  22. W.M. Soon, H.T. Ng, and D.C.Y. Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521–544. find our card
  23. H. Telljohann, E.W. Hinrichs, S. Kübler, and H. Zinsmeister. 2005. Stylebook for the Tübingen treebank of written German (TüBa-D/Z). Seminar fur Sprachwissenschaft, Universität Tübingen, Tübingen, Germany. find
  24. Y. Versley. 2006. A constraint-based approach to noun phrase coreference resolution in German newspaper text. In Konferenz zur Verarbeitung Natürlicher Sprache (KONVENS). find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/klenner-2009-optimization-coreference-resolution-is-not/