Sampling Techniques for Streaming Cross Document Coreference Resolution

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 1391–1396, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics Sampling Techniques for Streaming Cross Document Coreference Resolution Luke Shrimpton∗ Victor Lavrenko† Miles Osborne§ ∗ School of Informatics, University of Edinburgh: luke.shrimpton@ed.ac.uk † School of Informatics, University of Edinburgh: vlavrenk@inf.ed.ac.uk § Bloomberg, London: mosborne29@bloomberg.net Abstract We present the first truly streaming cross doc- ument coreference resolution (CDC) system. Processing infinite streams of mentions forces us to use a constant amount of memory and so we maintain a representative, fixed sized sam- ple at all times. For the sample to be repre- sentative it should represent a large number of entities whilst taking into account both tempo- ral recency and distant references. We intro- duce new sampling techniques that take into account a notion of streaming discourse (cur- rent mentions depend on previous mentions). Using the proposed sampling techniques we are able to get a CEAFe score within 5% of a non-streaming system while using only 30% of the memory. 1 Introduction Cross document coreference resolution (CDC) - identifying mentions that refer to the same entity across documents - is a prerequisite when combin- ing entity specific information from multiple docu- ments. Typically large scale CDC involves apply- ing a scalable clustering algorithm to all the men- tions. We consider streaming CDC, hence our sys- tem must conform to the streaming computational resource model (Muthukrishnan, 2005). Each men- tion is processed in bounded time and only a con- stant amount of memory is used. Honoring these constraints ensures our system can be applied to in- finite streams such as newswire or social media. Storing all the mentions in memory is clearly in- feasible, hence we need to either compress mentions or store a sample. Compression is more computa- tionally expensive as it involves merging/forgetting mention components (for example: components of a vector) whereas sampling decides to store or for- get whole mentions. We investigate sampling tech- niques due to their computational efficiency. We ex- plore which mentions should be stored while per- forming streaming CDC. A sample should repre- sent a diverse set of entities while taking into ac- count both temporal recency and distant mentions. We show that using a notion of streaming discourse, where what is currently being mentioned depends on what was previously mentioned significantly im- proves performance on a new CDC annotated Twit- ter corpus. 2 Related Work There are many existing approaches to CDC (Bagga and Baldwin, 1998; Lee et al., 2012; Andrews et al., 2014). Few of them scale to large datasets. Singh et al. (2011) proposed a distributed hierar- chical factor graph approach. While it can process large datasets, the scalability comes from distribut- ing the problem. Wick et al. (2012) proposed a sim- ilar approach based on compressing mentions, while scalable it does not conform to the streaming re- source model. The only prior work that addressed online/streaming CDC (Rao et al., 2010) …

Content truncated to 500 words