Lock-Free Parallel Perceptron for Graph-based Dependency Parsing
This work addresses training efficiency for NLP researchers and practitioners, but it is incremental as it builds on existing structured perceptron methods.
The paper tackles the slow training problem in graph-based dependency parsing by proposing a parallel perceptron algorithm, achieving an 8-fold faster training speed with 10 threads and no accuracy loss compared to traditional structured perceptron methods.
Dependency parsing is an important NLP task. A popular approach for dependency parsing is structured perceptron. Still, graph-based dependency parsing has the time complexity of $O(n^3)$, and it suffers from slow training. To deal with this problem, we propose a parallel algorithm called parallel perceptron. The parallel algorithm can make full use of a multi-core computer which saves a lot of training time. Based on experiments we observe that dependency parsing with parallel perceptron can achieve 8-fold faster training speed than traditional structured perceptron methods when using 10 threads, and with no loss at all in accuracy.