Paper: Transition-based Dependency Parsing with Selectional Branching

ACL ID P13-1104
Title Transition-based Dependency Parsing with Selectional Branching
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2013

We present a novel approach, called selec- tional branching, which uses confidence es- timates to decide when to employ a beam, providing the accuracy of beam search at speeds close to a greedy transition-based dependency parsing approach. Selectional branching is guaranteed to perform a fewer number of transitions than beam search yet performs as accurately. We also present a new transition-based dependency parsing algorithm that gives a complexity of O(n) for projective parsing and an expected lin- ear time speed for non-projective parsing. With the standard setup, our parser shows an unlabeled attachment score of 92.96% and a parsing speed of 9 milliseconds per sentence, which is faster and more accurate than the current state-of-the-art transition- based parser that uses beam search.