Lock-Free Parallel Perceptron for Graph-based Dependency Parsing

2017/03/02 by Xu Sun, Shuming Ma, Sun, Xu +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning in Bioinformatics #Natural Language Processing Techniques #Topic Modeling

paper · pdf · doi:10.48550/arxiv.1703.00782

openalex publication_date 2017/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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³), 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.

Related

• Embarrassingly Parallel Independent Training of Multi-Layer Perceptrons with Heterogeneous Architectures
• Horn: A System for Parallel Training and Regularizing of Large-Scale Neural Networks
• Parallel Algorithms Align with Neural Execution
• Effective Parallelisation for Machine Learning
• Exploring Parallelism in Learning Belief Networks