Elamur Research⌕
☰
home / papers / 2010 / End-to-End Coreference Resolution via Hypergraph Partitioning

End-to-End Coreference Resolution via Hypergraph Partitioning

Summary

Cai and Strube address coreference resolution, the task of grouping entity mentions so that each group refers to one entity. Most earlier systems use two stages: a pairwise classifier, then a separate clustering step. The authors argue that this loses global information. Their system, COPA (Coreference Partitioner), instead makes a single global decision. Each document becomes a hypergraph whose vertices are mentions and whose hyperedges are relational features linking two or more mentions. Training is used only to estimate hyperedge weights, which are the fraction of feature instances that are truly coreferent. Resolution then recursively bi-partitions the hypergraph with spectral clustering under the Normalized Cut criterion. A tuned threshold decides when to stop splitting, and a degree heuristic removes singletons.

The system runs end-to-end with an automatic ACE mention tagger and is evaluated only on system mentions, which the authors consider the realistic setting. Using the same feature set, COPA outperforms reimplemented versions of two earlier systems, Bengtson & Roth (2008) and Soon et al. (2001), chiefly through better recall. This shows that one-step global partitioning is a workable alternative to classify-then-cluster pipelines.

Key points

  • Data and baselines: Evaluation covers MUC7, ACE 2003 and ACE 2004 using system mentions only. Metrics are MUC, B³sys and CEAFsys. Most gains over the SOON baseline are statistically significant.
  • Comparison with B&R (B³sys F):
    • On ACE 2003, COPA scores 77.5 against 71.4 for B&R.
    • On ACE 2004, COPA scores 75.6 against 74.8 for B&R.
    • COPA trades some precision for higher recall.
  • Learned weights: Hyperedge weights come from simple training statistics. Examples on ACE 2004 are Alias 0.702 and StrMatch_Pron 0.568.
  • Partitioning method:
    • The partitioner follows Agarwal et al. (2005) and uses the symmetric Laplacian.
    • Eigensolving costs O(n³) in the number of mentions, which is manageable for a few hundred mentions per document.
    • Flat-K partitioning was also tried but performed worse.
  • Speed and future work: Preprocessing, training and partitioning ACE 2004 takes about 15 minutes on 2 Opteron CPUs with 8 GB RAM. Planned future work includes constrained clustering and better handling of positional 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

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

Cite

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

@inproceedings{cai2010end,
  title = {{End-to-End Coreference Resolution via Hypergraph Partitioning}},
  author = {Cai, Jie and Strube, Michael},
  booktitle = {Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010)},
  year = {2010},
  url = {https://aclanthology.org/C10-1017/}
}

References

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

  1. Agarwal, Sameer, Jonwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David Kriegman & Serge Belongie (2005). Beyond pairwise clustering. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), Vol. 2, pp. 838–845. find
  2. Bagga, Amit & Breck Baldwin (1998). Algorithms for scoring coreference chains. In Proceedings of the 1st International Conference on Language Resources and Evaluation, Granada, Spain, 28–30 May 1998, pp. 563–566. find our card
  3. Basu, Sugato, Ian Davidson & Kiri L. Wagstaff (Eds.) (2009). Constrained Clustering: Advances in Algorithms, Theory, and Applications. Boca Raton, Flo.: CRC Press. find
  4. Bengtson, Eric & Dan Roth (2008). Understanding the value of features for coreference resolution. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25-27 October 2008, pp. 294–303. find our card
  5. Bhattacharya, Indrajit & Lise Getoor (2009). Collective relational clustering. In S. Basu, I. Davidson & K. Wagstaff (Eds.), Constrained Clustering: Advances in Algorithms, Theory, and Applications, pp. 221–244. Boca Raton, Flo.: CRC Press. find
  6. Cai, Jie & Michael Strube (2010). Evaluation metrics for end-to-end coreference resolution systems. In Proceedings of the SIGdial 2010 Conference: The 11th Annual Meeting of the Special Interest Group on Discourse and Dialogue, Tokyo, Japan, 24–25 September 2010. To appear. find our card
  7. Chinchor, Nancy (2001). Message Understanding Conference (MUC) 7. LDC2001T02, Philadelphia, Penn: Linguistic Data Consortium. find
  8. Chinchor, Nancy & Beth Sundheim (2003). Message Understanding Conference (MUC) 6. LDC2003T13, Philadelphia, Penn: Linguistic Data Consortium. find
  9. Culotta, Aron, Michael Wick & Andrew McCallum (2007). First-order probabilistic models for coreference resolution. In Proceedings of Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics, Rochester, N.Y., 22–27 April 2007, pp.… find our card
  10. Daumé III, Hal & Daniel Marcu (2005). A large-scale exploration of effective global features for a joint entity detection and tracking model. In Proceedings of the Human Language Technology Conference and the 2005 Conference on Empirical Methods in Natural Language Processing, Vancouver, B.C., Cana… find
  11. Denis, Pascal & Jason Baldridge (2009). Global joint models for coreference resolution and named entity classification. Procesamiento del Lenguaje Natural, 42:87–96. find
  12. Klenner, Manfred (2007). Enforcing consistency on coreference sets. In Proceedings of the International Conference on Recent Advances in Natural Language Processing, Borovets, Bulgaria, 27–29 September 2007, pp. 323– 328. find
  13. Luo, Xiaoqiang (2005). On coreference resolution performance metrics. In Proceedings of the Human Language Technology Conference and the 2005 Conference on Empirical Methods in Natural Language Processing, Vancouver, B.C., Canada, 6–8 October 2005, pp. 25–32. find our card
  14. Luo, Xiaoqiang, Abe Ittycheriah, Hongyan Jing, Nanda Kambhatla & Salim Roukos (2004). A mention-synchronous coreference resolution algorithm based on the Bell Tree. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, 21–26 July 2004, pp. 136–… find our card
  15. Mitchell, Alexis, Stephanie Strassel, Shudong Huang & Ramez Zakhary (2004). find
  16. ACE 2004 Multilingual Training Corpus. LDC2005T09, Philadelphia, Penn.: Linguistic Data Consortium. find
  17. Mitchell, Alexis, Stephanie Strassel, Mark Przybocki, JK Davis, George Doddington, Ralph Grishman, Adam Meyers, Ada Brunstain, Lisa Ferro & Beth Sundheim (2003). TIDES Extraction (ACE) 2003 Multilingual Training Data. LDC2004T09, Philadelphia, Penn.: Linguistic Data Consortium. find
  18. Ng, Vincent (2008). Unsupervised models for coreference resolution. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25-27 October 2008, pp. 640– 649. find our card
  19. Ng, Vincent & Claire Cardie (2002). Improving machine learning approaches to coreference resolution. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, Philadelphia, Penn., 7–12 July 2002, pp. 104–111. find our card
  20. Nicolae, Cristina & Gabriel Nicolae (2006). BestCut: A graph algorithm for coreference resolution. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, Sydney, Australia, 22–23 July 2006, pp. 275–283. find our card
  21. Rahman, Altaf & Vincent Ng (2009). Supervised models for coreference resolution. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, Singapore, 6-7 August 2009, pp. 968–977. find our card
  22. Shi, Jianbo & Jitendra Malik (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905. find
  23. Soon, Wee Meng, Hwee Tou Ng & Daniel Chung Yong Lim (2001). A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521–544. find our card
  24. Stoyanov, Veselin, Nathan Gilbert, Claire Cardie & Ellen Riloff (2009). Conundrums in noun phrase coreference resolution: Making sense of the state-of-the-art. In Proceedings of the Joint Conference of the 47th Annual Meeting of the Association for Computational Linguistics and the 4th International… find our card
  25. Versley, Yannick, Simone Paolo Ponzetto, Massimo Poesio, Vladimir Eidelman, Alan Jern, Jason Smith, Xiaofeng Yang & Alessandro Moschitti (2008). BART: A modular toolkit for coreference resolution. In Companion Volume to the Proceedings of the 46th Annual Meeting of the Association for Computational… find our card
  26. Vilain, Marc, John Burger, John Aberdeen, Dennis Connolly & Lynette Hirschman (1995). A model-theoretic coreference scoring scheme. In Proceedings of the 6th Message Understanding Conference (MUC-6), pp. 45–52. find our card
  27. San Mateo, Cal.: Morgan Kaufmann. von Luxburg, Ulrike (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416. find
  28. Yang, Xiaofeng, Jian Su & Chew Lim Tan (2008). A twin-candidate model for learning-based anaphora resolution. Computational Linguistics, 34(3):327–356. find our card

↑ back to top

This page in Markdown →