Scalable Language Processing Algorithms for the Masses: A Case Study in Computing Word Co-occurrence Matrices with MapReduce

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 419–428, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Scalable Language Processing Algorithms for the Masses: A Case Study in Computing Word Co-occurrence Matrices with MapReduce Jimmy Lin The iSchool, University of Maryland National Center for Biotechnology Information, National Library of Medicine jimmylin@umd.edu Abstract This paper explores the challenge of scaling up language processing algorithms to increas- ingly large datasets. While cluster comput- ing has been available in commercial environ- ments for several years, academic researchers have fallen behind in their ability to work on large datasets. I discuss two barriers contribut- ing to this problem: lack of a suitable pro- gramming model for managing concurrency and difficulty in obtaining access to hardware. Hadoop, an open-source implementation of Google’s MapReduce framework, provides a compelling solution to both issues. Its simple programming model hides system-level de- tails from the developer, and its ability to run on commodity hardware puts cluster comput- ing within the reach of many academic re- search groups. This paper illustrates these points with a case study in building word co- occurrence matrices from large corpora. I con- clude with an analysis of an alternative com- puting model based on renting instead of buy- ing computer clusters. 1 Introduction Over the past couple of decades, the field of compu- tational linguistics (and more broadly, human lan- guage technologies) has seen the emergence and later dominance of empirical techniques and data- driven research. Concomitant with this trend is a coherent research thread that focuses on exploiting increasingly-large datasets. Banko and Brill (2001) were among the first to demonstrate the importance of dataset size as a significant factor governing pre- diction accuracy in a supervised machine learning task. In fact, they argued that size of training set was perhaps more important than the choice of ma- chine learning algorithm itself. Similarly, exper- iments in question answering have shown the ef- fectiveness of simple pattern-matching techniques when applied to large quantities of data (Brill et al., 2001; Dumais et al., 2002). More recently, this line of argumentation has been echoed in experi- ments with Web-scale language models. Brants et al. (2007) showed that for statistical machine trans- lation, a simple smoothing technique (dubbed Stupid Backoff) approaches the quality of the Kneser-Ney algorithm as the amount of training data increases, and with the simple method one can process signifi- cantly more data. Challenges in scaling algorithms to increasingly- large datasets have become a serious issue for re- searchers. It is clear that datasets readily available today and the types of analyses that researchers wish to conduct have outgrown the capabilities of individ- ual computers. The only practical recourse is to dis- tribute the computation across multiple cores, pro- cessors, or machines. The consequences of failing to scale include misleading generalizations on arti- ficially small datasets and limited practical applica- bility in real-world contexts, both undesirable. This paper focuses on two barriers to develop- ing scalable language processing algorithms: chal- …

Content truncated to 500 words