Top Accuracy and Fast Dependency Parsing is not a Contradiction

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 89–97, Beijing, August 2010 Very High Accuracy and Fast Dependency Parsing is not a Contradiction Bernd Bohnet University of Stuttgart Institut f¨ur Maschinelle Sprachverarbeitung bernd.bohnet@ims.uni-stuttgart.de Abstract In addition to a high accuracy, short pars- ing and training times are the most impor- tant properties of a parser. However, pars- ing and training times are still relatively long. To determine why, we analyzed the time usage of a dependency parser. We il- lustrate that the mapping of the features onto their weights in the support vector machine is the major factor in time com- plexity. To resolve this problem, we im- plemented the passive-aggressive percep- tron algorithm as a Hash Kernel. The Hash Kernel substantially improves the parsing times and takes into account the features of negative examples built dur- ing the training. This has lead to a higher accuracy. We could further increase the parsing and training speed with a paral- lel feature extraction and a parallel parsing algorithm. We are convinced that the Hash Kernel and the parallelization can be ap- plied successful to other NLP applications as well such as transition based depen- dency parsers, phrase structrue parsers, and machine translation. 1 Introduction Highly accurate dependency parsers have high de- mands on resources and long parsing times. The training of a parser frequently takes several days and the parsing of a sentence can take on average up to a minute. The parsing time usage is impor- tant for many applications. For instance, dialog systems only have a few hundred milliseconds to analyze a sentence and machine translation sys- tems, have to consider in that time some thousand translation alternatives for the translation of a sen- tence. Parsing and training times can be improved by methods that maintain the accuracy level, or methods that trade accuracy against better parsing times. Software developers and researchers are usually unwilling to reduce the quality of their ap- plications. Consequently, we have to consider at first methods to improve a parser, which do not in- volve an accuracy loss, such as faster algorithms, faster implementation of algorithms, parallel al- gorithms that use several CPU cores, and feature selection that eliminates the features that do not improve accuracy. We employ, as a basis for our parser, the second order maximum spanning tree dependency pars- ing algorithm of Carreras (2007). This algorithm frequently reaches very good, or even the best la- beled attachment scores, and was one of the most used parsing algorithms in the shared task 2009 of the Conference on Natural Language Learning (CoNLL) (Hajiˇc et al., 2009). We combined this parsing algorithm with the passive-aggressive per- ceptron algorithm (Crammer et al., 2003; McDon- ald et al., 2005; Crammer et al., 2006). A parser build out of these two algorithms provides a good baseline and starting point to improve upon the parsing and training times. The rest of the paper is structured as follows. In Section 2, we describe related work. …

Content truncated to 500 words