Elamur Research⌕
☰
home / papers / 2014 / Learning Structured Perceptrons for Coreference Resolution with Latent Antecedents and Non-local Features

Learning Structured Perceptrons for Coreference Resolution with Latent Antecedents and Non-local Features

Summary

Björkelund and Kuhn ask how to train a structured perceptron for coreference resolution when the model uses non-local features. Such features break exact decoding, so the system must rely on beam search. A further difficulty is that gold data marks only mention clusters, not antecedent links. The authors therefore induce latent antecedent trees, following Fernandes et al. (2012), and train them with a passive-aggressive perceptron.

They found that the usual remedies for inexact search perform worse than a greedy baseline that uses only local features. Early updates stop processing documents too soon. LaSO interferes with how latent antecedents are selected. Their proposed fix is a LaSO variant that collects updates and applies them only once a whole document has been decoded. With local features only, this variant reduces to standard exact-search perceptron learning. Adding non-local features on top of it yields clear gains.

Evaluated on the Arabic, Chinese, and English portions of the CoNLL 2012 Shared Task, the system outperformed every result published up to that point. The work matters because it shows how to combine latent structure learning with richer entity-level information.

Key points

  • The learning algorithm is a passive-aggressive variant of the structured perceptron, using a hash kernel and averaging.
  • The loss assigns 1.5 to wrong root attachments and Hamming loss to all other arcs.
  • A left-to-right best-first decoder gives the same optimal tree as the Chu-Liu-Edmonds algorithm, because every arc points rightward.
  • CoNLL average scores on the test sets:
    • Arabic: 48.72, versus 45.18 for Fernandes.
    • Chinese: 60.06, versus 57.63 for C&N.
    • English: 61.63, versus 61.40 for the Berkeley system (D&K) and 60.65 for Fernandes.
  • Most metric gains over the strongest competitor are significant at p < 0.05 (Wilcoxon test). The system is available from IMS Stuttgart.

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

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

Cite

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

@inproceedings{bjorkelund2014learning,
  title = {{Learning Structured Perceptrons for Coreference Resolution with Latent Antecedents and Non-local Features}},
  author = {Björkelund, Anders and Kuhn, Jonas},
  booktitle = {Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2014},
  doi = {10.3115/v1/p14-1005},
  url = {https://doi.org/10.3115/v1/p14-1005}
}

References

40 references, 27 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. Regina Barzilay and Mirella Lapata. 2008. Modeling local coherence: An entity-based approach. Computational Linguistics, 34(1):1–34. find our card
  3. Eric Bengtson and Dan Roth. 2008. Understanding the value of features for coreference resolution. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 294–303, Honolulu, Hawaii, October. Association for Computational Linguistics. find our card
  4. Shane Bergsma and Dekang Lin. 2006. Bootstrapping path-based pronoun resolution. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 33–40, Sydney, Australia, July. Association for Computatio… find our card
  5. Anders Björkelund and Richárd Farkas. 2012. Data-driven multilingual coreference resolution using resolver stacking. In Joint Conference on EMNLP and CoNLL - Shared Task, pages 49–55, Jeju Island, Korea, July. Association for Computational Linguistics. find our card
  6. Bernd Bohnet, Simon Mille, Benoı̂t Favre, and Leo Wanner. 2011. \<stumaba \>: From deep representation to surface. In Proceedings of the Generation Challenges Session at the 13th European Workshop on Natural Language Generation, pages 232–235, Nancy, France, September. Association for Computational Li… find
  7. Bernd Bohnet. 2010. Top accuracy and fast dependency parsing is not a contradiction. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 89–97, Beijing, China, August. find our card
  8. 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
  9. Kai-Wei Chang, Rajhans Samdani, and Dan Roth. 2013. A constrained latent variable model for coreference resolution. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 601–612, Seattle, Washington, USA, October. Association for Computational Linguistics. find our card
  10. Chen Chen and Vincent Ng. 2012. Combining the best of two worlds: A hybrid approach to multilingual coreference resolution. In Joint Conference on EMNLP and CoNLL - Shared Task, pages 56–63, Jeju Island, Korea, July. Association for Computational Linguistics. find our card
  11. Yoeng-jin Chu and Tseng-hong Liu. 1965. On the shortest aborescence of a directed graph. Science Sinica, 14:1396–1400. find
  12. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), Main Volume, pages 111–118, Barcelona, Spain, July. find our card
  13. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, pages 1–8. Association for Computational Linguistics, July. find our card
  14. Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. 2006. Online passive–aggressive algorithms. Journal of Machine Learning Reseach, 7:551–585, March. find
  15. Aron Culotta, Michael Wick, and Andrew McCallum. 2007. First-order probabilistic models for coreference resolution. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 81–88, Roc… find our card
  16. Hal Daumé III and Daniel Marcu. 2005a. A large-scale exploration of effective global features for a joint entity detection and tracking model. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 97–104, Vancouver, British… find
  17. Hal Daumé III and Daniel Marcu. 2005b. Learning as search optimization: approximate large margin methods for structured prediction. In ICML, pages 169–176. find
  18. Hal Daumé III, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. Machine Learning, 75(3):297–325. find
  19. Pascal Denis and Jason Baldridge. 2009. Global Joint Models for Coreference Resolution and Named Entity Classification. In Procesamiento del Lenguaje Natural 42, pages 87–96, Barcelona: SEPLN. find
  20. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 12:2121–2159, July. find
  21. Greg Durrett and Dan Klein. 2013. Easy victories and uphill battles in coreference resolution. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1971–1982, Seattle, Washington, USA, October. Association for Computational Linguistics. find our card
  22. Jack Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71(B):233–240. find
  23. Eraldo Fernandes, Cı́cero dos Santos, and Ruy Milidiú. 2012. Latent structure perceptron with feature induction for unrestricted coreference resolution. In Joint Conference on EMNLP and CoNLL - Shared Task, pages 41–48, Jeju Island, Korea, July. Association for Computational Linguistics. find our card
  24. Liang Huang, Suphan Fayong, and Yang Guo. 2012. Structured perceptron with inexact search. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 142–151, Montréal, Canada, June. Association for Comput… find our card
  25. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of ACL-08: HLT, pages 586–594, Columbus, Ohio, June. Association for Computational Linguistics. find
  26. Xiaoqiang Luo, Abe Ittycheriah, Hongyan Jing, Nanda Kambhatla, and Salim 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, pages 135–142, Barcelona, Spain, July. find our card
  27. Xiaoqiang Luo. 2005. On coreference resolution performance metrics. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 25–32, Vancouver, British Columbia, Canada, October. Association for Computational Linguistics. find our card
  28. Vincent Ng and Claire Cardie. 2002. Improving machine learning approaches to coreference resolution. In Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, pages 104– 111, Philadelphia, Pennsylvania, USA, July. Association for Computational Linguistics. find our card
  29. Vincent Ng. 2010. Supervised noun phrase coreference research: The first fifteen years. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1396– 1411, Uppsala, Sweden, July. Association for Computational Linguistics. find our card
  30. Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang. 2012. Conll-2012 shared task: Modeling multilingual unrestricted coreference in ontonotes. In Joint Conference on EMNLP and CoNLL - Shared Task, pages 1–40, Jeju Island, Korea, July. Association for Computational Lin… find our card
  31. Altaf Rahman and Vincent Ng. 2009. Supervised models for coreference resolution. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 968–977, Singapore, August. Association for Computational Linguistics. find our card
  32. Lev Ratinov and Dan Roth. 2009. Design challenges and misconceptions in named entity recognition. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL-2009), pages 147–155, Boulder, Colorado, June. Association for Computational Linguistics. find our card
  33. Stéphane Ross, Geoffrey J. Gordon, and J. Andrew Bagnell. 2011. A reduction of imitation learning and structured prediction to no-regret online learning. In AISTATS, pages 627–635. find
  34. Wee Meng Soon, Hwee Tou Ng, and Daniel Chung Yong Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521–544. find our card
  35. Veselin Stoyanov and Jason Eisner. 2012. Easy-first coreference resolution. In Proceedings of COLING 2012, pages 2519–2534, Mumbai, India, December. find our card
  36. Veselin Stoyanov, Nathan Gilbert, Claire Cardie, and 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 ACL and the 4th International Joint Conference on Natural Language… find our card
  37. Marc Vilain, John Burger, John Aberdeen, Dennis Connolly, and Lynette Hirschman. 1995. A model theoretic coreference scoring scheme. In Proceedings MUC-6, pages 45–52, Columbia, Maryland. find our card
  38. Xiaofeng Yang, Jian Su, Jun Lang, Chew Lim Tan, Ting Liu, and Sheng Li. 2008. An entity-mention model for coreference resolution with inductive logic programming. In Proceedings of ACL-08: HLT, pages 843–851, Columbus, Ohio, June. Association for Computational Linguistics. find our card
  39. Chun-Nam Yu and T. Joachims. 2009. Learning structural svms with latent variables. In International Conference on Machine Learning (ICML). find
  40. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 562– 571, Honolulu, Hawaii, October. Association for Computation… find our card

↑ back to top

This page in Markdown →