Elamur Research⌕
☰
home / papers / 2006 / BESTCUT: A Graph Algorithm for Coreference Resolution

BESTCUT: A Graph Algorithm for Coreference Resolution

Summary

The paper tackles coreference resolution, the task of grouping textual mentions that point to the same real-world entity. It focuses on the clustering step that follows pairwise classification. Earlier methods such as link-first, link-best and Bell-tree search make greedy or partial decisions and mostly look only backward in the text.

The authors build one undirected weighted graph per entity type. Nodes are mentions, and edge weights are coreference confidences from a maximum entropy classifier based on the Luo et al. (2004) feature set plus seven new features. Their algorithm, BESTCUT, adapts the Stoer–Wagner Min-Cut procedure in two ways. First, cuts are scored by how many mentions end up better connected to their own side. Second, an SVM model decides when to stop splitting. The process works top-down, from one big cluster to separate entities, so it treats anaphora and cataphora alike.

The pipeline also includes a mention detector that draws on word senses of common nouns. On MUC and ACE data, BESTCUT matches or beats reimplementations of Ng & Cardie (2002) and Luo et al. (2004). This suggests that globally informed graph partitioning is a strong option for coreference clustering.

Key points

  • Separate graphs are built for PERSON, ORGANIZATION, LOCATION, FACILITY and GPE, since mentions of different types never corefer.
  • The cut score averages two checks per mention, one based on average and one on maximum edge weight to its own side versus the other side. The stop-cut SVM was trained with 10-fold cross-validation and tuned for ECM-F.
  • The seven added features are head-match, type-pair, name-alias, same-governing-category, path, coll-comm and gn-agree.
  • On MUC 6 with key mentions, the new features raise ECM-F from 78.3% to 85.1% and MUC F from 90.49% to 92.55%. Lexical features help most, and gn-agree adds very little.
  • The authors report state-of-the-art results on the ACE Phase 2 corpus for both true and detected mentions. Using their mention detector gives better results than having no mention information.

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

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

Cite

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

@inproceedings{nicolae2006bestcut,
  title = {{BESTCUT: A Graph Algorithm for Coreference Resolution}},
  author = {Nicolae, Cristina and Nicolae, Gabriel},
  booktitle = {Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing},
  year = {2006},
  url = {https://aclanthology.org/W06-1633/}
}

References

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

  1. B. Baldwin, T. Morton, A. Bagga, J. Baldridge, R. Chandraseker, A. Dimitriadis, K. Snyder, and M. Wolska. 1998. Description of the university of pennsylvania camp system as used for coreference. In Proceedings of the 7th Message Understanding Conference (MUC-7). find
  2. A. L. Berger, S. A. D. Pietra, and V. J. D. Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 1(22):39– 71. find our card
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2001. Introduction to Algorithms, Second Edition. MIT. find
  4. C. Cortes and V. Vapnik. 1995. Support-vector networks. Machine Learning, 20(3):273–297. find
  5. H. DaumeIII and D. Marcu. 2005a. A large-scale exploration of effective global features for a joint entity detection and tracking model. pages 97–104, Vancouver. find
  6. H. DaumeIII and D. Marcu. 2005b. Learning as search optimization: Approximate large margin methods for structured prediction. In The International Conference on Machine Learning (ICML). find
  7. C. Fellbaum, editor. 1998. WordNet: An Electronic Lexical Database and Some of its Applications. MIT Press. find
  8. X. Luo, A. Ittycheriah, H. Jing, N. Kambhatla, and S. Roukos. 2004. A mention-synchronous coreference resolution algorithm based on the bell tree. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics, Barcelona, Spain. find our card
  9. R. Mihalcea and A. Csomai. 2005. Senselearner: Word sense disambiguation for all words in unrestricted text. In Proceedings of the 43rd Meeting of the Association for Computational Linguistics, Ann Arbor, MI. find
  10. MUC-6. 1995. Coreference task definition. find
  11. V. Ng and C. Cardie. 2002. Improving machine learning approaches to coreference resolution. In Proceedings of the 4Oth Meeting of the Association for Computational Linguistics, Philadelphia, Pennsylvania. find our card
  12. V. Ng. 2004. Learning noun phrase anaphoricity to improve conference resolution: Issues in representation and optimization. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics, Barcelona, Spain. find our card
  13. V. Ng. 2005. Machine learning for coreference resolution: From local classification to global ranking. In Proceedings of the 43rd Meeting of the Association for Computational Linguistics, pages 157–164, Ann Arbor, MI. find our card
  14. NIST. 2003. Entity detection and tracking - phase 1; edt and metonymy annotation guidelines. version 2.5.1 20030502. find
  15. M. Pasca and S. Harabagiu. 2001. High performance question/answering. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 366–374, New Orleans, LA. find
  16. W. M. Soon, H. T. Ng, and D. C. Y. Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 4(27):521–544. find our card
  17. M. Stoer and F. Wagner. 1994. A simple min cut algorithm. In Jan van Leeuwen, editor, Proceedings of the 1994 European Symposium on Algorithms, pages 141–147, New York. Springer-Verlag. find
  18. M. Vilain, J.Burger, J. Aberdeen, D. Connolly, and L. Hirschman. 1995. A model-theoretic coreference scoring scheme. In Proceedings of the Sixth Message Understanding Conference (MUC-6), pages 45–52. find our card

↑ back to top

This page in Markdown →