Elamur Research⌕
☰
home / papers / 2011 / Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models

Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models

Summary

The paper addresses cross-document coreference: deciding which entity mentions across a large document collection refer to the same real-world entity. Because the number of possible mention groupings grows super-exponentially, earlier work mostly used greedy pairwise clustering on datasets of a few thousand mentions. The authors frame coreference as a factor graph whose pairwise affinity and repulsion factors are based on context cosine similarity, and they search for the best configuration with MCMC (Metropolis-Hastings with annealing). They add two scaling ideas. First, inference is distributed: entities are spread across machines, each runs local sampling, and entities are periodically reshuffled. Second, a hierarchical model adds sub-entity and super-entity variables. Sub-entities let groups of mentions move together. Super-entities place similar entities on the same machine. For evaluation, they built a Web corpus labeled through hyperlinks to Wikipedia. The combined approach reaches clearly higher accuracy and converges faster, which suggests that probabilistic coreference can be applied to very large text collections.

Key points

  • The evaluation corpus treats Wikipedia link anchors as mentions, surrounding text as documents and the linked page titles as entity labels. It contains 1.5 million mentions covering 43k entities.
  • The best system reaches a B3 F1 of 73.7%, which is 16 points absolute above the baseline and corresponds to a 38% error reduction.
  • The comparison systems are exact mention-string matching and the distributed Subsquare clustering algorithm (Bshouty and Long, 2010).
  • The hierarchical model converges faster than the flat pairwise model, despite having many more variables.
  • The work concentrates on inference rather than learning. The only hand-set parameter is the bias b, and pairwise features are computed only when a proposal needs them.

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

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

Cite

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

@inproceedings{singh2011large,
  title = {{Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models}},
  author = {Singh, Sameer and Subramanya, Amarnag and Pereira, Fernando and McCallum, Andrew},
  booktitle = {Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies},
  year = {2011},
  url = {https://aclanthology.org/P11-1080/}
}

References

39 references, 10 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. Entity-based cross-document coreferencing using the vector space model. In International Conference on Computational Linguistics, pages 79–85. find
  2. A. Baron and M. Freedman. 2008. Who is who and what is what: experiments in cross-document co-reference. In Empirical Methods in Natural Language Processing (EMNLP), pages 274–283. find our card
  3. Eric Bengston and Dan Roth. 2008. Understanding the value of features for coreference resolution. In Empirical Methods in Natural Language Processing (EMNLP). find our card
  4. Matthias Blume. 2005. Automatic entity disambiguation: Benefits to NER, relation extraction, link analysis, and inference. In International Conference on Intelligence Analysis (ICIA). find
  5. Nader H. Bshouty and Philip M. Long. 2010. Finding planted partitions in nearly linear time using arrested spectral clustering. In Johannes Fürnkranz and Thorsten Joachims, editors, Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 135–142, Haifa, Israel, June. O… find
  6. Yuan Changhe, Lu Tsai-Ching, and Druzdzel Marek. 2004. Annealed MAP. In Uncertainty in Artificial Intelligence (UAI), pages 628–635, Arlington , Virginia. AUAI Press. find
  7. Wen-Yen Chen, Yangqiu Song, Hongjie Bai, Chih-Jen Lin, and Edward Y. Chang. 2010. Parallel spectral clustering in distributed systems. IEEE Transactions on Pattern Analysis and Machine Intelligence. find
  8. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithm. In Annual Meeting of the Association for Computational Linguistics (ACL). find
  9. Aron Culotta, Michael Wick, and Andrew McCallum. 2007. First-order probabilistic models for coreference resolution. In North American Chapter of the Association for Computational Linguistics - Human Language Technologies (NAACL HLT). find our card
  10. S. Datta, C. Giannella, and H. Kargupta. 2006. K-Means Clustering over a Large, Dynamic Network. In SIAM Data Mining Conference (SDM). find
  11. Hal Daumé III and Daniel Marcu. 2005. A Bayesian model for supervised clustering with the Dirichlet process prior. Journal of Machine Learning Research (JMLR), 6:1551–1577. find
  12. Jeffrey Dean and Sanjay Ghemawat. 2004. Mapreduce: Simplified data processing on large clusters. Symposium on Operating Systems Design & Implementation (OSDI). find
  13. Sharon Goldwater and Tom Griffiths. 2007. A fully bayesian approach to unsupervised part-of-speech tagging. In Annual Meeting of the Association for Computational Linguistics (ACL), pages 744–751. find
  14. Chung Heong Gooi and James Allan. 2004. Cross-document coreference on a large scale corpus. In North American Chapter of the Association for Computational Linguistics - Human Language Technologies (NAACL HLT), pages 9–16. find our card
  15. Aria Haghighi and Dan Klein. 2007. Unsupervised coreference resolution in a nonparametric bayesian model. In Annual Meeting of the Association for Computational Linguistics (ACL), pages 848–855. find our card
  16. Aria Haghighi and Dan Klein. 2009. Simple coreference resolution with rich syntactic and semantic features. In Empirical Methods in Natural Language Processing (EMNLP), pages 1152–1161. find our card
  17. Aria Haghighi and Dan Klein. 2010. Coreference resolution in a modular, entity-centered model. In North American Chapter of the Association for Computational Linguistics - Human Language Technologies (NAACL HLT), pages 385–393. find our card
  18. Gideon S. Mann and Andrew McCallum. 2008. Generalized expectation criteria for semi-supervised learning of conditional random fields. In Annual Meeting of the Association for Computational Linguistics (ACL), pages 870–878. find
  19. Gideon S. Mann and David Yarowsky. 2003. Unsupervised personal name disambiguation. In North American Chapter of the Association for Computational Linguistics - Human Language Technologies (NAACL HLT), pages 33–40. find
  20. Andre Martins, Noah Smith, Eric Xing, Pedro Aguiar, and Mario Figueiredo. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Empirical Methods in Natural Language Processing (EMNLP), pages 34–44, Cambridge, MA, October. Association for Computational Linguistics. find our card
  21. J. Mayfield, D. Alexander, B. Dorr, J. Eisner, T. Elsayed, T. Finin, C. Fink, M. Freedman, N. Garera, P. Mc-Namee, et al. 2009. Cross-document coreference resolution: A key technology for learning by reading. In AAAI Spring Symposium on Learning by Reading and Learning to Read. find
  22. Andrew McCallum and Ben Wellner. 2004. Conditional models of identity uncertainty with application to noun coreference. In Neural Information Processing Systems (NIPS). find
  23. Andrew McCallum, Karl Schultz, and Sameer Singh. 2009. FACTORIE: Probabilistic programming via imperatively defined factor graphs. In Neural Information Processing Systems (NIPS). find
  24. Horatiu Mocian. 2009. Survey of Distributed Clustering Techniques. Ph.D. thesis, Imperial College of London. find
  25. Vincent Ng. 2005. Machine learning for coreference resolution: From local classification to global ranking. In Annual Meeting of the Association for Computational Linguistics (ACL). find our card
  26. Cheng Niu, Wei Li, and Rohini K. Srihari. 2004. Weakly supervised learning for cross-document person name disambiguation supported by information extraction. In Annual Meeting of the Association for Computational Linguistics (ACL), page 597. find
  27. Ted Pedersen, Anagha Kulkarni, Roxana Angheluta, Zornitsa Kozareva, and Thamar Solorio. 2006. An unsupervised language independent method of name discrimination using second order co-occurrence features. In International Conference on Intelligent Text Processing and Computational Linguistics (CICLin… find
  28. Hoifung Poon, Pedro Domingos, and Marc Sumner. 2008. A general method for reducing the complexity of relational inference and its application to MCMC. In AAAI Conference on Artificial Intelligence. find
  29. Octavian Popescu, Christian Girardi, Emanuele Pianta, and Bernardo Magnini. 2008. Improving cross-document coreference. Journées Internationales d’Analyse statistique des Données Textuelles, 9:961– 969. find
  30. A. Purandare and T. Pedersen. 2004. Word sense discrimination by clustering contexts in vector and similarity spaces. In Conference on Computational Natural Language Learning (CoNLL), pages 41–48. find
  31. Delip Rao, Paul McNamee, and Mark Dredze. 2010. Streaming cross document entity coreference resolution. In International Conference on Computational Linguistics (COLING), pages 1050–1058, Beijing, China, August. find our card
  32. Coling 2010 Organizing Committee. find
  33. Yael Ravin and Zunaid Kazi. 1999. Is Hillary Rodham Clinton the president? disambiguating names across documents. In Annual Meeting of the Association for Computational Linguistics (ACL), pages 9–16. find
  34. Alexander M Rush, David Sontag, Michael Collins, and Tommi Jaakkola. 2010. On dual decomposition and linear programming relaxations for natural language processing. In Empirical Methods in Natural Language Processing (EMNLP), pages 1–11, Cambridge, MA, October. Association for Computational Linguist… find
  35. Evan Sandhaus. 2008. The New York Times annotated corpus. Linguistic Data Consortium. find
  36. Sameer Singh, Amarnag Subramanya, Fernando Pereira, and Andrew McCallum. 2010. Distributed map inference for undirected graphical models. In Neural Information Processing Systems (NIPS), Workshop on Learning on Cores, Clusters and Clouds. find
  37. Ben Wellner, Andrew McCallum, Fuchun Peng, and Michael Hay. 2004. An integrated, conditional model of information extraction and coreference with application to citation matching. In Uncertainty in Artificial Intelligence (UAI), pages 593–601. find
  38. Michael Wick, Aron Culotta, Khashayar Rohanimanesh, and Andrew McCallum. 2009a. An entity-based model for coreference resolution. In SIAM International Conference on Data Mining (SDM). find
  39. Michael Wick, Khashayar Rohanimanesh, Aron Culotta, and Andrew McCallum. 2009b. Samplerank: Learning preferences from atomic gradients. In Neural Information Processing Systems (NIPS), Workshop on Advances in Ranking. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/singh-2011-large-scale-cross-document-coreference/