Minibatch and Parallelization for Online Large Margin Structured Learning

Kai Zhao, Liang HuangNAACL 2013

TL;DR

This paper introduces a "minibatch" approach to online large-margin structured learning, making it significantly more efficient and parallelizable. By processing data in small batches rather than one example at a time, they achieve faster convergence, improved accuracy, and dramatic speedups (up to 9x) when combined with parallel processing, outperforming existing methods.

What Problem Does This Paper Address?

Online learning algorithms like the structured perceptron and MIRA are popular in NLP for tasks like dependency parsing and part-of-speech tagging due to their faster convergence and lower memory requirements compared to batch methods. However, a major bottleneck is their poor scalability: while batch learning is easily parallelized, online learning's sequential nature makes parallelization difficult. Previous attempts at parallelizing online learning have resulted in only marginal speedups and even decreased accuracy. This paper tackles the challenge of making these powerful online learning methods practical for large datasets by addressing their inherent sequentiality and lack of parallelizability.

Methods

The core innovation is the introduction of a "minibatch" strategy for online large-margin learning. Instead of processing one example at a time, the algorithm processes a small group of examples (a minibatch).

  • Serial Minibatch: In a serial setting, examples within a minibatch are decoded independently, but their updates are aggregated. This is argued to provide a "mixing effect" similar to averaging parameters, which can improve converged accuracy. For MIRA, this approach allows for optimizing against a larger set of aggregated constraints, leading to a better approximation of SVM.
  • Parallelized Minibatch: The minibatch approach is "trivially parallelizable" because the decoding of each example within a minibatch is independent. The proposed method splits each minibatch across multiple processors for decoding. After all processors finish, the constraints are collected, and a single batch update is performed. To mitigate performance issues caused by varying sentence lengths (and thus decoding times), they introduce a "per-minibatch load-balancing" technique that shuffles sentences within a minibatch to distribute the workload more evenly.

The paper also provides theoretical convergence proofs for both serial minibatch perceptron and MIRA.

Datasets

The experiments were conducted on the standard Penn Treebank (PTB) dataset for both dependency parsing and part-of-speech tagging.

  • Dependency Parsing: Sections 02-21 were used for training, and Section 22 for evaluation.
  • Part-of-Speech Tagging: Sections 00-18 were used for training, and Sections 19-21 for evaluation.

Key Insights and Ideas

  • Minibatch is not just for speed, but also for accuracy: Counterintuitively, using minibatches in a serial setting actually improved the converged accuracy for both perceptron and MIRA, likely due to a better approximation of the underlying optimization problem.
  • Parallelization unlocks dramatic speedups: While serial minibatch offers some speedup by converging faster, the real game-changer is combining it with parallel processing. This approach yields significantly higher speedups than previous methods like Iterative Parameter Mixing (IPM).
  • Load balancing is crucial for parallel efficiency: Simply distributing minibatches across processors isn't enough. Varying sentence lengths lead to unbalanced workloads, causing processors to wait. The proposed "per-minibatch load-balancing" technique effectively addresses this, leading to more efficient parallelization.
  • Trade-off between minibatch size and convergence speed: Larger minibatch sizes can slow down the convergence rate, suggesting a "sweet spot" for minibatch size that balances speed and accuracy.

Key Results

  • Accuracy Improvement: Minibatch learning (serial) improved accuracy by up to 0.27% for dependency parsing (MIRA) and 0.06% for part-of-speech tagging (Perceptron) compared to pure online methods.
  • Faster Convergence: Minibatch learning significantly reduced training time. For example, a minibatch size of 4 reached a target accuracy in 3.5 hours, while the pure online baseline took 6.9 hours.
  • Impressive Parallel Speedups: When combined with parallelization, the minibatch approach achieved substantial speedups. For dependency parsing, 12 processors achieved a speedup of up to 10.5x, reaching an accuracy in 0.66 hours that took the pure online MIRA 6.9 hours. For part-of-speech tagging, 12 processors achieved a speedup of 12x, converging in 0.10 hours compared to the baseline's 0.45 hours.
  • Outperforming IPM: The proposed minibatch parallelization consistently outperformed Iterative Parameter Mixing (IPM) in both speed and accuracy, offering superlinear speedups with increasing processors, whereas IPM showed only a constant speedup of around 3x.

Limitations and Future Work

  • Quadratic Optimization Bottleneck: For MIRA, the quadratic optimization step (Hildreth algorithm) scales super-linearly with the number of constraints. This limits the practical size of minibatches that can be used.
  • Future Work: The authors suggest exploring parallelized quadratic optimization techniques to enable the use of even larger minibatches. They also aim to apply their methods to machine translation and investigate more complex parallelization strategies.

Summary updated

BibTeX
@inproceedings{zhao2013minibatch,
  author = {Kai Zhao and Liang Huang},
  title = {{Minibatch and Parallelization for Online Large Margin Structured Learning}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2013},
}
Figure