Minibatch and Parallelization for Online Large Margin Structured Learning

Proceedings of NAACL-HLT 2013, pages 370–379, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Minibatch and Parallelization for Online Large Margin Structured Learning Kai Zhao1 1Computer Science Program, Graduate Center City University of New York kzhao@gc.cuny.edu Liang Huang2,1 2Computer Science Dept, Queens College City University of New York huang@cs.qc.cuny.edu Abstract Online learning algorithms such as perceptron and MIRA have become popular for many NLP tasks thanks to their simpler architec- ture and faster convergence over batch learn- ing methods. However, while batch learning such as CRF is easily parallelizable, online learning is much harder to parallelize: previ- ous efforts often witness a decrease in the con- verged accuracy, and the speedup is typically very small (∼3) even with many (10+) pro- cessors. We instead present a much simpler architecture based on “mini-batches”, which is trivially parallelizable. We show that, un- like previous methods, minibatch learning (in serial mode) actually improves the converged accuracy for both perceptron and MIRA learn- ing, and when combined with simple paral- lelization, minibatch leads to very significant speedups (up to 9x on 12 processors) on state- of-the-art parsing and tagging systems. 1 Introduction Online structured learning algorithms such as the structured perceptron (Collins, 2002) and k-best MIRA (McDonald et al., 2005) have become more and more popular for many NLP tasks such as de- pendency parsing and part-of-speech tagging. This is because, compared to their batch learning counter- parts, online learning methods offer faster conver- gence rates and better scalability to large datasets, while using much less memory and a much simpler architecture which only needs 1-best or k-best de- coding. However, online learning for NLP typically involves expensive inference on each example for 10 or more passes over millions of examples, which of- ten makes training too slow in practice; for example systems such as the popular (2nd-order) MST parser (McDonald and Pereira, 2006) usually require the order of days to train on the Treebank on a com- modity machine (McDonald et al., 2010). There are mainly two ways to address this scala- bility problem. On one hand, researchers have been developing modified learning algorithms that allow inexact search (Collins and Roark, 2004; Huang et al., 2012). However, the learner still needs to loop over the whole training data (on the order of mil- lions of sentences) many times. For example the best-performing method in Huang et al. (2012) still requires 5-6 hours to train a very fast parser. On the other hand, with the increasing popularity of multicore and cluster computers, there is a grow- ing interest in speeding up training via paralleliza- tion. While batch learning such as CRF (Lafferty et al., 2001) is often trivially parallelizable (Chu et al., 2007) since each update is a batch-aggregate of the update from each (independent) example, online learning is much harder to parallelize due to the de- pendency between examples, i.e., the update on the first example should in principle influence the de- coding of all remaining examples. Thus if we de- …

Content truncated to 500 words