Distributed Training Strategies for the Structured Perceptron
Published 2 June 2010
Ryan McDonald, Keith Hall, Gideon Mann
Citations265
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper investigates distributed training strategies for the structured perceptron as a means to reduce training times when computing clusters are available and looks at two strategies and provides convergence bounds for a particular mode of distributed structured perceptrons training based on iterative parameter mixing (or averaging).
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 inference, which is frequently non-linear in example sequence length. In this paper we investigate distributed training strategies for the structured perceptron as a means to reduce training times when computing clusters are available. We look at two strategies and provide convergence bounds for a particular mode of distributed structured perceptron training based on iterative parameter mixing (or averaging). We present experiments on two structured prediction problems – namedentity recognition and dependency parsing – to highlight the efficiency of this method. 1
Keywords
Computer Science
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
12,978 Citations2001John Lafferty, Andrew McCallum +1 more
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
Psychological ReviewThe perceptron: A probabilistic model for information storage and organization in the brain.
11,746 Citations1958Frank F. Rosenblatt
This article will be concerned primarily with the second and third questions, which are still subject to a vast amount of speculation, and where the few relevant facts currently supplied by neurophysiology have not yet been integrated into an acceptable theory.
IEEE Transactions on Automatic ControlDistributed asynchronous deterministic and stochastic gradient optimization algorithms
2,021 Citations1986John N. Tsitsiklis, Dimitri P. Bertsekas +1 more
Discriminative training methods for hidden Markov models
1,889 Citations2002Michael Collins
Experimental results on part-of-speech tagging and base noun phrase chunking are given, in both cases showing improvements over results for a maximum-entropy tagger.
Online Passive-Aggressive Algorithms
1,449 Citations2006Koby Crammer, Ofer Dekel +3 more
Support vector machine learning for interdependent and structured output spaces
1,260 Citations2004Ioannis Tsochantaridis, Thomas Hofmann +2 more
This paper proposes to generalize multiclass Support Vector Machine learning in a formulation that involves features extracted jointly from inputs and outputs, and demonstrates the versatility and effectiveness of the method on problems ranging from supervised grammar learning and named-entity recognition, to taxonomic text classification and sequence alignment.
The MIT Press eBooksMap-Reduce for Machine Learning on Multicore
1,253 Citations2007Cheng-Tao Chu, Sang Kyun Kim +5 more
This work shows that algorithms that fit the Statistical Query model can be written in a certain "summation form," which allows them to be easily parallelized on multicore computers and shows basically linear speedup with an increasing number of processors.
Max-Margin Markov Networks
1,251 Citations2003Ben Taskar, Carlos Guestrin +1 more
Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data, and a new theoretical bound for generalization in structured domains is provided.
Solving large scale linear prediction problems using stochastic gradient descent algorithms
1,150 Citations2004Tong Zhang
Stochastic gradient descent algorithms on regularized forms of linear prediction methods, related to online algorithms such as perceptron, are studied, and numerical rate of convergence for such algorithms is obtained.
Large margin classification using the perceptron algorithm
1,099 Citations1998Yoav Freund, Robert E. Schapire
CoNLL-X shared task on multilingual dependency parsing
976 Citations2006Sabine Buchholz, Erwin Marsi
How treebanks for 13 languages were converted into the same dependency format and how parsing performance was measured is described and general conclusions about multi-lingual parsing are drawn.
Online large-margin training of dependency parsers
816 Citations2005Ryan McDonald, Koby Crammer +1 more
An effective training algorithm for linearly-scored dependency parsers that implements online large-margin multi-class training on top of efficient parsing techniques for dependency trees is presented.
Online Learning of Approximate Dependency Parsing Algorithms.
479 Citations2006Ryan McDonald, Fernando C. N. Pereira
This paper extends the maximum spanning tree dependency parsing framework to incorporate higher-order feature representations and allow dependency structures with multiple parents per word, and shows that those extensions can make the MST framework computationally intractable, but that the intractability can be circumvented with new approximate parsing algorithms.
Incremental parsing with the perceptron algorithm
384 Citations2004Michael Collins, Brian Roark
It is demonstrated that training a perceptron model to combine with the generative model during search provides a 2.1 percent F-measure improvement over the Generative model alone, to 88.8 percent.
Confidence-weighted linear classification
374 Citations2008Mark Dredze, Koby Crammer +1 more
Empirical evaluation on a range of NLP tasks show that the confidence-weighted linear classifiers introduced here improves over other state of the art online and batch methods, learns faster in the online setting, and lends itself to better classifier combination after parallel training.
An end-to-end discriminative approach to machine translation
265 Citations2006Percy Liang, Alexandre Bouchard‐Côté +2 more
A perceptron-style discriminative approach to machine translation in which large feature sets can be exploited and a novel way to introduce learning into the initial phrase extraction process, which has previously been entirely heuristic.
Neural Information Processing SystemsEfficient Large-Scale Distributed Training of Conditional Maximum Entropy Models
242 Citations2009Ryan McDonald, Mehryar Mohri +3 more
This work examines three common distributed training methods for conditional maxent models, including a study of the convergence of the mixture weight method, the most resource-efficient technique, and presents a theoretical analysis of conditional maximum entropy models.
arXiv (Cornell University)Slow Learners are Fast
202 Citations2009John Langford, Alexander J. Smola +1 more
This paper proves that online learning with delayed updates converges well, thereby facilitating parallel online learning.
Efficient, Feature-based, Conditional Random Field Parsing
180 Citations2008Jenny Rose Finkel, Alex Kleeman +1 more
This work presents the first general, featurerich discriminative parser, based on a conditional random field model, which has been successfully scaled to the full WSJ parsing data, and achieves state-of-the-art results.
A tale of two parsers
177 Citations2008Yue Zhang, Stephen Clark
A beam-search-based parser that combines both graph-based and transition-based parsing into a single system for training and decoding is proposed, showing that it outperforms both the pure graph- based and the pure transition- based parsers.
Neural Information Processing SystemsSlow Learners are Fast
156 Citations2009Martin Zinkevich, John Langford +1 more
Neural Information Processing SystemsEfficient Learning using Forward-Backward Splitting
89 Citations2009Yoram Singer, John C. Duchi
A new framework for empirical loss minimization with regularization that alternates between two phases yields a simple yet effective algorithm for both batch penalized risk minimization and online learning.
Web-scale named entity recognition
80 Citations2008Casey Whitelaw, Alex Kehlenbeck +2 more
The resulting system gives precision and recall performance comparable to that obtained for more limited entity types in much more structured domains such as company recognition in newswire, even though web documents often lack consistent capitalization and grammatical sentence construction.
Lecture notes in computer scienceOn-line Learning with Delayed Label Feedback
32 Citations2005Chris Mesterharm
On-line learning is generalized to handle delays in receiving labels for instances to effect the original on-line mistake bounds by giving upper-bounds and restricted lower-bounded on the number of mistakes.