Elamur Research⌕
☰
home / papers / 2012 / A Discriminative Hierarchical Model for Fast Coreference at Large Scale

A Discriminative Hierarchical Model for Fast Coreference at Large Scale

Summary

Most coreference systems decide, for each pair of mentions, whether the two refer to the same entity. This scales quadratically and cannot capture properties of whole entities. Wick, Singh and McCallum replace this design with a discriminative hierarchical factor graph, a conditional random field in which each entity is a tree of latent sub-entities with mentions as leaves. Each internal node summarizes its children, so a few upper-level nodes can stand in for huge groups of near-identical mentions. Trees can grow to any depth and width. Compatibility factors link only child–parent pairs, so attaching or detaching a subtree means evaluating one factor rather than comparing against every mention in the entity. Inference uses Metropolis-Hastings MCMC. The authors test the model on author disambiguation using bibliographic records from DBLP and BibTeX. Against a pairwise CRF baseline, it reaches a given F1 accuracy one to two orders of magnitude faster, and the gap widens as the data grows. It resolves nearly six million author mentions on a single CPU in under four hours. This shows that rich entity-level coreference can run at web scale.

Key points

  • Speed on 145k mentions: the hierarchical model reached 60% F1 accuracy 19× faster than the pairwise CRF and 90% accuracy 31× faster. It needed more samples to converge, but each sample was much cheaper.
  • Speed on 1.3 million mentions: it hit 60% accuracy 72× faster than the pairwise model and reached 90% in 2,350 seconds.
  • DBLP at scale (about 5 million mentions): it reached 80% accuracy in 6,700 s (under two hours) and over 90% in 10,600 s.
  • Combined DBLP + BibTeX (5,803,811 mentions): it reached 90% accuracy in about 13,500 s on one CPU.
  • Comparison with earlier work: unlike the fixed, shallow sub-entity/super-entity hierarchy of Singh et al. (2011), the trees here are learned and arbitrarily deep. Unlike greedy streaming clustering (Rao et al., 2010), the model can revisit earlier errors.

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

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

Cite

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

@inproceedings{wick2012discriminative,
  title = {{A Discriminative Hierarchical Model for Fast Coreference at Large Scale}},
  author = {Wick, Michael and Singh, Sameer and McCallum, Andrew},
  booktitle = {Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2012},
  url = {https://aclanthology.org/P12-1040/}
}

References

31 references, 12 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. 1999. Cross-document event coreference: annotations, experiments, and observations. In Proceedings of the Workshop on Coreference and its Applications, CorefApp ’99, pages 1–8, Stroudsburg, PA, USA. Association for Computational Linguistics. find our card
  2. 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
  3. Indrajit Bhattacharya and Lise Getoor. 2006. A latent Dirichlet model for unsupervised entity resolution. In SDM. find
  4. Mikhail Bilenko, Beena Kamath, and Raymond J. Mooney. 2006. Adaptive blocking: Learning to scale up record linkage. In Proceedings of the Sixth International Conference on Data Mining, ICDM ’06, pages 87–96, Washington, DC, USA. IEEE Computer Society. find
  5. David M. Blei, Andrew Y. Ng, and Michael I. Jordan. 2003. Latent Dirichlet allocation. Journal on Machine Learning Research, 3:993–1022. find our card
  6. Aron Culotta and Andrew McCallum. 2006. Practical Markov logic containing first-order quantifiers with application to identity uncertainty. In Human Language Technology Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing (HLT/NAACL), June. find
  7. 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
  8. 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
  9. 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
  10. Mauricio A. Hernández and Salvatore J. Stolfo. 1995. The merge/purge problem for large databases. In Proceedings of the 1995 ACM SIGMOD international conference on Management of data, SIGMOD ’95, pages 127–138, New York, NY, USA. ACM. find
  11. Jun S. Liu, Faming Liang, and Wing Hung Wong. 2000. The multiple-try method and local optimization in metropolis sampling. Journal of the American Statistical Association, 96(449):121–134. find
  12. Andrew McCallum and Ben Wellner. 2004. Conditional models of identity uncertainty with application to noun coreference. In Neural Information Processing Systems (NIPS). find
  13. Andrew McCallum, Kamal Nigam, and Lyle Ungar. 2000. Efficient clustering of high-dimensional data sets with application to reference matching. In International Conference on Knowledge Discovery and Data Mining (KDD), pages 169–178. find
  14. Andrew McCallum, Karl Schultz, and Sameer Singh. 2009. FACTORIE: Probabilistic programming via imperatively defined factor graphs. In Neural Information Processing Systems (NIPS). find
  15. Brian Milch, Bhaskara Marthi, and Stuart Russell. 2006. BLOG: Relational Modeling with Unknown Objects. Ph.D. thesis, University of California, Berkeley. find
  16. Radford Neal. 2000. Slice sampling. Annals of Statistics, 31:705–767. find
  17. 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
  18. Hoifung Poon and Pedro Domingos. 2007. Joint inference in information extraction. In AAAI Conference on Artificial Intelligence, pages 913–918. find
  19. Altaf Rahman and Vincent Ng. 2009. Supervised models for coreference resolution. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2 - Volume 2, EMNLP ’09, pages 968–977, Stroudsburg, PA, USA. Association for Computational Linguistics. find our card
  20. 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
  21. Coling 2010 Organizing Committee. find
  22. 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
  23. Matthew Richardson and Pedro Domingos. 2006. Markov logic networks. Machine Learning, 62(1-2):107–136. find
  24. Sameer Singh, Michael L. Wick, and Andrew McCallum. 2010. Distantly labeling data for large scale cross-document coreference. Computing Research Repository (CoRR), abs/1005.4298. — [arXiv:1005.4298](https://arxiv.org/abs/1005.4298) find
  25. Sameer Singh, Amarnag Subramanya, Fernando Pereira, and Andrew McCallum. 2011. Large-scale cross-document coreference using distributed inference and hierarchical models. In Association for Computational Linguistics: Human Language Technologies (ACL HLT). find our card
  26. Parag Singla and Pedro Domingos. 2005. Discriminative training of Markov logic networks. In AAAI, Pittsburgh, PA. find
  27. Parag Singla and Pedro Domingos. 2008. Lifted first-order belief propagation. In Proceedings of the 23rd national conference on Artificial intelligence - Volume 2, AAAI’08, pages 1094–1099. AAAI Press. find
  28. Wee Meng Soon, Hwee Tou Ng, and Daniel Chung Yong Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Comput. Linguist., 27(4):521–544. find our card
  29. R.H. Swendsen and J.S. Wang. 1987. Nonuniversal critical dynamics in MC simulations. Phys. Rev. Lett., 58(2):68–88. find
  30. Michael Wick, Aron Culotta, Khashayar Rohanimanesh, and Andrew McCallum. 2009. An entity-based model for coreference resolution. In SIAM International Conference on Data Mining (SDM). find
  31. 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 Association for Computational Linguistics, pages 843–851. find our card

↑ back to top

This page in Markdown →