Elamur Research⌕
☰
home / papers / 2013 / A Constraint-Based Hypergraph Partitioning Approach to Coreference Resolution

A Constraint-Based Hypergraph Partitioning Approach to Coreference Resolution

Summary

The paper addresses coreference resolution, which means grouping the expressions in a text that point to the same real-world entity. The authors argue that common pairwise classifiers have three weaknesses. They judge pairs without context, they lack evidence for ambiguous pairs, and their decisions can contradict each other when chains are built. To address this, they represent a document as a hypergraph whose nodes are mentions. Edges and hyperedges encode weighted constraints over pairs or larger groups of mentions. Resolution then becomes partitioning this hypergraph, solved with relaxation labeling. Because constraints can involve partial entities, the framework supports both mention-pair and entity-mention models, and new knowledge enters as extra constraints. The implementation, RelaxCor, reached state-of-the-art results using only mention-pair information. It placed second in the CoNLL-2011 shared task. The authors also added world knowledge mined from Wikipedia. This gave only small, non-significant gains, mainly because the extracted facts were sparse, redundant or noisy. They conclude that more reliable knowledge extraction is the bottleneck, rather than the model.

Key points

  • Core method: coreference is treated as constrained hypergraph partitioning, solved by relaxation labeling. Mention-pair and entity-mention constraints can be combined in a single model.
  • System and evaluation: the system, RelaxCor, competed in SemEval-2010 and CoNLL-2011 and took second place at CoNLL-2011.
  • Wikipedia knowledge, how it was used: knowledge was added in two ways, as extra features and as extra constraints. The improvements showed up mostly for the mention types the knowledge was aimed at: CN N, CN P and PN N.
  • Wikipedia knowledge, results: overall gains were not statistically significant. Fewer than 1% of test mentions were actually affected by a Wikipedia-derived constraint in the features setup.
  • Side effects: performance dropped for ungendered pronouns (P3U, "it"), which make up 18% of coreferent mentions. Gains came in precision rather than recall, which the authors attribute to tuning on CEAF.

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

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

Cite

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

@article{sapena2013constraint,
  title = {{A Constraint-Based Hypergraph Partitioning Approach to Coreference Resolution}},
  author = {Sapena, Emili and Padró, Lluís and Turmo, Jordi},
  journal = {Computational Linguistics},
  year = {2013},
  doi = {10.1162/coli\_a\_00151},
  url = {https://doi.org/10.1162/coli_a_00151}
}

References

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

  1. Aone, C. and S. W. Bennett. 1995. Evaluating automated and manual acquisition of anaphora resolution strategies. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 1995), pages 122–129. find our card
  2. Atserias, J. 2006. Towards Robustness in Natural Language Understanding. Ph.D. thesis, Departamento de Lenguajes y Sistemas Informáticos, Euskal Herriko Unibertsitatea, Donosti, Spain. find
  3. Azzam, S., K. Humphreys, and R. Gaizauskas. 1999. Using coreference chains for text summarization. In Proceedings of the Workshop on Coreference and its Applications, pages 77–84, Stroudsburg, PA. find our card
  4. Bagga, A. and B. Baldwin. 1998. Algorithms for scoring coreference chains. In Proceedings of the Linguistic Coreference Workshop at LREC, pages 563–566, Granada. find our card
  5. Bean, D., E. Riloff, S. Dumais, D. Marcu, and S. Roukos. 2004. Unsupervised learning of contextual role knowledge for coreference resolution. In Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT 2004), pages 297–304, Boston… find our card
  6. Bengtson, E. and D. Roth. 2008. Understanding the value of features for coreference resolution. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP 2008), pages 294–303, Waikiki, HI. find our card
  7. Cai, J. and M. Strube. 2010. End-to-end coreference resolution via hypergraph partitioning. In Proceedings of the 23rd International Conference on Computational Linguistics, pages 143–151, Beijing. find our card
  8. Cardie, C. and K. Wagstaff. 1999. Noun phrase coreference as clustering. In Proceedings of the 1999 Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora (EMNLP-VLC 1999), pages 82–89, College Park, MD. find our card
  9. Collins, M. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  10. Culotta, A., M. Wick, and A. McCallum. 2007. First-order probabilistic models for coreference resolution. In Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT 2007), pages 81–88, Rochester, NY. find our card
  11. Denis, P. 2007. New Learning Models for Robust Reference Resolution. Ph.D. thesis, University of Texas at Austin. find
  12. Denis, P. and J. Baldridge. 2007. Joint determination of anaphoricity and coreference resolution using integer programming. Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT 2007), pages 236–243, Rochester, NY. find our card
  13. Denis, P. and J. Baldridge. 2008. Specialized models and ranking for coreference resolution. Proceedings of the Conference on Empirical Methods for Natural Language Processing (EMNLP 2008). find our card
  14. Finkel, J. R. and C. D. Manning. 2008. Enforcing transitivity in coreference resolution. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 2008), pages 45–48, Columbus, OH. find our card
  15. Finley, T. and T. Joachims. 2005. Supervised clustering with support vector machines. ACM International Conference Proceedings Series, 119:217–224. find
  16. Haghighi, A. and D. Klein. 2007. Unsupervised coreference resolution in a nonparametric bayesian model. In Proceedings of the Annual Meeting of the Association of Computational Linguistics (ACL 2007), pages 848–855. find our card
  17. Hummel, R. A. and S. W. Zucker. 1983. On the foundations of relaxation labeling processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5(3):267–287. find
  18. Ji, H., D. Westbrook, and R. Grishman. 2005. Using semantic relations to refine coreference decisions. Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing (HLT-EMNLP 2005), pages 17–24, Prague. find our card
  19. Kingsbury, P. and M. Palmer. 2003. Propbank: the next level of treebank. In Proceedings of Treebanks and Lexical Theories, Växjö. find
  20. Klenner, M. 2007. Enforcing consistency on coreference sets. In Proceedings of the Conference on Recent Advances in Natural Language Processing (RANLP 2007), pages 323–328, Borovets. find
  21. Klenner, M. and É. Ailloud. 2008. Enhancing Coreference Clustering. In Proceedings of the Second Workshop on Anaphora Resolution (WAR II, 2008), pages 31–40, Bergen. find
  22. Lee, H., Y. Peirsman, A. Chang, N. Chambers, M. Surdeanu, and D. Jurafsky. 2011. Stanford’s multi-pass sieve coreference resolution system at the CoNLL-2011 shared task. In Proceedings of the Fifteenth Conference on Computational Natural Language Learning: Shared Task, pages 28–34, Portland, OR. find our card
  23. Luo, X. 2005. On coreference resolution performance metrics. Proceedings of the Joint Conference on Human Language Technology and Empirical Methods in Natural Language Processing (HLT-EMNLP 2005), pages 25–32, Vancouver. find our card
  24. Luo, X. 2007. Coreference or not: A twin model for coreference resolution. In Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT 2007), pages 73–80, Rochester, NY. find our card
  25. Luo, X., 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 Annual Meeting of the Association for Computational Linguistics (ACL 2004), pages 135–142, Barcelona. find our card
  26. Màrquez, L., L. Padró, and H. Rodrı́guez. 2000. A machine learning approach for POS tagging. Machine Learning Journal, 39(1):59–91. find
  27. Màrquez, L., M. Recasens, and E. Sapena. 2012. Coreference resolution: An empirical study based on SemEval-2010 shared task 1. Journal on Language Resources and Evaluation, Special Issue on SemEval-2010. doi:10.1007/s510579-012-9194-z. — [doi:10.1007/s510579-012-9194-z](https://doi.org/10.1007/s510579-012-9194-z) find
  28. McCallum, A. and B. Wellner. 2005. Conditional models of identity uncertainty with application to noun coreference. Advances in Neural Information Processing Systems, 17:905–912. find
  29. McCarthy, J. F. and W. G. Lehnert. 1995. Using decision trees for coreference resolution. Proceedings of the Fourteenth International Conference on Artificial Intelligence, pages 1,050–1,055. find
  30. Mitkov, Ruslan. 2002. Anaphora Resolution. Longman. find
  31. Morton, T. S. 2000. Using coreference in question answering. NIST Special Publication SP, pages 685–688. find
  32. Ng, V. 2005. Machine learning for coreference resolution: From local classification to global ranking. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 2005), pages 157–164, Ann Arbor, MI. find our card
  33. Ng, V. 2007. Shallow semantics for coreference resolution. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2007), pages 1,689–1,694, Hyderabad. find
  34. Ng, V. 2008. Unsupervised models for coreference resolution. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP 2008), pages 640–649, Waikiki, HI. find our card
  35. Ng, V. 2009. Graph-cut-based anaphoricity determination for coreference resolution. In Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics (ACL 2009), pages 575–583, Suntec. find our card
  36. Ng, V. 2010. Supervised noun phrase coreference research: The first fifteen years. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 2010), pages 1,396–1,411, Uppsala. find our card
  37. Ng, V. and C. Cardie. 2002. Improving machine learning approaches to coreference resolution. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 2002), pages 104–111, Philadelphia, PA. find our card
  38. Nicolae, C. and G. Nicolae. 2006. Best Cut: A graph algorithm for coreference resolution. Proceedings of the Conference on Empirical Methods for Natural Language Processing (EMNLP 2006), pages 275–283, Sydney. find
  39. NIST, US. 2003. The ACE 2003 Evaluation Plan. US National Institute for Standards and Technology (NIST), pages 1–8. find
  40. Padró, L. 1998. A Hybrid Environment for Syntax–Semantic Tagging. Ph.D. thesis, Departamento de Llenguatges i Sistemes Informàics, Universitat Politécnica de Catalunya. find
  41. Pelillo, M. 1997. The dynamics of nonlinear relaxation labeling processes. Journal of Mathematical Imaging and Vision, 7(4):309–323. find
  42. Peral, J., M. Palomar, and A. Ferrández. 1999. Coreference-oriented interlingual slot structure & machine translation. In Proceedings of the Workshop on Coreference and its Applications, pages 69–76, Stroudsburg, PA. find
  43. Ponzetto, S. P. and M. Strube. 2006. Exploiting semantic role labeling, WordNet and Wikipedia for coreference resolution. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics (NAACL 2006), pages 192–199, New York, NY… find our card
  44. Poon, H. and P. Domingos. 2008. Joint unsupervised coreference resolution with Markov Logic. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP 2008), pages 650–659, Waikiki, HI. find our card
  45. Popescu, A. M. and O. Etzioni. 2005. Extracting product features and opinions from reviews. In Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing (HLT-EMNLP 2005), pages 339–346, Vancouver. find
  46. Pradhan, S., A. Moschitti, N. Xue, O. Uryupina, and Y. Zhang. 2012. CoNLL-2012 shared task: Modeling multilingual unrestricted coreference in OntoNotes. In Proceedings of the Conference on Computational Natural Language Learning (CoNLL 2012), pages 1–40, Jeju Island. find our card
  47. Pradhan, S., L. Ramshaw, M. Marcus, M. Palmer, R. Weischedel, and N. Xue. 2011. CoNLL-2011 shared task: Modeling unrestricted coreference in OntoNotes. In Proceedings of the Conference on Computational Natural Language Learning (CoNLL 2011), pages 1–27, Portland, OR. find our card
  48. Pradhan, S. S., L. Ramshaw, R. Weischedel, J. MacBride, and L. Micciulla. 2007. Unrestricted coreference: Identifying entities and events in OntoNotes. In Proceedings of the International Conference on Semantic Computing (ICSC 2007), pages 446–453. find
  49. Quinlan, J. R. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann. find our card
  50. Rahman, A. and V. Ng. 2011a. Coreference resolution with world knowledge. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 2011), pages 814–824, Portland, OR. find our card
  51. Rahman, A. and V. Ng. 2011b. Narrowing the modeling gap: A cluster-ranking approach to coreference resolution. Journal of Artificial Intelligence Research, 40(1):469–521. find
  52. Recasens, M., L. Màrquez, E. Sapena, M. A. Martı́, M. Taulé, V. Hoste, M. Poesio, and Y. Versley. 2010. SemEval-2010 Task 1: Coreference resolution in multiple languages. In Proceedings of the International Workshop on Semantic Evaluations (SemEval-2010), pages 1–8, Uppsala. find our card
  53. Rosenfeld, R., R. A. Hummel, and S. W. Zucker. 1976. Scene labelling by relaxation operations. IEEE Transactions on Systems, Man and Cybernetics, 6(6):420–433. find
  54. Rounds, E. M. 1980. A combined nonparametric approach to feature selection and binary decision tree design. Pattern Recognition, 12(5):313–317. find
  55. Safavian, S. R. and D. Landgrebe. 1991. A survey of decision tree classifier methodology. IEEE Transactions on Systems, Man and Cybernetics, 21(3):660–674. find
  56. Sapena, E. 2012. A Constraint-Based Hypergraph Partitioning Approach to Coreference Resolution. Ph.D. thesis, Universitat Politecnica de Catalunya. find
  57. Sapena, E., L. Padró, and J. Turmo. 2010a. A global relaxation labeling approach to coreference resolution. In Proceedings of the International Conference on Computational Linguistics (COLING 2010), pages 1,086–1,094, Beijing. find our card
  58. Sapena, E., L. Padró, and J. Turmo. 2010b. RelaxCor: A global relaxation labeling approach to coreference resolution. In Proceedings of the ACL Workshop on Semantic Evaluations (SemEval-2010), pages 88–91, Uppsala. find our card
  59. Sapena, E., L. Padró, and J. Turmo. 2011. RelaxCor participation in CoNLL shared task on coreference resolution. In Proceedings of the Fifteenth Conference on Computational Natural Language Learning: Shared Task, pages 35–39, Portland, OR. find our card
  60. Soon, W. M., H. T. Ng, and D. C. Y. Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521–544. find our card
  61. Stoyanov, V., N. Gilbert, C. Cardie, and E. Riloff. 2009. Conundrums in noun phrase coreference resolution: Making sense of the state-of-the-art. In Proceedings of the Joint Conference of the Annual Meeting of the ACL and the International Joint Conference on Natural Language Processing (ACL-IJCNLP… find our card
  62. Torras, C. 1989. Relaxation and neural learning: Points of convergence and divergence. Journal of Parallel and Distributed Computing, 6:217–244. find
  63. Uryupina, O. 2009. Detecting anaphoricity and antecedenthood for coreference resolution. Procesamiento del Lenguaje Natural, pages 113–120. find
  64. Uryupina, O., M. Poesio, C. Giuliano, and K. Tymoshenko. 2011. Disambiguation and filtering methods in using Web knowledge for coreference resolution. In Proceedings of the International Florida Artificial Intelligence Research Society Conference, pages 317–322, Palm Beach, FL. find
  65. Vilain, M., J. Burger, J. Aberdeen, D. Connolly, and L. Hirschman. 1995. A model-theoretic coreference scoring scheme. In Proceedings of the Message Understanding Conference (MUC-6), pages 45–52, Arlington, VA. find our card
  66. Yang, X., J. Su, J. Lang, C. L. Tan, T. Liu, and S. Li. 2008. An entity-mention model for coreference resolution with inductive logic programming. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 2008), pages 843–851, Columbus, OH. find our card
  67. Yang, X., J. Su, and C. L. Tan. 2006. Kernel-based pronoun resolution with structured syntactic knowledge. Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics (COLING-ACL 2006), pages 41–48, Sydney… find our card
  68. Yang, X., J. Su, G. Zhou, and C. L. Tan. 2004. An NP-cluster based approach to coreference resolution. In Proceedings of the International Conference on Computational Linguistics (COLING 2004), pages 226–232, Geneva. find our card
  69. Yang, X., G. Zhou, J. Su, and C. L. Tan. 2003. Coreference resolution using competition learning approach. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL 2003), pages 176–183, Sapporo. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sapena-2013-constraint-based-hypergraph-partitioning-approach/