Very High Accuracy and Fast Dependency Parsing is not a Contradiction

Bernd Bohnet

Research output: Chapter in Book/Report/Conference proceedingConference contribution

272 Citations (Scopus)


In addition to a high accuracy, short parsing and training times are the most important properties of a parser. However, parsing and training times are still relatively long. To determine why, we analyzed the time usage of a dependency parser. We illustrate that the mapping of the features onto their weights in the support vector machine is the major factor in time complexity. To resolve this problem, we implemented the passive-aggressive perceptron algorithm as a Hash Kernel. The Hash Kernel substantially improves the parsing times and takes into account the features of negative examples built during the training. This has lead to a higher accuracy. We could further increase the parsing and training speed with a parallel feature extraction and a parallel parsing algorithm. We are convinced that the Hash Kernel and the parallelization can be applied successful to other NLP applications as well such as transition based dependency parsers, phrase structrue parsers, and machine translation.
Original languageEnglish
Title of host publicationInternational Conference on Computational Linguistics
PublisherTsinghua University Press
Number of pages9
Publication statusPublished - 23 Aug 2010


Dive into the research topics of 'Very High Accuracy and Fast Dependency Parsing is not a Contradiction'. Together they form a unique fingerprint.

Cite this