Revisiting Higher-Order Dependency Parsers (2020)

Abstract: Neural encoders have allowed dependency parsers to shift from higher-order structured models to simpler first-order ones, making decoding faster and still achieving better accuracy than non-neural parsers. This has led to a belief that neural encoders can implicitly encode structural constraints, such as siblings and grandparents in a tree. We tested this hypothesis and found that neural parsers may benefit from higher-order features, even when employing a powerful pre-trained encoder, such as BERT. While the gains of higher-order features are small in the presence of a powerful encoder, they are consistent for long-range dependencies and long sentences. In particular, higher-order models are more accurate on full sentence parses and on the exact match of modifier lists, indicating that they deal better with larger, more complex structures.

## introduction before the advent of neural networks in nlp, dependency parsers relied on higher-order features to better model sentence structure @xcite @xcite . common choices for such features were siblings (a head word and two modifiers) and grandparents (a head word, its own head and a modifier). @xcite showed that even without higher order features, a parser with an rnn encoder could achieve state-of-the-art results. this led folk wisdom to suggest that modeling higher-order features in a neural parser would not bring additional advantages, and nearly all recent research on dependency parsing was restricted to first-order models @xcite . @xcite further reinforced this belief comparing transition and graph-based decoders (but none of which higher order); @xcite suggested that higher-order features become redundant because the parsing models encode them implicitly. however, there is some evidence that neural parsers still benefit from structure modeling. @xcite showed that a parser trained with a global structure loss function has higher accuracy than when trained with a local objective (i.e., learning the head of each word independently). @xcite examined the impact of consecutive sibling features in a neural dependency parser. while they found mostly negative results in a transition-based setting, a graph-based parser still showed significant gains on two out of 10 treebanks. in this paper, we test rigorously the hypothesis of the utility of second-order features. in particular, we experiment with consecutive sibling and grandparent features in a non-projective, graphbased dependency parser. we found that without a pretrained encoder, these features are only useful for large treebanks; however, when using bert, they can improve performance on most treebanks we tested on -especially true for longer sentences and long-distance dependencies, and full sentence parses foot_0 . this challenges the hypothesis that encoders can single-handedly improve parsers, or more generally, structured models in general. ## conclusion while their overall performance gain was small, they are distinctively better for longer sentences and long-range dependencies. considering the exact match of complete parse trees or all modifiers of a word, second-order models exhibit an advantage over first-order ones. our results indicate that even a powerful encoder as bert can still benefit from explicit output structure modelling; this would be interesting to explore in other nlp tasks as well. another interesting line of research would be to evaluate the contribution of higher-order features in a cross-lingual setting, leveraging structure learned from larger treebanks to underresourced languages.