Elamur Research
☰
home / papers / 2010 / Top Accuracy and Fast Dependency Parsing is not a Contradiction

Top Accuracy and Fast Dependency Parsing is not a Contradiction

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/C10-1011.pdf

Summary

This paper addresses the slow training and parsing of high-accuracy graph-based dependency parsers, which can take days to train and up to a minute per sentence. Bohnet built a baseline parser from the second-order algorithm of Carreras (2007), the passive-aggressive perceptron, and the non-projective approximation of McDonald and Pereira (2006). He then profiled where the time goes. Building the tree takes little time. The real cost is looking up each feature's weight index in a hash table. To fix this, he implemented the perceptron as a Hash Kernel, which hashes features straight to weight positions. It is faster, and it can also use features from negative examples, which raises accuracy. He also parallelised feature extraction and parsing across CPU cores, and tuned a threshold for the non-projective rearrangement step. On the CoNLL 2009 shared task languages, the parser's average LAS is higher than the best systems from that competition, and it is much faster. This shows that speed and accuracy can be gained together, and the code was released openly as mate-tools.

Key points

  • On English, mapping features to weight indices takes about 93% of feature-extraction time and 91% of total parsing time. Extracting features takes 1223 ms per sentence with the mapping and 88 ms without it, while projective decoding takes only 12.5 ms.
  • On a single core, the Hash Kernel alone makes parsing 3.5× faster than the baseline. Parallel processing adds a further 3.4× speedup on 4 cores, or 4.6× with hyper-threading. Overall, English parsing is about 16× faster, at roughly 77 ms per sentence.
  • Average LAS across the CoNLL 2009 languages is 86.33, compared with 85.77 for the best shared-task systems and 85.10 for the baseline. English reaches 90.33 LAS, but Catalan, Chinese and Japanese stay below the top results.
  • A rearrangement threshold of 0.3 for the non-projective approximation worked best on the Czech, English and German development sets.
  • Parallel training cut training time from 45.8 h on one core to 9.6 h with 8 hyper-threads.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Dependency parsing

Cited by

281 papers of our library cite it (of the 140673 whose bibliographies we read); 12 of them have a page here, 269 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{bohnet2010top,
  title = {{Top Accuracy and Fast Dependency Parsing is not a Contradiction}},
  author = {Bohnet, Bernd},
  booktitle = {Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010)},
  year = {2010},
  url = {https://aclanthology.org/C10-1011/}
}

References

25 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Attardi, G. 2006. Experiments with a Multilanguage Non-Projective Dependency Parser. In Proceedings of CoNLL, pages 166–170. find
  2. Blum., A. 2006. Random Projection, Margins, Kernels, and Feature-Selection. In LNCS, pages 52–68. Springer. find
  3. Bohnet, B. 2009. Efficient Parsing of Syntactic and Semantic Dependency Structures. In Proceedings of the 13th Conference on Computational Natural Language Learning (CoNLL-2009). find
  4. Carreras, X. 2007. Experiments with a Higher-order Projective Dependency Parser. In EMNLP/CoNLL. find
  5. Che, W., Li Z., Li Y., Guo Y., Qin B., and Liu T. 2009. Multilingual Dependency-based Syntactic and Semantic Parsing. In Proceedings of the 13th Conference on Computational Natural Language Learning (CoNLL-2009). find
  6. Collins, M. 2002. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. In EMNLP. find our card
  7. Crammer, K., O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2003. Online Passive-Aggressive Algorithms. In Sixteenth Annual Conference on Neural Information Processing Systems (NIPS). find
  8. Crammer, K., O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2006. Online Passive-Aggressive Algorithms. Journal of Machine Learning Research, 7:551–585. find
  9. Eisner, J. 1996. Three New Probabilistic Models for Dependency Parsing: An Exploration. In Proceedings of the 16th International Conference on Computational Linguistics (COLING-96), pages 340– 345, Copenhaen. find our card
  10. Eisner, J., 2000. Bilexical Grammars and their Cubic-time Parsing Algorithms, pages 29–62. Kluwer Academic Publishers. find
  11. Gesmundo, A., J. Henderson, P. Merlo, and I. Titov. 2009. A Latent Variable Model of Synchronous Syntactic-Semantic Parsing for Multiple Languages. In Proceedings of the 13th Conference on Computational Natural Language Learning (CoNLL-2009), Boulder, Colorado, USA., June 4-5. find
  12. Hajič, J., M. Ciaramita, R. Johansson, D. Kawahara, M. Antònia Martı́, L. Màrquez, A. Meyers, J. Nivre, S. Padó, J. Štěpánek, P. Straňák, M. Surdeanu, N. Xue, and Y. Zhang. 2009. The CoNLL-2009 Shared Task: Syntactic and Semantic Dependencies in Multiple Languages. In Proceedings of the 13t… find our card
  13. Johansson, R. and P. Nugues. 2008. Dependency-based Syntactic–Semantic Analysis with PropBank and NomBank. In Proceedings of the Shared Task Session of CoNLL-2008, Manchester, UK. find
  14. McDonald, R. and F. Pereira. 2006. Online Learning of Approximate Dependency Parsing Algorithms. In In Proc. of EACL, pages 81–88. find our card
  15. McDonald, R., K. Crammer, and F. Pereira. 2005. Online Large-margin Training of Dependency Parsers. In Proc. ACL, pages 91–98. find our card
  16. Nivre, J. and R. McDonald. 2008. Integrating Graph-Based and Transition-Based Dependency Parsers. In ACL-08, pages 950–958, Columbus, Ohio. find
  17. Nivre, J., J. Hall, and J. Nilsson. 2004. Memory-Based Dependency Parsing. In Proceedings of the 8th CoNLL, pages 49–56, Boston, Massachusetts. find
  18. Nivre, J. 2003. An Efficient Algorithm for Projective Dependency Parsing. In 8th International Workshop on Parsing Technologies, pages 149–160, Nancy, France. find our card
  19. Nivre, J. 2009. Non-Projective Dependency Parsing in Expected Linear Time. In Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 351–359, Suntec, Singapore. find our card
  20. Rahimi, A. and B. Recht. 2008. Random Features for Large-Scale Kernel Machines. In Platt, J.C., D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. MIT Press, Cambridge, MA. find
  21. Ren, H., D. Ji Jing Wan, and M. Zhang. 2009. Parsing Syntactic and Semantic Dependencies for Multiple Languages with a Pipeline Approach. In Proceedings of the 13th Conference on Computational Natural Language Learning (CoNLL-2009), Boulder, Colorado, USA., June 4-5. find
  22. Riedel, S. and J. Clarke. 2006. Incremental Integer Linear Programming for Non-projective Dependency Parsing. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 129–137, Sydney, Australia, July. Association for Computational Linguistics. find
  23. Shi, Q., J. Petterson, G. Dror, J. Langford, A. Smola, and S.V.N. Vishwanathan. 2009. Hash Kernels for Structured Data. In Journal of Machine Learning. find
  24. Titov, I. and J. Henderson. 2007. A Latent Variable Model for Generative Dependency Parsing. In Proceedings of IWPT, pages 144–155. find
  25. Yamada, H. and Y. Matsumoto. 2003. Statistical Dependency Analysis with Support Vector Machines. In Proceedings of IWPT, pages 195–206. find our card