Distributed Asynchronous Online Learning for Natural Language Processing

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 213–222, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Distributed Asynchronous Online Learning for Natural Language Processing Kevin Gimpel Dipanjan Das Noah A. Smith Language Technologies Institute Carnegie Mellon Univeristy Pittsburgh, PA 15213, USA {kgimpel,dipanjan,nasmith}@cs.cmu.edu Abstract Recent speed-ups for training large-scale models like those found in statistical NLP exploit distributed computing (either on multicore or “cloud” architectures) and rapidly converging online learning algo- rithms. Here we aim to combine the two. We focus on distributed, “mini-batch” learners that make frequent updates asyn- chronously (Nedic et al., 2001; Langford et al., 2009). We generalize existing asyn- chronous algorithms and experiment ex- tensively with structured prediction prob- lems from NLP, including discriminative, unsupervised, and non-convex learning scenarios. Our results show asynchronous learning can provide substantial speed- ups compared to distributed and single- processor mini-batch algorithms with no signs of error arising from the approximate nature of the technique. 1 Introduction Modern statistical NLP models are notoriously expensive to train, requiring the use of general- purpose or specialized numerical optimization al- gorithms (e.g., gradient and coordinate ascent al- gorithms and variations on them like L-BFGS and EM) that iterate over training data many times. Two developments have led to major improve- ments in training time for NLP models: • online learning algorithms (LeCun et al., 1998; Crammer and Singer, 2003; Liang and Klein, 2009), which update the parameters of a model more frequently, processing only one or a small number of training examples, called a “mini- batch,” between updates; and • distributed computing, which divides training data among multiple CPUs for faster processing between updates (e.g., Clark and Curran, 2004). Online algorithms offer fast convergence rates and scalability to large datasets, but distributed computing is a more natural fit for algorithms that require a lot of computation—e.g., processing a large batch of training examples—to be done be- tween updates. Typically, distributed online learn- ing has been done in a synchronous setting, mean- ing that a mini-batch of data is divided among multiple CPUs, and the model is updated when they have all completed processing (Finkel et al., 2008). Each mini-batch is processed only after the previous one has completed. Synchronous frameworks are appealing in that they simulate the same algorithms that work on a single processor, but they have the drawback that the benefits of parallelism are only obtainable within one mini-batch iteration. Moreover, empir- ical evaluations suggest that online methods only converge faster than batch algorithms when using very small mini-batches (Liang and Klein, 2009). In this case, synchronous parallelization will not offer much benefit. In this paper, we focus our attention on asyn- chronous algorithms that generalize those pre- sented by Nedic et al. (2001) and Langford et al. (2009). In these algorithms, multiple mini-batches are processed simultaneously, each using poten- tially different and typically stale parameters. The key advantage of an asynchronous framework is that it allows processors to remain in near-constant use, preventing them from wasting …

Content truncated to 500 words