Elamur Research⌕
☰
home / papers / 2012 / Easy-first Coreference Resolution

Easy-first Coreference Resolution

Summary

Stoyanov and Eisner tackle within-document noun phrase coreference resolution. They target a weakness of the dominant mention-pair approach: because it judges mentions only two at a time, it often yields incoherent clusters, such as chains that mix male and female referents. Their starting point is the multi-pass sieve system of Raghunathan et al. (2010), which links confident cases first. They keep that "easy-first" idea but replace hand-crafted rules with learned weights.

The system performs greedy agglomerative clustering. At each step it scores every possible merge of two existing clusters, plus a special stop action, with a linear model, then executes the best-scoring one. Features describe whole partial clusters, so earlier merges inform later, harder ones such as pronoun links. Training follows Goldberg and Elhadad's easy-first parser and uses perceptron-style updates during clustering, so the learner sees partial states like those met at test time.

On ACE data the method beats a strong pairwise baseline in most settings and also outperforms Raghunathan et al. This shows that learned greedy search can enforce global consistency cheaply.

Key points

  • Clustering is framed as an agent choosing between JOIN i j (merge two chains) and HALT. A priority queue holds the candidate actions, O(n²) of them for n clusters.
  • Weights come from structured-perceptron-style training applied during greedy inference, so they are tuned to the actual test-time search procedure.
  • The system beats a competitive pairwise-classifier baseline in 9 of 10 evaluation settings, which cover MUC and BCubed scores across corpora.
  • It outperforms the sieve system of Raghunathan et al. (2010) by more than 2 points in all 4 directly comparable settings.
  • The authors claim new state-of-the-art results with gold-standard mentions and for end-to-end systems on three ACE corpora. Qualitative examples from ACE04 and ACE05 show that the model avoids clusters with conflicting names or genders.

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

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

Cite

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

@inproceedings{stoyanov2012easy,
  title = {{Easy-first Coreference Resolution}},
  author = {Stoyanov, Veselin and Eisner, Jason},
  booktitle = {Proceedings of COLING 2012},
  year = {2012},
  url = {https://aclanthology.org/C12-1154/}
}

References

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

  1. Bagga, A. and Baldwin, B. (1998). Algorithms for scoring coreference chains. In Linguistic Coreference Workshop at LREC 1998. find our card
  2. Bengtson, E. and Roth, D. (2008). Understanding the value of features for coreference resolution. In Proceedings of EMNLP, pages 294–303. find our card
  3. Bergsma, S. and Lin, D. (2006). Bootstrapping path-based pronoun resolution. In Proc. of ACL. find our card
  4. Collins, M. and Roark, B. (2004). Incremental parsing with the perceptron algorithm. In Proceedings of ACL. find our card
  5. Culotta, A., Wick, M., Hall, R., and McCallum, A. (2007). First-order probabilistic models for coreference resolution. In Proceedings of HLT/NAACL, pages 81–88. find our card
  6. Daumé, H., Langford, J., and Marcu, D. (2009). Search-based structured prediction. Machine learning, 75(3):297–325. find
  7. Daumé III, H. and Marcu, D. (2005). Learning as search optimization: Approximate large margin methods for structured prediction. In Proceedings of ICML, pages 169–176. find
  8. Freund, Y. and Schapire, R. (1999). Large margin classification using the perceptron algorithm. Machine learning, 37(3):277–296. find
  9. Goldberg, Y. and Elhadad, M. (2010). An efficient algorithm for easy-first non-directional dependency parsing. In Proceedings of NAACL, pages 742–750. Association for Computational Linguistics. find
  10. Haghighi, A. and Klein, D. (2010). Coreference resolution in a modular, entity-centered model. In Proceedings of NAACL, pages 385–393. find our card
  11. Hasler, L., Orăsan, C., and Naumann, K. (2006). NPs for events: Experiments in coreference annotation. In Proceedings of LREC2006. find our card
  12. Huang, L., Fayong, S., and Guo, Y. (2012). Structured perceptron with inexact search. In Proceedings of NAACL. find our card
  13. Jain, V., Turaga, S., Briggman, K., Helmstaedter, M., Denk, W., and Seung, H. (2011). Learning to agglomerate superpixel hierarchies. In Proceedings of NIPS. find
  14. Kruskal, J. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48–50. find
  15. MUC-6 (1995). Coreference task definition. In Proceedings of the Sixth Message Understanding Conference (MUC-6), pages 335–344. find
  16. MUC-7 (1997). Coreference task definition. In Proceedings of the Seventh Message Understanding Conference (MUC-7). find
  17. Ng, V. and Cardie, C. (2002). Improving machine learning approaches to coreference resolution. In Proceedings of ACL, pages 104–111. find our card
  18. NIST (2004). The ACE Evaluation Plan. National Institute of Standards and Technology, United States of America. find
  19. Poon, H. and Domingos, P. (2008). Joint unsupervised coreference resolution with Markov logic. In Proceedings of EMNLP, pages 650–659. find our card
  20. Pradhan, S., Ramshaw, L., Marcus, M., Palmer, M., Weischedel, R., and Xue, N. (2011). Conll-2011 shared task: Modeling unrestricted coreference in ontonotes. In Proceedings of CoNLL 2011, pages 1–27. find our card
  21. Raghunathan, K., Lee, H., Rangarajan, S., Chambers, N., Surdeanu, M., Jurafsky, D., and Manning, C. (2010). A multi-pass sieve for coreference resolution. In Proceedings of EMNLP, pages 492–501. find our card
  22. Ross, S., Gordon, G. J., and Bagnell, J. A. (2011). A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of AISTATS. find
  23. Soon, W., Ng, H., and Lim, D. (2001). A machine learning approach to coreference resolution of noun phrases. Computational linguistics, 27(4):521–544. find our card
  24. Stoyanov, V., Cardie, C., Gilbert, N., Riloff, E., Buttler, D., and Hysom, D. (2010a). Coreference resolution with Reconcile. In Proceedings of the ACL Short Papers, pages 156–161. find our card
  25. Stoyanov, V., Cardie, C., Gilbert, N., Riloff, E., Buttler, D., and Hysom, D. (2010b). Reconcile: A coreference resolution research platform. Technical report, Cornell University. find
  26. Stoyanov, V. and Eisner, J. (2012). Minimum-risk training of approximate CRF-based NLP systems. In Proceedings of NAACL. find
  27. Stoyanov, V., Gilbert, N., Cardie, C., and Riloff, E. (2009). Conundrums in noun phrase coreference resolution: Making sense of the state-of-the-art. In Proceedings of ACL/IJCNLP, pages 656–664. find our card
  28. Stoyanov, V., Ropson, A., and Eisner, J. (2011). Empirical risk minimization of graphical model parameters given approximate inference, decoding, and model structure. In Proceedings of AISTATS. find
  29. Sutton, R., McAllester, D., Singh, S., and Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. NIPS. find
  30. Vilain, M., Burger, J., Aberdeen, J., Connolly, D., and Hirschman, L. (1995). A model-theoretic coreference scoring theme. In Proceedings of the Sixth Message Understanding Conference (MUC-6). find
  31. Watkins, C. and Dayan, P. (1992). Q-learning. Machine Learning, 8(3):279–292. find
  32. Yang, X., Zhou, G., Su, J., and Tan, C. (2003). Coreference resolution using competition learning approach. In Proceedings of ACL, pages 176–183. find our card
  33. Zhou, G. and Su, J. (2004). A high-performance coreference resolution system using a constraint-based multi-agent strategy. In Proceedings of COLING. find our card

↑ back to top

This page in Markdown →