Elamur Research⌕
☰
home / papers / 2014 / Prune-and-Score: Learning for Greedy Coreference Resolution

Prune-and-Score: Learning for Greedy Coreference Resolution

Summary

Most incremental coreference systems rely on one learned scoring function to make every clustering decision. The authors argue this makes learning very hard, because a single function cannot reliably separate the right choice from all the wrong ones. They propose Prune-and-Score, a greedy search method in which mentions are handled left to right. Each mention is either attached to an existing cluster or starts a new one. Every decision uses two learned components. A pruning function first keeps only the top b candidate actions, and a scoring function then picks the best of these survivors. The overall loss splits into a pruning part and a scoring part, so both functions can be trained as ranking problems with standard rank learners. The method was evaluated on OntoNotes 5.0, ACE2004 and MUC6. It consistently beat a scoring-only version of itself and was comparable to or better than strong published systems. The work matters because it shows that learned pruning constraints can make greedy structured prediction easier. The idea could carry over to other search-based NLP tasks.

Key points

  • The search space consists of partial clusterings. At each step, the possible actions are to place the next mention into an existing cluster or to open a NEW cluster. Setting b = ∞ reduces the method to the usual scoring-only incremental approach.
  • On the OntoNotes 5.0 dev set with predicted mentions, the best setting was b = 5, with a CoNLL score of 62.64. The scoring-only setting (b = ∞) reached 59.63. All tested values from 2 to 20 outperformed b = ∞, so b needs little tuning.
  • Test-set comparisons used gold mentions on OntoNotes 5.0, ACE2004 (Culotta split and Newswire) and MUC6. The baselines were HOTCoref, Berkeley (FINAL features), CPL3M, Stanford, Easy-first and Fernandes et al. (2012). Scores were computed with version 7 of the CoNLL scorer.
  • Unlike latent-antecedent mention-pair models, the method uses cluster-level features explicitly. The authors present it as complementary to existing incremental systems, which could adopt the same pruning idea.
  • The rank learners came from the RankLib library. Suggested future directions include Limited Discrepancy Search and applying the approach to dependency parsing and information extraction.

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

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/v1/d14-1225

@inproceedings{ma2014prune,
  title = {{Prune-and-Score: Learning for Greedy Coreference Resolution}},
  author = {Ma, Chao and Doppa, Janardhan Rao and Orr, J. Walker and Mannem, Prashanth and Fern, Xiaoli and Dietterich, Tom and Tadepalli, Prasad},
  booktitle = {Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2014},
  doi = {10.3115/v1/d14-1225},
  url = {https://doi.org/10.3115/v1/d14-1225}
}

References

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

  1. Amit Bagga and Breck Baldwin. 1998. Algorithms for scoring coreference chains. In In The First International Conference on Language Resources and Evaluation Workshop on Linguistics Coreference, pages 563–566. find our card
  2. Eric Bengtson and Dan Roth. 2008. Understanding the value of features for coreference resolution. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP), pages 294–303. find our card
  3. Anders Björkelund and Jonas Kuhn. 2014. Learning structured perceptrons for coreference resolution with latent antecedents and non-local features. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 47–57, Baltimore, Maryland, Ju… find our card
  4. Christopher Burges. 2010. From RankNet to LambdaRank to LambdaMART: An overview. Microsoft Technical Report, (MSR-TR-2010). find
  5. Kai-Wei Chang, Rajhans Samdani, Alla Rozovskaya, Mark Sammons, and Dan Roth. 2012. Illinois-Coref: The UI system in the CoNLL-2012 shared task. In Joint Conference on EMNLP and CoNLL - Shared Task, pages 113–117, Jeju Island, Korea, July. Association for Computational Linguistics. find
  6. Kai-Wei Chang, Rajhans Samdani, and Dan Roth. 2013. A constrained latent variable model for coreference resolution. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP), pages 601–612. find our card
  7. Sheng Chen, Alan Fern, and Sinisa Todorovic. 2014. Multi-object tracking via constrained sequential labeling. In To appear in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR). find
  8. William W. Cohen and Vitor Rocha de Carvalho. 2005. Stacked sequential learning. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), pages 671–676. find
  9. Michael Collins. 2000. Discriminative reranking for natural language parsing. In Proceedings of International Conference on Machine Learning (ICML), pages 175–182. find our card
  10. Aron Culotta, Michael L. Wick, and Andrew Mc-Callum. 2007. First-order probabilistic models for coreference resolution. In Proceedings of Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics (HLT-NAACL), pages 81–88. find our card
  11. Hal Daumé III. 2006. Practical Structured Learning Techniques for Natural Language Processing. Ph.D. thesis, University of Southern California, Los Angeles, CA. find
  12. Pascal Denis and Jason Baldridge. 2008. Specialized models and ranking for coreference resolution. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP), pages 660–669. find our card
  13. Janardhan Rao Doppa, Alan Fern, and Prasad Tadepalli. 2014a. HC-Search: A learning framework for search-based structured prediction. Journal of Artificial Intelligence Research (JAIR), 50:369–407. find
  14. Janardhan Rao Doppa, Alan Fern, and Prasad Tadepalli. 2014b. Structured prediction via output space search. Journal of Machine Learning Research (JMLR), 15:1317–1350. find
  15. Janardhan Rao Doppa, Jun Yu, Chao Ma, Alan Fern, and Prasad Tadepalli. 2014c. HC-Search for multi-label prediction: An empirical study. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI). find
  16. Greg Durrett and Dan Klein. 2013. Easy victories and uphill battles in coreference resolution. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1971– 1982. find our card
  17. Greg Durrett, David Leo Wright Hall, and Dan Klein. 2013. Decentralized entity-level modeling for coreference resolution. In Proceedings of Association of Computational Linguistics (ACL) Conference, pages 114–124. find our card
  18. Pedro F. Felzenszwalb and David A. McAllester. 2007. The generalized A* architecture. Journal of Artificial Intelligence Research (JAIR), 29:153–190. find
  19. Eraldo Rezende Fernandes, Cı́cero Nogueira dos Santos, and Ruy Luiz Milidiú. 2012. Latent structure perceptron with feature induction for unrestricted coreference resolution. International Conference on Computational Natural Language Learning (CoNL-L), pages 41–48. find our card
  20. Thomas Finley and Thorsten Joachims. 2005. Supervised clustering with support vector machines. In Proceedings of International Conference on Machine Learning (ICML), pages 217–224. find
  21. Yoav Goldberg and Joakim Nivre. 2013. Training deterministic parsers with non-deterministic oracles. Transactions of the Association for Computational Linguistics, 1:403–414. find
  22. Aria Haghighi and Dan Klein. 2010. Coreference resolution in a modular, entity-centered model. In Proceedings of Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics (HLT-NAACL). find our card
  23. Hannaneh Hajishirzi, Leila Zilles, Daniel S. Weld, and Luke S. Zettlemoyer. 2013. Joint coreference resolution and named-entity linking with multi-pass sieves. In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 289–299. find our card
  24. Hal Daumé III, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. Machine Learning Journal (MLJ), 75(3):297–325. find
  25. Hal Daumé III and Daniel Marcu. 2005. Learning as search optimization: Approximate large margin methods for structured prediction. In ICML. find
  26. Roni Khardon. 1999. Learning to take actions. Machine Learning Journal (MLJ), 35(1):57–90. find
  27. Michael Lam, Janardhan Rao Doppa, Xu Hu, Sinisa Todorovic, Thomas Dietterich, Abigail Reft, and Marymegan Daly. 2013. Learning to detect basal tubules of nematocysts in sem images. In ICCV Workshop on Computer Vision for Accelerated Biosciences (CVAB). IEEE. find
  28. Heeyoung Lee, Angel X. Chang, Yves Peirsman, Nathanael Chambers, Mihai Surdeanu, and Dan Jurafsky. 2013. Deterministic coreference resolution based on entity-centric, precision-ranked rules. Computational Linguistics, 39(4):885–916. find our card
  29. Qi Li, Heng Ji, and Liang Huang. 2013. Joint event extraction via structured prediction with global features. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (A-CL), pages 73–82. find
  30. Tie-Yan Liu. 2009. Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 3(3):225–331. find
  31. Xiaoqiang Luo. 2005. On coreference resolution performance metrics. In Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, HLT ’05, pages 25–32, Stroudsburg, PA, USA. Association for Computational Linguistics. find our card
  32. Andrew Mccallum and Ben Wellner. 2003. Toward conditional models of identity uncertainty with application to proper noun coreference. In Proceedings of Neural Information Processing Systems (NIPS), pages 905–912. MIT Press. find
  33. MUC6. 1995. Coreference task definition. In Proceedings of the Sixth Message Understanding Conference (MUC-6), pages 335–344. find
  34. Vincent Ng and Claire Cardie. 2002. Improving machine learning approaches to coreference resolution. In Proceedings of Association of Computational Linguistics (ACL) Conference, pages 104–111. find our card
  35. NIST. 2004. The ACE evaluation plan. find
  36. Joakim Nivre, Johan Hall, Jens Nilsson, Atanas Chanev, Gülsen Eryigit, Sandra Kübler, Svetoslav Marinov, and Erwin Marsi. 2007. Maltparser: A language-independent system for data-driven dependency parsing. Natural Language Engineering, 13(2):95–135. find
  37. Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang. 2012. Conll-2012 shared task: Modeling multilingual unrestricted coreference in ontonotes. In Proceedings of the Joint Conference on EMNLP and CoNLL: Shared Task, pages 1–40. find our card
  38. Altaf Rahman and Vincent Ng. 2011a. Coreference resolution with world knowledge. In Proceedings of Association of Computational Linguistics (ACL) Conference, pages 814–824. find our card
  39. Altaf Rahman and Vincent Ng. 2011b. Narrowing the modeling gap: A cluster-ranking approach to coreference resolution. Journal of Artificial Intelligence Research (JAIR), 40:469–521. find
  40. Lev-Arie Ratinov and Dan Roth. 2012. Learning-based multi-sieve co-reference resolution with knowledge. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP) Conference, pages 1234–1244. find our card
  41. Stéphane Ross, Geoffrey J. Gordon, and Drew Bagnell. 2011. A reduction of imitation learning and structured prediction to no-regret online learning. Journal of Machine Learning Research - Proceedings Track, 15:627–635. find
  42. Wee Meng Soon, Daniel Chung, Daniel Chung Yong Lim, Yong Lim, and Hwee Tou Ng. 2001. A machine learning approach to coreference resolution of noun phrases. find our card
  43. Veselin Stoyanov and Jason Eisner. 2012. Easy-first coreference resolution. In Proceedings of International Conference on Computational Linguistics (COLING), pages 2519–2534. find our card
  44. Veselin Stoyanov, Claire Cardie, Nathan Gilbert, Ellen Riloff, David Buttler, and David Hysom. 2010. Coreference resolution with reconcile. In Proceedings of Association of Computational Linguistics (A-CL) Conference, pages 156–161. find our card
  45. Marc B. Vilain, John D. Burger, John S. Aberdeen, Dennis Connolly, and Lynette Hirschman. 1995. A model-theoretic coreference scoring scheme. In MUC, pages 45–52. find our card
  46. David Weiss and Benjamin Taskar. 2010. Structured prediction cascades. Journal of Machine Learning Research - Proceedings Track, 9:916–923. find
  47. Michael L. Wick, Khashayar Rohanimanesh, Kedar Bellare, Aron Culotta, and Andrew McCallum. 2011. SampleRank: Training factor graphs with atomic gradients. In Proceedings of International Conference on Machine Learning (ICML). find
  48. Michael L. Wick, Sameer Singh, and Andrew McCallum. 2012. A discriminative hierarchical model for fast coreference at large scale. In Proceedings of Association of Computational Linguistics (ACL) Conference, pages 379–388. find our card
  49. Yuehua Xu, Alan Fern, and Sung Wook Yoon. 2009. Learning linear ranking functions for beam search with application to planning. Journal of Machine Learning Research (JMLR), 10:1571–1610. find
  50. Chun-Nam John Yu and Thorsten Joachims. 2009. Learning structural SVMs with latent variables. In Proceedings of International Conference on Machine Learning (ICML). find
  51. Jiaping Zheng, Luke Vilnis, Sameer Singh, Jinho D. Choi, and Andrew McCallum. 2013. Dynamic knowledge-base alignment for coreference resolution. In Conference on Computational Natural Language Learning (CoNLL). find our card

↑ back to top

This page in Markdown →