Distributed Training Strategies for the Structured Perceptron

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 456–464, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Distributed Training Strategies for the Structured Perceptron Ryan McDonald Keith Hall Gideon Mann Google, Inc., New York / Zurich {ryanmcd|kbhall|gmann}@google.com Abstract Perceptron training is widely applied in the natural language processing community for learning complex structured models. Like all structured prediction learning frameworks, the structured perceptron can be costly to train as training complexity is proportional to in- ference, which is frequently non-linear in ex- ample sequence length. In this paper we investigate distributed training strategies for the structured perceptron as a means to re- duce training times when computing clusters are available. We look at two strategies and provide convergence bounds for a particu- lar mode of distributed structured perceptron training based on iterative parameter mixing (or averaging). We present experiments on two structured prediction problems – named- entity recognition and dependency parsing – to highlight the efficiency of this method. 1 Introduction One of the most popular training algorithms for structured prediction problems in natural language processing is the perceptron (Rosenblatt, 1958; Collins, 2002). The structured perceptron has many desirable properties, most notably that there is no need to calculate a partition function, which is necessary for other structured prediction paradigms such as CRFs (Lafferty et al., 2001). Furthermore, it is robust to approximate inference, which is of- ten required for problems where the search space is too large and where strong structural indepen- dence assumptions are insufficient, such as parsing (Collins and Roark, 2004; McDonald and Pereira, 2006; Zhang and Clark, 2008) and machine trans- lation (Liang et al., 2006). However, like all struc- tured prediction learning frameworks, the structure perceptron can still be cumbersome to train. This is both due to the increasing size of available train- ing sets as well as the fact that training complexity is proportional to inference, which is frequently non- linear in sequence length, even with strong structural independence assumptions. In this paper we investigate distributed training strategies for the structured perceptron as a means of reducing training times when large computing clusters are available. Traditional machine learning algorithms are typically designed for a single ma- chine, and designing an efficient training mechanism for analogous algorithms on a computing cluster – often via a map-reduce framework (Dean and Ghe- mawat, 2004) – is an active area of research (Chu et al., 2007). However, unlike many batch learning algorithms that can easily be distributed through the gradient calculation, a distributed training analog for the perceptron is less clear cut. It employs online up- dates and its loss function is technically non-convex. A recent study by Mann et al. (2009) has shown that distributed training through parameter mixing (or averaging) for maximum entropy models can be empirically powerful and has strong theoretical guarantees. A parameter mixing strategy, which can be applied to any parameterized learning algorithm, trains separate models in parallel, each on a disjoint subset …

Content truncated to 500 words