Web-Scale Distributional Similarity and Entity Set Expansion

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 938–947, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Web-Scale Distributional Similarity and Entity Set Expansion Patrick Pantel†, Eric Crestan†, Arkady Borkovsky‡, Ana-Maria Popescu†, Vishnu Vyas† †Yahoo! Labs Sunnyvale, CA 94089 {ppantel,ecrestan}@yahoo-inc.com {amp,vishnu}@yahoo-inc.com ‡Yandex Labs Burlingame, CA 94010 arkady@yandex-team.ru Abstract Computing the pairwise semantic similarity between all words on the Web is a compu- tationally challenging task. Parallelization and optimizations are necessary. We pro- pose a highly scalable implementation based on distributional similarity, imple- mented in the MapReduce framework and deployed over a 200 billion word crawl of the Web. The pairwise similarity between 500 million terms is computed in 50 hours using 200 quad-core nodes. We apply the learned similarity matrix to the task of au- tomatic set expansion and present a large empirical study to quantify the effect on expansion performance of corpus size, cor- pus quality, seed composition and seed size. We make public an experimental testbed for set expansion analysis that in- cludes a large collection of diverse entity sets extracted from Wikipedia. 1 Introduction Computing the semantic similarity between terms has many applications in NLP including word clas- sification (Turney and Littman 2003), word sense disambiguation (Yuret and Yatbaz 2009), context- spelling correction (Jones and Martin 1997), fact extraction (Paşca et al. 2006), semantic role labe- ling (Erk 2007), and applications in IR such as query expansion (Cao et al. 2008) and textual ad- vertising (Chang et al. 2009). For commercial engines such as Yahoo! and Google, creating lists of named entities found on the Web is critical for query analysis, document categorization, and ad matching. Computing term similarity is typically done by comparing co- occurrence vectors between all pairs of terms (Sarmento et al. 2007). Scaling this task to the Web requires parallelization and optimizations. In this paper, we propose a large-scale term si- milarity algorithm, based on distributional similari- ty, implemented in the MapReduce framework and deployed over a 200 billion word crawl of the Web. The resulting similarity matrix between 500 million terms is applied to the task of expanding lists of named entities (automatic set expansion). We provide a detailed empirical analysis of the discovered named entities and quantify the effect on expansion accuracy of corpus size, corpus quality, seed composition, and seed set size. 2 Related Work Below we review relevant work in optimizing si- milarity computations and automatic set expansion. 2.1 Computing Term Similarities The distributional hypothesis (Harris 1954), which links the meaning of words to their contexts, has inspired many algorithms for computing term simi- larities (Lund and Burgess 1996; Lin 1998; Lee 1999; Erk and Padó 2008; Agirre et al. 2009). Brute force similarity computation compares all the contexts for each pair of terms, with complexi- ty O(n2m) where n is the number of terms and m is the number of possible contexts. More efficient strategies are of three kinds: 938 Smoothing: Techniques such as Latent Semantic Analysis reduce the context space by applying …

Content truncated to 500 words