Fast Large-Scale Approximate Graph Construction for NLP

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1069–1080, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Fast Large-Scale Approximate Graph Construction for NLP Amit Goyal and Hal Daum´e III Dept. of Computer Science University of Maryland College Park, MD {amit,hal}@umiacs.umd.edu Raul Guerra Dept. of Computer Science University of Maryland College Park, MD rguerra@cs.umd.edu Abstract Many natural language processing problems involve constructing large nearest-neighbor graphs. We propose a system called FLAG to construct such graphs approximately from large data sets. To handle the large amount of data, our algorithm maintains approximate counts based on sketching algorithms. To find the approximate nearest neighbors, our algorithm pairs a new distributed online-PMI algorithm with novel fast approximate near- est neighbor search algorithms (variants of PLEB). These algorithms return the approxi- mate nearest neighbors quickly. We show our system’s efficiency in both intrinsic and ex- trinsic experiments. We further evaluate our fast search algorithms both quantitatively and qualitatively on two NLP applications. 1 Introduction Many natural language processing (NLP) prob- lems involve graph construction. Examples in- clude constructing polarity lexicons based on lexi- cal graphs from WordNet (Rao and Ravichandran, 2009), constructing polarity lexicons from web data (Velikovich et al., 2010) and unsupervised part-of- speech tagging using label propagation (Das and Petrov, 2011). The later two approaches con- struct nearest-neighbor graphs between word pairs by computing nearest neighbors between word pairs from large corpora. These nearest neighbors form the edges of the graph, with weights given by the distributional similarity (Turney and Pantel, 2010) between terms. Unfortunately, computing the distri- butional similarity between all words in a large vo- cabulary is computationally and memory intensive when working with large amounts of data (Pantel et al., 2009). This bottleneck is typically addressed by means of commodity clusters. For example, Pantel et al. (2009) compute distributional similarity be- tween 500 million terms over a 200 billion words in 50 hours using 100 quad-core nodes, explicitly stor- ing a similarity matrix between 500 million terms. In this work, we propose Fast Large-Scale Ap- proximate Graph (FLAG) construction, a sys- tem that constructs a fast large-scale approximate nearest-neighbor graph from a large text corpus. To build this system, we exploit recent developments in the area of approximation, randomization and streaming for large-scale NLP problems (Ravichan- dran et al., 2005; Goyal et al., 2009; Levenberg et al., 2010). More specifically we exploit work on Lo- cality Sensitive Hashing (LSH) (Charikar, 2002) for computing word-pair similarities from large text col- lections (Ravichandran et al., 2005; Van Durme and Lall, 2010). However, Ravichandran et al. (2005) approach stored an enormous matrix of all unique words and their contexts in main memory, which is infeasible for very large data sets. A more efficient online framework to locality sensitive hashing (Van Durme and Lall, 2010; Van Durme and Lall, 2011) computes distributional similarity in a streaming set- ting. Unfortunately, their approach can handle only additive features like raw-counts, and …

Content truncated to 500 words