Elamur Research⌕
☰
home / papers / 2010 / Streaming Cross Document Entity Coreference Resolution

Streaming Cross Document Entity Coreference Resolution

Summary

Most earlier work on cross document coreference resolution (CDCR) assumes the whole collection is available up front. It clusters documents with greedy agglomerative methods whose pairwise comparisons cost quadratic time and memory, which is impractical for news feeds, blogs or tweets. Rao, McNamee and Dredze propose a streaming alternative. Each document is read once, and its within-document coreference chains, produced by BBN's SERIF, are either attached to an existing entity cluster or start a new one.

The clustering follows the update stage of Charikar et al.'s Doubling Algorithm. To keep cost manageable, the method:

  • stores clusters in a disk-backed LRU cache, motivated by the Zipfian frequency of names;
  • hashes clusters by mention strings so that only a few candidates are scored.

Candidates are ranked by orthographic similarity (a dice score over n-grams), bag-of-words context or topic features, and the method handles persons, organizations and locations. On the John Smith, NYT and ACE 2008 data, its accuracy is roughly on par with offline systems. It also scales to about ten times more data than previously reported CDCR evaluations.

Key points

  • The approach uses a single-pass streaming setup with roughly linear dependence on the number of documents. A new-cluster threshold of 0.5 was used, and the merge step was skipped so the number of entities can keep growing.
  • Several similarity variants were compared: Ortho, BoW, Topic, Ortho+BoW and Ortho+Topic. Orthographic similarity was hard to beat. Topic features beat BoW alone, but the two were equivalent when combined with Ortho.
  • On ace08, which has over 10,000 documents, the best B³ F-score was 0.819 (Ortho+Topic with exact-mention hashing). This is comparable to the offline results Baron and Freedman (2008) reported, which reached 83.2 on person entities and 67.8 on organization entities.
  • Three candidate-hashing strategies were tested: exact mention, words and character skip bigrams. Stricter matching was both more accurate and faster.
  • On kbp09, doubling the number of entities processed raised runtime about fivefold. This is because the set of candidate clusters keeps growing; limiting it, for example by ignoring older entities, is left for future work.

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

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

Cite

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

@inproceedings{rao2010streaming,
  title = {{Streaming Cross Document Entity Coreference Resolution}},
  author = {Rao, Delip and McNamee, Paul and Dredze, Mark},
  booktitle = {Coling 2010: Posters},
  year = {2010},
  url = {https://aclanthology.org/C10-2121/}
}

References

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

  1. Artiles, Javier, Satoshi Sekine, and Julio Gonzalo. 2008. Web people search: results of the first evaluation and the plan for the second. In World Wide Web (WWW). find
  2. Bagga, Amit and Breck Baldwin. 1998. Entity-based cross-document coreferencing using the vector space model. In Conference on Computational Linguistics (COLING). find
  3. Baron, Alex and Marjorie Freedman. 2008. Who nytac words 0.695 0.339 0.620 0.691 0.477 ace08 words 0.797 0.700 0.685 0.783 0.776 bigrams 0.120 0.344 0.071 0.340 0.120 mention 0.687 0.349 0.363 0.686 0.680 bigrams 0.540 0.551 0.544 0.519 0.520 mention 0.811 0.738 0.750 0.809 0.819 find
  4. Time (secs) 100K 200K 400K 600K 900K 1.1M 1K \# of coref chains processed Figure 5: The number of coreference chains processed over time in the kbp09 corpus. The processing of over 1 million coreference chains is at least an order of magnitude larger than previous systems reported. is Who and What is… find
  5. Blei, D.M., A.Y. Ng, and M.I. Jordan. 2003. Latent dirichlet allocation. Journal of Machine Learning Research (JMLR), 3:993–1022. find our card
  6. Can, F. and E. Ozkarahan. 1987. A dynamic cluster maintenance system for information retrieval. In Conference on Research and Development in Information Retrieval (SIGIR). find
  7. Charikar, Moses, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. 1997. Incremental clustering and dynamic information retrieval. In ACM Symposium on Theory of Computing (STOC). find
  8. Chen, Ying and James Martin. 2007. Towards robust unsupervised personal name disambiguation. In Empirical Methods in Natural Language Processing (EMNLP). find
  9. Choi, Y. and C. Cardie. 2007. Structured local training and biased potential functions for conditional random fields with application to coreference resolution. In North American Chapter of the Association for Computational Linguistics (NAACL), pages 65– 72. find
  10. Cucerzan, Silviu. 2007. Large-scale named entity disambiguation based on wikipedia data. In Empirical Methods in Natural Language Processing (EMNLP), pages 708–716. find
  11. Firth, J.R. 1957. A synopsis of linguistic theory 1930-1955. In Studies in Linguistic Analysis, pages 1–32. Oxford: Philological Society. find
  12. Gooi, Chung Heong and James Allan. 2004. Cross-document coreference on a large scale corpus. In North American Chapter of the Association for Computational Linguistics (NAACL). find our card
  13. Luo, X., A. Ittycheriah, H. Jing, N. Kambhatla, and S. Roukos. 2004. A mention-synchronous coreference resolution algorithm based on the bell tree. In Association for Computational Linguistics (ACL). find our card
  14. Mann, Gideon S. and David Yarowsky. 2003. Unsupervised personal name disambiguation. In Conference on Natural Language Learning (CONLL). find
  15. McNamee, Paul and Hoa Dang. 2009. Overview of the TAC 2009 knowledge base population track. In Text Analysis Conference (TAC). find
  16. Ng, V. and C. Cardie. 2002. Improving machine learning approaches to coreference resolution. In Association for Computational Linguistics (ACL), pages 104–111. find our card
  17. Nicolae, C. and G. Nicolae. 2006. Bestcut: A graph algorithm for coreference resolution. In Empirical Methods in Natural Language Processing (EMNLP), pages 275–283. Association for Computational Linguistics. find our card
  18. Omiecinski, Edward and Peter Scheuermann. 1984. A global approach to record clustering and file reorganization. In Conference on Research and Development in Information Retrieval (SIGIR). find
  19. Pradhan, S.S., L. Ramshaw, R. Weischedel, J. MacBride, and L. Micciulla. 2007. Unrestricted coreference: Identifying entities and events in ontonotes. In International Conference on Semantic Computing (ICSC). find
  20. Ramshaw, L. and R. Weischedel. 2005. Information extraction. In IEEE ICASSP. find
  21. Sanderson, Mark. 2000. Retrieving with good sense. Information Retrieval, 2(1):45–65. find
  22. Sandhaus, Evan. 2008. The new york times annotated corpus. Linguistic Data Consortium, Philadelphia. find
  23. Soon, Wee Meng, Hwee Tou Ng, and Daniel Chung Yong Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics. find our card
  24. Yao, L., D. Mimno, and A. McCallum. 2009. Efficient methods for topic model inference on streaming document collections. In Knowledge discovery and data mining (KDD). find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/rao-2010-streaming-cross-document-entity-coreference/