  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.
